In this lesson, you will learn how to optimize your data structures by arranging references to favor cache locality, which can significantly speed up your program's performance.
The Cache Hierarchy and You
Modern CPUs are incredibly fast, but they are often bottlenecked by the speed at which they can fetch data from your computer's main RAM. To mitigate this, processors use "caches." When your CPU fetches data from memory, it pulls in a small chunk of adjacent bytes (a cache line) hoping that if you needed one piece of data, you’ll soon need the data stored right next to it.
When you use references, you are pointing to a specific location in memory. If your data structure involves many pointers to disparate locations (like a Vec<&T> where each &T points to a different heap-allocated object), your CPU will constantly miss the cache, forcing it to wait for slow RAM.
Favoring Cache Locality
To maximize performance, you want to keep data "contiguous" in memory. If you have a collection of objects, storing them directly in a Vec<T> is almost always better than a Vec<&T>. By storing the actual values together, you ensure that as you iterate over them, the CPU loads multiple elements into its cache at once.
Consider this inefficient pattern:
// Inefficient: Many pointers scattered in memory
let items: Vec<Box<Data>> = load_data();
let references: Vec<&Data> = items.iter().map(|b| b.as_ref()).collect();
for item in references {
process(item); // CPU may jump to different RAM locations for every item
}
If your logic allows, restructure your data to avoid references to scattered heap objects:
// Efficient: Everything is in one contiguous block of memory
let items: Vec<Data> = load_data_directly();
for item in &items {
process(item); // CPU fetches multiple items in a single cache line
}
By reducing the amount of "pointer chasing" your code does, you allow the hardware prefetcher to do its job, loading your data into the cache before you even ask for it. When designing systems, always ask yourself: "Is this reference pointing to a single, stable value, or am I creating a web of pointers that forces my CPU to jump around?"
Key Takeaway: To optimize performance, prioritize storing data contiguously rather than using collections of references, as this maximizes cache hits and reduces memory access latency.