Cache-Aware Linked Data Structures

In this lesson, you will learn how to replace memory-fragmented pointers with index-based references to boost CPU cache hit rates in linked data structures.

The Pointer Problem

Traditional Rust linked structures often rely on Box<Node> or Rc<Node>. While idiomatic, these nodes are scattered across the heap as the allocator finds available space. When traversing a list, the CPU cannot predict the next memory address, leading to frequent cache misses and "pointer chasing" latency. Because each pointer dereference might require a fetch from main memory, your data structure becomes bandwidth-bound rather than compute-bound.

The Index-Based Solution

To improve spatial locality, we move nodes into a single, contiguous Vec<Node>. Instead of using *mut Node or Box<Node>, we store a u32 or usize index. By keeping nodes adjacent in a contiguous array, we increase the probability that the next node is already loaded into the CPU cache line when the current one is accessed.

Consider a simple linked list implementation:

struct Node<T> {
    data: T,
    next: Option<usize>, // Index instead of pointer
}

struct ArenaList<T> {
    nodes: Vec<Node<T>>,
    head: Option<usize>,
}

By using this "Arena" pattern, you gain two critical performance advantages:

1. Spatial Locality: Nodes are allocated in a dense block. When the CPU fetches nodes[i], it likely pulls nodes[i+1] into the L1/L2 cache simultaneously.
2. Reduced Metadata: A usize index is often smaller than a 64-bit pointer, and you eliminate the Box allocation overhead per node. Furthermore, this approach makes your data structure trivial to serialize and send across process boundaries, as you are dealing with relative offsets rather than absolute memory addresses.

When implementing this, ensure your Vec does not frequently reallocate; pre-allocating capacity for your expected workload keeps the memory layout stable and prevents the "pointer invalidation" issues often associated with growing heap structures.

Key Takeaway: By replacing heap-allocated pointers with indices into a contiguous array (Arena), you transform unpredictable memory traversal into a cache-friendly linear scan.