LRU caches

A cache of four, and ten requests. Watch which item leaves when a fifth one arrives, and what a hit does to the order.

⋯50bool get(struct cache *c, int key, int *value)51{52    struct entry *e = find(c, key);53    if (e == NULL)54        return false;55    unlink_entry(e);56    push_front(c, e);57    *value = e->value;58    return true;59}60 61void put(struct cache *c, int key, int value)62{63    if (c->size == CAP) {64        struct entry *old = c->list.prev;65        unlink_entry(old);66        drop_from_bucket(c, old);67        free(old);68        c->size--;69    }70    struct entry *e = malloc(sizeof *e);71    if (e == NULL)72        exit(1);73    e->key = key;74    e->value = value;75    push_front(c, e);76    e->chain = c->bucket[key % M];77    c->bucket[key % M] = e;78    c->size++;79}⋯81int main(void)82{83    struct cache c;84    c.list.prev = &c.list;85    c.list.next = &c.list;86    for (int b = 0; b < M; b++)87        c.bucket[b] = NULL;88    c.size = 0;89    const int requests[10] = { 1, 2, 3, 1, 4, 2, 5, 1, 2, 6 };90    int hits = 0;91    for (int i = 0; i < 10; i++) {92        int v;93        if (get(&c, requests[i], &v)) {94            hits++;95            printf("h ");96        } else {97            put(&c, requests[i], 10 * requests[i]);98            printf("m ");99        }100    }101    printf("\n%d hits, %d misses; most recent first:", hits, 10 - hits);102    for (const struct entry *e = c.list.next; e != &c.list; e = e->next)103        printf(" %d", e->key);104    printf("\n");105    struct entry *e = c.list.next;106    while (e != &c.list) {107        struct entry *next = e->next;108        free(e);109        e = next;110    }111    return 0;112}

Finding and ordering

A cache keeps a few items that are slow to fetch, so that a second request for one is quick. It has room for a fixed number, its capacity. When it is full and a new item arrives, one item has to go. Least recently used, LRU, evicts the item whose last use is furthest in the past, on the bet that what was used recently will be used again soon.

An LRU cache has to do two jobs in a fixed number of steps. It has to find an item by its key, and it has to know which item was used least recently. The clip does them with two structures that share their nodes. The bucket heads are a hash table with chaining: a key’s bucket is key % 4, and its chain is short. The row is a doubly linked list in order of use: the most recent at the front, the least recent at the back. Each node belongs to both.

The code and its cost

struct entry {
    int key, value;
    struct entry *prev, *next;
    struct entry *chain;
};

struct cache {
    struct entry list;
    struct entry *bucket[M];
    int size;
};

bool get(struct cache *c, int key, int *value)
{
    struct entry *e = find(c, key);
    if (e == NULL)
        return false;
    unlink_entry(e);
    push_front(c, e);
    *value = e->value;
    return true;
}

void put(struct cache *c, int key, int value)
{
    if (c->size == CAP) {
        struct entry *old = c->list.prev;
        unlink_entry(old);
        drop_from_bucket(c, old);
        free(old);
        c->size--;
    }
    struct entry *e = malloc(sizeof *e);
    if (e == NULL)
        exit(1);
    e->key = key;
    e->value = value;
    push_front(c, e);
    e->chain = c->bucket[key % M];
    c->bucket[key % M] = e;
    c->size++;
}

An entry carries two sets of pointers. prev and next place it in the list; chain places it in its bucket. It is 32 bytes: two ints and three pointers, with no padding.

The list is the ring of 7.6, closed by a sentinel: c.list is a whole entry inside the cache that holds no item. The front of the list is c.list.next and the back is c.list.prev; an empty list is the sentinel pointing at itself. unlink_entry and push_front are 7.6’s moves: unlinking makes the two neighbours point past the entry, two writes, and pushing on the front sets four pointers between the sentinel and the old front. find walks the key’s chain, as get did in 18.2.

The keys must not be negative. In C, -3 % 4 is −3, because division rounds toward zero, and c->bucket[-3] lies outside the array: undefined behaviour.

A hit and a miss

A hit finds the entry, unlinks it from wherever it is in the list and pushes it on the front. Its bucket does not change, because the key has not changed. A hit always changes the order unless the entry is already at the front: request 1 turns 3 2 1 into 1 3 2.

A miss returns false, and main calls put to load the item. (put is called only after a miss, so the key is never already in the cache.) If the cache is full, the entry at the back, c.list.prev, is the least recently used. It has to leave both structures: unlink_entry takes it out of the list, and drop_from_bucket takes it out of its chain. Then the new entry goes on the front of the list and on the front of its bucket’s chain. The value 10 × key stands for whatever a real cache would fetch.

static void drop_from_bucket(struct cache *c, struct entry *e)
{
    struct entry **link = &c->bucket[e->key % M];
    while (*link != e)
        link = &(*link)->chain;
    *link = e->chain;
}

link holds the address of the pointer that points at the entry: the bucket head when the entry is first in its chain, a chain field when it is not. One loop serves both, as in Removing from a linked list.

The ten requests print m m m h m h m h h m, then 4 hits, 6 misses; most recent first: 6 2 1 5. When 5 arrives the list is 2 4 1 3, and 3 is evicted; when 6 arrives it is 2 1 5 4, and 4 goes.

In this build, the malloc for 5 returned the very block that 3 had just freed, and the one for 6 the block of 4. That is the C library on this platform: glibc keeps a small cache of freed chunks and hands the most recent one of the right size back first. C itself promises nothing about where malloc’s next block lies.

Why both structures

The list alone keeps the order, but finding a key in it means walking it: O(n) for a cache of n items. The table alone finds a key quickly, but it has no idea which entry is oldest: finding the least recently used would mean looking at every entry. Together, the table finds the entry and the list, through the entry’s own prev and next, moves it or removes it without a walk. A singly linked list would not do: unlinking needs the entry before, and only prev gives it in one step.

The cost

Apart from walking one chain, get and put do a fixed number of steps: two writes to unlink, four to push on the front, two to put a new entry in its bucket. The chain walks in find and drop_from_bucket look at about 1 + α entries on average, where α is the load factor of 18.2: here at most 4 entries in 4 buckets, α ≤ 1. So with a table sized to the capacity, every operation is O(1) on average, and O(n) only in the worst case, when every key lands in one bucket.

Worked example

A cache of 3. The same ten requests give m m m h m m m m h m: 2 hits. The 4 pushes out 2, the least recent at that moment, so the next request for 2 is a miss.

A cache of 5. Still 4 hits: one more slot does not help here. The cache of 4 evicted only 3 and 4, and neither is requested again.

Memory. Each cached item costs one 32-byte entry, and the table adds M bucket pointers, here 4 × 8 = 32 bytes, plus the sentinel. On this platform glibc gives each 32-byte malloc a 48-byte chunk, so the heap holds 48 bytes per item.

Two checks. Which key is evicted when 5 arrives? (3, the least recently used.) Why does drop_from_bucket take a pointer to a link? (So that one loop works whether the entry is first in its chain or not.)

Where it’s used

Web caches, in browsers and in proxy servers, which keep recently fetched pages.

Operating systems, which keep recently used disk blocks in memory, usually with a cheaper approximation of LRU.

Database buffer pools, which keep recently used pages of a table in memory.

Memoisation with a size limit, where stored answers are kept for the most recent arguments only.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, struct entry 32, struct cache 72, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.