If a particular memory location is referenced, it is very likely that nearby memory locations will be referenced in the near future.
CPUs do not pull single bytes from RAM. Instead, they pull Cache Lines (typically 64 bytes). If you request one float, the CPU fetches that float plus the next 15 floats (in a 64-byte line) and stores them in the Cache.
- High Spatial Locality: Iterating through a std-vector or std-array linearly. Since the data is contiguous, every time the CPU fetches a cache line, it gets 16 values for the price of one. The hardware prefetcher recognizes this pattern and starts pulling the next lines before you even ask for them.
- Low Spatial Locality: Iterating through a std::list or a Linked List. Because each node is allocated at a random heap address, the CPU must fetch a brand-new cache line for every single element. You spend more time waiting for the bus (RAM) than doing the work.