liveBook · Manning

Spatial locality

As explained in The Coder Cafe

Spatial locality is the tendency for accesses near a recently accessed memory location to occur soon afterward.

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

How The Coder Cafe covers it

How deep it goes
Connects locality to cache lines, cache misses, prefetching, and SIMD, but does not develop hardware internals further.
Examples
Contrasts array iteration with contiguous and potentially scattered linked-list allocation, including a 230% slower benchmark.
What you can do after
Evaluate array-versus-linked-list choices using cache behavior and iteration performance, not theoretical time complexity alone.
How it connects
Connects spatial locality with arrays, linked lists, cache lines, cache misses, CPU prefetching, and SIMD.

Also explained in

Compare how 2 books explain spatial locality →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.