SIMD substring search for CPython (str/bytes) — 4–8× on large inputs

Status: a proposed patch, not merged into CPython. This is an independent benchmark + patch, shared for discussion and review. It has not been submitted to or accepted by CPython. See Honest limitations and Status below before drawing conclusions.

A ~60-line patch to CPython's Objects/stringlib/fastsearch.h that adds a vectorised (NEON on ARM, SSE2 on x86-64) forward substring search and count for byte-width strings. Multi-byte-needle search in str.find, str.index, str.count, str.replace, str.split, the in operator, the re module's literal prefilter, and all the bytes/bytearray equivalents currently has no SIMD — only a scalar Bloom/Horspool loop and Crochemore–Perrin two-way.

Result (measured, Apple M1 Pro, CPython built from source at

b86a41cbf631c959d274ad6180cf0a0ac6f6e180)

bytes.count over a 60 MB corpus of real text + code, per needle:

needle	baseline	patched	speedup
import (6B)	1.50 GB/s	11.17 GB/s	7.4×
function (8B)	1.81 GB/s	13.60 GB/s	7.5×
PyObject_ (9B)	2.29 GB/s	15.74 GB/s	6.9×
return value (12B)	2.25 GB/s	10.37 GB/s	4.6×
def __init__(self (17B)	3.43 GB/s	15.70 GB/s	4.6×
NULL pointer dereference (24B)	3.83 GB/s	16.72 GB/s	4.4×

Median ~4.6×. str.count on UCS1 (ASCII/Latin-1) strings is the same. in, .replace, .index on large inputs see the same win (they share the search).

How it works

The classic "first byte + last byte" filter (glibc memmem, ripgrep memchr::memmem, StringZilla): a match can only begin where both needle[0] and needle[m-1] line up, so one 16-byte vector compare rejects 16 candidate start positions at once, and only survivors are verified with a short compare.

Worst-case guarantee preserved. Against adversarial needles (e.g. "aaab" in "aaaa…") where the first+last filter matches everywhere, the routine falls back to CPython's existing O(n) two-way algorithm once verification work grows disproportionate — mirroring the existing adaptive_find. So the linear worst-case bound the CPython maintainers care about is kept.

Correctness

• 220,000+ differential fuzz iterations, 0 failures — patched str/bytes .find and .count vs an independent naive reference, on adversarial periodic haystacks up to 25 kB (which exercise overlapping candidates, the non-overlapping count semantics, and the >2000-position adaptive fallback). Reproduce: ./python.exe bench/fuzz_correctness.py.
• CPython's own suite passes: test_bytes, test_str, test_re, test_capi, plus string-heavy stdlib tests test_difflib, test_email, test_json, test_html, test_urllib, test_tokenize, test_configparser, test_csv — all green.
• No small-string regression: the SIMD path only engages for haystacks ≥ 64 bytes and needles ≥ 2 chars; below that the existing scalar path is unchanged.

Honest limitations

• The win is scan-bound, i.e. it helps searching large strings/buffers (log lines, documents, file contents, x in big_text, .count/.replace over big text, re literal prefilters on big inputs). Short-string operations — a .split() on a 60-byte line — are dominated by allocation/interpreter overhead and see little change; the search itself is already sub-microsecond there.
• The technique is not novel. The first+last SIMD filter is used by glibc, ripgrep and StringZilla. What is new here is bringing it into CPython's own str/bytes, with the two-way fallback that keeps CPython's worst-case guarantee, plus a rigorous differential-correctness and benchmark harness.
• Portability. The SIMD path is enabled at compile time for the two ISAs that are baseline on their 64-bit targets and therefore need no runtime CPU detection: NEON on aarch64 (GCC/Clang __ARM_NEON) and SSE2 on x86-64 (GCC/Clang __SSE2__, and MSVC x64 via _M_X64 with a _BitScanForward shim). This covers Linux/macOS x86-64 and arm64 and 64-bit Windows. Wider ISAs (AVX2, SVE) would need the runtime feature detection being built in python/cpython#125022 and are intentionally out of scope. Every other compiler/target falls through to the existing scalar path unchanged.
• The SSE2 (x86) path is correctness-validated but not speed-validated on native x86. A standalone harness (bench/simd_selftest.c) reproduces the exact _simd_find logic and passes ~200,000 differential fuzz cases for both the NEON build (native arm64) and the SSE2 build (cross-compiled -arch x86_64, run under Rosetta 2) — so the x86 code path provably finds and counts correctly. Native-hardware throughput for x86, and a build on MSVC itself, still need real x86 / Windows machines; Rosetta timings are emulated and not representative. A maintainer or CI run on x86/Windows is the one remaining measurement.
• Wide strings (UCS2/UCS4 str — any non-Latin-1 content) are unchanged; the patch targets the 1-byte-char case (bytes, bytearray, ASCII/Latin-1 str), which is the common case in practice.

Files

• fastsearch_simd.patch — the patch against Objects/stringlib/fastsearch.h.
• bench/benchmark.py — the throughput benchmark (build the corpus per the note inside).
• bench/fuzz_correctness.py — the differential correctness fuzzer.

Reproduce

git clone --depth 1 https://github.com/python/cpython
cd cpython && ./configure && make -j
./python.exe ../bench/benchmark.py corpus.txt      # baseline
git apply ../fastsearch_simd.patch && make -j
./python.exe ../bench/benchmark.py corpus.txt      # patched
./python.exe ../bench/fuzz_correctness.py          # 0 failures

Status

Not submitted. External publication / a CPython PR requires the operator's approval and an x86 benchmark run.