Compile pattern set for one shared traversal
perfloop/casei · INEFFICIENT ALGORITHM
https://perfloop.ai/t/oss/case_9r9ntnxjd1
Verdict
VERIFIED · settled 2026-08-12 · merged as tsenart/casei#1
What happened: The paired measurements met the required improvement.
Hypothesis
The accepted source trace has casei.Matcher.Find calling casei.IndexFold for each configured pattern, so a Find invocation repeats the single-pattern haystack scan as pattern count N grows. The submitted claim proposes compiling fold-orbit transitions once and advancing all patterns in one haystack traversal, preserving leftmost and tie semantics plus Unicode and invalid-byte behavior. This is structural only: neither dominance versus fold work nor a crossover cardinality has been measured. Confirm or reject with the arena bar across pattern counts, haystack sizes, hits, and misses on both tiers; collect a CPU profile attributing time to Find's repeated scan path; and run casei_test.go differentials for the stated semantics. Reject if the shared traversal cannot beat the per-pattern scan on multi-pattern rows without using a field engine.
Change to test: Replace Find's per-pattern IndexFold loop with a package-owned compiled plan built by NewMatcher, so Find advances all configured patterns during one haystack traversal and IndexFold uses the same plan for its N=1 case while retaining existing semantics.
Where it lives
perfloop/casei · matcher.go
Evidence
full native BenchmarkBar matrix (33 rows) · 10 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
max_x_vs_best |
6.718 |
0.9123 |
−86.6% (−5.816) |
−6.177 to −5.67 |
< 0 |
PASSED |
Checks: 11 of 11 passed. Verification: no defect found.