Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Trace — where it appears

A recorded sequence of the primitive acts one run performed, from which both a figure and the numbers in its caption are taken. Both the figure and the numbers in its caption come from it, so a plate and its text cannot disagree about what happened.

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

10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapDijkstra, all V queuedBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons

Counting on a graph

An instrumented array counts comparisons, swaps, reads and writes, and none of those is what a graph algorithm spends its time on. Three new primitives are needed — an adjacency scanned, a vertex first reached, an edge relaxed — and once they exist, breadth-first and depth-first search turn out to be the same algorithm by every count kept on arrays.

graphs · Graph 10⁵10⁶10³10⁴10⁵comparisonscache misses (modelled)Insertion sortSelection sortBubble sortMerge sortHeapsortQuicksort, firstQuicksort, median-3Quicksort, randomShellsortMerge + cutofffully associative · 64 lines × 8 elements · LRUa modelled count, not a time

The count is not the time

An operation count is exact, machine-independent, and not a running time. The gap between them is mostly memory, and it is large enough to reorder the rankings. This site carries a second count — modelled cache misses from the same runs — and asserts that the two disagree, because if they agreed the second one would carry no information.

machine · Machine Merge sort49% sequential · 7,540 accesses2560Heapsort15% sequential · 14,044 accesses2560time (accesses, left to right) · index (bottom to top)one run each, n = 256every access plotted

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 10³10³10⁴Vmodelled missesadjacency listCSR array96% miss27% miss64 lines × 8 elements, fully associative, LRU3.6× between two layouts of one graph

A list and a block of memory

The same traversal, over the same graph, examining the same edges in the same order, laid out two ways. Twelve thousand two hundred and eighty-eight edge slots either way; 11,812 modelled cache misses against 3,258. This is the site's largest gap between two counts of one run, and it exists because one of the layouts is a pointer chase and the other is a sweep.

graphs · Graph 10⁵10⁶10⁴10⁵comparisonsmispredictions (modelled)Insertion 0%Selection 1%Bubble 29%Merge sort 52%Heapsort 27%Quicksort, first 24%Quicksort, median-3 39%Quicksort, random 27%Shellsort 51%Merge + cutoff 40%Timsort 41%Introsort 32%pdqsort 43%Dual-pivot 37%2-bit counters, no historysquares are the sorts that ship

The branch the machine guesses

Insertion sort does 176 times as many comparisons as Timsort at n = 8,192 and mispredicts a sixth as many branches. Merge sort's inner test is a coin flip and misses 51.5% of the time; selection sort's misses 0.6%. A processor does not wait to learn the answer to a comparison — it guesses, and throws away the work when it guessed wrong — and this is the fifth quantity this site counts.

machine · Machine

Named alongside it

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

CacheComparison countLocalityAccess patternAdjacencyCost modelHeapQuicksortTraversalAdjacency listBranch predictionBranchless

All concepts