How this site is made

The figure library

Every picture here is generated from code at build time. This page lists the generator families, how many essays call each one, and what each draws with no arguments at all. Page 1 of 5, access-pattern to cost-model.

No figure on this site is a drawing that was made once and saved. Each one is a function: it takes parameters and returns SVG, so the same generator draws the merge sort's access trace and the heapsort's without either being redrawn, and both are drawn from a real run.

That is the reason the collection can keep growing without the illustrations drifting apart. A generator is written once, checked once, and every essay that calls it inherits the same line weights, the same colour roles, and the same behaviour in dark mode. There are 154 of them so far, called by 154 distinct names across 384 essays.

The number beside each family is the count of essays that call it, and it is the number this collection is really built on. A generator instantiated once is a drawing with extra steps; the target is a family used dozens of times, because nobody writes two thousand generators. Each family has a page of its own listing every essay that calls it — which is also the blast radius of changing it.

The library runs to 5 pages, and they are cut by weight rather than by count: each card carries its generator's actual output, and those run from about two kilobytes to about eighty. A cut at n cards a page would therefore make some pages forty times heavier than others for no reason a reader could see, so the cut is made at a fixed number of bytes and the card count is whatever fits.

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

access-pattern

8 essays
with the edge — connected01234567all 8 edges presentwithout it — two components01234567one edge withheld, everything else identicalV = 8, E = 8Ω(E), by adversary rather than by counting

adversary-edges

2 essays
1234152abcbcbccbsolid: a transition on a character · dashed: a suffix or failure link8 states ≤ 9, 9 transitions ≤ 11

automaton-map

5 essays
1,00010⁴10⁵10⁶charactersoperationscharacter comparisonstransitions and linksrepetitive · 8 copies346 phrases at 8,192

automaton-parse

4 essays
0$abracadabra1a$abracadabr2abra$abracad3abracadabra$4acadabra$abr5adabra$abrac6bra$abracada7bracadabra$a8cadabra$abra9dabra$abraca10ra$abracadab11racadabra$aball 12 rotations of "abracadabra$", sorted0 character comparisons

backward-search

5 essays
1234567characters addedoccurrencesgrown leftwardsgrown rightwards"tgatatt"4,000 characters · four symbols1 occurrences

bidirectional-search

7 essays
1,00010,0000.1bits of state heldrelative errorHyperLogLog (-0.49)LogLog (-0.44)bottom-k (-0.38)50,000 distinct keys · 14 runs per point · truth counted exactlybest: 2.00% at 10,240 bits

bits-against-error

2 essays
bits per elementε = 0.13.3 → 4.8 (+1.5)ε = 0.035.1 → 7.3 (+2.2)ε = 0.016.6 → 9.6 (+2.9)ε = 0.0038.4 → 12.1 (+3.7)ε = 0.00110.0 → 14.4 (+4.4)ε = 1e-413.3 → 19.2 (+5.9)floor log₂(1/ε) filled; Bloom's log₂(1/ε)/ln 2 outlined44.3% above the floor at every rate

bits-against-floor

3 essays
46810120.010.1bits per element (m / n)false-positive ratemeasured(1 − e^(−kn/m))^kfrom the bits set60,000 absent-key queries per point, seed 80800 false negatives at every size

bloom-rate

12 essays
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

branch-ranking

4 essays
levels on the path (outline) · transfers actually paid (filled)B = 411 levels · 6.99 transfers · 16,384 blocks residentB = 166 levels · 3.23 transfers · 4,096 blocks residentB = 644 levels · 1.99 transfers · 1,024 blocks residentB = 2563 levels · 1.30 transfers · 256 blocks residentB = 10243 levels · 1.01 transfers · 64 blocks residentbinary search over the same 4,194,304 keys: 20 transfersB = 1024, M = 65,536 (M/B = 64)20× between binary search and the widest tree

btree-shape

5 essays
column height = keys in that bucket · line = threshold of 8a well-spread hashlongest 44 → 4worst lookupthe low bits onlylongest 3131 → 5worst lookupevery key collideslongest 192192 → 8worst lookup192 keys, 256 buckets, seed 20260811threshold 8, 64 buckets shown

bucket-occupancy

2 essays
each row is one rotation · the table is sorted · the transform is the last columnfirstlastmeasured-not-asserted-assertedmeasured-not-not-assertedmeasuredassertedmeasured-not-asured-not-assertedmedmeasured-not-asserted-not-assertedmeasureeasured-not-assertedmedmeasured-not-asserted-not-assertedmeasurertedmeasured-not-assmeasured-not-assertednot-assertedmeasured-ot-assertedmeasured-n… 8 further rotationsmeasured on 8,192 symbols of the same source:H₀ of the text3.899 bitsH₀ of the last column3.899 bitsH₀ after move-to-front, before4.156 bitsH₀ after move-to-front, after1.802 bitsmodel: order 0, before and after a permutationmean run 1.01 → 3.38

bwt-columns

4 essays
110110cap on the depthphrases ÷ free parseten revisionsfourteen revisionstwelve essayseight modulesthe model5 collections · free parse = 1worst 35x at a cap of one

cap-real

4 essays
cap 2cap 4cap 8cap nonephrases followedposition in the collectionEnglish-like · 2,048 charactersworst 2 to 12

cap-structure

6 essays
11010⁴10⁵worst copy chain, phrases followedbits124816noneno capcap on each pointEnglish-like · 16 copies of 512z 156 to 7,351

capped-parse

6 essays
50318223749516674879310811positionthe minimum12 values · depth 3answer 6 (1)

cartesian-shape

3 essays
range consideredminimum atC[at] < lonew document[476, 489)483 · document 4yesyes[476, 483)477 · document 1yesyes[476, 477)476 · document 0yesyes[478, 483)482 · document 2yesyes[478, 482)478 · document 0nono[484, 489)486 · document 3yesyes[484, 486)484 · document 0nono[487, 489)487 · document 2nono8 steps, 5 documents, and the two columns never differrows 476–489 · 8 documents8 steps

chainless-listing

6 essays
71 s60 ticks11100 ms600 ticks1410 ms6,000 ticks171 ms60,000 ticks270.001 ms60,000,000 ticksclock resolutionbits per stamp⌈log₂ 2D/r⌉no arrival rateappears in itD = 60 s · key 32 bitscomputed, not measured

clock-stamps

4 essays
bits per symbolhuffman3.9371.01× the floorarithmetic (adaptive)3.8981.00× the floorLZSS (window 4096)2.1130.54× the floorLZ783.1470.81× the floorH₀ = 3.89216,384 symbols · alphabet 21 · floor shown is H0 = 3.892 bits/symbolmodel: order 0 · Words from a fixed vocabularybest here: 2.113 bits/symbol

coder-gap

3 essays
one text16 short documentsprosecopies of one baseprose, one textr/n 0.2996z/n 0.1273prose, many short documentsr/n 0.3053z/n 0.1301copies of one base, run togetherr/n 0.0638z/n 0.0354one copy per documentr/n 0.0768z/n 0.04188,192 characters throughoutthe outlined cell is the one that was empty

collection-corners

8 essays
level 0 · left335 keptlevel 1 · right+207 smallerlevel 2 · left61 keptlevel 3 · right+33 smallerlevel 4 · left8 keptpositions still in play, and the half the code leaves behindsmaller symbols before position 400: 240rank of "m": 8 — from the same 5 operationsσ 21 · code 010105 ranks, not 105

compound-walk

4 essays
00.2500.5000.750101234567891011level of the wavelet treebits a bitthe parse's grida uniform permutation3,612 points · 12 levels0.997 bits a bit

compressed-grid

4 essays
10010³10⁴10⁵10⁶⌊1/2ε⌋ = 50151025501002005001,000tuples, and tuples examinedcompression period, in updatestuples examinedpeak tuplesresident tuplesworst rank errorε = 0.01 · 20,000 arrivalspeak 10× · work 72× · answer 1.21×

compression-schedule

2 essays
10⁴10⁵10⁶0.1characters in the collectionphrases per charactermeasured hereshuffledthe collectiona million characters of prose · 1,004,741 charactersphrases x2.34, control x1.70

corpus-scale

2 essays
acgtacgtseen ->0313303113033130a gap of k characters costs 2krows: expected · columns: seen · unit: bitslinear gaps

cost-model

10 essays