Replace hot Unicode token-map probes with a compiled classifier

perfloop/casei · DEPENDENT LOAD CHAIN

https://perfloop.ai/t/oss/case_jr9bkjn25q

Verdict

CLOSED · opened 2026-08-17

What happened: Closed; the settled verdict is recorded on the case.

Hypothesis

I traced the `casei.Matcher.Find` general fallback at `plan.go:2318` through `findUnfiltered` and `findNonASCII` to `(*searchPlan).haystackToken` at `plan.go:1897`. The non-ASCII loop invokes this method for each candidate token before it advances the plan state.

The submitted report says that, on losing Russian Unicode rows, pprof attributes 58.65% cumulative CPU to `haystackToken` and 41.63% to `runtime.mapaccess1_fast32`. Every surviving UTF-8 candidate is decoded and then probes `searchPlan.runes` before the dense state transition. The reported profile and comparison to PCRE2 JIT and Hyperscan motivate the hypothesis; source alone does not prove that the decode/map chain is latency-bound or not hidden by instruction-level parallelism.

Confirm with a reproducible Russian Unicode run that this route executes across relevant candidates, the per-rune disassembly exposes a serial dependent lookup chain, and the proposed classifier reduces cost without changing invalid UTF-8 or matching behavior. Compare portable and AVX-512 implementations on the stated Rebar and BenchmarkBar rows and CPUs.

Change to test: Compile the plan's finite folded-rune alphabet into a cache-local classifier selected by measured alphabet shape, such as a bounded direct range/page table with a sparse fallback, and make haystackToken avoid Go map lookup on the hot path. Keep invalid UTF-8 bytes opaque and preserve the existing token/state-machine semantics. Inspect generated assembly and pursue AVX-512 byte classification only where it improves the exact rows. Accept only after portable and AVX-512 differential fuzz, the three losing single-pattern Rebar rows beat their fastest correct entrant, and the full BenchmarkBar remains below its field bar on both Ice Lake and Sapphire Rapids.

Where it lives

perfloop/casei · matcher.go

Evidence

Timeline