How ReadOnlySpan<char>.IndexOf finds a substring with SIMD
This article walks through how the .NET 10 runtime's ReadOnlySpan<char>.IndexOf finds a substring using SIMD vector instructions. The author compares it with a naive loop in a BenchmarkDotNet run and explains where the speed difference comes from. It is a useful deep dive for developers who care about string search performance.
Key points
- Comparison is ordinal, working on UTF-16 code units rather than culture-aware rules.
- In the late-match case on a 65,536-char text, the naive loop averaged 134.935 µs versus 5.653 µs for IndexOf.
- The runtime's SpanHelpers.IndexOf uses a vectorized candidate filter and then verifies the full substring.
- Numbers come from .NET 10.0.12 on an AVX2 host; other runtimes and CPUs may choose different paths.
- KMP and Boyer–Moore–Horspool are compared in a supplementary section at the end.
A benchmark compares a hand-written substring loop with ReadOnlySpan<char>.IndexOf on .NET 10.0.12. On one AMD EPYC host, the built-in call was about 24 times faster for a late match in a 65,536-character text. The author stresses that this reflects one machine and one input set, and that the two methods use different algorithms.
The runtime path in SpanHelpers.IndexOf uses vectorized comparisons over 16-bit char lanes to filter candidate starts, then verifies each survivor against the full needle. The article walks through a small example showing how two chosen needle positions prune candidates. For most code, the takeaway is to use the span API for substring search, and to measure custom algorithms such as KMP on real data.
Real-world use
- A log parser that scans large files for the first occurrence of an error marker.
- A high-throughput protocol or message parser that searches for a fixed delimiter or header.
- Benchmarking a custom search routine against the built-in span API before adopting it.
Why it matters
In hot string-search paths, relying on the built-in span API instead of a hand-written loop can yield a large speedup. Still, the gain depends on hardware, runtime version and input, so measure with your own data before rewriting code.