Unrolled Linked Lists

In our previous lessons , we examined the trade-offs between contiguous and linked data structures.

Arrays like std::vector provide fast traversal speeds because they feed the CPU's hardware prefetcher perfectly. However, maintaining contiguity makes structural changes expensive - inserting data into the middle of a massive vector forces the CPU to physically shift millions of bytes, destroying performance.

Conversely, lists like std::list allow for fast insertions and deletions because they only require swapping local pointers. But their node-based design increases their memory footprint and scatters the elements unpredictably in memory, reducing cache efficiency and confusing the prefetcher.

Here is the reality: we don't have to choose to optimize just for fast iteration or fast modification. We can build custom data structures that combine both approaches to find a balance that works best for the usage pattern that our problem requires, and the hardware we expect our program to run on.

We can design a structure that is mostly contiguous to keep iteration speed high, but uses some linking to prevent huge memory shifts when structural changes are needed.

In this lesson, we'll introduce the simplest example of this - the unrolled linked list.

To understand why an unrolled linked list is so effective, let's quickly review hardware's cache line.

When you ask the CPU to read a single 4-byte int from RAM, the CPU does not fetch 4 bytes. The memory controller physically fetches an entire line of memory and pulls it into the L1 cache.

In this lesson, we'll optimize our implementation to assume our program will usually be run on systems that have 64-byte cache lines. If we are using a standard singly-linked list, how much of that 64-byte fetch is actually useful data?

Our payload is 4 bytes. We also have an 8-byte Next pointer. Due to alignment padding, the node consumes 16 bytes. Furthermore, the global allocator injects a hidden 16-byte chunk header.

Out of the 64 bytes the CPU painstakingly hauled from main RAM, we are only using 4 bytes of payload. We waste over 90% of the memory bus bandwidth. When the CPU moves to the next node, it is forced to fetch an entirely different 64-byte cache line, suffering the massive RAM latency penalty all over again.

We can fix this by changing the metadata-to-payload ratio. Instead of wrapping a single int inside a node, what if we wrap an array of integers inside the node?

An unrolled linked list replaces single-element nodes with "fat nodes". Each node contains a small, fixed-size contiguous array of elements, alongside a counter to track how many slots are currently in use.

Just how fat these nodes are is something we would tune for our specific use case. If each node is relatively small, our container will need more of them to store all our data. This makes our structure look more like a linked list, inheriting those performance characteristics. If we have larger nodes, our data is more contiguous, pushing the performance characteristics towards that of an array.

Let's assume we want our container to store 4-byte int values, and we want our nodes to perfectly fill a 64-byte cache line. We'll use a 4-byte Count variable to track how many elements are in our node, and we'll need a pointer (8-bytes) for the Next node.

Combined, that consumes 12 bytes of overhead, leaving us with 52 bytes for our payload. This means we can fit exactly 13 integers into the remaining space. Each of our nodes would look like this:

By unrolling the list, a single 64-byte RAM fetch now gives the CPU 13 useful elements to process. We just reduced our cache misses by a factor of 13.

Let's implement this. To keep the code generic, we will use template parameters for the payload type and the node size. T will be the type of object our list will store, and NodeCapacity will be how many Ts each node can store:

1#pragma once
2#include <array>
3#include <cstddef>
4
5template <typename T, uint32_t NodeCapacity>
6class UnrolledList {
7private:
8  struct Node {
9    // A contiguous block of elements
10    std::array<T, NodeCapacity> Elements;
11
12    // How many elements are currently active in this chunk
13    uint32_t Count{0};
14
15    // Pointer to the next chunk
16    Node* Next{nullptr};
17  };
18
19  Node* Head{nullptr};
20  size_t TotalElements{0};
21
22public:
23  UnrolledList() {
24    Head = new Node();
25  }
26
27  ~UnrolledList() {
28    Node* Current = Head;
29    while (Current != nullptr) {
30      Node* ToDelete = Current;
31      Current = Current->Next;
32      delete ToDelete;
33    }
34  }
35};

Iterating over an unrolled linked list requires a nested loop. The outer loop walks the pointer chain from node to node. The inner loop walks the contiguous array within the current node.

Because the inner loop operates on a flat std::array, the hardware prefetcher engages instantly. The CPU glides over the elements without stalling.

1// ...
2
3template <typename T, size_t NodeCapacity>
4class UnrolledList {
5  // ...
6
7public:
8  // ...
9
10  template <typename Func>
11  void Traverse(Func Callback) const {
12    Node* Current = Head;
13
14    // The Outer Loop: A slow pointer chase
15    while (Current != nullptr) {
16
17      // The Inner Loop: Fast, contiguous execution
18      for (size_t i = 0; i < Current->Count; ++i) {
19        Callback(Current->Elements[i]);
20      }
21
22      // Jump to the next fat node
23      Current = Current->Next;
24    }
25  }
26};

If we set our NodeCapacity to be 100 elements, the CPU executes 100 lightning-fast instructions for every 1 slow pointer chase.

When we insert an element into the front or middle of a massive std::vector, the CPU is forced to physically shift every single element that comes after it. If there are a million elements, that is a million heavy memory copies moving through the memory bus.

With an unrolled list, we only need to shift the elements within that specific fat node. The rest of the nodes in the list remain completely untouched.

The canonical insertion pattern supported by lists is that elements are inserted either at the start or at an arbitrary position represented by an iterator. Standard library lists provide these patterns as the push_front() and insert() methods respectively.

Let's define a simple Iterator to represent a position within our UnrolledList, and implement our first pass of the Insert() method. For this step, we will assume our node has plenty of empty space:

1// ...
2
3template <typename T, size_t NodeCapacity>
4class UnrolledList {
5  // ...
6public:
7  // A simple struct to represent a position in the list
8  struct Iterator {
9    Node* TargetNode;
10    size_t LocalIndex;
11  };
12
13  void Insert(Iterator Pos, const T& Value) {
14    Node* Target = Pos.TargetNode;
15
16    if (Target->Count == NodeCapacity) {
17      // Node is full - cannot insert
18      // We'll add support for this in the next section
19      return;
20    }
21
22    // Shift elements to the right to make a gap
23    for (size_t i = Target->Count; i > Pos.LocalIndex; --i) {
24      Target->Elements[i] = Target->Elements[i - 1];
25    }
26
27    // Drop the new value into the gap
28    Target->Elements[Pos.LocalIndex] = Value;
29
30    Target->Count++;
31    TotalElements++;
32  }
33  
34  // Helper to insert a new element at start of the list
35  void InsertFront(const T& Value) {
36    Insert({Head, 0}, Value);
37  }
38};

This mechanism also highlights a key difference between lists and unrolled lists. With a regular list, inserting an element does not invalidate the pointers to any other element, as those elements do not need to be moved.

However, with an unrolled list, other elements within the same chunk may move to make room for the new addition. Therefore, any pre-existing pointers, references, and iterators should be considered invalid after a call to Insert().

When a node hits maximum capacity, we cannot accept any more elements. We must perform a structural modification: the node split.

When a node fills up, we allocate a brand new node. We then take the back half of the elements from the full node and physically move them into the new node. Finally, we wire the new node into the linked list chain.

This ensures that both nodes are now at ~50% capacity, giving them plenty of breathing room for future insertions without triggering another immediate split.

Let's implement this splitting mechanism in code:

1// ...
2
3template <typename T, size_t NodeCapacity>
4class UnrolledList {
5  // ...
6
7public:
8  // ...
9  void Insert(Iterator Pos, const T& Value) {
10    Node* Target = Pos.TargetNode;
11
12    if (Target->Count == NodeCapacity) {
13      return; 
14      Node* NewNode = new Node(); 
15      size_t Half = NodeCapacity / 2; 
16
17      // Move the back half of the data to the new node
18      for (size_t i = 0; i < Half; ++i) { 
19        NewNode->Elements[i] = Target->Elements[Half + i]; 
20      } 
21
22      NewNode->Count = Half; 
23      Target->Count = NodeCapacity - Half; 
24
25      // Wire the new node into the chain
26      NewNode->Next = Target->Next; 
27      Target->Next = NewNode; 
28
29      // Adjust our target if the insertion point
30      // falls into the newly created right-hand node
31      if (Pos.LocalIndex >= Target->Count) { 
32        Target = NewNode; 
33        Pos.LocalIndex -= Target->Count; 
34      } 
35    }
36
37    for (size_t i = Target->Count; i > Pos.LocalIndex; --i) {
38      Target->Elements[i] = Target->Elements[i - 1];
39    }
40
41    Target->Elements[Pos.LocalIndex] = Value;
42    Target->Count++;
43    TotalElements++;
44  }
45};

This split operation introduces a sudden latency spike. We are executing a new allocation and copying memory.

However, because each node has NodeCapacity slots, we only suffer this split penalty once every NodeCapacity / 2 insertions. This is an amortized cost. By paying a slightly higher cost occasionally, we guarantee that the vast majority of our insertions execute via the ultra-fast L1 cache shift.

Additionally, if we combine this with some of the custom allocator techniques covered previously, such as storing our nodes in a pre-allocated object pool , we can avoid the performance cost of allocating new memory on the heap.

The canonical removal pattern that lists need to support is the removal of the first element, or the removal of an arbitrary element for which we acquired an iterator. For example, these are implemented as the pop_front() and erase() methods of the standard library lists.

Just like insertion, standard contiguous arrays suffer massively here. If we remove an element near the front of a std::vector, the CPU must move every subsequent element one position to the left to close the gap.

In our unrolled list, we only shift the elements located within the current fat node. The rest of the collection remains physically undisturbed.

Let's implement this in code:

1// ...
2
3template <typename T, size_t NodeCapacity>
4class UnrolledList {
5  // ...
6
7public:
8  // ...
9  void Remove(Iterator Pos) {
10    Node* Target = Pos.TargetNode;
11
12    // Shift local elements to the left to overwrite the victim
13    for (size_t i = Pos.LocalIndex; i < Target->Count - 1; ++i) {
14      Target->Elements[i] = Target->Elements[i + 1];
15    }
16
17    Target->Count--;
18    TotalElements--;
19  }
20  
21  // Simple helper to remove the first element in the list
22  void RemoveFront() {
23    Remove({Head, 0});
24  }
25};

Again, because removal from an unrolled list involves physical movement of other elements within the same chunk, any pre-existing pointers should be considered invalid after this action.

Removing Empty Nodes

After removing an element from a node, it is possible that the node is now empty. We can check for that and remove the entire node from the list to keep things compact and efficient:

1// ...
2
3template <typename T, size_t NodeCapacity>
4class UnrolledList {
5  // ...
6
7public:
8  // ...
9  void Remove(Iterator Pos) {
10    // ...
11
12    // If the node is completely empty, and it isn't the Head,
13    // we should unlink it and free the memory
14    if (Target->Count == 0 && Target != Head) {
15      // Because this is a singly-linked implementation, we must
16      // walk from the Head to find the previous node to unlink it
17      Node* Prev = Head;
18      while (Prev != nullptr && Prev->Next != Target) {
19        Prev = Prev->Next;
20      }
21
22      if (Prev != nullptr) {
23        Prev->Next = Target->Next;
24        delete Target;
25      }
26    }
27  }
28  // ...
29};

Advanced: Merging Sparse Nodes

In our implementation above, we only delete a node when its Count reaches 0. While this works, it introduces a subtle fragmentation risk. We could end up with hundreds of fat nodes that each contain only 1 or 2 active elements.

If this happens, the performance of the unrolled list degrades back into a standard std::list but with a much larger memory footprint. The CPU is forced to chase pointers constantly because the contiguous arrays are practically empty.

In a more robust implementation, we could implement a merge mechanic. During the Remove() function, if a node's Count drops below a certain threshold (e.g., 25% capacity), the structure checks the neighboring node. If the combined elements of both nodes can fit into a single node, the data is merged, and one node is deleted.

This guarantees that the structural density of the arrays remains high, keeping our cache lines populated with useful data.

The goal of the unrolled linked list is to create a middle ground between the traversal speed of contiguous arrays and the insertion flexibility of linked lists. That is, our container should:

• Iterate through the collection faster than a std::list
• Insert items in arbitrary positions faster than a std::vector

Let's check if we were successful. We will first simulate inserting 100,000 elements right into the front of a collection:

1#include <benchmark/benchmark.h>
2#include <vector>
3#include <list>
4#include <dsa/UnrolledList.h>
5
6static void BM_VectorFrontInsert(benchmark::State& state) {
7  for (auto _ : state) {
8    state.PauseTiming();
9    std::vector<int> v;
10    state.ResumeTiming();
11    for (int i = 0; i < 100'000; ++i) {
12      v.insert(v.begin(), 42);
13    }
14  }
15}
16
17static void BM_ListFrontInsert(benchmark::State& state) {
18  for (auto _ : state) {
19    state.PauseTiming();
20    std::list<int> l;
21    state.ResumeTiming();
22    for (int i = 0; i < 100'000; ++i) {
23      l.insert(l.begin(), 42);
24    }
25  }
26}
27
28static void BM_UnrolledFrontInsert(benchmark::State& state) {
29  for (auto _ : state) {
30    state.PauseTiming();
31    UnrolledList<int, 64> ul;
32    state.ResumeTiming();
33    for (int i = 0; i < 100'000; ++i) {
34      ul.InsertFront(42);
35    }
36  }
37}
38
39#define BENCHMARK_MS(func) \
40  BENCHMARK(func)->Unit(benchmark::kMillisecond)
41
42BENCHMARK_MS(BM_VectorFrontInsert);
43BENCHMARK_MS(BM_ListFrontInsert);
44BENCHMARK_MS(BM_UnrolledFrontInsert);

For std::vector, this will trigger massive hardware shifts. For std::list, it will trigger individual global heap allocations. For our UnrolledList, it will perform blazing-fast L1 cache shifts, occasionally splitting a node:

1---------------------------------
2Benchmark                    Time
3---------------------------------
4BM_VectorFrontInsert      9.38 ms
5BM_ListFrontInsert        1.72 ms
6BM_UnrolledFrontInsert   0.024 ms

Now, let's benchmark the traversal speeds. We'll give each container 1,000,000 elements, and then benchmark an algorithm that iterates through all of them:

1#include <benchmark/benchmark.h>
2#include <vector>
3#include <list>
4#include <dsa/UnrolledList.h>
5
6static void BM_ListTraversal(benchmark::State& state) {
7  std::list<int> l(1'000'000, 42);
8  for (auto _ : state) {
9    int sum = 0;
10    for (int val : l) sum += val;
11    benchmark::DoNotOptimize(sum);
12  }
13}
14
15static void BM_UnrolledTraversal(benchmark::State& state) {
16  UnrolledList<int, 64> ul;
17  for (int i = 0; i < 1'000'000; ++i) ul.InsertFront(42);
18  for (auto _ : state) {
19    int sum = 0;
20    ul.Traverse([&](int val) { sum += val; });
21    benchmark::DoNotOptimize(sum);
22  }
23}
24
25static void BM_VectorTraversal(benchmark::State& state) {
26  std::vector<int> v(1'000'000, 42);
27  for (auto _ : state) {
28    int sum = 0;
29    for (int val : v) sum += val;
30    benchmark::DoNotOptimize(sum);
31  }
32}
33
34#define BENCHMARK_MS(func) \
35  BENCHMARK(func)->Unit(benchmark::kMillisecond)
36
37BENCHMARK_MS(BM_ListTraversal);
38BENCHMARK_MS(BM_UnrolledTraversal);
39BENCHMARK_MS(BM_VectorTraversal);

1-------------------------------
2Benchmark                   CPU
3-------------------------------
4BM_ListTraversal        12.2 ms
5BM_UnrolledTraversal   0.600 ms
6BM_VectorTraversal     0.322 ms

As expected, our unrolled list crushes the pure pointer-chasing mechanics of std::list. Because we pack 64 elements contiguously before jumping to a new pointer, the CPU prefetcher is heavily engaged.

Arrays likestd::vector are the gold standard of traversal, but our UnrolledList is keeping up admirably in these tests.

Here is the complete implementation of our UnrolledList:

Our unrolled linked list solves the cache-line problem by grouping elements into contiguous blocks. However, it still suffers from one of the major drawbacks of standard linked lists: a lack of fast random access.

Finding the Nth element fundamentally still requires walking the Next pointer chain from the head node. It is faster than a linked list, as each pointer jump skips over Count elements rather than 1, but it is still an $O(N)$ process.

A chunked array (also called a segmented array) trades some of the insertion and deletion speed of an unrolled list to solve the random access problem. Whilst an unrolled list links nodes together with Next pointers, a chunked array uses a central "directory" to keep track of where all the nodes are:

Because every chunk is uniform in capacity, the container does not need to traverse a chain to find elements. It can use simple $O(1)$ math to locate any element by index instantly.

For example, if every chunk holds exactly 64 elements and we request a global index 200, the container knows immediately that the value lives in chunk 3 (200 / 64) at local index 8 (200 % 64). It reads the pointer from index 3 of the top-level directory, and jumps straight to the correct memory address almost as quickly as a std::vector.

This arithmetic only works across chunks that are fully populated, which imposes some structural limitations. Segmented arrays typically only permit gaps in their "first" and "last" chunks, ensuring all of the "middle" chunks remain fully allocated and compatible with the $O(1)$ pointer math.

This makes them ideal for double-ended queues such as std::deque, where insertion and removal of elements at the start or end (in the first and last chunks) are fast $O(1)$ operations, but anywhere else requires a slow $O(N)$ restructuring. If we can accept these limitations, chunked arrays strike a middle ground between the structural flexibility of an unrolled list and the fast $O(1)$ random access of an array.

In this lesson, we explored a highly practical architectural compromise.

1. We broke the false dichotomy between strict arrays and strict linked lists by designing a fat node that holds an internal array.
2. We tuned the capacity of our nodes to align with our use case or target hardware, such as the CPU's 64-byte cache line, ensuring that a single RAM fetch yields maximum payload processing.
3. We implemented the split mechanic, dynamically dividing full nodes to accommodate new insertions without triggering a global array reallocation.
4. We relied on the physical efficiency of the CPU's L1 cache and SIMD instructions to prove that shifting tiny amounts of memory locally is significantly faster than chasing pointers out to main RAM.

Our nodes so far have acted as wrappers around our data. UnrolledList::Node physically encloses the array of elements. But what if we don't want a wrapper at all? What if we want objects that exist independently but can still be logically linked together?

In the next lesson, we will look at the exact technique the Linux Kernel uses to manage its internal structures without making a single memory allocation: the intrusive linked list.