LRU cache

A cache keeps a few answers close by, so they do not have to be fetched or worked out again. When it is full, it must choose what to throw out. The usual choice is the item used longest ago. Building this with every step in O(1) needs two structures working together: a dict and a two-way linked list.

What a cache is

Reading from a disk or a far-away server is slow. Recomputing a hard result is slow too. A cache keeps recent results in fast memory. Your web browser keeps recent pages, a database keeps recent disk blocks, and a processor keeps recent memory.

Memory is limited, so a cache holds at most some number of items, its capacity. When a new item arrives and the cache is full, one item must be thrown out. This is called eviction. A good rule throws out an item that is unlikely to be needed soon. The most common rule is least recently used, LRU: throw out the item whose last use is furthest in the past. It works because programs tend to reuse what they used recently.

The cache needs two jobs:

• get(key): return the value, or say it is missing. A successful get counts as a use.
• put(key, value): store the value; this is also a use. If the key is new and the cache is full, evict the least recently used key first.

A dict and a two-way list

Each job needs two things to be fast:

1. Find a key. A dict does this in O(1) on average.
2. Keep the keys in order of last use, and move any key to the “most recent” end in O(1). A Python list cannot do this: taking an item out of the middle moves every item after it, O(n).

A two-way linked list (LINK-3) can remove a node from the middle in O(1), if you already hold that node. And the dict can hand you the node. So the dict maps each key to its node, and the nodes form a two-way list in order of use. Two sentinel nodes, front and back, sit at the ends (LINK-3), so every real node always has neighbours on both sides.

get and put

Step through a cache with room for 3 items:

Every job is made of three small moves:

def _unlink(self, node):            # take a node out: O(1)
    node.prev.next = node.next
    node.next.prev = node.prev

def _push_front(self, node):        # put a node just after front: O(1)
    node.prev = self.front
    node.next = self.front.next
    self.front.next.prev = node
    self.front.next = node

def get(self, key):
    node = self.map.get(key)
    if node is None:
        return -1
    self._unlink(node)              # a use: move it to the front
    self._push_front(node)
    return node.value

put on an existing key changes the value and moves the node to the front. On a new key with a full cache, it takes the node back.prev, unlinks it and deletes its key from the dict. For that last step, each node stores its own key as well as its value. Then it makes the new node, puts it in the dict, and pushes it to the front.

Each job is one dict lookup plus a fixed number of reference changes, so get and put both take O(1) on average. The space is O(capacity): one dict entry and one node per item.

Python’s own tools

functools.lru_cache wraps a function and caches its results by its arguments, with LRU eviction. Inside, it uses exactly this design: a dict plus a two-way circular list.

from functools import lru_cache

@lru_cache(maxsize=1000)
def fare(src, dst):
    ...                         # slow work, done once per (src, dst)

fare.cache_info()               # hits, misses, maxsize, currsize

The arguments become the dict key, so they must be hashable. maxsize=None keeps everything and never evicts; the shorter functools.cache means the same thing. The DYNP station uses it to remember answers (memoisation).

collections.OrderedDict is a dict that keeps its own order and can change it: move_to_end(key) makes a key the newest in O(1), and popitem(last=False) removes the oldest. An LRU cache takes about ten lines with it. It too is a dict plus a two-way list inside.