Pseudo-LRU implementation using 1-bit per entry and achieving hit ratios within 1-2% of Full-LRU (using expensive doubly-linked lists). This algorithm is commonly refered to as "PLRUm" because each bit serves as a MRU flag for each cache entry.
Academic literature where PLRUm is mentioned:
- Performance evaluation of cache replacement policies for the SPEC CPU2000 benchmark suite
- Shows that PLRUm is a very good approximation of LRU
- Study of Different Cache Line Replacement Algorithms in Embedded Systems
- Shows that PLRUm usually outperforms other PLRU algorithms
- In some cases, PLRUm outperforms LRU
NOTE: This is a small experiment repo and everything's still up in the air. Future plans include trying to implement a full cache out of this where it handles collisions and increases data locality.
This library is intended to be small and flexible for use within full cache implementations. Therefore, it is not safe for concurrent use out of the box and it does nothing to handle collisions. It makes sense to use this within a mutex lock close to a hashmap.
// create a new Policy tracking 1024 entries
p := NewPolicy(1024)
// on a Get operation, call policy.Hit() for the cache entry
p.Hit(1)
// when the cache is full, call policy.Evict() to get a LRU bit
victim := p.Evict()
// add some things to the victim location
// ...
// call policy.Hit() on the new entry to flag it as MRU
p.Hit(victim)This PLRUm implementation uses uint64 blocks and uses round-robin for
selecting which block to evict from (performs better than random selection).
Before being populated, each block is 0.
Adding new items behaves just like a hit operation in which the bit is set to 1 because of the recent access.
After adding items A, B, C, D, E, F, and G, the PLRUm state looks like this:
The eviction operation requires 0 bits to be present and sample from. To prevent all bits from being 1 and a potential deadlock situation, all bits except the newest are set to 0 when capacity is reached.
After adding item H, the PLRUm state looks like this:
A hit just sets the bit to 1.
After hitting item D, the PLRUm state looks like this:
The eviction process returns the location of the first 0 bit found.
After eviction and adding item I, the PLRUm state looks like this:
