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

[lizthegrey]

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.

[gopherbot]

Change https://go.dev/cl/809280 mentions this issue: internal/bytealg: add NEON implementation of Index for arm64

[lizthegrey]

CL up for review: https://go-review.googlesource.com/c/go/+/809280

This builds directly on the existing arm64 Index/IndexString work in this file — @randall77 and @cherrymui reviewed the most recent optimization pass (CL 662415, by @vleonen) and Cherry also reviewed the two CLs before that (109895, 109015, by Eric Fang / erifan01@arm.com, who doesn't appear to have a linked GitHub account, so no handle to tag here). Added Keith and Cherry as reviewers on the CL and cc'd Vasily; happy to loop in anyone else who'd have useful context.

[gabyhelp]

Related Issues

• string.Index/bytes.Index can use SSE/AVX to speed searches for long substrs too #25186 (closed)

Related Code Changes

• internal/bytealg: add NEON implementation of Index for arm64
• bytes: add optimized Index for arm64
• bytes: add asm version of Index for short strings on arm64
• internal/bytealg: optimize Index for riscv64
• bytes: optimize IndexAny for ARM64 with NEON
• internal/bytealg: optimize IndexByte for riscv64
• internal/bytealg: optimize Index/IndexString/IndexByte/IndexByteString on arm64
• internal/bytealg: optimize Index (substring lengths from 9 to 32) on arm64
• internal/cpu,internal/bytealg: add SIMD prefix match for Index/amd64

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[gopherbot]

Change https://go.dev/cl/809500 mentions this issue: simd/archsimd: add arm64 CMTST, ShiftRightNarrow, ToBits, and Lookup2OrZero

[gopherbot]

Change https://go.dev/cl/809560 mentions this issue: internal/bytealg: add archsimd alternative for Index

[lizthegrey]

Patchset 2 of CL 809280 adds a second change to index_arm64.go: MaxBruteForce 16 → 64. Recording the data here rather than in the commit message.

bytes.Index/strings.Index reach the vector kernel two ways — len(s) <= MaxBruteForce, or fails > Cutover(i). With MaxBruteForce = 16, a haystack of 17–64 bytes only reaches the kernel if enough IndexByte false positives accumulate, which for a sparse leading byte never happens. So that window was effectively unvectorized regardless of the new kernel.

16 was correct for the scalar kernel, not stale. Giving the existing scalar kernel haystacks up to 64 bytes is a 2.2% overall loss on Neoverse-N1, decomposing by leading-byte density (fraction of haystack positions matching the needle's first byte):

density	1/2	1/8	1/26	1/64	1/240
scalar kernel, MBF 64 vs 16	−25.2%	−21.2%	+4.0%	+23.3%	+47.3%

It wins where the leading byte is common and loses badly where it's rare, which is a reasonable trade to have made in 2018. The NEON kernel wins that comparison at every density measured within the ≤64-byte window. It does not win everywhere: at larger haystacks with a sparse leading byte, IndexByte skipping is still ahead, which is exactly what puts a ceiling on this bound.

Why 64 and not higher. Aggregate keeps improving past 64, but the worst case grows with the bound, and on N1 its location is structural — len(s) == MaxBruteForce exactly, at the sparsest density, with no match: the longest haystack committed to a full vector scan when IndexByte would have skipped nearly all of it.

MBF	geomean	sparse-only (1/64 and rarer)	worst single shape
64	−19.6%	−6.9%	+5.3% (0.7ns, n=8 h=64 1/240 miss)
128	−42.1%	−17.7%	+28.2% (n=8 h=128 1/240 miss)
256	−53.3%	−25.8%	+62.6% (n=8 h=256 1/240 miss)

Neoverse-N1, strings.Index across builds; needles of 2/8/32 bytes, haystacks of 48–384 bytes, densities 1/2 through 1/240, no-match and match-at-end. The tail at 128 and 256 isn't worth the aggregate gain. 64 also matches amd64 and s390x, though that's corroboration rather than the reason.

Cross-microarchitecture check. Apple M4 was probed over a narrower slice — needles of 2 and 8 bytes, haystacks of 48–128, densities 1/2, 1/26 and 1/240 — so its geomeans (−35.4% at 64, −63.8% at 128) are over a different shape set and are not comparable to the N1 column above. What does compare is the failure point: at MBF=128 the worst shape on M4 is the identical one, n=8 h=128 1/240 miss, at +25.8% against N1's +28.2%. Two different microarchitectures degrading at the same structural point is better evidence than matching aggregates would be. Two limits on the M4 data: at MBF=64 its worst shape is only +1.0% and sits elsewhere (n=2 h=80, densest), too small to localize; and because its haystacks stop at 128, MBF=256 was never probed at its own boundary there.

Disclosed regression. On M4, Contains over a 24-byte haystack with an 8-byte needle and no match costs +8.5% to +13.4% across two runs (roughly 6.6ns → 7.4ns, under +1ns absolute, p≤0.002). That shape satisfies the kernel's len(a)-len(b) >= 15 check, so MBF=64 routes it to the kernel where 16 used the dispatch loop; M4's vector setup slightly exceeds the loop's early exit, while N1's does not — the same shape gains 22% on N1. Everything else in that family improves 11–63%.

Rejected: adopting amd64's Cutover slope. (n+16)/8 in place of arm64's 3 + n>>4 is 9.1% worse on its own. Combined with MBF=64 it is worse still: at 1/8 density the CL's slope is 38.9% faster, i.e. adopting amd64's costs 64% there. arm64 is the only vectorized arch not using (n+16)/8 and should stay that way. Only MaxBruteForce changes.

Application-shaped datapoint. Not a production measurement, but a benchmark whose payload sizes and needle lengths are taken from one: bytes.Contains over event attribute values in a columnar query engine's substring filter. The kernel alone is worth −25.8% there and the constant a further −9.1%, for −32.6% total on Graviton2; −29.4% → −33.6% on M4. The constant's contribution is entirely short attribute values in the 17–64 byte window, and it's the only reason 8-byte needles improve at all. Graviton2 shows no regression on any shape in it; M4 shows the one above.

Caveats. Unlike the kernel — measured on A72, N1, and V2 — this constant was tuned on N1 and M4 only; A72 and Neoverse-V2 are unverified for it. Benchmarking bytealg.IndexString directly against strings.Index embeds a fixed ~6.5ns call-frame tax in the latter, which dominates at small inputs and inverts conclusions; every number here compares strings.Index across builds instead, so that tax cancels. M4 runs are kept short because the machine is fanless — an initial one was discarded as thermally throttled, and the runs used here carry a first-vs-last-round drift check (median +0.03% across 60 shapes on the table above).

Co-authored-by: Claude Opus 5 noreply@anthropic.com

[lizthegrey]

We've done real-world testing of this by patching our go runtime before compilation, and we see, for the specific subset of our workload that is Contains, approx a 20% improvement.