In this lesson, you will learn how to arrange graph data in memory to minimize cache misses and maximize traversal speed by prioritizing spatial locality over compact memory usage.
The Locality Trap in Pointer-Chasing
Traditional graph representations like Vec<Vec<NodeId>> (the Adjacency List) are intuitive but often disastrous for modern CPU caches. Because each inner Vec is allocated on the heap, the neighbors of Node A may be scattered far away from the neighbors of Node B. When your iterator pipeline traverses these nodes, the CPU frequently stalls waiting for data to be fetched from main memory, as it cannot predict the next memory address to prefetch.
Contiguous Flattened Adjacency
To optimize for traversal, we transition from an "array of pointers" approach to a Compressed Sparse Row (CSR) style layout. Instead of separate allocations, we store all graph edges in one single, contiguous Vec<Edge>. We then use a secondary "offset" array to track where each node's range of edges begins and ends.
struct Graph {
// All edges laid out contiguously in memory
edges: Vec<TargetNode>,
// Offsets[i] marks the start index in `edges` for node `i`
offsets: Vec<usize>,
}
impl Graph {
fn neighbors(&self, node: usize) -> &[TargetNode] {
let start = self.offsets[node];
let end = self.offsets[node + 1];
&self.edges[start..end]
}
}
Why This Improves Pipelines
By placing the edges contiguously, you transform a random-access traversal into a linear scan. When you use an iterator pipeline over neighbors(node), the CPU's hardware prefetcher recognizes the sequential access pattern and loads upcoming edges into the cache before you even request them. This drastically reduces stalls during hot loops.
Furthermore, because the edges data is packed, you maximize the number of edges fitting into a single cache line. While this approach is less flexible—making dynamic insertions expensive—it shifts the bottleneck from memory latency to raw compute throughput, allowing your iterators to run at the speed of the hardware.
Key Takeaway: By flattening nested allocations into a single contiguous buffer with an offset array, you turn pointer-chasing into predictable linear access, drastically increasing performance in high-frequency traversal loops.