LRU cache design
C++AlgorithmData StructuresLruC++ Problem Overview
Least Recently Used (LRU) Cache is to discard the least recently used items first How do you design and implement such a cache class? The design requirements are as follows:
-
find the item as fast as we can
-
Once a cache misses and a cache is full, we need to replace the least recently used item as fast as possible.
How to analyze and implement this question in terms of design pattern and algorithm design?
C++ Solutions
Solution 1 - C++
A linked list + hashtable of pointers to the linked list nodes is the usual way to implement LRU caches. This gives O(1) operations (assuming a decent hash). Advantage of this (being O(1)): you can do a multithreaded version by just locking the whole structure. You don't have to worry about granular locking etc.
Briefly, the way it works:
On an access of a value, you move the corresponding node in the linked list to the head.
When you need to remove a value from the cache, you remove from the tail end.
When you add a value to cache, you just place it at the head of the linked list.
Thanks to doublep, here is site with a C++ implementation: Miscellaneous Container Templates.
Solution 2 - C++
This is my simple sample c++ implementation for LRU cache, with the combination of hash(unordered_map), and list. Items on list have key to access map, and items on map have iterator of list to access list.
#include <list>
#include <unordered_map>
#include <assert.h>
using namespace std;
template <class KEY_T, class VAL_T> class LRUCache{
private:
list< pair<KEY_T,VAL_T> > item_list;
unordered_map<KEY_T, decltype(item_list.begin()) > item_map;
size_t cache_size;
private:
void clean(void){
while(item_map.size()>cache_size){
auto last_it = item_list.end(); last_it --;
item_map.erase(last_it->first);
item_list.pop_back();
}
};
public:
LRUCache(int cache_size_):cache_size(cache_size_){
;
};
void put(const KEY_T &key, const VAL_T &val){
auto it = item_map.find(key);
if(it != item_map.end()){
item_list.erase(it->second);
item_map.erase(it);
}
item_list.push_front(make_pair(key,val));
item_map.insert(make_pair(key, item_list.begin()));
clean();
};
bool exist(const KEY_T &key){
return (item_map.count(key)>0);
};
VAL_T get(const KEY_T &key){
assert(exist(key));
auto it = item_map.find(key);
item_list.splice(item_list.begin(), item_list, it->second);
return it->second->second;
};
};
Solution 3 - C++
I see here several unnecessary complicated implementations, so I decided to provide my implementation as well. The cache has only two methods, get and set. Hopefully it is better readable and understandable:
#include<unordered_map>
#include<list>
using namespace std;
template<typename K, typename V = K>
class LRUCache
{
private:
list<K>items;
unordered_map <K, pair<V, typename list<K>::iterator>> keyValuesMap;
int csize;
public:
LRUCache(int s) :csize(s) {
if (csize < 1)
csize = 10;
}
void set(const K key, const V value) {
auto pos = keyValuesMap.find(key);
if (pos == keyValuesMap.end()) {
items.push_front(key);
keyValuesMap[key] = { value, items.begin() };
if (keyValuesMap.size() > csize) {
keyValuesMap.erase(items.back());
items.pop_back();
}
}
else {
items.erase(pos->second.second);
items.push_front(key);
keyValuesMap[key] = { value, items.begin() };
}
}
bool get(const K key, V &value) {
auto pos = keyValuesMap.find(key);
if (pos == keyValuesMap.end())
return false;
items.erase(pos->second.second);
items.push_front(key);
keyValuesMap[key] = { pos->second.first, items.begin() };
value = pos->second.first;
return true;
}
};
Solution 4 - C++
Here is my implementation for a basic, simple LRU cache.
//LRU Cache
#include <cassert>
#include <list>
template <typename K,
typename V
>
class LRUCache
{
// Key access history, most recent at back
typedef std::list<K> List;
// Key to value and key history iterator
typedef unordered_map< K,
std::pair<
V,
typename std::list<K>::iterator
>
> Cache;
typedef V (*Fn)(const K&);
public:
LRUCache( size_t aCapacity, Fn aFn )
: mFn( aFn )
, mCapacity( aCapacity )
{}
//get value for key aKey
V operator()( const K& aKey )
{
typename Cache::iterator it = mCache.find( aKey );
if( it == mCache.end() ) //cache-miss: did not find the key
{
V v = mFn( aKey );
insert( aKey, v );
return v;
}
// cache-hit
// Update access record by moving accessed key to back of the list
mList.splice( mList.end(), mList, (it)->second.second );
// return the retrieved value
return (it)->second.first;
}
private:
// insert a new key-value pair in the cache
void insert( const K& aKey, V aValue )
{
//method should be called only when cache-miss happens
assert( mCache.find( aKey ) == mCache.end() );
// make space if necessary
if( mList.size() == mCapacity )
{
evict();
}
// record k as most-recently-used key
typename std::list<K>::iterator it = mList.insert( mList.end(), aKey );
// create key-value entry, linked to the usage record
mCache.insert( std::make_pair( aKey, std::make_pair( aValue, it ) ) );
}
//Purge the least-recently used element in the cache
void evict()
{
assert( !mList.empty() );
// identify least-recently-used key
const typename Cache::iterator it = mCache.find( mList.front() );
//erase both elements to completely purge record
mCache.erase( it );
mList.pop_front();
}
private:
List mList;
Cache mCache;
Fn mFn;
size_t mCapacity;
};
Solution 5 - C++
I implemented a thread-safe LRU cache two years back.
LRU is typically implemented with a HashMap and LinkedList. You can google the implementation detail. There are a lot of resources about it(Wikipedia have a good explanation too).
In order to be thread-safe, you need put lock whenever you modify the state of the LRU.
I will paste my C++ code here for your reference.
Here is the implementation.
/***
A template thread-safe LRU container.
Typically LRU cache is implemented using a doubly linked list and a hash map.
Doubly Linked List is used to store list of pages with most recently used page
at the start of the list. So, as more pages are added to the list,
least recently used pages are moved to the end of the list with page
at tail being the least recently used page in the list.
Additionally, this LRU provides time-to-live feature. Each entry has an expiration
datetime.
***/
#ifndef LRU_CACHE_H
#define LRU_CACHE_H
#include <iostream>
#include <list>
#include <boost/unordered_map.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/make_shared.hpp>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/thread/mutex.hpp>
template <typename KeyType, typename ValueType>
class LRUCache {
private:
typedef boost::posix_time::ptime DateTime;
// Cache-entry
struct ListItem {
ListItem(const KeyType &key,
const ValueType &value,
const DateTime &expiration_datetime)
: m_key(key), m_value(value), m_expiration_datetime(expiration_datetime){}
KeyType m_key;
ValueType m_value;
DateTime m_expiration_datetime;
};
typedef boost::shared_ptr<ListItem> ListItemPtr;
typedef std::list<ListItemPtr> LruList;
typedef typename std::list<ListItemPtr>::iterator LruListPos;
typedef boost::unordered_map<KeyType, LruListPos> LruMapper;
// A mutext to ensuare thread-safety.
boost::mutex m_cache_mutex;
// Maximum number of entries.
std::size_t m_capacity;
// Stores cache-entries from latest to oldest.
LruList m_list;
// Mapper for key to list-position.
LruMapper m_mapper;
// Default time-to-live being add to entry every time we touch it.
unsigned long m_ttl_in_seconds;
/***
Note : This is a helper function whose function call need to be wrapped
within a lock. It returns true/false whether key exists and
not expires. Delete the expired entry if necessary.
***/
bool containsKeyHelper(const KeyType &key) {
bool has_key(m_mapper.count(key) != 0);
if (has_key) {
LruListPos pos = m_mapper[key];
ListItemPtr & cur_item_ptr = *pos;
// Remove the entry if key expires
if (isDateTimeExpired(cur_item_ptr->m_expiration_datetime)) {
has_key = false;
m_list.erase(pos);
m_mapper.erase(key);
}
}
return has_key;
}
/***
Locate an item in list by key, and move it at the front of the list,
which means make it the latest item.
Note : This is a helper function whose function call need to be wrapped
within a lock.
***/
void makeEntryTheLatest(const KeyType &key) {
if (m_mapper.count(key)) {
// Add original item at the front of the list,
// and update <Key, ListPosition> mapper.
LruListPos original_list_position = m_mapper[key];
const ListItemPtr & cur_item_ptr = *original_list_position;
m_list.push_front(cur_item_ptr);
m_mapper[key] = m_list.begin();
// Don't forget to update its expiration datetime.
m_list.front()->m_expiration_datetime = getExpirationDatetime(m_list.front()->m_expiration_datetime);
// Erase the item at original position.
m_list.erase(original_list_position);
}
}
public:
/***
Cache should have capacity to limit its memory usage.
We also add time-to-live for each cache entry to expire
the stale information. By default, ttl is one hour.
***/
LRUCache(std::size_t capacity, unsigned long ttl_in_seconds = 3600)
: m_capacity(capacity), m_ttl_in_seconds(ttl_in_seconds) {}
/***
Return now + time-to-live
***/
DateTime getExpirationDatetime(const DateTime &now) {
static const boost::posix_time::seconds ttl(m_ttl_in_seconds);
return now + ttl;
}
/***
If input datetime is older than current datetime,
then it is expired.
***/
bool isDateTimeExpired(const DateTime &date_time) {
return date_time < boost::posix_time::second_clock::local_time();
}
/***
Return the number of entries in this cache.
***/
std::size_t size() {
boost::mutex::scoped_lock lock(m_cache_mutex);
return m_mapper.size();
}
/***
Get value by key.
Return true/false whether key exists.
If key exists, input paramter value will get updated.
***/
bool get(const KeyType &key, ValueType &value) {
boost::mutex::scoped_lock lock(m_cache_mutex);
if (!containsKeyHelper(key)) {
return false;
} else {
// Make the entry the latest and update its TTL.
makeEntryTheLatest(key);
// Then get its value.
value = m_list.front()->m_value;
return true;
}
}
/***
Add <key, value> pair if no such key exists.
Otherwise, just update the value of old key.
***/
void put(const KeyType &key, const ValueType &value) {
boost::mutex::scoped_lock lock(m_cache_mutex);
if (containsKeyHelper(key)) {
// Make the entry the latest and update its TTL.
makeEntryTheLatest(key);
// Now we only need to update its value.
m_list.front()->m_value = value;
} else { // Key exists and is not expired.
if (m_list.size() == m_capacity) {
KeyType delete_key = m_list.back()->m_key;
m_list.pop_back();
m_mapper.erase(delete_key);
}
DateTime now = boost::posix_time::second_clock::local_time();
m_list.push_front(boost::make_shared<ListItem>(key, value,
getExpirationDatetime(now)));
m_mapper[key] = m_list.begin();
}
}
};
#endif
Here is the unit tests.
#include "cxx_unit.h"
#include "lru_cache.h"
struct LruCacheTest
: public FDS::CxxUnit::TestFixture<LruCacheTest>{
CXXUNIT_TEST_SUITE();
CXXUNIT_TEST(LruCacheTest, testContainsKey);
CXXUNIT_TEST(LruCacheTest, testGet);
CXXUNIT_TEST(LruCacheTest, testPut);
CXXUNIT_TEST_SUITE_END();
void testContainsKey();
void testGet();
void testPut();
};
void LruCacheTest::testContainsKey() {
LRUCache<int,std::string> cache(3);
cache.put(1,"1"); // 1
cache.put(2,"2"); // 2,1
cache.put(3,"3"); // 3,2,1
cache.put(4,"4"); // 4,3,2
std::string value_holder("");
CXXUNIT_ASSERT(cache.get(1, value_holder) == false); // 4,3,2
CXXUNIT_ASSERT(value_holder == "");
CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // 2,4,3
CXXUNIT_ASSERT(value_holder == "2");
cache.put(5,"5"); // 5, 2, 4
CXXUNIT_ASSERT(cache.get(3, value_holder) == false); // 5, 2, 4
CXXUNIT_ASSERT(value_holder == "2"); // value_holder is still "2"
CXXUNIT_ASSERT(cache.get(4, value_holder) == true); // 4, 5, 2
CXXUNIT_ASSERT(value_holder == "4");
cache.put(2,"II"); // {2, "II"}, 4, 5
CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // 2, 4, 5
CXXUNIT_ASSERT(value_holder == "II");
// Cache-entries : {2, "II"}, {4, "4"}, {5, "5"}
CXXUNIT_ASSERT(cache.size() == 3);
CXXUNIT_ASSERT(cache.get(2, value_holder) == true);
CXXUNIT_ASSERT(cache.get(4, value_holder) == true);
CXXUNIT_ASSERT(cache.get(5, value_holder) == true);
}
void LruCacheTest::testGet() {
LRUCache<int,std::string> cache(3);
cache.put(1,"1"); // 1
cache.put(2,"2"); // 2,1
cache.put(3,"3"); // 3,2,1
cache.put(4,"4"); // 4,3,2
std::string value_holder("");
CXXUNIT_ASSERT(cache.get(1, value_holder) == false); // 4,3,2
CXXUNIT_ASSERT(value_holder == "");
CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // 2,4,3
CXXUNIT_ASSERT(value_holder == "2");
cache.put(5,"5"); // 5,2,4
CXXUNIT_ASSERT(cache.get(5, value_holder) == true); // 5,2,4
CXXUNIT_ASSERT(value_holder == "5");
CXXUNIT_ASSERT(cache.get(4, value_holder) == true); // 4, 5, 2
CXXUNIT_ASSERT(value_holder == "4");
cache.put(2,"II");
CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // {2 : "II"}, 4, 5
CXXUNIT_ASSERT(value_holder == "II");
// Cache-entries : {2, "II"}, {4, "4"}, {5, "5"}
CXXUNIT_ASSERT(cache.size() == 3);
CXXUNIT_ASSERT(cache.get(2, value_holder) == true);
CXXUNIT_ASSERT(cache.get(4, value_holder) == true);
CXXUNIT_ASSERT(cache.get(5, value_holder) == true);
}
void LruCacheTest::testPut() {
LRUCache<int,std::string> cache(3);
cache.put(1,"1"); // 1
cache.put(2,"2"); // 2,1
cache.put(3,"3"); // 3,2,1
cache.put(4,"4"); // 4,3,2
cache.put(5,"5"); // 5,4,3
std::string value_holder("");
CXXUNIT_ASSERT(cache.get(2, value_holder) == false); // 5,4,3
CXXUNIT_ASSERT(value_holder == "");
CXXUNIT_ASSERT(cache.get(4, value_holder) == true); // 4,5,3
CXXUNIT_ASSERT(value_holder == "4");
cache.put(2,"II");
CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // II,4,5
CXXUNIT_ASSERT(value_holder == "II");
// Cache-entries : {2, "II"}, {4, "4"}, {5, "5"}
CXXUNIT_ASSERT(cache.size() == 3);
CXXUNIT_ASSERT(cache.get(2, value_holder) == true);
CXXUNIT_ASSERT(cache.get(4, value_holder) == true);
CXXUNIT_ASSERT(cache.get(5, value_holder) == true);
}
CXXUNIT_REGISTER_TEST(LruCacheTest);
Solution 6 - C++
I have a LRU implementation here. The interface follows std::map so it should not be that hard to use. Additionally you can provide a custom backup handler, that is used if data is invalidated in the cache.
sweet::Cache<std::string,std::vector<int>, 48> c1;
c1.insert("key1", std::vector<int>());
c1.insert("key2", std::vector<int>());
assert(c1.contains("key1"));
Solution 7 - C++
Is cache a data structure that supports retrieval value by key like hash table? LRU means the cache has certain size limitation that we need drop least used entries periodically.
If you implement with linked-list + hashtable of pointers how can you do O(1) retrieval of value by key?
I would implement LRU cache with a hash table that the value of each entry is value + pointers to prev/next entry.
Regarding the multi-threading access, I would prefer reader-writer lock (ideally implemented by spin lock since contention is usually fast) to monitor.
Solution 8 - C++
LRU Page Replacement Technique:
When a page is referenced, the required page may be in the cache.
If in the cache: we need to bring it to the front of the cache queue.
If NOT in the cache: we bring that in cache. In simple words, we add a new page to the front of the cache queue. If the cache is full, i.e. all the frames are full, we remove a page from the rear of cache queue, and add the new page to the front of cache queue.
# Cache Size
csize = int(input())
# Sequence of pages
pages = list(map(int,input().split()))
# Take a cache list
cache=[]
# Keep track of number of elements in cache
n=0
# Count Page Fault
fault=0
for page in pages:
# If page exists in cache
if page in cache:
# Move the page to front as it is most recent page
# First remove from cache and then append at front
cache.remove(page)
cache.append(page)
else:
# Cache is full
if(n==csize):
# Remove the least recent page
cache.pop(0)
else:
# Increment element count in cache
n=n+1
# Page not exist in cache => Page Fault
fault += 1
cache.append(page)
print("Page Fault:",fault)
Input/Output
Input:
3
1 2 3 4 1 2 5 1 2 3 4 5
Output:
Page Fault: 10
Solution 9 - C++
This is my simple Java programmer with complexity O(1).
//
package com.chase.digital.mystack;
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
private int size;
private Map<String, Map<String, Integer>> cache = new HashMap<>();
public LRUCache(int size) {
this.size = size;
}
public void addToCache(String key, String value) {
if (cache.size() < size) {
Map<String, Integer> valueMap = new HashMap<>();
valueMap.put(value, 0);
cache.put(key, valueMap);
} else {
findLRUAndAdd(key, value);
}
}
public String getFromCache(String key) {
String returnValue = null;
if (cache.get(key) == null) {
return null;
} else {
Map<String, Integer> value = cache.get(key);
for (String s : value.keySet()) {
value.put(s, value.get(s) + 1);
returnValue = s;
}
}
return returnValue;
}
private void findLRUAndAdd(String key, String value) {
String leastRecentUsedKey = null;
int lastUsedValue = 500000;
for (String s : cache.keySet()) {
final Map<String, Integer> stringIntegerMap = cache.get(s);
for (String s1 : stringIntegerMap.keySet()) {
final Integer integer = stringIntegerMap.get(s1);
if (integer < lastUsedValue) {
lastUsedValue = integer;
leastRecentUsedKey = s;
}
}
}
cache.remove(leastRecentUsedKey);
Map<String, Integer> valueMap = new HashMap<>();
valueMap.put(value, 0);
cache.put(key, valueMap);
}
}
Solution 10 - C++
Detailed explanation here in my blogpost.
class LRUCache {
constructor(capacity) {
this.head = null;
this.tail = null;
this.capacity = capacity;
this.count = 0;
this.hashMap = new Map();
}
get(key) {
var node = this.hashMap.get(key);
if(node) {
if(node == this.head) {
// node is already at the head, just return the value
return node.val;
}
if(this.tail == node && this.tail.prev) {
// if the node is at the tail,
// set tail to the previous node if it exists.
this.tail = this.tail.prev;
this.tail.next = null;
}
// link neibouring nodes together
if(node.prev)
node.prev.next = node.next;
if(node.next)
node.next.prev = node.prev;
// add the new head node
node.prev = null;
node.next = this.head;
this.head.prev = node;
this.head = node;
return node.val;
}
return -1;
}
put(key, val) {
this.count ++;
var newNode = { key, val, prev: null, next: null };
if(this.head == null) {
// this.hashMap is empty creating new node
this.head = newNode;
this.tail = newNode;
}
else {
var oldNode = this.hashMap.get(key);
if(oldNode) {
// if node with the same key exists,
// clear prev and next pointers before deleting the node.
if(oldNode.next) {
if(oldNode.prev)
oldNode.next.prev = oldNode.prev;
else
this.head = oldNode.next;
}
if(oldNode.prev) {
oldNode.prev.next = oldNode.next;
if(oldNode == this.tail)
this.tail = oldNode.prev;
}
// removing the node
this.hashMap.delete(key);
this.count --;
}
// adding the new node and set up the pointers to it's neibouring nodes
var currentHead = this.head;
currentHead.prev = newNode;
newNode.next = currentHead;
this.head = newNode;
if(this.tail == null)
this.tail = currentHead;
if(this.count == this.capacity + 1) {
// remove last nove if over capacity
var lastNode = this.tail;
this.tail = lastNode.prev;
if(!this.tail) {
//debugger;
}
this.tail.next = null;
this.hashMap.delete(lastNode.key);
this.count --;
}
}
this.hashMap.set(key, newNode);
return null;
}
}
var cache = new LRUCache(3);
cache.put(1,1); // 1
cache.put(2,2); // 2,1
cache.put(3,3); // 3,2,1
console.log( cache.get(2) ); // 2,3,1
console.log( cache.get(1) ); // 1,2,3
cache.put(4,4); // 4,1,2 evicts 3
console.log( cache.get(3) ); // 3 is no longer in cache
Solution 11 - C++
you can visit my LRU Cache Blogpost : https://lrucachejava.blogspot.com/
Java Code :
package DataStructures;
import java.util.HashMap;
class Node2 {
int key;
int value;
Node2 pre;
Node2 next;
Node2(int key ,int value)
{
this.key=key;
this.value=value;
}
} class LRUCache {
private HashMap<Integer,Node2> lrumap;
private int capacity;
private Node2 head,tail;
LRUCache(int capacity)
{
this.capacity=capacity;
lrumap=new HashMap<Integer,Node2>();
head=null;
tail=null;
}
public void deleteNode(Node2 node)
{
if(node==head)
{
head.next.pre=null;
head=head.next;
node=null;
}
else if(node==tail)
{
tail.pre.next=null;
tail=tail.pre;
node=null;
}
else
{
node.pre.next=node.next;
node.next.pre=node.pre;
node=null;
}
}
public void addToHead(Node2 node)
{
if(head==null && tail==null)
{
head=node;
tail=node;
}
else
{
node.next=head;
head.pre=node;
head=node;
}
}
public int get(int key)
{
if(lrumap.containsKey(key))
{
Node2 gnode=lrumap.get(key);
int result=gnode.value;
deleteNode(gnode);
addToHead(gnode);
return result;
}
return -1;
}
public void set(int key,int value)
{
if(lrumap.containsKey(key))
{
Node2 snode=lrumap.get(key);
snode.value=value;
deleteNode(snode);
addToHead(snode);
}
else
{
Node2 node=new Node2(key,value);
//System.out.println("mapsize="+lrumap.size()+" capacity="+capacity);
if(lrumap.size()>=capacity)
{
System.out.println("remove="+tail.key);
lrumap.remove(tail.key);
deleteNode(tail);
}
lrumap.put(key, node);
addToHead(node);
}
}
public void show()
{
Node2 node = head;
while(node.next!=null)
{
System.out.print("["+node.key+","+node.value+"]--");
node=node.next;
}
System.out.print("["+node.key+","+node.value+"]--");
System.out.println();
}
}
public class LRUCacheDS{
public static void main(String[] args) {
LRUCache lr= new LRUCache(4);
lr.set(4,8);
lr.set(2,28);
lr.set(6,38);
lr.show();
lr.set(14,48);
lr.show();
lr.set(84,58);
lr.show();
lr.set(84,34);
lr.show();
lr.get(6);
System.out.println("---------------------------------------------------------");
lr.show();
}
}
Solution 12 - C++
Is LRU approximation allowed? Here is one that does 20 million get/set operations per second for some image smoothing algorithm. I don't know if its not the worst but its certainly a lot faster than Javascript equivalent which does only 1.5 million get/set per second.
Unordered_map to keep track of items on circular buffers. Circular buffer doesn't add/remove nodes as other linked-list versions. So it should be at least friendly on the CPU's L1/L2/L3 caches unless cache size is much bigger than those caches. Algorithm is simple. There is a hand of clock that evicts victim slots while the other hand does save some of them from eviction as a "second chance" but lags the eviction by 50% phase so that if cache is big then cache items have a good amount of time to get their second chance / be saved from eviction.
Since this is an approximation, you shouldn't expect it to evict the least recent one always. But it does give a speedup on some network I/O, disk read/write, etc that are slower than RAM. I used this in a VRAM virtual buffer class that uses 100% of system video-ram (from multiple graphics cards). VRAM is slower than RAM so caching in RAM makes 6GB VRAM look like as fast as RAM for some cache-friendly access patterns.
Here is implementation:
#ifndef LRUCLOCKCACHE_H_
#define LRUCLOCKCACHE_H_
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<functional>
#include<mutex>
#include<unordered_map>
/* LRU-CLOCK-second-chance implementation */
template< typename LruKey, typename LruValue>
class LruClockCache
{
public:
// allocates circular buffers for numElements number of cache slots
// readMiss: cache-miss for read operations. User needs to give this function
// to let the cache automatically get data from backing-store
// example: [&](MyClass key){ return redis.get(key); }
// takes a LruKey as key, returns LruValue as value
// writeMiss: cache-miss for write operations. User needs to give this function
// to let the cache automatically set data to backing-store
// example: [&](MyClass key, MyAnotherClass value){ redis.set(key,value); }
// takes a LruKey as key and LruValue as value
LruClockCache(size_t numElements,
const std::function<LruValue(LruKey)> & readMiss,
const std::function<void(LruKey,LruValue)> & writeMiss):size(numElements)
{
ctr = 0;
// 50% phase difference between eviction and second-chance hands of the "second-chance" CLOCK algorithm
ctrEvict = numElements/2;
loadData=readMiss;
saveData=writeMiss;
// initialize circular buffers
for(size_t i=0;i<numElements;i++)
{
valueBuffer.push_back(LruValue());
chanceToSurviveBuffer.push_back(0);
isEditedBuffer.push_back(0);
keyBuffer.push_back(LruKey());
}
}
// get element from cache
// if cache doesn't find it in circular buffers,
// then cache gets data from backing-store
// then returns the result to user
// then cache is available from RAM on next get/set access with same key
inline
const LruValue get(const LruKey & key) noexcept
{
return accessClock2Hand(key,nullptr);
}
// thread-safe but slower version of get()
inline
const LruValue getThreadSafe(const LruKey & key) noexcept
{
std::lock_guard<std::mutex> lg(mut);
return accessClock2Hand(key,nullptr);
}
// set element to cache
// if cache doesn't find it in circular buffers,
// then cache sets data on just cache
// writing to backing-store only happens when
// another access evicts the cache slot containing this key/value
// or when cache is flushed by flush() method
// then returns the given value back
// then cache is available from RAM on next get/set access with same key
inline
void set(const LruKey & key, const LruValue & val) noexcept
{
accessClock2Hand(key,&val,1);
}
// thread-safe but slower version of set()
inline
void setThreadSafe(const LruKey & key, const LruValue & val) noexcept
{
std::lock_guard<std::mutex> lg(mut);
accessClock2Hand(key,&val,1);
}
void flush()
{
for (auto mp = mapping.cbegin(); mp != mapping.cend() /* not hoisted */; /* no increment */)
{
if (isEditedBuffer[mp->second] == 1)
{
isEditedBuffer[mp->second]=0;
auto oldKey = keyBuffer[mp->second];
auto oldValue = valueBuffer[mp->second];
saveData(oldKey,oldValue);
mapping.erase(mp++); // or "it = m.erase(it)" since C++11
}
else
{
++mp;
}
}
}
// CLOCK algorithm with 2 hand counters (1 for second chance for a cache slot to survive, 1 for eviction of cache slot)
// opType=0: get
// opType=1: set
LruValue const accessClock2Hand(const LruKey & key,const LruValue * value, const bool opType = 0)
{
typename std::unordered_map<LruKey,size_t>::iterator it = mapping.find(key);
if(it!=mapping.end())
{
chanceToSurviveBuffer[it->second]=1;
if(opType == 1)
{
isEditedBuffer[it->second]=1;
valueBuffer[it->second]=*value;
}
return valueBuffer[it->second];
}
else
{
long long ctrFound = -1;
LruValue oldValue;
LruKey oldKey;
while(ctrFound==-1)
{
if(chanceToSurviveBuffer[ctr]>0)
{
chanceToSurviveBuffer[ctr]=0;
}
ctr++;
if(ctr>=size)
{
ctr=0;
}
if(chanceToSurviveBuffer[ctrEvict]==0)
{
ctrFound=ctrEvict;
oldValue = valueBuffer[ctrFound];
oldKey = keyBuffer[ctrFound];
}
ctrEvict++;
if(ctrEvict>=size)
{
ctrEvict=0;
}
}
if(isEditedBuffer[ctrFound] == 1)
{
// if it is "get"
if(opType==0)
{
isEditedBuffer[ctrFound]=0;
}
saveData(oldKey,oldValue);
// "get"
if(opType==0)
{
LruValue loadedData = loadData(key);
mapping.erase(keyBuffer[ctrFound]);
valueBuffer[ctrFound]=loadedData;
chanceToSurviveBuffer[ctrFound]=0;
mapping[key]=ctrFound;
keyBuffer[ctrFound]=key;
return loadedData;
}
else /* "set" */
{
mapping.erase(keyBuffer[ctrFound]);
valueBuffer[ctrFound]=*value;
chanceToSurviveBuffer[ctrFound]=0;
mapping[key]=ctrFound;
keyBuffer[ctrFound]=key;
return *value;
}
}
else // not edited
{
// "set"
if(opType == 1)
{
isEditedBuffer[ctrFound]=1;
}
// "get"
if(opType == 0)
{
LruValue loadedData = loadData(key);
mapping.erase(keyBuffer[ctrFound]);
valueBuffer[ctrFound]=loadedData;
chanceToSurviveBuffer[ctrFound]=0;
mapping[key]=ctrFound;
keyBuffer[ctrFound]=key;
return loadedData;
}
else // "set"
{
mapping.erase(keyBuffer[ctrFound]);
valueBuffer[ctrFound]=*value;
chanceToSurviveBuffer[ctrFound]=0;
mapping[key]=ctrFound;
keyBuffer[ctrFound]=key;
return *value;
}
}
}
}
private:
size_t size;
std::mutex mut;
std::unordered_map<LruKey,size_t> mapping;
std::vector<LruValue> valueBuffer;
std::vector<unsigned char> chanceToSurviveBuffer;
std::vector<unsigned char> isEditedBuffer;
std::vector<LruKey> keyBuffer;
std::function<LruValue(LruKey)> loadData;
std::function<void(LruKey,LruValue)> saveData;
size_t ctr;
size_t ctrEvict;
};
#endif /* LRUCLOCKCACHE_H_ */
Here is usage:
using MyKeyType = std::string;
using MyValueType = MinecraftChunk;
LruClockCache<MyKeyType,MyValueType> cache(1024*5,[&](MyKeyType key){
// cache miss (read)
// access data-store (network, hdd, graphics card, anything that is slower than RAM or higher-latency than RAM-latency x2)
return readChunkFromHDD(key);
},[&](MyKeyType key,MyValueType value){
// cache miss (write)
// access data-store
writeChunkToHDD(key,value);
});
// cache handles all cace-miss functions automatically
MinecraftChunk chunk = cache.get("world coordinates 1500 35 2000");
// cache handles all cace-miss functions automatically
cache.set("world coordinates 1502 35 1999",chunk);
cache.flush(); // clears all pending-writes in the cache and writes to backing-store
Solution 13 - C++
We have to create a data structure that allows us to optimize all three main operations at the same time.
Based on the above graph, we could infer that:
-
Using tree would be best choice for general case.
-
The hash table would be the best choice if we know the size of the cache is big enough (and the insertion of new elements infrequent enough) to rarely require the removal of the oldest entry.
-
The linked list could be a valid option if removing old entries were more important than storing entries or finding cache elements: but in that case, the cache would basically be useless, and adding it would provide no benefit.
-
In all cases, the memory needed to store n entries is O(n).
Now my favorite question is, can we do any better?
A single data structure might not be enough to build the most efficient solution to the problem. On the one hand, we have data structures that are particularly good for quickly storing and retrieving entries. Hash tables are pretty much impossible to beat if that’s the game. On the other hand, hash tables are terrible when it comes to maintaining an ordering of things and they are not great when it comes to retrieving the minimum (or maximum) element they contain, but we have other structures that handle this very well. Depending on the kind of order we would like to keep, we might need trees, or we might be fine with lists.
We only have to keep an ordering on the cache entries, being able to go from the least to the most recently used. Since the order is only based on insertion time, new elements are not changing the order of the older elements; therefore, we don’t need anything fancy: we only need a structure that supports FIFO. We could just use a list or a queue. A linked list is usually the best choice when we don’t know in advance the number of elements we will have to store or the number can change dynamically, while a queue is usually implemented using an array (and so more static in dimension), but optimized for insertion on the head and removal on the tail.
Linked lists can also support fast insertion/removal at their ends. We need, however, a doubly-linked list, where we insert elements on the front and remove them from the tail. By always keeping a pointer to the tail and links from each node to its predecessor, we can implement tail removal in O(1) time.
You can see the tree data elements that are stored for the cache and need to be updated after every operation: (1) The hash table. (2) The head of a doubly-linked list. (3) A pointer to the last element in the list. Notice how each element in the hash table points to a node in the list where all the data is stored. To get from a list entry to the corresponding hash entry, we have to hash the name of the company stored in the node, which is the key for the table.
We considered the hash table and the linked list separately, but we need to make them work together in synchrony. We might store very large objects in the cache, and we definitely don’t want to duplicate them in both data structures. One way to avoid duplication is storing the entries only in one of the structures and referencing them from the other one. We could either add the entries to the hash table and store in the other DS the key to the a hash table, or vice versa.
Now, we need to decide which data structure should hold the values and which one should be left with the reference. The best choice is having hash table entries store pointers to linked list nodes, and have the latter store the actual values. (If we do the opposite, then the way we link from a linked list node to the hash table entry will be tied to the implementation of the hash table. It could be an index for open addressing or a pointer if we use chaining. This coupling to implementation is neither good design nor, often, possible, as you usually can’t access standard library internals).
This cache is called least recently used. It’s not least recently added. This means the ordering is not just based on the time we first add an element to cache, but on the last time, it was accessed.
-
When we add a new entry to the cache, when we have a cache miss, trying to access an element that is not on the cache, we just add a new entry to the front of our linked list.
-
But when we run into a cache hit, accessing an element that is indeed stored on the cache, we need to move an existing list element to the front of the list, and we can only do that efficiently if we can both retrieve in constant (we still need to include the time for computing each hash value for the entry we look up.) time a pointer to the linked list node for the existing entry (which could be anywhere in the list, for what we know), and remove an element from the list in constant time (again, we need a doubly-linked list for this; with an array-based implementation of a queue, removal in the middle of the queue takes linear time).
-
If the cache is full, we need to remove the least-recently-used entry before we can add a new one. In this case, the method to remove the oldest entry can access the tail of the linked list in constant time, from which we recover the entry to delete. To locate it on the hash table and delete it from it, we will need to hash the entry (or its ID) at an extra cost (potentially non-constant: for strings, it will depend on the length of the string).
Solution 14 - C++
Working of LRU Cache
Discards the least recently used items first. This algorithm requires keeping track of what was used when which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes.
The access sequence for the below example is A B C D E C D B.
class Node: def init(self, k, v): self.key = k self.value = v self.next = None self.prev = None class LRU_cache: def init(self, capacity): self.capacity = capacity self.dic = dict() self.head = Node(0, 0) self.tail = Node(0, 0) self.head.next = self.tail self.tail.prev = self.head def _add(self, node): p = self.tail.prev p.next = node self.tail.prev = node node.next = self.tail node.prev = p def _remove(self, node): p = node.prev n = node.next p.next = n n.prev = p def get(self, key): if key in self.dic: n = self.dic[key] self._remove(n) self._add(n) return n.value return -1 def set(self, key, value): n = Node(key, value) self._add(n) self.dic[key] = n if len(self.dic) > self.capacity: n = self.head.next self._remove(n) del self.dic[n.key] cache = LRU_cache(3) cache.set('a', 'apple') cache.set('b', 'ball') cache.set('c', 'cat') cache.set('d', 'dog') print(cache.get('a')) print(cache.get('c'))