Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

LRU implementation in production code

Tags:

c++

algorithm

lru

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?

like image 335
sud03r Avatar asked Jan 13 '10 14:01

sud03r


People also ask

How can LRU be implemented?

To implement an LRU cache we use two data structures: a hashmap and a doubly linked list. A doubly linked list helps in maintaining the eviction order and a hashmap helps with O(1) lookup of cached keys.

What does LRU mean in coding?

A Least Recently Used (LRU) Cache organizes items in order of use, allowing you to quickly identify which item hasn't been used for the longest amount of time.

What is LRU in data structure?

The Least Recently Used (LRU) cache is a cache eviction algorithm that organizes elements in order of use. In LRU, as the name suggests, the element that hasn't been used for the longest time will be evicted from the cache.


1 Answers

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--; } 
like image 146
Kornel Kisielewicz Avatar answered Sep 22 '22 01:09

Kornel Kisielewicz