Vectorize multi-byte substring search in stringlib/fastsearch.h (SSE2/NEON, ~4–8× on large inputs)

[Amacfa]

Proposal

FASTSEARCH in Objects/stringlib/fastsearch.h uses memchr for single-character search (which libc vectorizes), but every needle of length ≥ 2 goes through the scalar Bloom/Horspool default_find/adaptive_find or the two-way algorithm. None of the ≥2-char paths is vectorized.

On an Apple M1 Pro, bytes.count of a multi-byte needle over a 60 MB text/code corpus runs at 1.5–3.8 GB/s, while single-byte count runs an order of magnitude faster. The same gap shows up in str.find/.index/.count/in/.replace/.split and the re module's literal prefilter, for bytes, bytearray, and ASCII/Latin-1 str.

I have a small patch that adds the standard "first byte + last byte" SIMD filter (as used by glibc memmem, Rust's memchr::memmem, and StringZilla): one vector compare rejects 16 candidate start positions at once, and only survivors are verified. It's behind a tiny _simd_mask16 helper with a NEON and an SSE2 implementation.

Measured (M1 Pro, bytes.count, 60 MB corpus): median 4.6×, range 4.4–7.5×. str on ASCII/Latin-1 is the same. Patch + benchmark + fuzzer: https://github.com/Amacfa/cpython-simd-substring

It keeps the O(n) worst-case guarantee

The concern with a first+last filter is adversarial input (e.g. "aaab" in "aaaa…"), where the filter matches everywhere and naive verification is O(nm). The patch handles this exactly like the existing adaptive_find: once verification work grows disproportionate it falls back to the current two-way implementation (thanks @sweeneyde for that). So the linear worst-case bound is preserved; SIMD only accelerates the common case.

Correctness

• ~220,000 differential-fuzz iterations vs a naive reference (bytes and str, find and count, adversarial periodic haystacks up to 25 kB that exercise overlapping candidates, the non-overlapping count semantics, and the two-way fallback) — 0 failures.
• A standalone harness reproducing the exact _simd_find logic passes for both the NEON build (native arm64) and the SSE2 build (cross-compiled, run under Rosetta), so both code paths are correctness-checked.
• test_bytes, test_str, test_re, test_capi, and string-heavy stdlib tests (test_difflib/email/json/html/urllib/tokenize/configparser/csv) pass.

Portability / scope

• Enabled only for ISAs that are baseline on their 64-bit target and so need no runtime detection: NEON on aarch64, SSE2 on x86-64 (GCC/Clang __SSE2__ and MSVC _M_X64, with a _BitScanForward shim). Everything else — other compilers/targets and the UCS2/UCS4 str representations — falls through to the current scalar path unchanged.
• Wider ISAs (AVX2, SVE) would benefit more but need runtime feature detection; those are intentionally out of scope here and would build on Provide detection for SIMD features in autoconf and at runtime #125022.
• The SIMD path engages only for m ≥ 2 and n ≥ 64, so short strings are untouched and unregressed.

Honest limitations

• The win is scan-bound — it helps searching large inputs. Short-string operations are dominated by interpreter/allocation overhead and change little; this is not an across-the-board speedup of all string ops.
• The technique is not novel; the contribution is the CPython integration + the worst-case fallback + the correctness harness.
• I've only benchmarked NEON on real hardware. The SSE2 path is correctness-checked but its throughput on native x86, and a build on MSVC itself, are unmeasured by me.

What I'm asking

1. Is there appetite for SIMD in fastsearch.h, or a known reason it's been avoided (portability, maintenance, the two-way worst-case contract)?
2. Could someone run the benchmark on native x86 / Windows? That's the one measurement I can't produce.
3. If the direction is welcome, I'll clean it up into a PR (and sign the CLA) — guidance on the n ≥ 64 dispatch threshold and whether the fallback heuristic should exactly match adaptive_find's constants would help.

Disclosure: this patch and its benchmark/fuzz harness were developed with AI assistance and then verified as described above (differential fuzzing + the CPython test suite); the linked repo's commit history reflects that. Happy to iterate on any of it.

[picnixz]

There are already issues about this and we do not want for now to include aSIMD. Look also at closed issues when searching for prior work.