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

The cliff: miss rate against working-set size

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
The cliff: miss rate against working-set sizeTwenty thousand uniformly random accesses into an array of n elements, replayed through a cache holding 512 elements. Below 512 the miss rate is essentially zero; a factor of eight above it, essentially everything misses. The comparison count of an algorithm says nothing about which side of this cliff it is working on, which is why the two counts are carried separately. Model: fully associative · 64 lines × 8 elements · LRU.0%25%50%75%100%645124,09665,536cache holds 512array size n (elements)miss ratefully associative · 64 lines × 8 elements · LRU20,000 random accesses per point

The cliff: miss rate against working-set size

Twenty thousand uniformly random accesses into an array of n elements, replayed through a cache holding 512 elements. Below 512 the miss rate is essentially zero; a factor of eight above it, essentially everything misses. The comparison count of an algorithm says nothing about which side of this cliff it is working on, which is why the two counts are carried separately. Model: fully associative · 64 lines × 8 elements · LRU.

Drawn at 660 × 400, wide on the page. Everything above is what working-set returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

10 essays call working-set. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

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 What the machine does

The count is not the time

 0%25%50%75%100%645124,09665,536cache holds 512array size n (elements)miss ratefully associative · 64 lines × 8 elements · LRU20,000 random accesses per point What the machine does

The cliff where the data stops fitting

 average 8.001,0242,048bucket, 0 to 255keys in the bucketthe low bits · keys built for this hashworst bucket 2,048 against 8.0 When the algorithm flips a coin

A hash is a family, not a function

 10³10³10⁴Vmodelled missesadjacency listCSR array96% miss27% miss64 lines × 8 elements, fully associative, LRU3.6× between two layouts of one graph Two parameters

A list and a block of memory

 01234567801234567891724303539424410182531364043111926323741122027333813212834142229152316one unit = one subproblem given a valueeach number is a storage offset, of 45 slots When the algorithm is a table

A triangle stored in a square

 cache misses per split point consideredsquare array, by length1.1063,128,465 missestwo copies, by rows0.212598,455 missessquare array, split scans0.095268,386 missesfully associative · 32 lines × 8 elements · LRU256 keys, 32,896 cells When the algorithm is a table

The split scan cut into blocks

 1632649612810³10⁴10⁵table sizesplit points appliedevery splitbounded per blockbounded per cell, by lengthweights satisfying the quadrangle inequalityall three compute the same table When the algorithm is a table

The bound a block can and cannot have

 rounds, if every ready cell ran at oncerow by row65,793column by column65,793anti-diagonal by anti-diagonal513reads that miss the cacherow by row6.3%column by column28.2%anti-diagonal by anti-diagonal31.1%fully associative · 32 lines × 8 elements · LRU263,169 reads and writes per order What the machine does

The order with the best depth

 rounds, if every ready cell ran at oncerow order, stored by rows65,793anti-diagonal order, stored by rows513anti-diagonal order, stored by diagonals513reads that miss the cacherow order, stored by rows6.3%anti-diagonal order, stored by rows31.1%anti-diagonal order, stored by diagonals8.7%fully associative · 32 lines × 8 elements · LRU263,169 reads and writes per order What the machine does

The table stored the way it is filled

 124816326410step width, cellscache lines a stepstored by diagonalsby diagonals, each line-alignedstored by rows512 × 512, lines of 8 cellsone step of an anti-diagonal What the machine does

Eight cells at once

The library, page 5 of 5 — where working-set sits