Skip to content
0 50 100 150 200 25 ◆ 40 50 ◆ 60 75 100 ◆ 125 150 ◆ 200 ◆ 250 ◆ 500 ◆ worst rank error value cycle length, p the ordered stream the same values shuffled period 50 · ◆ commensurate commensurate excess 1.03×
schedule-aliasing1 essay
10³ 10⁴ 10⁴ array length n total over 2,000 searches branchy, comparisons branchless, comparisons branchy, mispredicts branchless, mispredicts 2-bit counters, no history solid: comparisons · dashed: mispredicts
search-branches1 essay
0 4 8 best: 0 at 150 position in the text cost of the best match ending here, in edits dashed: the threshold k = 2 · unit cost 9 positions under it
search-row2 essays
randomised pivot 164 random bits 2.96 ±23% median of medians no random bits 7.94 ±2% 0.0 4.3 8.6 comparisons per element — bar is the range over seeds, tick is the mean 30 seeds, n = 4,001, median 2.68× the mean, 14× the spread
select-constants2 essays
1,000 10,000 10³ bits of select support positions inspected, worst case binary search, no extra bits: 510 L=8 L=256 L=8 L=256 one position per L ones dense and sparse 6,554 ones in 65,536 positions · sub-blocks of 8 worst cases, every k
select-cost3 essays
0 100 200 300 400 2 1 φ 3 8 2 φ 7 20 3 φ 17 43 4 φ 42 88 5 φ 101 248 6 φ 242 measured 409 counts charged level of the fold charged at this level running total 64 shards · k = 32 · hashed charged 409 · measured 409
shard-regime3 essays
1 coefficient 13 members 2 coefficients 169 members 3 coefficients 2,197 members 4 coefficients 28,561 members 1 key 2 keys 3 keys 4 keys 5 keys exact 92% gone 99% gone 100% gone 100% gone exact exact 92% gone 99% gone 100% gone exact exact exact 92% gone 99% gone exact exact exact exact 92% gone every member walked · GF(13) · no tolerance and no seed degree 1, 2, 3, 4
sign-degree2 essays
hash row h1 h2 h3 h4 h1 → cell 30: 7,315 h2 → cell 29: 7,467 h3 → cell 19: 7,423 h4 → cell 4: 7,660 key 0 occurred 6,793 times · the minimum of the four is 7,315 · over by 522 the additive bound at this width is e/w × N = 3,398 4×32 counters · 4,096 bits · Zipf s = 1.1 exact would take 86,265 bits
sketch-state9 essays
0.125 0.3 0.5 0.7 0.8 0.9 0.99 probability of the dominant symbol bits per symbol 0.0 1.6 3.2 one bit per symbol Huffman Arithmetic Entropy H₀ model: order 0 · 16,384 symbols per point 8.7× at p = 0.99
skew-staircase2 essays
8 patterns of 10 characters over four symbols 0 2,000 4,000 6,000 8,000 10,000 12,000 14,000 16,000 18,000 one cell = 10 positions · shade = fraction read 61.6% of the text
skip-profile2 essays
level 1 level 2 level 3 level 4 level 5 key 21 search: 8 comparisons, 3 hops 26 keys, p = 0.5, seed 20260810 57 coin flips decided the shape
skiplist-shape2 essays
10⁴ 100 10³ n (elements) block transfers measured sort the bound 3.20× 2.67× 2.29× 2.94× 2.67× 2.40× B = 32, M = 512 (M/B = 16) 3.20× the floor at worst
sort-floor-gap2 essays
10³ 10⁴ 100 10³ n (elements) block transfers M = 256 · fan-in 7 M = 1024 · fan-in 31 B = 32, M as labelled 4 passes against 3
sort-passes9 essays
after 0 writes 0 cmp after 32 writes 32 cmp after 64 writes 63 cmp after 95 writes 94 cmp after 127 writes 125 cmp after 159 writes 157 cmp random input, seed stated in lib/count.js 157 comparisons in this run
sort-trace2 essays