LRU cache with tests and a benchmark

What you will practise

• a doubly linked list with explicit node pointers
• combining two data structures so each covers the other's weakness
• manual memory ownership, and freeing exactly once
• writing assertions that name what they check
• generating a repeatable pseudo-random workload
• reading a benchmark honestly, including what it cannot tell you

Requirements

The project is done when every one of these is true.

• get and put are both average constant time: neither ever walks the recency list looking for a key, and neither loops over the capacity.
• A hash map takes a key straight to its list node, and a doubly linked list holds the nodes in recency order with the most recently used at one known end.
• The cache has a fixed capacity set at construction, and once it is full a put of a new key evicts exactly the least recently used entry.
• A get that hits returns the value and makes that entry the most recently used; a get that misses reports a miss and does not insert anything.
• A put on a key already present updates the value and counts as a use, and does not increase the size.
• The cache exposes its current size and its running hit and miss counts, and those counts only change in the places you intend.
• Every node allocated is freed exactly once: on eviction, on erase, and on destruction. There is no path that leaks and none that frees twice.
• A test function runs every case below as a named assertion, printing a line per failure and a final pass count out of the total, and returns a non-zero result if anything failed.
• A benchmark runs the same deterministic workload through your cache and through a naive implementation that keeps the same capacity but finds the least recently used entry by scanning, prints the operation count, the hit count and the elapsed time for each, and asserts the two hit counts are equal.

Milestones

A sensible order to build it in, so something works at every step.

1. 1

   Write the doubly linked list alone

   Build push-to-front, unlink and pop-from-back on a list of nodes with no cache around them, and test those three operations on their own. Almost every LRU bug lives here.

2. 2

   Add the map and make get work

   Map each key to its node, implement get as a lookup plus a move to the front, and test that a hit reorders the list while a miss leaves it alone.

3. 3

   Add put without eviction

   Insert new keys at the front and update existing keys in place, keeping size correct, while the capacity is still large enough that nothing is ever evicted.

4. 4

   Add eviction and the counters

   When a put would exceed the capacity, pop the back node, erase its key from the map, free it, and only then insert. Add the hit and miss counters in the same pass.

5. 5

   Write the test function

   Turn every case in the testing list below into a named assertion with a pass count, so a change you make in ten minutes cannot quietly break eviction.

6. 6

   Write the naive implementation

   Implement the same interface with a plain array and a last-used timestamp per entry, finding the least recently used entry by scanning. It is the thing your fast version has to agree with.

7. 7

   Benchmark, then read the result carefully

   Run one deterministic workload through both, check the hit counts match exactly, and write down what the timings do and do not tell you about a real machine.

Hints

Open one only when you are stuck. Each gives a little more away.

How to test it

Run these checks yourself, or turn them into automated tests once you know how.

• Capacity 2. put(1,a), put(2,b), get(1) hits and returns a. Now put(3,c): key 2 must be the one evicted, because get(1) made key 1 more recent. get(2) misses, get(3) hits, get(1) hits. Run from a fresh cache, that whole sequence leaves 3 hits and 1 miss, assuming put counts towards neither.
• Capacity 2. put(1,a), put(1,b): the size must still be 1 and get(1) must return b. Capacity 1. put(1,a), put(2,b): get(1) misses and get(2) returns b.
• get on an empty cache misses, the size stays 0, and a following get for the same key misses again, proving a miss inserts nothing.
• Insert capacity plus 1000 distinct keys one after another: the size must never exceed the capacity, and only the last capacity keys may still hit.
• Decide and document what capacity 0 means, then assert it: whatever you choose, it must not crash, must not evict forever, and must report every get as a miss.
• Fill the cache, then get the oldest key just before inserting a new one: the new insert must evict the second-oldest instead, which is the case a naive move-to-front gets wrong.
• Run 200,000 operations drawn from 5,000 keys at capacity 1,000 through both implementations: the hit counts must be identical to the last hit. If they differ, one of the two is not implementing least-recently-used.
• Run the test function twice in one program from separate cache objects and confirm both runs pass, which catches state accidentally shared through a static or a global. Then destroy a full cache and, if your toolchain has one, run the same program under a memory sanitiser on your own computer to confirm nothing leaks and nothing is freed twice.

Stretch goals

• Add a most-recently-used eviction policy behind the same interface and compare hit rates on the same workload.
• Add a size limit in bytes rather than in entries, with each value declaring its own cost.
• Make the capacity resizable at runtime, evicting down to the new capacity in the right order.
• Replace the hash map with one you write yourself, with open addressing, and compare against the library version.
• Add a workload generator with a skewed key distribution and show how the hit rate changes as capacity grows.

Learn what you need

• C: dynamic memory, malloc and free →
• Linked lists →
• Hashing →
• Big O notation →
• Caching strategies →
• See a linked list step by step →