Thread-safe LRU cache

Question

Please review my code. I am trying to implement a thread-safe LRU cache using std::list and std::unordered_map. This is a header-only template class which you can use to keep an object cache.

The constructor takes a size as an input parameter and creates a cache of a specified size. Items will be removed based on the least recently used from the cache if the cache goes above the size.

#ifndef LRUCache_h__
#define LRUCache_h__

#pragma once
#include <vector>
#include <list>
#include <unordered_map>
#include <shared_mutex>
#include <iostream>

namespace objcache {

template <class T>
class LRUCache
{    
    struct _node {
        int _key;
        T    _value;
    };

    // use map of key to iterator of LRU list
    using ListIterator = typename std::list<_node>::const_iterator;
    using CacheMap = std::unordered_map<int, ListIterator>;

    size_t                m_cacheSize;
    std::list<_node>    m_lruList;
    CacheMap            m_lruMap;
    std::mutex            m_lock;            // reader writer lock, multiple getters are allowed

public:

    /***
     * Method:        objcache::LRUCache::LRUCache
     * Access:        public 
     * Description: This creates a cache of given size. 
     */
    LRUCache(size_t size) :
        m_cacheSize{ size },
        m_lruList{},
        m_lruMap{},
        m_lock{}
    {
        //m_lruList.resize(m_cacheSize, 0);
        m_lruMap.reserve(m_cacheSize);
    }

    /***
     * Method:    objcache::LRUCache::set
     * Access:    public      
     * Description : This API updates or sets the value val to key. 
     */
    void Set(int key, const T &val) noexcept
    {
        std::lock_guard<std::mutex> guard(m_lock);

        if (auto mapIter = m_lruMap.find(key); mapIter != m_lruMap.end()) {
            //key already exists, just update the queue
            m_lruList.splice(m_lruList.begin(), m_lruList, mapIter->second);
        }
        else {
            // new item in the cache.
            m_lruList.push_front({ key, val });
            m_lruMap.insert(std::make_pair(key, m_lruList.begin()));
        }

        //remove least recently used element if cache is full. 
        if (m_lruList.size() > m_cacheSize) {
            m_lruMap.erase(m_lruList.back()._key);
            m_lruList.pop_back();
        }
    }

    /***
     * Method:        objcache::LRUCache::get
     * Access:        public 
     * Description: This API gets the value of key if it exists in cache,
     *                otherwise, just returns 0
     */
    T Get(int key) noexcept
    {
        std::lock_guard<std::mutex> gaurd(m_lock);
        T val = 0;
        if (auto key_iter = m_lruMap.find(key); key_iter != m_lruMap.end()) {
            m_lruList.splice(m_lruList.begin(), m_lruList, key_iter->second);
            val = (key_iter->second)->_value;
        }
        return val;
    }

    /***
     * Method:    objcache::LRUCache::printCache
     * Access:    public 
     * Description : Prints the keys of the cache one-by-one
     */
    void PrintCache() noexcept
    {
        std::lock_guard<std::mutex> guard(m_lock);
        for (const auto &node : m_lruList)
            std::cout << node._key << std::endl;
    }

};

} // namespace objcache

#endif // LRUCache_h__

Answer 1

Not repeating what 1201ProgramAlarm reported.

---

std::mutex    m_lock;   // reader writer lock, multiple getters are allowed

I see a regular exclusive lock, not a reader/writer lock.

std::lock_guard<std::mutex> gaurd(m_lock);

Not taking advantage of class template argument deduction? This is a case where I really want it. (If not, use an alias for the lock type so it can be easily changed.)

std::lock_guard guard(m_lock);

---

    m_lruList{},
    m_lruMap{},
    m_lock{}

Just adds noise — is that a thing someone actually recommends? I would say don’t list all the things that are taken care of on their own.

   for (const auto &node : m_lruList)
        std::cout << node._key << std::endl;

The style in C++ is to put the * or & with the type, not the identifier. This is called out specifically near the beginning of Stroustrup’s first book, and is an intentional difference from C style.

Some people criticize the leading underscore of identifiers as a style. I point out that it is easy to clash with compiler-supplied identifiers and you must remember to never use a capital letter after the score, so it is a hazard.

---

Update

#ifndef LRUCache_h__

Any name containing a double underscore is reserved for use by the implementation.

---

/***
 * Method:        objcache::LRUCache::LRUCache
 * Access:        public 
 * Description: This creates a cache of given size. 
 */

Banner comments like this just get in the way of reading the code. Repeating the function name in a comment just before its definition does what exactly? (Oh, and a point of nomenclature: C++ does not have “methods”.) Nobody comments each function as being public or private. For the description, don’t prefix it with “Description:”; just describe it.

Since I can see name of the argument is size and see how it’s used on the on the following line

LRUCache(size_t size) :
    m_cacheSize{ size },

a comment saying

// This creates a cache of given size

is useless. It only repeats what is in the signature: A constructor creates an instance of this class, and this one takes a size.

See (⧺P.1). You might also find this useful (Comments starts on page 17; material originally published in 1992).

Answer 2

The LRUCache constructor should be explicit, to avoid declarations like LRUCache c = 7;. The copy constructor and copy assignment operator should be deleted (declared with = delete) since the compiler generated ones will not work properly because the iterator stored in m_lruMap will refer to the original object and not the new one.

In your Get function, you assume that an object of type T can be constructed from the integer 0. This limits the sorts of objects you can track in your cache. Returning a default constructed object would be better since it will still return 0 for built in numeric types while supporting a wider variety of objects. You can get rid of val and just either return the located value, or the default object (return T();). And you misspell guard in this function.

In Set, the check for removing an element in a full cache needs to only be made if a new element was added. This check could be done before adding the new element, which would better restrain the total size used, and allow possibly reusing the removed _node object rather than allocating a new one.

Answer 3

This code is much too complex and it results in a major unfixable bug.

The code is too complex because of class _node and using ListIterator = typename std::list<_node>::const_iterator;. This is all unnecessary. I believe you went that route so you could use list.splice() which takes a const_iterator as one of its arguments.

The bug arises in Set(): if you reset the value for a key which is already in the cache, it does not update the value at all and just keeps the original value. And you can't just fix it by adding one line of code, because the variable you are working with at this point is mapIter->second which is a std::list<_node>::const_iterator, which cannot have its value modified.

You don't need class _node at all. The m_lruList should store only the keys and not the values; its role is just to keep the order in which the keys were accessed. The m_lruMap should be a simple map from key to value. So:

std::list<int> m_lruList;
std::unordered_map<int, T> m_lruMap;

Rewriting your code starting from that should make it much simpler.

Another point is that Get() should not return 0, but maybe instead null. The line T val = 0; unfortunately does not trigger a compiler error, but it will trigger a runtime error if for example you use strings for T. If you do choose to return null when Get() does not find the key, you should modify Set() so that it does not accept null as a value.

Another minor point is that in both Get() and Set() you have to reset the accessed key at the head of the queue, if it is already in the cache. I would write a method resetHeadKey(int key) which would be called in both Get() and Set() if needed.

The multithreading part seems all right to me.