Sapphire Rapids: Scan interior ASCII windows before recovering variable-width prefixes

perfloop/casei · DATA PARALLEL GAP

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

Verdict

VERIFIED · settled 2026-09-27 · merged as tsenart/casei#20

What happened: The paired measurements met the required improvement.

Hypothesis

A caller can use the documented one-needle `IndexFold` or `ContainsFold` operations, or retain `NewMatcher([]string{"Sherlock Holmes"})` and use `Find` or non-overlapping `Each` on a UTF-8 text field. A singleton ASCII needle with a simple-fold prefix that can take a wider UTF-8 spelling, followed by at least three ASCII-only-fold bytes, is an ordinary case-insensitive text-search shape. Its runtime cost on Intel Sapphire Rapids model 143 with AVX-512F/BW/VBMI is unmeasured.

The anchored construction route is `casei.NewMatcher` at `matcher.go:34` to `casei.newSearchPlan`, then `casei.searchPlan.makeASCIIAnchor` at `plan.go:956`. `makeASCIIAnchor` advances only through a leading ASCII prefix whose whole `unicode.SimpleFold` orbit remains ASCII, and declines the anchor when that prefix is shorter than three bytes (`plan.go:1023-1045`). `findWithWidth` reaches `findASCIIAnchor` only when the resulting probe is usable. Thus an initial width-changing fold can prevent the existing block probe even when a later interior span is safe.

The proposed data-parallel gap is in the later retained-plan search, not in compilation itself. Without a compiled interior window, long clean ASCII spans cannot use the existing no-high-byte-stop block probe for this shape and must take another exact-search route. A fixed interior window could classify those blocks independently and send only survivors to the common plan confirmation, but it must recover the true source start rather than treat the interior-byte position as an offset.

On model 143, first measure probe selection, survivor count, exact-confirmation count, and fallback work for a retained singleton matcher scanning a representative natural-language UTF-8 field with `Sherlock` or `Sherlock Holmes`. Then run alternating-order paired full-operation measurements of `NewMatcher(...).Each`, with construction performed once and the matcher retained for the field scan. Differential fuzzing must cover portable and feature-enabled builds, malformed UTF-8, fold variants, tails, periodic input, source widths, leftmost order, and `Each` behavior. Equivalent results without a material survivor/confirmation reduction, any semantic mismatch, or no paired full-field saving falsifies the claim.

Change to test: On Intel Sapphire Rapids model 143 with AVX-512F/BW/VBMI, for N=1 ASCII literals of at most 64 units, compile one static ASCII-only-fold interior window of at least three units after a width-changing prefix. Reuse the existing no-high-byte-alarm probe for that window. Before exact confirmation, verify that its first ASCII byte is a source boundary and recover the candidate through the fixed prefix; never return `windowByte-u` as the true offset. Keep common-plan exact confirmation authoritative for leftmost order and source widths, reject malformed prefix units, and leave every other route unchanged without adding an alternate engine. Validate selectivity and source equivalence before the paired model-143 full-field timing.

Where it lives

perfloop/casei · matcher.go

Evidence

Pinned Rebar 463d00f31887e84c38467805b9e3122c314b9521 curated/01-literal/sherlock-casei-en: the 899232-byte UTF-8 opensubtitles/en-sampled field (sha256 0d40805f6d02c8fe02bd75945b98911891f707e8ecb939e018446858065d76ea) and Sherlock Holmes singleton. The runner verifies 522 ordered Each matches and a source-width sum of 7830 before timing; one Matcher is retained and the full-field Each count operation is timed, with construction and preflight outside timed work. Host: Intel family 6/model 143 with AVX-512F/BW/VBMI. · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 209238 80637 −61.5% (−128636) −130055 to −126884 < −10462 PASSED
MB/s 4298 11152 +159.7% (+6862) +6754 to +6919 ≥ −214.9 PASSED

Pinned Rebar 463d00f31887e84c38467805b9e3122c314b9521 imported/sherlock/name-sherlock-casei: the 594933-byte UTF-8 sherlock.txt field (sha256 242ec73a70f0a03dcbe007e32038e7deeaee004aaec9a09a07fa322743440fa8) and Sherlock singleton. The runner verifies 102 ordered Each matches totaling 816 source bytes before timing; one Matcher is retained and the full-field Each source-width sum is timed, with construction and preflight outside timed work. Host: Intel family 6/model 143 with AVX-512F/BW/VBMI. · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 43319 24556 −43.6% (−18893) −19133 to −18372 < −2166 PASSED
MB/s 13734 24229 +76.9% (+10561) +10130 to +10751 ≥ −686.7 PASSED

Pinned Rebar 463d00f31887e84c38467805b9e3122c314b9521 imported/sherlock/name-sherlock-holmes-casei: the 594933-byte UTF-8 sherlock.txt field (sha256 242ec73a70f0a03dcbe007e32038e7deeaee004aaec9a09a07fa322743440fa8) and Sherlock Holmes singleton. The runner verifies 96 ordered Each matches totaling 1440 source bytes before timing; one Matcher is retained and the full-field Each source-width sum is timed, with construction and preflight outside timed work. Host: Intel family 6/model 143 with AVX-512F/BW/VBMI. · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 46478 27082 −41.8% (−19436) −19729 to −19003 < −2324 PASSED
MB/s 12801 21968 +71.7% (+9182) +9087 to +9263 ≥ −640 PASSED

Pinned Rebar 463d00f31887e84c38467805b9e3122c314b9521 curated/01-literal/sherlock-casei-ru: the 1570556-byte UTF-8 opensubtitles/ru-sampled field and Russian singleton. The runner verifies 746 ordered Each matches and their source widths before timing; one Matcher is retained and the full-field Each count operation is timed, with construction and preflight outside timed work. This is the named Russian regression guard on Intel family 6/model 143 with AVX-512F/BW/VBMI. · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 125419 123735 −1.7% (−2119) −4176 to +519 ≤ 6271 PASSED
MB/s 12523 12693 +1.7% (+216.1) −51.85 to +425.6 ≥ −626.1 PASSED

Pinned Rebar 463d00f31887e84c38467805b9e3122c314b9521 opt/prefilter/literal-casei-russian: the 613423-byte UTF-8 opensubtitles/ru-huge field and Russian singleton. The runner verifies one ordered Each match and its source width before timing; one Matcher is retained and the full-field Each count operation is timed, with construction and preflight outside timed work. This is the named Russian regression guard on Intel family 6/model 143 with AVX-512F/BW/VBMI. · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 24212 23979 −0.8% (−202.5) −362 to +329 ≤ 1211 PASSED
MB/s 25336 25582 +0.8% (+214.2) −350.1 to +381.2 ≥ −1267 PASSED

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

Timeline