In this lesson, you will learn how to arrange your data to satisfy the CPU’s hunger for predictable, sequential memory access.
The CPU Prefetcher
Modern CPUs are incredibly fast, but fetching data from main RAM is relatively slow. To bridge this gap, CPUs use a prefetcher. When you access a piece of data, the prefetcher predicts what you will need next and pulls it into the high-speed CPU cache before you even ask for it. However, the prefetcher is a creature of habit: it thrives on spatial locality—the idea that if you access an address, you will likely access the one immediately following it.
Pointers: The Cache Killer
In Rust, we often use Box<T>, Vec<T>, or Rc<T>. While these provide safe ownership, they store data on the heap. If you have a Vec<Box<T>>, your data is scattered across memory. When the CPU iterates through this vector, it doesn't see a contiguous block of values; it sees a list of pointers.
To "fetch" the actual data, the CPU must first load the pointer (the address), then jump to a completely different location in RAM to get the value. This creates a "cache miss," forcing the CPU to sit idle while it waits for memory.
Aligning Data
To be cache-friendly, we want to store data inline rather than behind a pointer. Compare these two patterns:
// Cache-unfriendly: Each object is a jump away in memory
let items: Vec<Box<MyStruct>> = vec![...];
// Cache-friendly: All data sits in a single, contiguous memory block
let items: Vec<MyStruct> = vec![...];
By storing MyStruct directly in the Vec, the CPU prefetcher can see the entire array as one long, predictable line. As you loop through items, the hardware fetches multiple elements into the cache simultaneously. Because the data is packed tightly, you minimize the "jumps" that cause the CPU to stall. When designing your structures, favor flat, contiguous memory layouts whenever your ownership model allows it, ensuring your data is ready and waiting exactly where the prefetcher expects to find it.
Key Takeaway: To maximize performance, favor contiguous memory layouts that keep your data tightly packed, allowing the CPU prefetcher to load your next pieces of data before you even request them.