Skip to content
peak slots held at once, logarithmic 1 8 64 512 4096 Insertion sort 1 1 Selection sort 1 1 Bubble sort 1 1 Heapsort 1 1 Shellsort 1 1 Quicksort, median of three 22 log n Quicksort, random pivot 28 log n Quicksort, first-element 29 log n Merge sort with a cutoff 4,106 n Merge sort 4,110 n n = 4,096, random input one slot = one array element or one stack frame
space-profile7 essays
plain bit vector 19,475 compressed blocks 4,557 23.4% Elias–Fano 3,905 20.1% positions, priced as Elias–Fano 3,591 18.4% 16,385 rows · one in 32 marked Elias-Fano at 20.1%
sparse-marks8 essays
100 10³ 10 100 10³ n stack frames a stack of 512 frames pivot: first-element pivot: median of three pivot: random pivot Merge sort already sorted input, n from 64 to 4,096 one frame charged as one slot
stack-depth4 essays
0 11 22 8 10 12 14 16 18 20 universe size u bits of state a u-bit bitmap log₂ C(u, u/2) ⌈log₂(u+1)⌉, a counter at u = 12: 924 subsets, 8 bits two collide → answers 6 and 7 floor computed exactly · collision found by exhaustion at u = 12 floor 9.85 bits
state-floor5 essays
windowed HyperLogLog 4,088 bits one stamp per live key 8,775 bits blocks of Misra-Gries 18,549 bits the last W keys, kept 131,072 bits keys stamps payload index the parts, in the order they stack window 4,096 · the popular keys drift 131,072 bits at most
state-parts3 essays
100 10³ 10⁴ 10⁵ length of each string subproblems given a value Full table · 1.98 Rolling frontier · 1.98 one unit = one subproblem given a value subproblems given a value, n from 32 to 512
subproblem-count15 essays
parentheses 32,768 17.6% select support 28,416 15.3% superblock minima 4,688 2.5% superblock table 19,215 10.3% block minima 37,456 20.2% block tables 63,188 34.0% the parts bits total 185,731 · the segment tree 491,520 shared lookup table 32,768, not counted 16,384 values · openings in index order, found by select 2.65x smaller
succinct-size3 essays
1 10 100 10⁴ 10⁵ queries answered character comparisons, cumulative 5 queries Scan each time Index, then query one unit = one character comparison · 4 doubling rounds break-even at 5 queries
suffix-index3 essays
0.1% 1% 10% 100% 0.5 0.75 0.9 0.99 0.999 quantile asked for rank error ÷ (1 − q) Greenwald–Khanna 7,080 bits high-biased 56,064 bits t-digest 5,952 bits 8 streams per point · ε = 0.01, δ = 100 denominator: the tail
tail-error3 essays
10,000 0.1 total bits of state runs outside ±15% 1 × 48 3 × 48 5 × 48 7 × 48 9 × 48 240 runs per design · tolerance ±15% · truth 12,000 67 → 3 failures
tail-sharpening1 essay
10 100 10⁵ minrun comparisons shipped: 32 random nearly sorted Timsort, n = 8,192 comparisons; rings mark the measured minimum
threshold-sweep1 essay
10⁵ 10⁶ 10⁷ 1 10 100 10³ 10⁴ comparisons peak auxiliary slots Insertion sort Selection sort Bubble sort Merge sort Heapsort Quicksort Quicksort Quicksort Shellsort Merge sort with a cutoff n = 8,192, random input 5 on the frontier, 5 dominated
time-space-frontier4 essays
block transfers In order, 0 to n−1 1,024 1.0× a scan · 64.0 elements per transfer Every B-th element (B = 64) 65,536 64.0× a scan · 1.0 elements per transfer Uniformly at random 61,407 60.0× a scan · 1.1 elements per transfer a scan of this array is 1,024 transfers B = 64, M = 4,096 (M/B = 64) 64× between the cheapest order and the dearest
transfer-cost10 essays
root, priority 0.965 1.0 0.0 priority key 24 keys, sorted insertion, seed 20260810 height 8 against an ideal of 4
treap-shape1 essay
sorted insertion — height 62 shuffled insertion — height 10 truncated at depth 16 63 keys, identical set, different arrival order 62 deep against 10
tree-shape4 essays
+1 −1 keys, most frequent first Σ s(x)·f(x) = 9,034 squared: 81,613,156 true F2: 36,931,352 121.0% out a polynomial of degree 4 · cash-register model · counts exact one register, 32 bits
tug-of-war-run3 essays
Count-Min 4×64 exact 184 under 16 over rms 42 Count-Sketch 4×64 -174 -87 0 87 174 99 under 101 over rms 13 general turnstile · insertions and deletions, counts may go negative · counts exact 8,192 bits each
turnstile-errors3 essays
comparisons swaps Insertion sort 63,071 / 0 Selection sort 130,816 / 504 Bubble sort 129,688 / 62,563 Merge sort 3,964 / 0 Heapsort 7,653 / 4,170 Quicksort 5,049 / 2,380 n = 512, random input counted in the same run
two-counts21 essays
10⁵ 10⁶ 10³ 10⁴ 10⁵ comparisons cache misses (modelled) Insertion sort Selection sort Bubble sort Merge sort Heapsort Quicksort, first Quicksort, median-3 Quicksort, random Shellsort Merge + cutoff fully associative · 64 lines × 8 elements · LRU a modelled count, not a time
two-quantities4 essays
0 4 8 16 24 32 characters every key shares operations 0 72,581 145,162 Character comparisons Radix sort, characters read Element comparisons one unit = one character comparison element comparisons constant at 3,955
two-units1 essay
16 32 64 128 256 1024 4096 window length W, in arrivals (D = W × the mean gap) share of the counts they disagree on even Poisson bursty drifting 1 ms clock · mean gap 10 ticks · 30,000 arrivals even: 0% at every length
two-windows5 essays
10³ 10⁴ 1 10 100 10³ n pointer hops per find neither path compression union by rank both 3n random unions, seeded α(n) ≤ 4 for every n on this axis
union-find-paths1 essay
0 0 1 0 0 0 0 0 0 1 0 root 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 00 0 1 01 0 0 10 one box = one bit · left child 0, right child 1 5 symbols, 217 bits
wavelet-tree6 essays
3,600 — the window opens 4,000 — now 32 16 16 16 8 8 4 the window edge 215 in buckets −16 for the oldest = 200 true 200 0.3% out sliding-window model · ε = 0.2, k = 5 · 1,764 merges 406 bits against 400
window-buckets4 essays
1,000 10³ window length W, in arrivals bits of state held W bits, exact ε = 0.2 ε = 0.1 ε = 0.05 sliding-window model · 40,000 arrivals · state from the shape of the structure 2,808 bits at W = 8,000
window-cost3 essays
even stream duration, in 1 ms ticks block, in order drifting · 100 Hz · 1 ms clock 565 ms – 14.8 s, a factor of 26.1
window-resolution3 essays
0.1 bits of state held mean relative error exact, and no smaller m = 32 m = 64 m = 128 m = 256 m = 512 windowed HyperLogLog window 4,096 · 8 sample times · truth held apart 8,505 bits exact
window-saving2 essays
adjacency scans relaxations queue comparisons visits Breadth-first 132,912 Dijkstra, all V queued 330,440 Dijkstra, binary heap 204,687 Bellman–Ford, all passes 135,313,312 Prim 202,711 Kruskal 790,734 V = 512, E = 66,200, dense, fixed density every segment counted exactly
work-components8 essays
0% 25% 50% 75% 100% 64 512 4,096 65,536 cache holds 512 array size n (elements) miss rate fully associative · 64 lines × 8 elements · LRU 20,000 random accesses per point
working-set10 essays
elements of block written per key inserted B-tree, in place 49.3 Log-structured, T = 2 3.0 · 16× less than the tree Log-structured, T = 4 2.0 · 25× less than the tree Log-structured, T = 8 1.0 · 49× less than the tree Log-structured, T = 16 1.0 · 49× less than the tree B = 64, M = 4,096 (M/B = 64) 25× between the two structures at T = 4
write-amp4 essays