Intrusive Linked Lists

In our exploration of linked data structures, we have treated the "node" as an unavoidable necessity. Whether we allocate it on the global heap using std::list(), pack it into a custom std::vector() using indices, or clump elements together in an unrolled list, the fundamental architecture has remained the same.

The data structure owns the data. It wraps our payload inside a structural envelope.

But what if we don't want the data structure to own our objects? In highly optimized environments, objects are usually pre-allocated in massive slabs of memory, like the object pools we built earlier.

When an object already exists in physical memory, and we want it to be included in a collection, wrapping it inside a separate logical "node" introduces a severe performance bottleneck. In this lesson, we will explore strategies that eliminate the wrapper.

Let's assume we have a Player struct that is heavily managed by a custom memory allocator. We want to keep track of all active players by putting them into a linked list.

If we use a standard non-intrusive container like std::list<Player>, the list will allocate a brand new node on the heap and copy our player data into it:

1struct Player {
2  int ID;
3  float Health;
4};
5
6// ...
7
8Player p{1, 100.0f};
9
10// The list allocates a new node and copies 'p' into it
11ActivePlayers.push_back(p);

We now have two copies of the player, which is rarely what we want. To solve this, developers often instinctively switch to a list of pointers: std::list<Player*>. This allows the list to reference our original object, without copying it:

1Player* p = PlayerPool.Spawn(1, 100.0f);
2
3// The list allocates a new node, and stores the pointer
4ActivePointerPlayers.push_back(p);

This is a slightly better design, but it creates a disaster for the CPU's cache prefetcher: double pointer chasing. When we iterate through a std::list<Player*>, the CPU must now perform two distinct trips to main RAM for every single element:

1. Follow the Next pointer to find the physical memory address of the list node. (Cache Miss).
2. Read the Player* payload from that node, and follow that pointer to find the physical memory address of the actual player data. (Cache Miss).

We are paying the memory latency penalty twice. Furthermore, we have added complexity - we now need to manage and optimize the memory allocation of both the Player objects and the Node objects that link to them.

If wrapping the data inside the node is slow, we can simply invert the relationship: we can embed the node inside the data. An intrusive data structure dictates that the payload itself must provide the structural links. Instead of the list providing the Prev and Next pointers, our Player struct will physically hold them, just like it would hold any other variable.

First, we'll define a completely generic ListHook. This is nothing but a pair of links - it contains no payload data whatsoever:

1#pragma once
2
3struct ListHook {
4  ListHook* Prev{nullptr};
5  ListHook* Next{nullptr};
6};

To keep things simple and focused on the new topics, we're representing our links as full 64-bit pointers to the global heap in this lesson. However, intrusive lists can be combined with previous techniques for even more optimization, such as storing the players in an object pool and using index-based links rather than pointers.

Once we have our ListHook available, we intrude upon our Player struct. We add a ListHook directly into the physical memory layout of our entity:

1#include <dsa/IntrusiveList.h>
2
3struct Player {
4  int ID;
5  float Health;
6
7  // We embed the linkage directly into the data
8  ListHook Hook; 
9};

By doing this, we have permanently fused the structural metadata with the payload. When the CPU fetches the ListHook to find the next element in the chain, the Player data (ID and Health) is sitting in the same 64-byte physical cache line.

Double indirection is eliminated - when we have the hook, we have the data.

We now face a complex problem. We want to build a generic IntrusiveList container that works for any data type. Our linked list logic is only going to wire ListHook pointers together - it won't know what a Player is.

When we iterate through our list, we will have a pointer to a ListHook. But the application developer doesn't care about the hook; they want a pointer to their Player object. How do we convert a ListHook* back into the Player* that holds that hook?

We cannot use a standard static_cast or dynamic_cast, because Player does not inherit from ListHook. ListHook is just a raw variable sitting somewhere inside the physical memory of Player.

Fortunately, when the compiler builds our Player struct, it assigns a strict, unchangeable physical byte offset to every member.

1struct Player {
2  int ID;          // Offset 0 (Size: 4 bytes)
3  float Health;    // Offset 4 (Size: 4 bytes)
4  ListHook Hook;   // Offset 8 (Size: 16 bytes)
5};

If we have a pointer to Hook, and we know that Hook always sits exactly 8 bytes away from the start of the Player struct, we can simply subtract 8 bytes from the hook's memory address. The resulting memory address is guaranteed to be the start of the Player object that owns that Hook.

Fortunately, we don't need to calculate this offset for every type we want a linked list to intrude upon. The C standard library provides the helpful offsetof(type, member) macro for this. We provide the name of the type (Player) and the name of the member within that type (Hook) and it calculates the byte offset for us at compile time.

We'll use offsetof soon but, for now, let's write a generic helper function that takes a ListHook pointer and the calculated offset to return a pointer to the object that holds that ListHook.

Our offset is measured in bytes, so we want our pointer arithmetic to also use bytes. To do this, we'll reinterpret the hook pointer to a raw std::byte pointer, subtract the provided offset, and cast the resulting physical address into our desired T*:

1#pragma once
2#include <cstddef>  // for std::byte, size_t, offsetof
3
4struct ListHook {
5  ListHook* Prev{nullptr};
6  ListHook* Next{nullptr};
7};
8
9// Convert a Hook pointer back into the Parent object pointer
10template <typename T>
11T* GetParent(ListHook* Hook, size_t Offset) {
12  if (!Hook) return nullptr;
13
14  // Treat the memory address as raw bytes
15  std::byte* RawAddress = reinterpret_cast<std::byte*>(Hook);
16
17  // Slide the pointer backward by the calculated offset
18  std::byte* ParentAddress = RawAddress - Offset; 
19
20  // Cast the raw memory back into the typed object
21  return reinterpret_cast<T*>(ParentAddress); 
22}

We can now build our IntrusiveList container. Our list needs to know two things at compile time: the type of object it is storing (T), and the physical offset of the ListHook within that type.

Requiring consumers to provide low-level details about their memory layout isn't ideal. We'd like to calculate this ourselves, but determining where the ListHook is within their type, especially when we don't even know what they've called it, is quite difficult. Additionally, in the next section, we'll allow objects to be in multiple lists, meaning there can be multiple ListHook members within T.

Future C++ capabilities, particularly static reflection, will allow us to improve this API. But, for now, the simplest implementation is to ask consumers to use the offsetof macro themselves and provide the result to HookOffset:

1// ...
2
3// T is the payload type
4// HookOffset is the physical byte offset of the ListHook within T
5template <typename T, size_t HookOffset>
6class IntrusiveList {
7private:
8  ListHook* Head{nullptr};
9
10  // Internal helper to extract the hook from a given object
11  ListHook* ExtractHook(T* Item) const {
12    std::byte* RawAddress = reinterpret_cast<std::byte*>(Item);
13    return reinterpret_cast<ListHook*>(RawAddress + HookOffset);
14  }
15
16public:
17  IntrusiveList() = default;
18};

1// Example Usage
2#include <dsa/IntrusiveList.h>
3
4struct Player {
5  int ID;
6  float Health;
7  ListHook Hook;
8};
9
10int main() {
11  using PlayerList = IntrusiveList<Player, offsetof(Player, Hook)>;
12  PlayerList Players;
13}

Implementing Insertions

Let's implement PushFront(). In a standard list, this method allocates a new node. In our intrusive list, the application developer already created the object. They simply hand us a pointer to it.

Our list calculates where the hook lives inside that object, and wires the Prev and Next pointers to attach it to the front of the chain:

1// ...
2
3template <typename T, size_t HookOffset>
4class IntrusiveList {
5  // ...
6
7public:
8  // ...
9
10  void PushFront(T* Item) {
11    if (!Item) return;
12
13    // Find the hook inside the provided item
14    ListHook* ItemHook = ExtractHook(Item);
15
16    // Wire the new hook to point to the current Head
17    ItemHook->Next = Head;
18    ItemHook->Prev = nullptr;
19
20    // If the list wasn't empty, wire the old Head backward
21    if (Head) {
22      Head->Prev = ItemHook;
23    }
24
25    // Update the Head pointer
26    Head = ItemHook;
27  }
28};

We performed four simple pointer assignments. There is no call to new. There is no hidden chunk header metadata being created. There is no search through an implicit free list. Because no memory is allocated, this function can never fail or throw an exception. It executes deterministically in roughly 2 CPU cycles.

Deleting Elements

To remove an element, we disconnect the hook from the chain, bridging the gap between its Prev and Next neighbors:

1// ...
2
3template <typename T, size_t HookOffset>
4class IntrusiveList {
5  // ...
6
7public:
8  // ...
9
10  void Remove(T* Item) {
11    if (!Item) return;
12
13    ListHook* ItemHook = ExtractHook(Item);
14
15    // Disconnect the Previous node
16    if (ItemHook->Prev) {
17      ItemHook->Prev->Next = ItemHook->Next;
18    } else {
19      // If there is no Prev, we were the Head. Update Head.
20      Head = ItemHook->Next;
21    }
22
23    // Disconnect the Next node
24    if (ItemHook->Next) {
25      ItemHook->Next->Prev = ItemHook->Prev; 
26    }
27
28    // Clear our own links for safety
29    ItemHook->Prev = nullptr;
30    ItemHook->Next = nullptr;
31  }
32};

Notice what Remove() does not do. It does not call delete.

An intrusive list does not own the memory. When we remove a Player from the list, we are simply untying the knot that held it in the chain. The physical Player object still exists wherever the application developer originally placed it (e.g., in a pre-allocated object pool). The responsibility for destroying the payload remains entirely with the user.

Traversal

To traverse the list, we walk the chain of ListHook pointers. For each hook, we use our GetParent() offset math to reconstruct the original T* object pointer, and pass it to the user's callback. Because the hook and the payload share the same memory address, reading Item->ID does not trigger a secondary cache miss:

1// ...
2
3template <typename T, size_t HookOffset>
4class IntrusiveList {
5  // ...
6
7public:
8  // ...
9
10  template <typename Func>
11  void Traverse(Func Callback) const {
12    ListHook* Current = Head;
13
14    while (Current != nullptr) {
15      // Recover the typed object pointer from the raw hook
16      T* Item = GetParent<T>(Current, HookOffset); 
17
18      Callback(Item);
19
20      Current = Current->Next;
21    }
22  }
23};

We have successfully eliminated the wrapper node. But intrusive structures have another interesting architectural advantage.

Imagine we are building a game engine. We have an Entity struct. Every frame, the physics engine needs to iterate over all active physics bodies. Every frame, the renderer needs to iterate over all visible meshes.

An Entity needs to exist in both the PhysicsList and the RenderList at the same time.

If we use std::list, we must maintain two completely separate collections of Entity* pointers. That means two allocations per entity, two separate chains of wrapper nodes, and twice the amount of pointer-chasing latency.

With an intrusive design, we simply embed two ListHook variables directly into the physical memory layout of the Entity:

1struct Entity {
2  int ID;
3
4  // Data for the Physics system
5  float Velocity;
6  ListHook PhysicsHook; 
7
8  // Data for the Render system
9  bool IsVisible;
10  ListHook RenderHook; 
11};

We now have two distinct structural connectors living inside the same block of memory. We can thread this single physical object through two completely independent logical lists.

Let's see this in action. We use offsetof to configure two distinct IntrusiveList types. One list is threaded through the PhysicsHooks of our objects, and the other is threaded through the RenderHooks:

1#include <iostream>
2#include <dsa/IntrusiveList.h>
3
4struct Entity {
5  int ID;
6  ListHook PhysicsHook;
7  ListHook RenderHook;
8};
9
10int main() {
11  // Configure the Physics list using the PhysicsHook offset
12  using PhysicsList = IntrusiveList<
13    Entity,
14    offsetof(Entity, PhysicsHook) 
15  >;
16
17  // Configure the Render list using the RenderHook offset
18  using RenderList = IntrusiveList<
19    Entity,
20    offsetof(Entity, RenderHook) 
21  >;
22
23  PhysicsList ActivePhysics;
24  RenderList ActiveRender;
25
26  // Assume these entities live in a pre-allocated array or pool
27  Entity E1{1};
28  Entity E2{2};
29
30  // E1 participates in both systems
31  ActivePhysics.PushFront(&E1);
32  ActiveRender.PushFront(&E1);
33
34  // E2 only participates in physics (e.g., an invisible wall)
35  ActivePhysics.PushFront(&E2);
36
37  std::cout << "Physics Entities: ";
38  ActivePhysics.Traverse([](Entity* e) {
39    std::cout << e->ID << " ";
40  });
41
42  std::cout << "\nRender Entities: ";
43  ActiveRender.Traverse([](Entity* e) {
44    std::cout << e->ID << " ";
45  });
46
47  return 0;
48}

1Physics Entities: 2 1
2Render Entities: 1

By adding a mere 16 bytes of data (a second hook) to our object, we can participate in an infinite number of highly optimized systems without making a single allocation. The physical Entity never moves, and we never chase a secondary pointer to find the payload.

The Lifecycle Trade-off

This power comes with a strict responsibility. Because an intrusive list does not own the objects it links together, the application architecture must guarantee that an object is removed from all intrusive lists before its memory is destroyed or recycled.

If E1 is destroyed or its memory pool slot is overwritten while the PhysicsList still holds a pointer to E1.PhysicsHook, the application has a dangling pointer. The next time the physics system traverses the list, it will read garbage memory.

Let's benchmark our IntrusiveList against the standard library's std::list<Entity*>. We will pre-allocate 100,000 entities in a std::vector to simulate an object pool. We will first measure how long it takes to create the lists containing all of these objects:

1#include <benchmark/benchmark.h>
2#include <list>
3#include <vector>
4#include <dsa/IntrusiveList.h>
5
6struct TestEntity {
7  int Value;
8  ListHook Hook;
9};
10
11static void BM_StdListPointers_Insert(benchmark::State& state) {
12  std::vector<TestEntity> Pool(100000);
13  for (int i = 0; i < 100000; ++i) Pool[i].Value = 1;
14
15  for (auto _ : state) {
16    std::list<TestEntity*> L;
17    for (int i = 0; i < 100000; ++i) {
18      // Allocates a node wrapper for every single pointer
19      L.push_front(&Pool[i]); 
20    }
21  }
22}
23
24static void BM_Intrusive_Insert(benchmark::State& state) {
25  std::vector<TestEntity> Pool(100000);
26  for (int i = 0; i < 100000; ++i) Pool[i].Value = 1;
27
28  for (auto _ : state) {
29    IntrusiveList<TestEntity, offsetof(TestEntity, Hook)> L;
30    for (int i = 0; i < 100000; ++i) {
31      // Zero allocations. Pure pointer wiring.
32      L.PushFront(&Pool[i]); 
33    }
34  }
35}
36
37#define BENCHMARK_MS(func) \
38  BENCHMARK(func)->Unit(benchmark::kMillisecond)
39
40BENCHMARK_MS(BM_StdListPointers_Insert);
41BENCHMARK_MS(BM_Intrusive_Insert);

1-----------------------------------
2Benchmark                       CPU
3-----------------------------------
4BM_StdListPointers_Insert   5.16 ms
5BM_Intrusive_Insert        0.075 ms

The std::list is suffocating under the weight of creating 100,000 wrapper nodes, while the intrusive list simply updates pointers that already exist within each TestEntity.

Next, once we've created the lists, let's benchmark how long it takes to traverse through them:

1// ...
2
3static void BM_StdListPointers_Traverse(benchmark::State& state) {
4  std::vector<TestEntity> Pool(100000);
5  std::list<TestEntity*> L;
6  for (int i = 0; i < 100000; ++i) {
7    Pool[i].Value = 1;
8    L.push_front(&Pool[i]);
9  }
10
11  for (auto _ : state) {
12    int sum = 0;
13    // Pointer chase 1 - follow the link to get the next node
14    for (TestEntity* e : L) {
15      // Pointer chase 2, follow the link from node to object
16      sum += e->Value; 
17    }
18    benchmark::DoNotOptimize(sum);
19  }
20}
21BENCHMARK(BM_StdListPointers_Traverse);
22
23static void BM_Intrusive_Traverse(benchmark::State& state) {
24  std::vector<TestEntity> Pool(100000);
25  IntrusiveList<TestEntity, offsetof(TestEntity, Hook)> L;
26  for (int i = 0; i < 100000; ++i) {
27    Pool[i].Value = 1;
28    L.PushFront(&Pool[i]);
29  }
30
31  for (auto _ : state) {
32    int sum = 0;
33    // Pointer chase 1 - follow the link to get the next Hook
34    L.Traverse([&](TestEntity* e){
35      // No more chasing - Hook and Value are in the same cache line
36      sum += e->Value; 
37    });
38    benchmark::DoNotOptimize(sum);
39  }
40}
41BENCHMARK(BM_Intrusive_Traverse);

1--------------------------------------
2Benchmark                          CPU
3--------------------------------------
4BM_StdListPointers_Traverse   0.215 ms
5BM_Intrusive_Traverse         0.100 ms

While both structures suffer from the erratic pointer chasing of a linked list, the intrusive variation only misses the cache once per element, whilst std::list<TestEntity*> misses twice. It is forced to fetch the wrapper node from the heap, and then fetch the payload from the vector pool, doubling the pointer-chasing inefficiency.

Here is the complete implementation of our zero-allocation IntrusiveList:

Remember that when the CPU fetches memory, it doesn't just pull the 8 bytes of our ListHook. It pulls an entire 64-byte cache line from main RAM. We can exploit this by being strategic about where we place our hooks within the struct.

If some system is iterating through the PhysicsHook chain, it's likely to be interested in physics-related variables. Therefore, those variables should sit directly adjacent to the hook in the struct definition. When the CPU fetches the hook, the payload data comes along for the ride in the same cache line, eliminating memory stalls:

1struct Player {
2  int ID;
3
4  // Grouped for a single cache-line fetch
5  float VelocityX;
6  float VelocityY;
7  ListHook PhysicsHook; 
8
9  // Grouped for the renderer
10  bool IsVisible;
11  int MeshID;
12  ListHook RenderHook; 
13};

If there is no obvious spatial grouping we can apply, placing the hook at the very top of the type has some benefits.

If the hook is the very first member, it has an offset of 0, meaning its physical memory address is the same as the object's address. This removes the need for offsetof and associated pointer arithmetic, which simplifies the code and saves CPU cycles.

1struct Player {
2  // Offset 0: The hook and the player share the same address
3  ListHook Hook; 
4
5  int ID;
6  float Health;
7};

In this lesson, we tackled the challenges of data structures that do not own the objects they organize.

1. Standard containers like std::list wrap data in nodes. Storing pointers (std::list<T*>) avoids payload copying but causes devastating double indirection and cache thrashing.
2. An intrusive data structure embeds the node metadata (ListHook) directly inside the payload struct.
3. We used the offsetof macro to calculate the physical distance between the embedded hook and the start of the object, allowing us to convert a ListHook* back into a typed object pointer.
4. Because the structure only rewires pre-existing physical memory, insertions are guaranteed zero-allocation and $O(1)$.
5. By embedding multiple hooks, a single physical object can exist in multiple logical lists simultaneously with minimal performance overhead.

We have now explored contiguous chunks, index-based pools, unrolled fat nodes, and intrusive structures. All of these techniques optimize the physical layout of linear sequences.

In the next lesson, we will push linked architecture beyond flat chains. We will trade some of our memory capacity to build algorithmic "express lanes" and introduce the probabilistic linking of skip lists.