Unrolled Linked Lists and the Cost of a Cache Miss per Node

A linked list pays a full memory round trip per element. The successor address is stored in the element itself, so the processor cannot compute it until the element has arrived. Every node is therefore a serialised dependency in the traversal, and the time to walk n nodes is n times the latency of whatever level of the hierarchy holds them, not n times the bandwidth cost of the bytes.

Unrolling attacks this directly. Each node holds an array of k elements instead of one, so a traversal performs n/k pointer chases and reads the k payloads from a line or two that are already resident. The pointer cost per element drops by the factor k, and the cache-line waste of the plain node layout disappears.

The structure of an unrolled node

A node carries a count, a successor, and a fixed-capacity array. With a capacity of k, the storage per node is roughly k * sizeof(element) plus the count and pointer, and consecutive elements sit next to each other.

#define K 8

struct unode {
    int count;              /* 0 <= count <= K */
    struct unode *next;
    int elem[K];
};

With 4-byte integers and a 64-bit pointer, that struct is 16 bytes of header (count, four bytes of padding, and the pointer) plus 32 bytes of elements, 48 bytes total, and it fits inside a single 64-byte cache line. A traversal therefore reads eight useful integers per line touched, against four bytes of payload per 64-byte line for the plain node layout, where four 16-byte nodes share a line. The pointer chase count falls by 8.

Two invariants keep the structure well behaved. The first is the occupancy bound: every node except possibly the last holds at least ceil(K/2) elements, so the space overhead of partially filled nodes is bounded. The second is that the list is ordered, so an element’s position within its node matters for search.

Insertion and the split

Insertion into an unrolled list mirrors insertion into a B-tree leaf. Find the node whose element range covers the position, shift the tail of its array right by one, and write the new element. The shift is O(k) with a small constant, since k is chosen to fit a cache line and is typically between 4 and 16. If the node was already full, split it into two nodes of about k/2 and link the new one after.

#include <string.h>

/* Shift the tail right by one and store v at index i. Requires n->count < K. */
static void shift_insert(struct unode *n, int i, int v) {
    for (int j = n->count; j > i; j--) n->elem[j] = n->elem[j - 1];
    n->elem[i] = v;
    n->count++;
}

/* Insert v into n at index i, splitting if full. Returns new right sibling or NULL. */
static struct unode *insert_at(struct unode *n, int i, int v) {
    if (n->count < K) {
        shift_insert(n, i, v);
        return NULL;
    }
    struct unode *r = alloc_unode();
    int half = K / 2;
    r->count = K - half;
    memcpy(r->elem, n->elem + half, (K - half) * sizeof(int));
    n->count = half;
    if (i < half) shift_insert(n, i, v);        /* n now has room */
    else          shift_insert(r, i - half, v); /* r now has room */
    r->next = n->next;
    n->next = r;
    return r;
}

Both branches call shift_insert on a node whose count is below K, so neither can write past the array. alloc_unode returns a node with count zero and next null; the code sets both fields before the node is published by the final two assignments, so a reader that observes the new link also sees an initialised node.

The split is O(k) because it copies half an array. It happens once per k/2 insertions in the steady state, so the amortised cost per insertion is O(1) plus the O(k) search within the node. This is the same accounting argument as a dynamic array’s geometric growth, applied to a chain of fixed-capacity blocks.

Deletion has the mirror problem. Removing an element leaves the node under-filled, and if it drops below k/2 the neighbours should be merged or the elements redistributed. Merging two nodes of k/2 each yields one full node, which is exactly the inverse of the split. Implementations that skip the merge are still correct, but their space usage degrades toward one element per node after a long run of deletions, at which point the structure has become the plain linked list it was meant to replace.

Choosing k

The choice of k is a trade between three quantities: pointer overhead per element, shift cost per insertion, and lines touched per traversal.

k	Bytes per node (4-byte int)	Pointer overhead per element	Elements per 64-byte line
1	16	16 bytes	4 (four nodes)
4	32	4 bytes	8 (two nodes)
8	48	2 bytes	8
16	80	1 byte	~13 (spans two lines)
32	144	0.5 bytes	~14 (spans three lines)

The useful range ends where a node no longer fits in a small number of cache lines. At k = 8 with 4-byte elements the node is 48 bytes and sits in one line; at k = 16 it is 80 bytes and straddles two, which reintroduces a second line access per node without halving the chase count again. For the layout above, where the header is two words, the largest k that keeps the node inside one 64-byte line is 10 for 4-byte elements and 6 for 8-byte elements, because 64 - 16 = 48. A larger header, or an element size that does not divide the remainder, moves those limits down; sizes are chosen per layout rather than by a single formula.

The node above carries four bytes of header padding because the pointer needs 8-byte alignment. Placing the count after the pointer instead, or storing it as a separate word, changes the total and therefore the largest k that fits a line. Nothing in the structure depends on the order of the fields.

There is a second consideration that pushes k down: the shift cost on insertion is linear in k, and the memmove is not free even when it stays in L1. Workloads dominated by insertion at random positions favour smaller nodes; workloads dominated by traversal favour larger ones. A k between 4 and 8 is defensible for both, which keeps the choice conservative on both axes.

Search cost and the loss of binary search

An ordered unrolled list cannot binary search across nodes, because reaching the middle node requires a traversal. It can binary search within a node, since the array is contiguous and sorted. The resulting complexity for a lookup is O(n/k) node hops plus O(log k) comparisons inside the located node, which is asymptotically still O(n). Unrolling improves the constant by roughly k and no more.

That is the honest characterisation: unrolling is a constant-factor optimisation on a linear structure, and it does not change the complexity class. It is worth doing when the constant matters, which is most of the time in practice, and it is not worth doing when a balanced tree or a hash table would remove the linear term entirely. The value of the technique is that it keeps the splice and stable address properties of a linked structure while recovering most of the array’s locality.

Comparison with the alternatives

Three other layouts solve the same locality problem, and the differences are instructive.

A dynamic array has perfect locality and no pointer chase at all, but insertion in the middle is O(n) and every growth invalidates references. An unrolled list trades a small pointer overhead for O(k) middle insertion and stable element addresses.

A B-tree is the unrolled list plus a search index over the nodes. The index costs O(log n) comparisons and adds a level of indirection, but it turns lookup from O(n) into O(log n). When the workload is lookup-dominated rather than splice-dominated, the B-tree is strictly better, which is why databases use B-trees and not unrolled lists. The skip list in Skip Lists is the other way to add an index without moving elements: it keeps the chain and adds express pointers over it.

A rope is an unrolled structure specialised for byte strings, where the leaves are short strings and the internal nodes store lengths rather than keys. The same block-size reasoning applies, with the added twist that concatenation can share leaves rather than copy them.

The unrolled list remains the right choice when the operations are predominantly insert, remove, and sequential scan, and when the elements must not move. That combination appears in text editors’ piece tables, in log-structured buffers, and in caches that hold pointers to their entries.

Failure modes

The bugs in unrolled lists cluster around the count field and the split boundary.

Off-by-one in the split index. Splitting at K/2 when the insertion index equals K/2 decides which node receives the new element, and getting it wrong puts the element in a node whose range does not cover it. The resulting list is unsorted only in a narrow band around the split, which makes the bug invisible to a test that inserts in ascending order.

Count exceeding capacity. The insert path must check the full condition before writing, not after. A node with count == K has no slot at index K, and writing there corrupts the next pointer that follows the array in memory.

Merge that breaks the occupancy invariant. Merging two nodes when their combined count exceeds K is not possible; the correct operation is to redistribute, moving elements from the fuller neighbour. Code that merges unconditionally overflows the array.

Stale count after bulk copy. A memcpy of half an array must be paired with updating both counts. Forgetting one leaves a node claiming elements it does not hold, and the traversal reads uninitialised slots.

Iterator invalidation across a split. A cursor that holds a node pointer and an index becomes wrong when the node splits, because the element it names may now live in the new right sibling. Cursors must either be invalidated explicitly or hold a node pointer plus a key rather than a position.

The last is the subtlest, because the cursor is valid in the sense that it still points into the structure; it names a different element than it did before the split.

A note on allocation

Unrolled nodes are larger than plain nodes, so an allocator that serves small objects from size classes will place them in a different class. A 32-byte payload with a 16-byte header usually lands in a 64-byte class, which means roughly half of each allocation is unused, comparable to the plain node’s waste. The locality gain comes from the elements sharing a line with the link, not from the allocator being kinder. Measured as payload bytes per allocation byte, the two layouts come out close to each other; the difference is in lines touched per element visited.

For a structure that must guarantee a fixed memory budget, an unrolled list can be allocated as one contiguous slab of nodes with links as indices rather than pointers. That removes the per-node allocation entirely and makes the whole structure relocatable, at the cost of a maximum capacity fixed at creation. This is the layout used by on-disk and shared-memory variants, and it is the point where the unrolled list converges with Index-Based Linked Lists for Relocatable Storage.