Spatial locality is the tendency for accesses near a recently accessed memory location to occur soon afterward. Contiguous data lets a CPU cache line bring nearby elements into the cache, reducing misses during iteration. section 1.1
Spatial locality affects practical performance in several ways:
- Arrays usually provide contiguous storage, while linked-list elements are not guaranteed to be adjacent. section 1.1
- Poor locality can cause more cache misses and prevent effective CPU prefetching during iteration. section 1.1
- Applications with poor locality may also lose opportunities to use SIMD instructions for operations such as summing elements. section 1.1
Contiguous linked-list iteration
Even a linked list allocated contiguously by one thread can iterate more slowly than an array. A benchmark found it 230% slower because linked-list iteration required more cycles and followed an unpredictable pattern that limited prefetching. section 1.1

