Concept

Prefetching — where it appears

Fetching a block before it is asked for, which hides the latency of a predictable access pattern and does nothing for a pointer chase. It hides the latency of a predictable access pattern and does nothing for a pointer chase, which is why layout changes a clock and no operation count.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

Where an algorithm looks

Plotted as index against time, every array access an algorithm makes becomes a picture that no count contains. Merge sort's is a set of sweeps. Heapsort's is a spray. Quicksort's is a narrowing triangle. These shapes decide how fast the algorithms run and they are entirely absent from the analysis that says all three are Θ(n log n).

machine · Machine

The block that is not a block

This field's model has one memory, one block size, one processor, no prefetcher, no queue and no clock, and every number in it is a count of transfers rather than a duration. A real machine has five levels, reads ahead, issues a hundred requests at once, and charges four orders of magnitude more for one kind of transfer than another. What survives the difference is worth stating exactly, and so is what does not.

wrong · Transfer

Named alongside it

The objects these essays reach for when they reach for this one.

Access pattern Block transfer Cache Comparison count Cost model Divide and conquer External-memory model Failure mode Heap Honest limit Locality Memory hierarchy

All concepts