internal/bytealg, strings, bytes: vectorize Index for arm64 with NEON

Background

internal/bytealg.Index/IndexString back strings.Index/Contains and bytes.Index/Contains. index_amd64.s has vectorized substring search using PCMPEQB/PMOVMSKB (SSE2) and VPCMPEQB/VPMOVMSKB (AVX2). index_arm64.s is fully scalar — zero NEON (V-register) instructions. This looks like an isolated gap rather than systemic neglect: sibling primitives in the same package (Count, Equal, IndexByte) already have NEON ports on arm64.

Note that arm64 does not fall back to the naive two-pointer Go implementation — index_arm64.go has its own tuned MaxBruteForce/Cutover constants, so the existing scalar assembly is already reasonably tuned for the architecture. The baseline to beat is decent scalar code, not a naive fallback. The most recent tuning pass on this file was CL https://go-review.googlesource.com/c/go/+/662415 (2025, @vleonen, reviewed by @randall77 and @cherrymui) — it wasn't tracked by an issue of its own, so this one isn't a "follow-up" in the tracker sense, just a continuation of the same file/effort.

Proposed change

Add a NEON fast path, used when the haystack has at least 16 valid start offsets (len(a)-len(b) >= 15); shorter inputs keep using the existing scalar code.

PMOVMSKB (pack the top bit of each byte lane into a scalar bitmask) has no direct NEON equivalent. The approach used here: broadcast the needle's first and last bytes, VCMEQ 16 consecutive haystack start offsets against both anchors in parallel, VAND the two comparison masks, and narrow the resulting byte-lane mask (0x00/0xff per lane) to a 64-bit nibble mask with VSHRN $4. Because each lane's mask ends up in bits [4L, 4L+4), RBIT+CLZ finds the lowest matching lane directly (bit index >> 2 is the lane).

When a 16-lane block has more than one anchor-matching candidate, a second vectorized pass (two more anchor bytes, b[1] and b[len(b)-2]) prunes bulk false-positive blocks before falling through to scalar per-candidate verification. An earlier version without this pass regressed adversarial inputs (haystacks engineered so both anchor bytes recur often, e.g. "ababab..." against a needle starting/ending in a/b) by 50–228%, confirmed by profiling the scalar per-candidate loop; a version that always ran the refine pass fixed that but taxed the common single-candidate case by ~10ns on Cortex-A72, so single-candidate blocks skip straight to verification. Verification chunk widths are sized per needle-length class (2/4/8/4×8 bytes) so every load is provably within [&a[0], &a[len(a)]); no lane masking, MTE-specific handling, or Android-specific 16-byte-alignment workaround is needed anywhere (unlike IndexByte), because the final 16-lane block is always positioned so all 16 candidate offsets are valid.

A related bug found while benchmarking (update: already fixed elsewhere)

internal/bytealg.Cutover on arm64 was 4 + n>>4. internal/stringslite.Index's own Rabin-Karp fallback threshold (fails >= 4+i>>4) is checked immediately after the Cutover check in the same loop iteration, so fails > Cutover(n) could never be satisfied before fails >= 4+n>>4 also became true — bytealg.IndexString was unreachable from strings.Index on arm64, independent of this change (the pre-existing scalar kernel was equally unreachable). amd64 is unaffected (its Cutover formula, (n+16)/8, sits strictly below the Rabin-Karp threshold already); bytes.Index is unaffected (it has its own haveFastIndex-gated loop, structured differently from stringslite.Index).

That diagnosis was right, but the fix landed elsewhere first: CL https://go-review.googlesource.com/c/go/+/807360, merged independently before this CL rebased past it, fixes the identical defect generically for every architecture — it adds an explicit n <= bytealg.MaxLen guard that makes the Cutover and Rabin-Karp branches structurally exclusive in stringslite.Index, rather than retuning any one platform's Cutover value. That makes arm64's originally-proposed Cutover retune (3 + n>>4) redundant, so the CL now leaves Cutover unchanged at 4 + n>>4 and relies on 807360 for reachability. Mentioned here for the record since it changes the shape of this proposal from "two independent fixes" to "one kernel plus a reachability fix that already shipped."

Benchmarks (updated for patchset 4)

benchstat, -test.count=6, measured against current master (which already includes CL 807360, so reachability is equal on both sides of the comparison — see above). Cross-compiled and run on Neoverse-N1 (Ampere Altra, oracle) and Neoverse-V1/V2/V3 (Graviton3/4/5, c7g/c8g/c9g.medium). All deltas below are p=0.002 (Mann-Whitney, n=6) unless noted.

	N1	Graviton3 (V1)	Graviton4 (V2)	Graviton5 (V3)
bytealg.IndexString calibration matrix (geomean)	−60.6%	−56.3%	−59.3%	−64.0%
strings suite (geomean)	−54.3%	−41.1%	−44.2%	−48.4%
bytes suite (geomean)	−59.9%	−50.5%	−52.7%	−50.9%

Highlights from the strings/bytes test suites (realistic call shapes, not the synthetic calibration matrix):

• IndexHard1 (short absent needle, <>, over a large haystack): −86%/−78%/−80%/−80%
• IndexPeriodic2 (periodic false-positive-heavy haystack): −86%/−78%/−80%/−80%
• bytes.Index/4M (4MiB haystack, absent needle): −91%/−85%/−87%/−80%

Caveats:

• The tiniest scalar-path calls (single-digit-nanosecond) get slightly slower (+2–5%) from the added entry branch that decides scalar-vs-SIMD.
• Graviton3's IndexPeriodic16 shows +18% — the same shape of anomaly an earlier patchset root-caused, on a different core (N1), as a code-layout artifact rather than a logic difference. Not re-derived from scratch for this specific core, so flagged rather than asserted with the same confidence.
• Everything else is flat within noise or improved. (The A72-only adversarial regression and Graviton4-baseline-variance caveats from the previous benchmark round no longer apply — this round's kernel and comparison methodology are both different; not carrying forward stale caveats without re-verifying them.)

Disclosure

The implementation, tests, and benchmarking described above (and in the CL) were produced by Claude (Anthropic), under my direction and review; I take responsibility for the contribution. Any questions about the code or data are mine to answer.

CL: https://go-review.googlesource.com/c/go/+/809280 — patchset 4, addressing Keith Randall's review (verify-chunk simplifications for the 2-3 and 4-8 byte needle classes, naming/latency nits) and the Cutover/807360 correction above.