NAME
LinkedList::Single::Example::LRU - least-recently-used cache with the order kept in a linked list
SYNOPSIS
use LinkedList::Single::Example::LRU;
my $cache
= LinkedList::Single::Example::LRU->new
(
limit => 1_000
, on_evict => sub( $key, $value ) { write_back( $key, $value ) }
);
$cache->put( $key => $value );
my $value = $cache->get( $key ); # undef on a missDESCRIPTION
A cache holds at most limit entries. get returns a value and makes its entry the newest; put adds or replaces an entry as the newest and, if the cache is then over its limit, evicts the oldest, passing its key and value to on_evict if there is one. This is the least-recently-used (LRU) policy. exists, size, limit and contents (newest first) look at the cache without changing it.
The order of the entries is kept in a LinkedList::Single. A hash maps each key to a cursor on the node before its entry, so a hit finds the entry without searching and moves it to the front with pointer changes, and the eviction of the oldest is another. The cost of one operation does not depend on how many entries the cache holds.
Three classes with the same interface keep the same cache in perl arrays and hashes: LinkedList::Single::Example::LRU::Array (an array of pairs, searched on every hit), LinkedList::Single::Example::LRU::Order (a hash and an array of keys) and LinkedList::Single::Example::LRU::Lazy (a hash and a queue of time-stamped uses, never searched). The first is the test oracle: the tests drive the list and the arrays with the same random requests and compare what each returns and what each evicts.
How it is benchmarked
benchmarks/10-LRU/compare runs a read-through cache (a get that misses is followed by a put) at limits of 100, 10,000 and 200,000 entries, with three request patterns: hot (90% of requests to a tenth of the limit's worth of keys), uniform (keys drawn from twice the limit, about half hit) and scan (keys taken in turn from one more than the limit). It reports microseconds per operation, the memory of a fresh process holding 200,000 entries, and statements and branches counted in each implementation's code.
Why it matters
A cache is on the hot path of whatever uses it, and the order of its entries is touched on every hit. How that order is kept decides whether the cost of a hit stays the same or grows with the size of the cache. Here the list's cost stays flat, the arrays that search for the key grow with the cache, and the array version written to avoid the search is fastest of the four at every size measured. So the list is a fair choice against an array that searches and not against one that does not. The measurements, the background and the references are in LinkedList::Single::Example::LRU::POD.
This is an example, not a cache for production use: it has no expiry, no thread safety and no hit counters.