Russian matcher construction rescans literals for every anchor triple

perfloop-oss/casei · INEFFICIENT ALGORITHM

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

Verdict

VALIDATED BY A DIFFERENT CHANGE · settled 2026-10-13 · merged as tsenart/casei#38

What happened: The paired measurements met the required improvement.

Hypothesis

Compiling the documented five-pattern Russian matcher repeatedly scans identical literal ranges while trying three-anchor combinations. This work dominates sampled CPU in a fresh matcher-construction workload. Revised construction time remains unmeasured, and retained searches do not pay this cost.

The benefiting API is NewMatcher at revision 89bf471b1031bb767db0bced96b8afd5b49769d1. The exact input comes from the pinned curated/02-literal-alternate/sherlock-casei-ru row in audit/rebar/runner/testdata/rows.tsv:4, not from a synthetic pattern distribution. The adapter parses that alternation and calls NewMatcher in audit/rebar/runner/main.go:57–61. Its five literals total 133 bytes and 69 runes. Their compact-plan and two-to-eight-pattern guards pass. Compilation runs once per matcher setup. README.md:165–168 recommends reuse, and REBAR.md:129–137 explicitly excludes construction from retained scan timing. This proposal adds no public API and makes no Rebar scan-win claim.

For each pattern whose unit collection and enumeration complete, makeRawByteMultiAnchorFilter tries C(m,3) triples of eligible positions, with m bounded by 16. CandidateFor rejects a primary at byte zero before width expansion; failed prefix or confirmation checks skip later work. In the successful pinned compilation, the eligible-position counts are [8,4,8,11,11]. A counter-instrumented NewMatcher invocation observed 446 candidate trials, 783 width-generator calls and 3,776 rune visits. These are counts for that input and completion path, not bounds on every invocation.

The repeated results have separate dependencies: start widths depend only on the primary position; confirmation widths depend on the primary and confirmation positions; guard widths depend on the primary and guard positions. Shared confirmation admission depends only on confirmation offsets. The score adds the three independent pair costs. For a fixed primary/confirmation pair, only the cheapest feasible later guard can win; equal guard costs retain the earliest guard. This permits pairwise selection without changing the existing preference for fewer confirmation offsets, lower score, later primary, and first encountered remaining ties.

CPU receipt call_E0faqtoms7cXiAqSItN7stYB ran BenchmarkPerfloopPinnedCyrillicNewMatcher, reading the pinned row and calling public NewMatcher for each fresh compilation. Grouped pprof attribution shows rawByteMultiAnchorPrefixWidths at 2.58 seconds inclusive and 0.75 seconds flat out of 3.79 seconds sampled CPU: 68.1% and 19.8%. The enclosing anchor compiler accounts for 73.1% inclusive. These shares describe this repeated-compilation receipt, including runtime activity, not production frequency or elapsed time per call.

The temporary TestPerfloopAnchorSelectionFactorization retained the original width generator and compared exhaustive selection with shared interval results and suffix-minimum guard selection. All 776 checked pattern decisions agreed across 204 compact plans, including 105 usable filters. Selected anchors also matched the public constructor's anchors where usable. For the pinned five-pattern case, width calls fell to 139 and rune visits to 766. That establishes a removable work delta, not an implemented optimization or measured speedup. If width CPU roughly tracks visits and added state costs little, the counts suggest roughly half of this receipt's total CPU could be removed. That estimate remains unmeasured.

The required Case comparison is the receipt's complete public NewMatcher compilation on the pinned five-pattern input, measuring CPU, ns/op and allocations against the unchanged baseline. Reject the performance claim if whole-operation cost does not fall. Independently compare complete compiled filters and public Find/Each results, exact widths, ordering and callback stopping. Regression controls should cover width-changing folds, equal-score ties, shared confirmation limits, position/width caps and rejected shapes. The probe does not prove every boundary or final state-propagation implementation. Confidence is medium; deployment-wide setup frequency and benefits after matcher reuse remain unknown.

Change to test: Replace exhaustive anchor-triple rescans with bounded per-primary width-state propagation, per-unit costs, and pairwise selection using the cheapest feasible later guard. Keep the change internal and preserve exact candidate tie order, shared confirmation admission, compiled filter contents and fallback decisions, immutable plans, and all Find/Each results and source widths.

Where it lives

perfloop-oss/casei · plan.go

Evidence

Pinned Russian NewMatcher construction · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 364068 82968 −77% (−280194) −291094 to −276687 < −18203 PASSED
cpu-ns/op 357253 96575 −73.2% (−261500) −274967 to −246372 ≤ 17863 PASSED
B/op 41778 41776 −0.5 −2 to 0 ≤ 2089 PASSED
allocs/op 371 371 0 0 to 0 ≤ 18.55 PASSED

Checks: 10 of 10 passed. Verification: no defect found.

Timeline