LRU implementation in production code

Question

I have some C++ code where I need to implement cache replacement using LRU technique.
So far I know two methods to implement LRU cache replacement:

1. Using timeStamp for each time the cached data is accessed and finally comparing the timeStamps at time of replacement.
2. Using a stack of cached items and moving them to the top if they are accessed recently, so finally the bottom will contain the LRU Candidate.

So, which of these is better to be used in production code?
Are their any other better methods?

Suite

What do you mean by "better" - you have to specify what your criteria are. Also, take a look at this question #1936277 – Skinflint

Instead of timestamp, you can use integer to keep track. When an element is accessed, make it 0 and increment others tracks – Farm

@Farm that would be a poor design because it would make the access cost O(n) – Farland

Answer 1

Recently I implemented a LRU cache using a linked list spread over a hash map.

    /// Typedef for URL/Entry pair
    typedef std::pair< std::string, Entry > EntryPair;

    /// Typedef for Cache list
    typedef std::list< EntryPair > CacheList;

    /// Typedef for URL-indexed map into the CacheList
    typedef boost::unordered_map< std::string, CacheList::iterator > CacheMap;

    /// Cache LRU list
    CacheList mCacheList;

    /// Cache map into the list
    CacheMap mCacheMap;

It has the advantage of being O(1) for all important operations.

The insertion algorithm:

// create new entry
Entry iEntry( ... );

// push it to the front;
mCacheList.push_front( std::make_pair( aURL, iEntry ) );

// add it to the cache map
mCacheMap[ aURL ] = mCacheList.begin();

// increase count of entries
mEntries++;

// check if it's time to remove the last element
if ( mEntries > mMaxEntries )
{
    // erease from the map the last cache list element
    mCacheMap.erase( mCacheList.back().first );

    // erase it from the list
    mCacheList.pop_back();

    // decrease count
    mEntries--;
}

Assurbanipal

I have implemented LRU caching too and use a similar technique. A lookup is no longer const, of course as it changes the state and so in a multi-threaded environment you need exclusive locks for every access even multiple readers. – Whitman

why is this a valid answer? consider, you the size of the cache is 5 elements. And the stream of inputs are 1,2,3,4,5. at this point the linked-list would have this order 5->4->3->2->1. Now when a new element that is already existing is inserted, say '1', then the list becomes 1 -> 5-> 4-> 3-> 2-> 1. And the Hash(key=1) is overwritten and points to the beginning of the list. Since the cache is over-limit, you'd delete the element Hash(key=1) and pop from the list. Therefore, list will be 1 -> 5 -> 4-> 3-> 2 but the Hash will contain only 4 elements – Frication

what this code is missing is, when inserting, if an existing element is inserted then the previous occurrence of that should be removed from the list and the Hash before inserting – Frication

Answer 2

Here is a very simple implementation of LRU cache

https://github.com/lamerman/cpp-lru-cache .

It's easy to use and understand how it works. The total size of code is about 50 lines.

Adis

Answer 3

For simplicity, maybe you should consider using Boost's MultiIndex map. If we separate the key from the data, we support multiple sets of keys on the same data.

From [ http://old.nabble.com/realization-of-Last-Recently-Used-cache-with-boost%3A%3Amulti_index-td22326432.html ]:

"...use two indexes: 1) hashed for searching value by key 2) sequential for tracking last recently used items (get function put item as last item in sequesnce. If we need to remove some items from cache, we may delete they from begin of sequence)."

Note that the "project" operator "allows the programmer to move between different indices of the same multi_index_container" efficiently.

Autonomic

See also an example in boost::multi_index documentation: boost.org/doc/libs/1_45_0/libs/multi_index/doc/… – Asperse

Answer 4

This article describes implementation using a pair of STL containers (a key-value map plus a list for the key access history), or a single boost::bimap.

Avelar

link is since dead? – Bruin

@Gregory: bitbucket seem to have changed something about static hosting from a repo. You can find the doc at bitbucket.org/timday/timday.bitbucket.org/src but you'd have to download it (and accompanying css) or the pdf. Will see if something can be done... – Avelar

OK link fixed; it was due to bitbucket's static hosting moving to bitbucket.io domain confluence.atlassian.com/bitbucket/… – Avelar

Answer 5

In our production environment we use a C++ double linked list which is similar to the Linux kernel linked list. The beauty of it is that you can add an object to as many linked lists as you want and list operation is fast and simple.

Shrievalty

Answer 6

This can be done with boost/compute/detail/lru_cache.hpp. Here is a basic example using it.

#include <boost/compute/detail/lru_cache.hpp>
...

// create an instance that maps from a double to a string and has a max size of 1000
auto my_lru_cache = boost::compute::detail::lru_cache<double, std::string>(1000);

my_lru_cache.insert(3.14, "pi");

if (my_lru_cache.contains(3.14))
{
  // the first get returns a boost::optional
  auto value = my_lru_cache.get(3.14).get();
  std::cout << value << "\n"; 
}

Doubs