In this lesson, you will learn how to arrange your data structures to keep your CPU processing at peak efficiency by minimizing "cache misses."
The CPU Cache Hierarchy
Your CPU is significantly faster than your RAM. To bridge this speed gap, the CPU keeps small amounts of data in a high-speed buffer called L1/L2 cache. When your code loops over data, the CPU tries to pull a "chunk" (a cache line) from memory into the cache. If the data your code needs next is already in that chunk, the CPU works at full speed (a cache hit). If it isn't, the CPU must wait for slow RAM (a cache miss).
Data Locality: Arrays vs. Pointers
The most important rule for cache locality is: Keep related data together in memory.
In Rust, a Vec<T> stores its elements in a contiguous block of memory. If you iterate over a Vec<i32>, the CPU can pre-fetch the next numbers into the cache before you even ask for them.
However, consider this "bad" structure:
struct Bad {
data: Vec<Box<i32>>, // Pointers scatter data all over the heap!
}
If you iterate over Bad, the CPU only gets the address of the number. To get the actual value, it must jump to a random memory location, potentially causing a cache miss every single time. Instead, prefer keeping the values directly in the struct:
struct Good {
data: Vec<i32>, // Values are stored right next to each other
}
Struct of Arrays (SoA) vs Array of Structs (AoS)
If you have a complex struct, think about how you access it. If you only ever need a specific field inside a loop, keeping that field in its own Vec (SoA) is often faster.
struct Player {
health: i32,
_position: [f32; 100], // Huge chunk of data
}
// If you only loop to update health, the CPU is wasting cache space
// loading the unused _position data!
By keeping your data contiguous and avoiding excessive pointer chasing, you ensure the CPU spends more time calculating and less time waiting on RAM.
Key Takeaway: To maximize cache hits, prefer contiguous data like arrays or vectors and store actual values rather than pointers to heap-allocated data.