Building Cache-Friendly Graphs

In this lesson, you will learn how to improve graph performance by replacing pointer-heavy structures with contiguous, index-based arrays to maximize CPU cache efficiency.

The Pointer Problem

When you build a graph using Box<Node> or Rc<Node>, every "edge" in your graph acts as a pointer. To traverse the graph, the CPU must jump to a random memory location for every node. Because these nodes are likely scattered across the heap, the CPU cannot predict where the next piece of data is, leading to "cache misses"—where the processor sits idle waiting for data to arrive from slow RAM.

Moving to Flat Arrays

To keep the CPU happy, we store our graph in flat vectors. Instead of pointers, we use usize indices to represent edges. Since a Vec stores its contents in a contiguous block of memory, the processor can pre-fetch the next node’s data before you even ask for it.

Consider this structure:

struct Edge {
    to: usize,
    weight: i32,
}

struct Graph {
    // All nodes are stored contiguously
    nodes: Vec<Vec<Edge>>,
}

impl Graph {
    fn neighbors(&self, node_idx: usize) -> &[Edge] {
        &self.nodes[node_idx]
    }
}

Why This Wins

1. Spatial Locality: By packing the Edge data together, you ensure that when you load one edge, the next edge in the list is likely already sitting in the L1 cache.
2. Simplified Ownership: Because you are using usize indices, you eliminate complex lifetime chains. The Graph struct owns everything, and you don't need to worry about RefCell or lifetime annotations propagating through every traversal.
3. Reduced Allocation: Instead of allocating thousands of small heap objects for every edge, you perform a few large allocations for the backing vectors, significantly reducing pressure on the memory allocator.

When your graph is just a collection of slices within a Vec, the CPU treats your graph traversal like a simple iteration over an array. This shift transforms your code from a memory-pointer-chasing bottleneck into a high-speed data stream.

Key Takeaway: Replace pointer-based graph nodes with index-based arrays to store your data contiguously, allowing the CPU to utilize its cache effectively and eliminating complex lifetime dependencies.