03 · Writing
Engineering Notes
~1606 min of readingDeep dives into systems, ML, and data engineering. Search, filter, or browse.
Deep Dives
longest readsPostgreSQL 18 Skip Scan, Measured: Skip Arrays, a Missing Increment That Doubles Descents, and Two Cliffs at One Value per Leaf Page
Who Ran While You Waited? Culprit-Attributed CPU Contention on Stock Kernels
Range as a Key: Why Cloud Block Store Indexes Are a Memory Problem
vAttention: Dynamic KV Cache Allocation Without Breaking Virtual Contiguity
Latest
newest firstOct 16, 2026
AE Chunking, Solved Exactly: A 256-State Recursion, e^γ Instead of e−1, and Why Real Text Overshoots by 16%
A new ICDE 2027 benchmark of content-defined chunking finds that the standard horizon formula for Asymmetric Extremum (AE), h = µ/(e−1), produces chunks 13–39% smaller than intended. The authors call exact analysis impractical and calibrate by simulation. I show a 256-state backward recursion that gives the exact mean in microseconds and reproduces their simulated horizons (348 and 793). Its continuum limit says the formula is wrong even on continuous values: the constant is e^γ ≈ 1.781, not e−1. On this blog's own markdown, AE overshoots by 16% for a reason the byte histogram cannot explain.
Oct 16, 2026
Quake's Recall Estimator Works Because Its Geometry Is Off: Caps in d/2, a 1/e Ceiling, and a Split Example That Needs α < 0.51
Quake (OSDI '25) chooses nprobe per query by estimating recall from hyperspherical cap volumes, with no offline tuning. On SIFT1M I reproduce its Table 5 to within a point of recall. The released code computes cap volumes with sqrt(1−t²) where the textbook formula has 1−t², which is exactly the volume in 64 dimensions instead of 128. That error is what makes the estimator calibrated: the textbook formula delivers 78% recall at a 90% target. The same audit finds a 1/e ceiling on the first-partition estimate and a split example that only commits when α < 0.509. Measured α is 0.67–0.83.
Oct 15, 2026
PostgreSQL 18 Skip Scan, Measured: Skip Arrays, a Missing Increment That Doubles Descents, and Two Cliffs at One Value per Leaf Page
PostgreSQL 18 lets a B-tree on (a, b) answer WHERE b = 7700 by skipping through every distinct a. I read the nbtree source and measured PG 18.6 on 4M-row tables across 10 to 1M distinct leading values. Descents come out at exactly ndistinct + 2. Types without skip support pay 2·ndistinct + 1. The planner and the executor both give up at about one distinct value per leaf page. At that point a skip scan that kept descending would still have been 1.7× faster.
Oct 14, 2026
CPython's Tail-Call Interpreter on an M3 Pro: Collapsing 212 Dispatch Branches to 8 Costs Nothing, and preserve_none Only Shows Up on the Slow Path
Python 3.14 added an interpreter built from tail-calling C functions. The first benchmarks claimed 10-15%. Later work traced most of that to an LLVM 19 regression that merged computed-goto dispatch, which put the real gain at 1-5%. I built a 214-opcode toy VM in three dispatch styles and ran it on an Apple M3 Pro. Forcing the dispatch from 212 indirect branches down to 8 changed nothing, while switch dispatch lost about one cycle per opcode. preserve_none left the fast path byte-for-byte identical and only made the slow path cheaper.
All Posts
by dateOct 16, 2026
AE Chunking, Solved Exactly: A 256-State Recursion, e^γ Instead of e−1, and Why Real Text Overshoots by 16%
A new ICDE 2027 benchmark of content-defined chunking finds that the standard horizon formula for Asymmetric Extremum (AE), h = µ/(e−1), produces chunks 13–39% smaller than intended. The authors call exact analysis impractical and calibrate by simulation. I show a 256-state backward recursion that gives the exact mean in microseconds and reproduces their simulated horizons (348 and 793). Its continuum limit says the formula is wrong even on continuous values: the constant is e^γ ≈ 1.781, not e−1. On this blog's own markdown, AE overshoots by 16% for a reason the byte histogram cannot explain.
Oct 14, 2026
CPython's Tail-Call Interpreter on an M3 Pro: Collapsing 212 Dispatch Branches to 8 Costs Nothing, and preserve_none Only Shows Up on the Slow Path
Python 3.14 added an interpreter built from tail-calling C functions. The first benchmarks claimed 10-15%. Later work traced most of that to an LLVM 19 regression that merged computed-goto dispatch, which put the real gain at 1-5%. I built a 214-opcode toy VM in three dispatch styles and ran it on an Apple M3 Pro. Forcing the dispatch from 212 indirect branches down to 8 changed nothing, while switch dispatch lost about one cycle per opcode. preserve_none left the fast path byte-for-byte identical and only made the slow path cheaper.
Oct 14, 2026
Infini-gram on 360k Tokens: The ∞-gram Ties the 5-gram Exactly, Long Matches Are a Symptom Rather Than a Cause, and Backoff Costs 1.95 Counts per Token
Infini-gram (COLM 2024) turns a suffix array into an n-gram LM with unbounded n. On trillion-token corpora it agrees with human text on 47% of tokens, against 29% for a 5-gram. I rebuilt it from scratch on this blog's own posts. At 360k tokens the ∞-gram and the 5-gram score exactly the same 16.9%, because the effective n is at most 5 for 91.5% of tokens. Even where long matches exist, the 5-gram is right just as often. The incremental backoff costs a measured 1.95 counts per token, and a two-line argument bounds it at 2.
Oct 14, 2026
SOAP: Adam in Shampoo's Eigenbasis — Rebuilt, Measured, and One Redundant Rotation Per Step
SOAP (ICLR 2025) runs Adam inside the eigenbasis of Shampoo's Kronecker preconditioner. I rebuilt it in NumPy and PyTorch. The paper's Shampoo/Adafactor equivalence checks out to 1.2e-12. On a rotated quadratic, Adam's loss gets 7.6× worse and SOAP recovers almost all of it. On a char-level LM trained on this blog, SOAP beats Adam by 0.07 nats but sits within seed noise of grafted Shampoo, and neither degrades from f=1 to f=100. The paper's per-step overhead formula charges m³ where the work is m²n. The reference code rotates the first moment out of the eigenbasis and back every step, which is 2 of its 5 per-step matmul blocks; skipping that makes the optimizer step 1.65× faster.
Oct 12, 2026
Do You Need the 'H' in HNSW? Flat Graphs, Hub Highways, and Where the Distance Computations Actually Go
An ICML 2025 workshop paper finds that a flat navigable small-world graph matches HNSW on 13 high-dimensional benchmarks, and argues that hub nodes form a 'highway' that does the hierarchy's job. In my own 50k-point simulation the flat graph matches HNSW to within 2% at every d ≥ 8, including on the uniform sphere, which has no hubs at all. The upper layers account for just 6–9% of distance computations there, so the hierarchy has little left to save.
Oct 12, 2026
SuperBPE on a 1.3 MB Corpus: Superword Tokens Cut 21% of Tokens In-Domain, Half That Out of Domain, and My Section Headings Became Vocabulary
SuperBPE (COLM 2025) trains BPE in two stages: subwords first, then merges that are allowed to cross whitespace. I reimplemented it and trained it on this blog's own posts. At a 16k vocabulary it needs 20.9% fewer tokens than BPE on held-out posts, but only 10.9% fewer on npm READMEs. The transition point that is best in-domain is close to the worst out of domain. The paper's 4-word cap had no effect on encoding efficiency, and it also failed to stop the tokenizer from learning my post template ('.\n\n## What the') and markdown table rules as tokens.
Oct 11, 2026
Aleph Filter: Growing a Quotient Filter Forever in O(1), and the Generation-Zero Term Its FPR Bounds Miss
Aleph Filter (VLDB 2024) lets a quotient filter double indefinitely without the original keys and keeps every query to one hash table by duplicating fingerprints that have run out of bits. I rebuilt its expansion logic as an exact bucket simulator. The fixed-width FPR matches Eq. 2 to two decimals. The widening and predictive bounds come in 1.3× and 1.4–1.7× too optimistic because the initial generation is twice as large as the model assumes and three generations around the target size get the same fingerprint length. One extra bit fixes the first. The longest-match delete rule holds: 0 false negatives against 536 for the shortest-match rule.
Oct 11, 2026
Breaking the Sorting Barrier for SSSP: A Working BMSSP, Pivots That Almost Never Fire, and the Tie-Break That Prevents a Livelock
Duan, Mao, Mao, Shu and Yin's O(m log^(2/3) n) directed SSSP algorithm (STOC 2025 best paper) is the first to beat Dijkstra in the comparison-addition model. I implemented it in Python and checked it against Dijkstra. It gets every distance right on graphs up to 384k vertices, using 6.6× Dijkstra's edge relaxations. FindPivots took its early exit in 849 of 850 calls on random graphs and in all 1,263 on grids. Removing FindPivots entirely cuts relaxations by 21% without any wrong answers. Dropping the paper's tie-breaking order livelocks the algorithm on the zero-weight cycles that its own constant-degree transform creates.
Oct 10, 2026
Driftsort: Rust's Stable Sort Ignores Runs Shorter Than √n, and Gets 45% Slower Just Above It
Since Rust 1.81, slice::sort is driftsort: powersort's merge policy, glidesort's lazy runs, and a branchless stable quicksort, with a √n entry threshold for pre-sorted runs. I ported its top-level loop to Python and measured the real std sort on an M3 Pro. Comparison counts match the port exactly (10.00, 9.00, 7.00 per element). But at n = 2^18, input made of sorted runs of 512 elements takes 31.0 ns/element, while runs of 511 take 21.3. Detecting the runs halves the comparisons and adds 45% to the time. I also found a counterexample to the source comment claiming its integer merge-depth trick reproduces the exact powersort tree for n < 2^30.
Oct 10, 2026
SynthID-Text's Tournament Watermark: 2^30 Candidates Become One Line per Layer, and the 10→1 Weights Are 99% Optimal
SynthID-Text (Nature, 2024) watermarks LLM output with a 30-layer knockout tournament over sampled tokens, but the reference code never samples a candidate. Each layer is the closed-form tilt p·(1 + g − G). I verified the tilt against a literal tournament, derived how it concentrates the distribution, and ran the watermark end to end on Qwen2.5-0.5B. Per-layer signal falls 6× from layer 1 to layer 30. The default 10→1 weights capture 99.1% of the optimal signal-to-noise ratio, and the plain mean needs 25% more tokens.