Card 02/ 06
Trace an LRU Cache Through Gets and Puts
Each access moves its key to the front, and a full cache evicts from the back.
Tracing an LRU cache means following both of its structures through every get and put, and checking that they agree after each one. This card covers the four things an operation can do: a get that finds its key, a get that misses, a put of a new key with or without an eviction, and a put that updates a key already present.
An LRU cache evicts the least recently used key when it is full. It keeps a hash map from each key to a node, and a doubly linked list of those nodes, most recently used at the front, between two placeholder nodes called head and tail. The cache here has capacity 3 and runs seven operations: put(a, 1), put(b, 2), put(c, 3), get(a), put(d, 4), get(b) and put(c, 5). Each state below is as a run printed it.
Predict first: after put(a, 1), put(b, 2), put(c, 3) and get(a), which key does put(d, 4) evict?
It evicts b. a was put first, but get(a) used it again and moved it to the front, so b became the key that had gone longest without use. Choosing a means reading the cache as first in, first out, which ignores every get.
Seven operations on an LRU cache of capacity 3
put(a, 1), put(b, 2), put(c, 3): three new keys, no eviction
Each new key gets a node at the front of the list and an entry in the map pointing to it. The cache now holds three keys, its capacity.
list: c=3 ⇄ b=2 ⇄ a=1
map: a b cget(a): a hit, so a moves to the front
The map finds a's node in one step. The node is unlinked from its neighbours and relinked after head, and get returns 1. The map does not change, because the node it points to is the same node in a new place.
list: a=1 ⇄ c=3 ⇄ b=2
map: a b cput(d, 4): a new key in a full cache, so b is evicted
The cache is full, so the node before tail goes first: b. It is unlinked from the list, and its key, stored on the node, deletes b from the map. Then d gets a node at the front.
list: d=4 ⇄ a=1 ⇄ c=3
map: a c dget(b): a miss, so nothing moves
b is not in the map, so get reports a miss and neither structure changes. A program would now fetch b from wherever it lives and put it.
list: d=4 ⇄ a=1 ⇄ c=3
map: a c dput(c, 5): an existing key, so its value changes and it moves to the front
c is already in the map, so no node is created and nothing is evicted. Its node takes the value 5 and moves from the back to the front, so a put counts as a use in the same way as a get.
list: c=5 ⇄ d=4 ⇄ a=1
map: a c dThe final order, most recent first, is c, d, a, and the next eviction would remove a. After every step the map held exactly the keys in the list. Each operation touched a fixed number of nodes and map entries, whatever the capacity: one lookup, at most two unlinks and one relink, which is why get and put are both O(1).
To trace any sequence, keep two columns, the list and the map, and change both on every line: a hit or an update moves one key to the front; a new key goes to the front and, when the cache is full, pushes the back key out of both columns.
← → move through sections and cards