Predictable Memory Access Patterns

In this lesson, you will learn how to transform chaotic, pointer-heavy graph traversals into predictable, cache-friendly array lookups to maximize CPU throughput.

The Problem with Pointer Chasing

In standard graph representations—like a struct Node { edges: Vec<Box<Node>> }—each step in a traversal requires dereferencing a pointer to an arbitrary heap location. This forces the CPU to stall while it fetches data from main memory, as it cannot "prefetch" the next node until the current one is loaded. These jumps destroy spatial locality, causing cache misses that leave your processor waiting idle.

The Solution: Compact Index-Based Graphs

To achieve predictable memory access, replace heap-allocated pointers with integer indices into contiguous arrays. By storing all nodes in a flat Vec<Node> and representing edges as arrays of indices, you convert a "pointer chase" into a simple "base + offset" memory calculation.

Consider this transition:

// Pointer-heavy (unpredictable)
struct Node {
    next: Option<Box<Node>>,
}

// Array-based (predictable)
struct Graph {
    nodes: Vec<NodeData>,
}

struct NodeData {
    next_idx: Option<usize>,
}

When you iterate through Graph.nodes, the CPU’s hardware prefetcher recognizes the linear memory access pattern. Because the nodes are packed tightly together, the next node is likely already sitting in the L1 or L2 cache by the time you reach for it.

Engineering for Predictability

By shifting from pointers to indices, you also gain architectural benefits:

1. Compactness: usize indices are often smaller than 64-bit pointers, allowing more nodes to fit in a single cache line.
2. Determinism: The memory layout becomes stable and compact. You can reorder the array to match common traversal paths (e.g., Breadth-First or Depth-First order), ensuring that the "next" node is physically adjacent to the current one.
3. Safety: You avoid the complexity of recursive lifetimes and self-referential structures that often plague graph-heavy Rust code, keeping your hot paths clean and idiomatic.

Key Takeaway: Replace pointer-based graph nodes with index-based array lookups to transform random memory access into predictable, cache-friendly sequential streams.