In this lesson, you will learn how to structure your hot loops to traverse memory linearly, ensuring the CPU hardware prefetcher can predict your data access patterns and keep your cache filled.
The Physics of the Cache Line
Modern CPUs do not fetch single bytes from RAM; they fetch "cache lines," typically 64 bytes at a time. If you access a byte at address X, the CPU automatically pulls X through X+63 into the L1 cache. Spatial Locality is the practice of organizing your data so that the next piece of information you need is already sitting in that 64-byte block.
Linear Traversal vs. Pointer Chasing
When you traverse a linked list or a collection of Box<T>, you are "pointer chasing." Each step requires a new memory fetch that might reside on a different, non-contiguous page, causing the CPU to stall while waiting for RAM.
To optimize for spatial locality, you must keep your "hot" data in contiguous memory, such as a Vec<T>. Consider a particle system where you frequently update positions:
struct Particle {
x: f32,
y: f32,
velocity: f32,
// ... metadata that isn't needed for the movement loop
}
// Optimization: By keeping the data in a flat Vec,
// the loop traverses memory linearly.
fn update_positions(particles: &mut [Particle]) {
for p in particles {
p.x += p.velocity;
}
}
By iterating over a slice &[Particle], you ensure that as the loop processes index i, index i+1 is already being pulled into the cache by the hardware prefetcher. If you instead stored these as Vec<Box<Particle>>, the prefetcher would fail, as the pointers would point to disparate heap locations.
Packing the Hot Path
To maximize the usage of every cache line, place the fields accessed within your hot loop at the start of your struct (referencing your knowledge of field alignment). If your loop only needs x and velocity, ensure those fields are packed together to minimize the number of cache lines required to perform a single iteration. When data is packed tightly, a single 64-byte fetch might contain data for 8 or 16 iterations of your loop, drastically reducing the cycles spent waiting for the memory bus.
Key Takeaway: Design your data layouts so that your hot loops access memory in a single, contiguous linear sequence to leverage the CPU's hardware prefetcher and maximize cache line density.