Skip to content

PATTERN Cited by 1 source

Run-length encoded lookup table

Intent

Compress a sparse lookup table by exploiting the observation that adjacent entries often share the same delta/operation, encoding them as runs (start, end, stride, delta) rather than individual entries. This reduces both storage and search time.

Mechanism (casefold instance)

Unicode case-fold entries within a 64-codepoint page are stored as runs rather than per-codepoint entries:

  • Contiguous runs: A–Z all fold with delta +32 → one run covers 26 entries
  • Alternating runs: Latin Extended has every-other-codepoint patterns (0x0100, 0x0102, 0x0104...) → one run with stride=2 covers dozens of entries
  • 1-bit stride flag: Covers both contiguous (stride=1) and alternating (stride=2) cases

This collapses 1,484 individual folds into 238 runs across 59 pages (~4 runs per page on average).

Encoding

Each run is two bytes: - RUN_END_LOW[i] = end & 0x3F — the scan key (used for SWAR search) - RUN_START_STRIDE[i] = (start & 0x3F) | ((stride − 1) << 6) — read only on hit

Because keys are single clean bytes, 8 can be loaded into a u64 for parallel SWAR comparison. Runs within a page are sorted by end, so the first match in the SWAR scan is the correct run.

Design lineage

The range-with-delta encoding (including the stride trick) is adapted from Go's unicode package, whose CaseRange records store Lo/Hi ranges plus per-case deltas with an UpperLower sentinel for alternating blocks. The casefold crate splits runs at page boundaries so no run straddles two pages.

(Source: sources/2026-07-31-github-dont-stop-early-case-folding-source-code-at-memory-speed)

Seen in

Last updated · 607 distilled / 1,851 read