Skip to content

GITHUB 2026-07-31

Read original ↗

Don't stop early: Case-folding source code at memory speed

Summary

GitHub's code search engine Blackbird indexes 180 million repositories (480 TB of source code), case-folding every byte before ngram extraction and at query time. This post describes how they made simple Unicode case-folding run at memory bandwidth (~45 GiB/s on Apple M4) for the ASCII fast path by removing an "optimization" — the early-exit branch on non-ASCII bytes — and how the non-ASCII path avoids full codepoint decode via a 1,776-byte lookup table that performs folds as little-endian byte-space arithmetic. The result is open-sourced as the casefold Rust crate.

Key takeaways

  1. Early-exit branches gate vectorization. A break on the first non-ASCII byte prevents LLVM from auto-vectorizing the loop, even if the loop body is perfectly branchless. Removing the break — and accumulating the non-ASCII signal into a single high_bit_acc |= *b tested after the loop — enables full SIMD vectorization: 3.1 GiB/s → 45+ GiB/s on the same hardware.

  2. Branchless is a pessimization in scalar code; it wins only via vectorization. Making the loop body branchless while keeping the early-exit break is slower than naive branches (2.6 vs 3.1 GiB/s) because it replaces a rarely-taken conditional store with an unconditional store on every byte. The branchless body pays off only when it unlocks SIMD, at which point stores become 16-byte vector writes and per-byte cost vanishes.

  3. Two fast branchless passes beat one branchy fused pass. A "fused" approach — scan 16-byte chunks for ASCII and convert each chunk inline — clocks 8.7 GiB/s vs the two-pass 23 GiB/s (scan-then-convert). The data-dependent exit every 16 bytes prevents unrolling/pipelining across blocks, making the fused loop pay full load→test→branch→convert→store latency per block.

  4. Zero-allocation on the common path. simple_fold takes a String by value, mutates in place for ASCII-only or non-folding multibyte input, and returns the same allocation. A second buffer is allocated only when a fold changes byte length (two Unicode outliers: U+023A and U+023E grow from 2→3 bytes), pre-sized at 1.5× input for worst-case with a raw write cursor and no capacity checks.

  5. 1,776-byte lookup table eliminates codepoint decode. Unicode 16.0's 1,484 simple folds are compressed into a paged-bitmap (59 active "pages" of 64 codepoints), cumulative-popcount side table, and run-length-encoded entries (238 runs). Negative test (no fold) is a single bit test from the UTF-8 lead byte without decoding. Within-page search uses SWAR (8-byte-at-a-time comparison) to find the matching run in one step.

  6. Fold as byte-space addition — decode-free. The folded character's UTF-8 bytes, read as a u32, equal the source bytes plus a per-run constant delta. This avoids both UTF-8 decode and re-encode — believed to be novel; every other folder inspected (ICU, Go, Rust regex, CPython, glibc) decodes to a codepoint first. Requires well-formed shortest-form UTF-8 (guaranteed by Rust's &str).

  7. 9.6 bits per fold entry — vs ~70 KB for regex-syntax, ~11.6 KB for naïve array, ~17 KB for HashMap. Table fits in L1 cache; hot-path never leaves the data cache.

  8. Operational numbers: Pure ASCII throughput >45 GiB/s; CJK/no-folds ~2.95 GiB/s; worst-case all-folding Latin/Greek/Cyrillic ~869 MiB/s; length-changing folds ~1.26 GiB/s. All on Apple M4.

Architectural insights

  • The scale driver: Blackbird indexes 480 TB of source code. Case-folding runs on every byte at index time and implicitly at query time. At that volume, even a "basic" operation at 3 GiB/s vs 45 GiB/s is a meaningful infrastructure cost difference.

  • Source code is ASCII-dominated. This workload characteristic means the ASCII fast path isn't a special case — it's the common case (overwhelming majority of bytes). Designing for it to hit memory bandwidth is the single most impactful optimization.

  • Run-encoding borrows from Go's unicode package. The CaseRange Lo/Hi/delta design with an UpperLower sentinel for alternating runs is adapted and split at 64-codepoint page boundaries for the bitmap lookup.

Caveats

  • Benchmarks are on Apple M4 (ARM NEON) only; ratios shift on different microarchitectures (x86 AVX2/AVX-512, wider/narrower vector units, different memory bandwidth).
  • Only simple (1-to-1) folds are supported — not full folds (ß → ss) or Turkic locale folds. This matches ripgrep's behavior.
  • Byte-space arithmetic assumes valid shortest-form UTF-8; overlong encodings would produce incorrect results.
  • No fleet-wide performance numbers from Blackbird production deployment disclosed.

Source

Last updated · 607 distilled / 1,851 read