Unrolled & Intrusive Lists

July 2026 · 22 min read

The first post in this series measured the two real costs of a linked list: it chases pointers so it thrashes the cache, and it allocates a node per element so it hammers the allocator. This post is the pair of fixes that production code actually uses. Unrolled lists attack the cache cost by packing many elements into each node. Intrusive lists attack the allocation cost by putting the links inside the element itself. Neither is exotic — between them they describe std::deque, the Linux kernel, Boost, and half the game engines you have played.

Two Costs, Two Fixes

Recall the numbers. A Node{ int; Node*; } is 16 bytes of which 8 are payload; the allocator adds a header and rounds up, so a 4-byte integer can occupy 32 bytes of resident memory. And every hop to node->next is a dependent load the prefetcher cannot anticipate, so a traversal stalls once per element. Unrolled lists shrink the pointer-per-element ratio and let the CPU read many values per cache miss. Intrusive lists remove the per-element allocation entirely. They are orthogonal — you can have both — but they solve different problems, so we take them in turn.

Unrolled Lists: Pack the Node

An unrolled linked list stores, in each node, a small array of up to k elements together with a count and a single next pointer. Twelve integers now share one next instead of demanding twelve, so the pointer overhead falls by a factor of k. More importantly, those twelve integers are contiguous, so one cache miss brings in the whole node and the next eleven reads are L1 hits. You have reintroduced the array's sequential locality inside each node while keeping the list's cheap splicing between nodes.

The magic number k is chosen to make a node fill one or two cache lines. On a 64-byte line with 4-byte elements, a node's header is a next pointer (8 bytes) plus a count (8 after alignment) = 16 bytes, leaving 48 bytes — exactly twelve 4-byte integers. So k = 12 lands one node on one cache line; k = 13 or 14 spills into a second line, which is often still a good trade. Pick k from the element size and the line size, not by feel.

One Miss, Many Elements

The animation walks the same twelve elements through a plain list (one value per node, one cache line each) and an unrolled list (four values per node). Count the cache lines each structure touches to read all twelve.

Twelve reads cost the plain list twelve misses and the unrolled list three. With a realistic k = 12 the ratio is 12:1 — the traversal touches memory a twelfth as often, which is the whole point.

Splitting and Merging Nodes

The node is an array with a count. Insertion walks whole nodes at a time — skipping count elements per hop instead of one — then inserts within a node by shifting. The only complication is a full node: split it in half, creating room, then insert into whichever half now owns the position.

#include <array>
#include <cstddef>

template <class T, std::size_t K = 12>
class UnrolledList {
    struct Node {
        Node*            next = nullptr;
        std::size_t      count = 0;      // slots [0, count) are live
        std::array<T, K> data{};
    };
    Node* head_ = nullptr;

public:
    void insert(std::size_t pos, const T& value) {
        if (!head_) head_ = new Node();
        Node* n = head_;
        while (n->next && pos > n->count) {   // stride over whole nodes
            pos -= n->count;
            n = n->next;
        }
        if (pos > n->count) pos = n->count;    // clamp to this node

        if (n->count == K) {                    // full: split before inserting
            Node* right = new Node();
            std::size_t half = K / 2;
            right->count = K - half;
            for (std::size_t i = 0; i < right->count; ++i)
                right->data[i] = n->data[half + i];
            n->count = half;
            right->next = n->next;
            n->next = right;
            if (pos > half) { n = right; pos -= half; }   // pick the correct half
        }
        for (std::size_t i = n->count; i > pos; --i)      // shift right within node
            n->data[i] = n->data[i - 1];
        n->data[pos] = value;
        ++n->count;
    }

Erase is the mirror image. Remove the element by shifting left over the hole; then, if the node has fallen below half-full, restore balance by either merging with the next node (when the two together fit in one node) or borrowing a single element from it (when they do not). Keeping every node at least half-full bounds the wasted space and keeps the effective k high.

A worked split makes the insert path concrete. Take K = 6 and a full node, and insert 25 at position 2:

full node: [10 20 30 40 50 60]   count = 6 = K,  insert 25 at pos 2
  split at half = 3:
    left  = [10 20 30]           count = 3
    right = [40 50 60]           count = 3      (right->next = old next; left->next = right)
  pos 2 <= half 3  ->  the insert stays in the LEFT node
  shift right within left, place 25 at pos 2:
    left  = [10 20 25 30]        count = 4
  result: [10 20 25 30] -> [40 50 60] -> ...   (both nodes now comfortably half-full)

    void erase(std::size_t pos) {
        Node* n = head_;
        while (n && pos >= n->count) { pos -= n->count; n = n->next; }
        if (!n) return;
        for (std::size_t i = pos; i + 1 < n->count; ++i)   // close the gap
            n->data[i] = n->data[i + 1];
        --n->count;

        if (n->count >= K / 2 || !n->next) return;          // still balanced, or last node
        Node* r = n->next;
        if (n->count + r->count <= K) {                     // merge r into n
            for (std::size_t i = 0; i < r->count; ++i)
                n->data[n->count + i] = r->data[i];
            n->count += r->count;
            n->next = r->next;
            delete r;
        } else {                                           // borrow one from r
            n->data[n->count++] = r->data[0];
            for (std::size_t i = 0; i + 1 < r->count; ++i)
                r->data[i] = r->data[i + 1];
            --r->count;
        }
    }

    template <class F>
    void for_each(F f) const {
        for (Node* n = head_; n; n = n->next)
            for (std::size_t i = 0; i < n->count; ++i)
                f(n->data[i]);                              // k contiguous reads per node
    }
};

What Unrolling Buys

The complexity class does not change — search is still O(n) — but the constant that dominates real benchmarks, the cache-miss count, drops by roughly k. That is why this shape recurs everywhere: std::deque is essentially an unrolled list of fixed-size blocks with an index of block pointers; ropes and gap buffers unroll text so editors can insert into a megabyte file without shifting it all; and a B-tree is the same idea lifted from a list to a tree — fat nodes holding many keys so each cache miss makes maximal progress. Unrolling is not a niche trick; it is the standard answer to "linked structures are cache-hostile".

Intrusive Lists: Move the Links Inside

The second cost is allocation, and the intrusive list removes it completely. Instead of a separate node that points at your object, the next and prev pointers live inside the object. Threading an element onto a list is then pure pointer assignment — no new, no node, no second cache line to reach the payload — and one object can carry several sets of links and thus belong to several lists at once.

This inverts ownership. A std::list<T> owns its elements: it allocates a node, copies or moves your T into it, and frees it later. An intrusive list owns nothing; it is merely a chain running through objects whose lifetimes you manage. That single change is why the Linux kernel, which cannot afford an allocation on every enqueue and routinely puts one task on a dozen lists, uses intrusive lists for essentially every list it has.

The Linux list_head Pattern

The kernel's design is worth learning exactly, because it is the canonical intrusive list. The links are a tiny standalone struct that you embed inside whatever you want to enlist:

struct list_head { struct list_head *next, *prev; };

struct task {
    int pid;
    struct list_head run_queue;   // embed the links; the list threads through here
};

The list is circular with a sentinel: a standalone list_head whose next and prev both point to itself when the list is empty. Circularity means insertion and deletion never special-case the ends — there is no null to check — and the sentinel means the list itself is not one of your objects, so an empty list is still a valid, dereferenceable ring.

static inline void __list_add(struct list_head *nw,
                              struct list_head *prev,
                              struct list_head *next) {
    next->prev = nw;
    nw->next   = next;
    nw->prev   = prev;
    prev->next = nw;
}
static inline void list_add(struct list_head *nw, struct list_head *head) {
    __list_add(nw, head, head->next);      // splice just after the sentinel
}
static inline void list_del(struct list_head *entry) {
    entry->prev->next = entry->next;        // unlink: neighbours skip over entry
    entry->next->prev = entry->prev;
    entry->next = entry->prev = NULL;
}

But there is a puzzle. These routines manipulate list_head pointers, yet what you actually want is the enclosing struct task. Given a pointer to the embedded run_queue member, how do you recover the object that contains it? That is container_of, the macro at the heart of the whole pattern:

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

Read it right to left. offsetof(type, member) is the compile-time byte distance from the start of type to member. The pointer ptr aims at the member, sitting exactly that many bytes into the object. Cast ptr to char* so arithmetic counts in bytes, subtract the offset to land on the first byte of the enclosing struct, and cast that address to type*. You have walked backwards from a member to its owner using nothing but a compile-time constant — zero runtime cost, no stored back-pointer.

In C++ the same recovery is type-safe: the return type is a real Task*, so no void* escapes to the call site.

#include <cstddef>

struct ListHook { ListHook *next, *prev; };
struct Task { int pid; ListHook hook; };   // standard-layout: offsetof is well defined

inline Task* task_of(ListHook* h) {
    return reinterpret_cast<Task*>(
        reinterpret_cast<char*>(h) - offsetof(Task, hook));
}

Iteration then combines the ring walk with container_of. The kernel wraps it in a macro so call sites read like a normal for-each:

#define list_for_each_entry(pos, head, member)                     \
    for (pos = container_of((head)->next, typeof(*pos), member);    \
         &pos->member != (head);                                    \
         pos = container_of(pos->member.next, typeof(*pos), member))

Each step advances the embedded member.next around the ring and immediately converts it back to the owning object, stopping when the walk returns to the sentinel head. You iterate objects, not links, and never see the plumbing.

Boost.Intrusive: the Library Version

Writing container_of by hand is fine in C; in C++ you reach for Boost.Intrusive, which generates it for you from a hook you add to your type. A base hook is inherited; a member hook is declared as a field:

#include <boost/intrusive/list.hpp>
using namespace boost::intrusive;

struct Session : public list_base_hook<> {   // base hook: links via inheritance
    int id;
};
using Sessions = list<Session>;               // no allocation on push_back

struct Job {
    int priority;
    list_member_hook<> hook;                   // member hook: links as a field
};
using Jobs = list<Job, member_hook<Job, list_member_hook<>, &Job::hook>>;

Because the hook is a distinct type per list, one object can hold several hooks and live on several lists simultaneously — a session on both an LRU list and a hash-bucket list, say — with no copies. Boost also offers auto_unlink mode (list_base_hook<link_mode<auto_unlink>>): the element unlinks itself from whatever list holds it in its own destructor, so destroying an object can never leave a dangling link. The cost is that such lists cannot cache their size in O(1).

The one rule you must internalise is ownership. The container does not own the elements; you do. The elements must outlive the list, and — unless you are in auto_unlink mode — destroying or freeing an element while it is still linked corrupts the list, because its neighbours still point into freed memory. Intrusive lists hand you performance in exchange for managing lifetimes yourself.

std::list vs. Intrusive List

Read top-to-bottom, the intrusive list wins every performance and flexibility row and pays for it in the last one: you take over lifetime management. That is the right trade in a kernel, an allocator, a scheduler, or a game engine's entity lists — anywhere allocation is the bottleneck and objects already have owners. For ordinary application code where convenience matters more than the last allocation, std::list's owning model is the safer default.

Check Yourself

Six situations spanning both structures. Pick the statement that is actually true.

Practice

• Implement the unrolled list above, then sum ten million elements from it and from a std::list. locality time both and confirm the k-fold cache-miss reduction.
• Derive the ideal k for T = double on a 64-byte line, then for a 32-byte cache line. tuning account for the 16-byte header each time.
• Write container_of from scratch and use it to recover a struct task from a pointer to its embedded list_head. offsetof print the offset and verify the pointer arithmetic by hand.
• Put one object on two intrusive lists at once using two hooks, then remove it from one without touching the other. membership confirm no copies and no allocations occurred.
• Take a Boost.Intrusive list without auto_unlink and destroy a still-linked element. ownership observe the corruption, then fix it with auto_unlink.
• LeetCode 146 — LRU Cache intrusive reimplement it with an intrusive doubly linked list so moving a node to the front costs zero allocations.