Skip to content
① prose 12,335 12 ① code 13,150 8 ① revisions 7,774 10 ② essays 12,335 82 ② captions 230 2,214 ② history 12,963 14 documents characters in a document ① the first freeze · ② the second median marked
many-documents6 essays
characters examined Naive scan 20,862 1.04 per text character Knuth–Morris–Pratt 20,833 1.04 per text character Boyer–Moore–Horspool 2,985 0.15 per text character Rabin–Karp 8 0.00 per text character one unit = one character comparison 2607.8× between best and worst
match-cost4 essays
1 10 100 10⁴ patterns in the set characters Aho-Corasick: 20,000, always characters examined positions ever read patterns of 8 over four symbols · answers identical crossing at 8 patterns
matcher-set2 essays
one read per text character 2 4 8 16 32 64 95 alphabet size, m = 8 characters read ÷ text length 0.0 1.1 2.2 Naive scan Knuth–Morris–Pratt Boyer–Moore–Horspool one unit = one character comparison · n = 20,000, m = 8 Horspool's best here: 0.132 per character
matcher-sweep2 essays
one summary, k = 32 769 one summary, k = 256 0 8 summaries of 32, merged 536 worst error over the top keys, in arrivals concentration 1.00 — the mean share of a heavy key held by one shard 8 shards · hashed · balanced merge 536 against matched 0
merge-against-matched4 essays
round 967 0 Space-Saving · 967 Misra-Gries · load 6 hashed 606 509 Space-Saving · 97 Misra-Gries · load 55 blocked 967 0 Space-Saving · 967 Misra-Gries · load 6 the sum of the shard floors, in arrivals stationary Zipf · 8 shards · k = 32 one bill, two ways of splitting it
merge-bill4 essays
HyperLogLog 1024/1024 identical Count-Min 256/256 identical bottom-k 128/128 identical Misra-Gries 20/36 identical fraction of the state that merged to the identical value → 1,974 → 10,291 → 2,322 → 8,766 two streams of 30,000 · 2,007 distinct keys in the union 3 of 4 merge exactly
merge-check2 essays
Space-Saving, predicted 537 Space-Saving, measured 536 Misra-Gries, predicted 154 Misra-Gries, measured 152 worst error over the top keys, in arrivals the shard floors sum to 606 — the whole bill, before it is split 8 shards · hashed · k = 32 predicted from 8 histograms
merge-damage-predicted4 essays
quantile promised one summary merge of 8 q = 0.5 100.0 14 18 q = 0.9 20.0 18 3 q = 0.99 2.0 0 5 over q = 0.999 0.2 1 4 over rank error, in items out of 20,000 ε = 0.01 · high-biased · 8 shards, round 2 of 4 quantiles over the single summary's promise
merge-quantiles6 essays
key truth folded tree reversed 1 6,362 6,866 6,869 6,869 2 3,074 3,578 3,581 3,581 3 1,963 2,467 2,470 2,470 4 1,373 1,902 1,907 1,954 5 1,098 1,602 1,605 1,605 6 935 1,512 1,471 1,463 7 769 1,280 1,285 1,306 8 656 1,160 1,163 1,163 9 566 1,100 1,101 1,095 10 510 1,051 1,036 1,029 shaded rows are keys whose count depends on the order alone Space-Saving, k = 32 · 8 shards · hashed 37 keys move with the order
merge-shape5 essays
stack depth, peak 7 runs pushed, in order 0 4,096 128 runs 127 merges peak 7 four-entry rule elements pending, by run
merge-stack2 essays
Count-Min 8,192 bits Count-Sketch 8,192 bits tug-of-war, F2 2,560 bits Greenwald–Khanna 0 bits exponential histogram 0 bits cash register + strict turnstile ± general turnstile ± may go negative sliding window + expires declared declared 93% under — declared declared declared — declared declared declared — declared — — — — — — declared 40,000 updates · deletion rate 0.5 · every count exact 1,758 of 1,895 under
model-check4 essays
H0 H1 H2 H3 H4 model order — symbols of context bits per symbol 0.0 2.1 4.2 Uniform over 8 symbols Order-1 Markov chain Words from a fixed vocabulary 32,768 symbols · at H4 the deepest source has 709 contexts, 0 seen once models: orders 0, 1, 2, 3, 4 2.06 bits found by one symbol of context
model-order5 essays
10 100 10 B (elements per block) block transfers per search tuned for B = 64 Sorted array B-tree tuned for B = 64 van Emde Boas — told nothing M = 16,384, B as drawn one layout, 7 block sizes, no parameter
oblivious-across-b1 essay
10³ 10⁴ 10⁵ 10⁶ passes over the data peak bits of state one pass, exact: 1,048,576 bits radix, uniform sample, uniform radix, pareto sample, pareto every point exact · 32,768 values 320 bits at best
pass-state3 essays
text position i phi(i) anchor: a run start 25 of them a text that repeats itself · 4 copies of 32 r = 26 · pieces 24
phi-locate3 essays
1,000 10,000 10⁴ bits 1 2 4 8 16 32 characters in the collection · copies above FM-index, compressed r-index phrase index English-like · divergence 0 z 156 · r 233
phrase-index7 essays
i s · h o l d s · n o · t h e · t h e · o f · o f · r a t h e r · c o u n t · c l a s s · t h a t · i s · a l g o r i t h m · o 1 1 1 1 1 1 1 2 1 1 1 1 1 1 5 1 1 4 1 1 3 1 1 1 1 1 1 1 2 1 1 1 2 2 2 1 3 1 1 1 1 1 1 2 1 2 phrase lengths below each block · a shaded block is a literal English-like · 64 characters z = 46 · 17 literals
phrase-parse7 essays
"t than" 8 found · set 8 · frontier 4 "of her" 7 found · set 7 · frontier 4 " that " 16 found · set 16 · frontier 11 " every" 31 found · set 31 · frontier 19 "the ev" 8 found · set 8 · frontier 4 "o of c" 8 found · set 8 · frontier 5 " than " 15 found · set 15 · frontier 9 "ime ra" 7 found · set 7 · frontier 4 the visited set, pale; the sweep's frontier, dark 17,715 phrases examined either way 1.67x on what is held
phrase-sweep6 essays
first-element pivot 130,816 on sorted median of three 5088 mean random pivot 4937 mean blue bar: range over 400 random inputs · marker: the already-sorted input n = 512 a bad case that cannot be chosen is a different kind of bad case
pivot-rules4 essays
least recently used the offline optimum A loop over 7 blocks 35 accesses 35 11 3.18× Random over 7 blocks 35 accesses 9 7 1.29× A straight sweep 35 accesses 35 35 1.00× B = 8, M = 48 (M/B = 6) 3.2× on the loop
policy-gap1 essay
shard 1 · 120 → 119 shard 2 · 121 → 120 shard 3 · 120 → 120 shard 4 · 121 → 120 shard 5 · 119 → 118 shard 6 · 124 → 123 shard 7 · 121 → 120 shard 8 · 122 → 121 floor, in arrivals naive: tail ÷ k fixed point measured stationary Zipf · round · k = 32 1.006× the measured floor
predicted-floor7 essays
1 2 3 4 5 6 0.00 0.25 0.50 0.75 formula measured load factor α probes per insertion 8,192 slots, mean of 8 fills, seeds stated in lib/structures.js two routes agree to 2.3%
probe-count8 essays
10 100 1,000 10⁴ 10⁵ characters of pattern in the set characters examined no shift (step one) bad character only the 1979 shift functions both rules, exactly four symbols · patterns of 10 n = 20,000
published-shift8 essays
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5 q = 2 23 21 19 17 15 13 q = 3 22 19 16 13 10 7 q = 4 21 17 13 9 5 1 q = 5 20 15 10 5 0 -5 q = 6 19 13 7 1 -5 -11 q = 8 17 9 1 -7 -15 -23 a shaded cell is a threshold of zero or less: every window proposed t = m + 1 − q(k+1) · m = 24 7 collapsed cells
qgram-filter4 essays
1,000 10,000 2 4 8 16 32 64 ε = 0.02, α = 0.58 ε = 0.01, α = 0.56 ε = 0.005, α = 0.54 tuples kept shards merged log-normal, σ = 1.2 — a latency distribution · 20,000 values α 0.58 / 0.56 / 0.54 · worst residual 2.0%
quantile-tuples4 essays
10,000 100 characters of text primitive operations suffix array + text counter array per symbol FM-index, plain FM-index, compressed every query run with the text withheld English-like
query-cost6 essays
mean 4945 99th 6030 4,282 5,413 6,543 comparisons runs 600 independent random inputs, n = 512 worst run 1.32× the mean
quicksort-spread6 essays
10³ 10⁴ 10³ 10⁴ 10⁵ n random bits skip list, one build — n reservoir, Algorithm R — n log n reservoir, Algorithm L — log n n from 256 to 16,384 bits charged including rejections
randomness-consumed4 essays
answered 2,170 0% 25% 50% 75% 100% 0.364 20.5 2,170 value, logarithmic fraction of the stream at or below rank ±2% value 187–2,170 answered 581.7% out 20,000 values · log-normal, σ = 1.2 — a latency distribution · Greenwald–Khanna, ε = 0.02 rank 1.00% · value 581.7%
rank-against-value7 essays
even 1.00× / 1.00× Poisson 1.16× / 1.21× bursty 1.00× / 1.14× drifting 26.14× / 17.69× upper: W arrivals, duration varies · lower: D milliseconds, count varies 4,096 arrivals in 8 blocks · 100 Hz matched at the block, not at the window
rate-sizing2 essays
twelve essays repeats a vocabulary 1.26x eight source modules repeats a form 3.12x ten revisions of one file repeats almost everything 3.76x generated, matched one length by construction 1.00x document length · the ratio of longest to shortest at the right 24,576 characters a part 3.76x at the widest
real-corpus5 essays
— b c a b — a b c a 63 88 32 8 1 88 63 25 7 1 32 25 13 5 1 8 7 5 3 1 1 1 1 1 1 one unit = one invocation of the recurrence 481 calls, 25 distinct subproblems
recursion-dag3 essays
one column per clause; filled means this half fails it vars 1..3 vars 4..6 #0 0 1 1 1 0 0 0 0 #1 1 1 1 1 0 0 0 1 #2 0 0 0 0 1 0 0 0 #3 1 0 0 0 1 0 0 1 #4 0 1 0 1 0 1 1 0 #5 1 1 0 1 0 0 1 1 #6 0 0 0 0 1 1 1 0 #7 1 0 0 0 1 0 1 1 #0 0 1 1 0 0 1 0 0 #1 0 0 1 0 0 1 0 0 #2 0 0 0 0 1 1 0 1 #3 0 0 0 1 0 1 0 1 #4 0 1 1 0 0 0 1 0 #5 1 0 1 0 0 0 0 0 #6 0 0 0 0 1 0 1 0 #7 1 0 0 1 0 0 0 0 rows #0 and #2 fill no clause in common first 8 of 8 rows each side · 8 clauses satisfiable
reduction1 essay
1 10 100 k, the operators after the alternation states its DFA: 512 its NFA: 30 a literal's DFA: 11 alphabet ab 2^(k+1), exactly
regex-machine6 essays
1,000 10,000 10³ 10⁴ bits · runs 1 2 4 8 16 32 characters in the collection · copies above n·H₃, bits r, runs in the transform English-like · base 512 · divergence 0 n·H₃ x15.8 · r x1.00
repeat-size4 essays
k/n = 0.125 0.081 0.125 0.169 position in the stream share of runs in which it was sampled Algorithm R, n = 32, k = 4, 40,000 runs worst departure 3.3% · noise 1.4%
reservoir-frequency1 essay
0 10 20 30 40 1e+4 2e+4 3e+4 values in the array reads a query the segment tree succinct 80 queries a size 2.49x apart
rmq-work4 essays
all 4,096 texts of 12 characters over 2 symbols 2 runs 2 0.0% 3 runs 25 0.6% 4 runs 127 3.1% 5 runs 396 9.7% 6 runs 738 18.0% 7 runs 990 24.2% 8 runs 916 22.4% 9 runs 554 13.5% 10 runs 256 6.3% 11 runs 77 1.9% 12 runs 13 0.3% 13 runs 2 0.0% 2 symbols · exhaustive 4,096 texts
run-floor2 essays
1,000 10,000 10⁴ 10⁵ characters in the collection bits FM-index, plain FM-index, compressed run-length index sample one in 64 · divergence 0 · r = 224 11,900 bits at 32 copies
run-index4 essays
1,000 10,000 10³ 10⁴ bits 1 2 4 8 16 32 characters in the collection · copies above regular, one in 32 run boundaries, 2r English-like · divergence 0 r = 233 at n = 16,385
run-sampling5 essays
1 10 100 10³ 10⁴ 10⁵ 10⁶ 10⁷ natural runs r in the input comparisons n / minrun = 256 Timsort Merge sort Insertion n + n log₂ r n = 8,192, runs built exactly comparisons, counted exactly
runs-and-cost2 essays
a loop over the alphabet 1,478,400 the compound walk, inside the loop 134,400 11x one descent per node 18,916 78x 6 patterns · 1 error · sigma 21 55.8% of the extensions were dead
savings-ladder6 essays