Linked lists: cache misses and benchmarks

Linked Lists and Cache Misses: Why They Fall Short Against Arrays in Real-World Tasks

Linked lists seem ideal for dynamic operations: O(1) insertions and deletions, no reallocations. But in practice, they often lose to arrays due to cache misses. Each jump via the next pointer burdens the memory subsystem, turning theoretical advantages into bottlenecks.

Testing on 100,000 elements shows the gap:

| Operation | Array | Linked List | Lag |

|-----------------------|---------|----------------|--------|

| Sequential traversal | 70 μs | 179 μs | ×2.5 |

| Random access | 95 μs | 2847 μs | ×30 |

| Appends | 42 μs | 1234 μs | ×29 |

Even insertions, where lists should dominate, end up slower due to reallocations and cache misses.

Cache Miss Mechanism

CPU cache lines fetch 64 bytes at a time. In an array, elements are laid out sequentially—one miss gives access to 16 ints. In a linked list, nodes are scattered across the heap:

// Typical node
struct node {
    int value;     // 4 bytes
    node *next;    // 8 bytes
}; // 16 bytes with padding

Traversing the list generates a miss for each node (~100 cycles delay). For 100,000 nodes—that's 10 million cycles vs. 625 thousand for the array. The array uses 400 KB, the list—1.6 MB (4× overhead).

Memory Allocation Costs

Creating the list requires 100,000 malloc() calls:

for (int i = 0; i < 100000; i++) {
    node *n = malloc(sizeof(node)); // Heap search, metadata, fragmentation
    n->value = i;
    n->next = head;
    head = n;
}

Array—one call. Benchmark difference: 42 μs vs. 1234 μs.

Rare Scenarios Where Lists Are Justified

Linked lists make sense in niche cases:

• Intrusive lists in kernels (Linux list_head): nodes embedded in structures, improved locality.
• Lock-free structures: atomic CAS on pointers simpler than on arrays.
• Small static datasets with rare insertions.

Example of Treiber's lock-free stack:

typedef struct node {
    int value;
    struct node *next;
} node_t;

void push(node_t **head, node_t *node) {
    do {
        node->next = *head;
    } while (!atomic_compare_exchange(head, &node->next, node));
}

Optimizations for When You Have To Use Them

Object Pools

Pre-allocate an array of nodes:

#define POOL_SIZE 10000
node_t pool[POOL_SIZE];
int idx = 0;

node_t *alloc() {
    return idx < POOL_SIZE ? &pool[idx++] : NULL;
}

Speed: 287 μs (×4.3 vs. malloc, but ×6.8 vs. array).

Unrolled Lists

Store multiple elements per node:

#define N 16
typedef struct {
    int values[N];
    int count;
    struct node *next;
} unrolled_t;

Traversal: 45 μs (better than standard list, comparable to array for sequential access).

XOR-Linked Lists

Save memory via XOR of prev^next:

typedef struct {
    int value;
    node *xor_ptr; // prev ^ next
} xor_node;

// Traversal requires tracking prev
node *next = (uintptr_t)prev ^ (uintptr_t)curr->xor_ptr;

Downsides: debugging complexity, no bidirectional traversal. Not recommended.

RTOS Case: Why Lists Work There

In FreeRTOS, the scheduler uses an array of lists by priority (32 levels):

list_head ready_tasks[MAX_PRIORITIES];

Success due to:

• Small lists (1–5 tasks).
• Nodes embedded in task_struct.
• O(1) operations by priority.

Benchmark on Cortex-M4: insertion 0.8 μs, deletion 0.6 μs.

Key Takeaways

• Cache dominates: pointer misses kill performance even in O(1) operations.
• Memory overhead: 4× growth from pointers + fragmentation.
• Dynamic arrays preferred: amortized O(1) insertions without cache penalties.
• Optimizations help somewhat: pools and unrolled lists close the gap but don't surpass.
• RTOS exception: embedded nodes + small size justify the choice.

— Editorial Team