Skip to content

PATTERN Cited by 1 source

Paged bitmap lookup

Intent

Provide a fast negative test for sparse lookups (e.g., "does this codepoint have a case-fold?") by partitioning the key space into fixed-size "pages" and maintaining a one-bit-per-page bitmap. A clear bit definitively answers "no" without consulting any per-entry data — making the common case (no match) a single bit test.

Structure

┌─────────────────────────┐
│  PAGE_BITMAP (1 bit/page)│  → 248 bytes for Unicode
├─────────────────────────┤
│  POPCNT_SAMPLES          │  → cumulative popcount for page ranking
├─────────────────────────┤
│  PAGE_OFFSET             │  → byte offset to each page's runs
├─────────────────────────┤
│  RUN_END_LOW / START_STRIDE │ → per-run entries (2 bytes each)
├─────────────────────────┤
│  BYTE_DELTA              │  → fold constant per run
└─────────────────────────┘

Mechanism

  1. Page identification from raw UTF-8 bytes: The page index (word_idx) is derived from the lead byte (and first continuation byte for 4-byte sequences) without decoding the full codepoint. This allows the bitmap load to issue early.

  2. Bitmap test: (PAGE_BITMAP[word_idx] >> bit_idx) & 1. If zero → no fold on this page → copy through, done. This rejects ~97% of Unicode codepoints (1,900+ of ~1,960 pages are empty).

  3. Page ranking: On a set bit, a cumulative-popcount side table converts the page index to a dense rank (how many populated pages precede it), locating the page's slice of run entries.

  4. Within-page SWAR search: Load 8 run-end bytes into a u64, compare all 8 at once against the target via SWAR arithmetic. A single bit-scan finds the matching run. Average page has ~4 runs; one comparison suffices.

Size efficiency

1,484 Unicode simple-fold mappings compressed to 1,776 bytes total (9.6 bits per entry):

Component Bytes
PAGE_BITMAP 248
POPCNT_SAMPLES 32
PAGE_OFFSET 60
RUN_END_LOW (+8 pad) 246
RUN_START_STRIDE 238
BYTE_DELTA 952

vs naïve [(u32,u32); 1484] at ~11.6 KB, HashMap<u32,u32> at ~17 KB, or regex-syntax's table at ~70 KB.

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

Design principles

  • Optimize for the miss. The hot operation is "does this character fold?" — almost always no. The bitmap makes the negative test trivially cheap.
  • Never decode. Page index comes from raw UTF-8 lead bytes, not codepoints.
  • L1-resident. 1,776 bytes fits entirely in L1 data cache on any modern CPU.

Seen in

Last updated · 607 distilled / 1,851 read