In this lesson, you will learn how to structure your Rust data types to minimize CPU cache misses by favoring contiguous memory access over "pointer-chasing."
The Problem: Pointer-Chasing
Modern CPUs are incredibly fast, but they are often bottlenecked by the time it takes to fetch data from main RAM. To compensate, CPUs use caches. When your code accesses a piece of data, the CPU loads a "cache line" (typically 64 bytes) into the cache. If your data is laid out linearly, the CPU pre-fetches your next needed values automatically.
"Pointer-chasing" occurs when you use structures like Box<T>, Rc<T>, or nested vectors where the data is stored at a disjoint memory address. Accessing a Box<T> requires the CPU to load the pointer address first, then perform a second, unpredictable fetch to the heap. If that memory isn't in the cache, the CPU stalls while waiting for RAM.
Designing for Locality
Instead of creating a graph of objects connected by pointers, prefer Data-Oriented Design. If you have a collection of entities, store them in a single Vec<T> where T is a plain "struct of data" rather than a container of pointers.
Compare these two approaches:
// Cache-Unfriendly: Pointer-chasing
struct Entity {
name: Box<String>,
stats: Box<Stats>, // Two pointer dereferences needed
}
// Cache-Friendly: Contiguous memory
struct Entity {
name: String, // Inline if small or using a fixed-size array
stats: Stats, // Stats is stored right next to 'name'
}
By embedding Stats directly into Entity, you guarantee that when you load an Entity into the cache, the Stats data comes along for the ride in the same cache line. If you are processing thousands of these entities, a Vec<Entity> will lay them out back-to-back in memory, allowing the CPU hardware prefetcher to predict your next access with high accuracy.
When designing your systems, always ask: "Is this data layout forcing the CPU to jump to a random heap location?" If the answer is yes, consider flattening your structures to keep related data close together.
Key Takeaway: To maximize cache performance, prioritize contiguous memory layouts over nested pointers to ensure that when one piece of data is loaded, its neighbors are ready in the CPU cache.