Fuse Shufti four-way AND reduction

perfloop/casei · DATA PARALLEL GAP

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

Verdict

VERIFIED · settled 2026-08-13 · merged as tsenart/casei#3

What happened: The paired measurements met the required improvement.

Hypothesis

The accepted Case-insensitive multi-pattern lookup path reaches `casei.pairShuftiSkip64` from `casei.Matcher.Find` through the Shufti filter path. The directed source locality is the AVX-512 64-byte assembly kernel selected after the existing feature and input-length guards.

The proposed mechanism is an associative byte-mask reduction. The current reduction is claimed to chain AND operations before testing the result; a ternary-logic instruction may combine three inputs and leave the final test against the fourth input. The expected benefit is reduced reduction uops on executions that select this kernel. The actual instruction sequence and throughput effect remain a hypothesis until disassembly and hardware measurement confirm them.

Prove the change by disassembling both kernels and benchmarking the runtime-gated AVX-512 path across realistic input sizes and matcher tiers on the target Ice Lake and Sapphire Rapids hosts. The check must show identical match results and a reduced cycles-per-64-byte-block or end-to-end lookup cost, without regression when the guarded fallback paths are selected.

Change to test: Replace the four-way lookup-mask AND reduction in the AVX-512 Shufti kernels with an equivalent ternary-logic reduction and test it against the fourth lookup. Preserve tables, loads, loop structure, masks, and runtime feature gating.

Where it lives

perfloop/casei · matcher.go

Evidence

pure-pair Shufti non-ASCII miss 1KiB AVX-512 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 596.2 567.3 −4.9% (−29.5) −45.3 to −14 < 0 PASSED

pure-pair Shufti non-ASCII miss 64KiB AVX-512 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 8603 6757 −21.6% (−1862) −1929 to −1814 < 0 PASSED

pure-pair Shufti short scalar guard 64B · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 462 465 −0.3% (−1.25) −8 to +9 ≤ 20 PASSED

pure-pair Shufti AVX2 fallback miss 64KiB · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 31522 31577 −0.5% (−170) −571 to +876 ≤ 2000 PASSED

pure-pair Shufti scalar fallback miss 64KiB · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 914436 938630 +3.1% (+28545) −10406 to +43981 ≤ 50000 PASSED

field multi N512 hazard miss 64KiB AVX-512 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
x_vs_best 0.5036 0.3949 −21.8% (−0.1099) −0.1152 to −0.1038 < 0 PASSED
candidate_vector_bits 512 512 0 0 to 0 ≥ 0 PASSED

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

Timeline