liveBook · Manning

Cache miss

As explained in The Coder Cafe

A cache miss occurs when a requested memory location is not present in the relevant CPU cache.

A cache miss occurs when a requested memory location is not present in the relevant CPU cache. It matters because irregular memory access can make software slower even when its theoretical operation costs look favorable. section 1.1

Linked lists often have weaker spatial locality than arrays because their elements are not guaranteed to occupy contiguous memory. After fetching one cache line, the next element may require another cache line, causing more cache misses. Unpredictable traversal also limits effective CPU prefetching and can prevent SIMD-based processing. section 1.1 section 1.1

Contiguous linked-list traversal

A benchmark compared iterating over an array with iterating over a linked list allocated contiguously. The linked-list iteration was still 230% slower: its assembly required more cycles per iteration, and its less predictable access pattern caused more cache misses and lower performance. section 1.1

How The Coder Cafe covers it

How deep it goes
Connects cache misses to cache lines, spatial locality, prefetching, and iteration patterns without detailing cache hardware.
Examples
Uses a benchmark where a contiguous linked list iterated 230% slower than an array.
What you can do after
Evaluate/understand how memory layout and access patterns affect iteration performance when choosing arrays or linked lists.
How it connects
Connects cache misses to spatial locality, cache lines, CPU prefetching, SIMD instructions, and linked lists.

Also explained in

Compare how 4 books explain cache miss →

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.