How ReadOnlySpan<char>.IndexOf finds a substring with SIMD

Leia em português.

This article follows the video's sequence of ideas: the video animates the
states; here we can pause at each diagram and examine the code and assembly.
The walkthrough uses the same teaching example, separate from the measured
inputs. The opening result comes from a selected MediumRun, but still applies
to a particular machine and scenario. The KMP and BMH comparison at the end is
supplementary material, outside the main video.

1. The surprising result

A search written as a loop might seem cheaper than a call to a higher-level
API. To test that intuition, we compared two implementations that find the
first occurrence of a substring and return its index, or -1 if none exists.

Here is the result used in the opening: a 16-char substring inserted at the
end of a pseudorandom text containing 65,536 char elements.

Implementation	Mean per search	Standard deviation
Naive loop	134.935 µs	24.518 µs
ReadOnlySpan<char>.IndexOf	5.653 µs	389 ns

For this input and host, the loop's mean was approximately 23.9× the mean
for IndexOf. That is not a prediction for every string, CPU, or runtime
version. As we will see, the loop and runtime also use different algorithms;
this benchmark does not isolate the cost of abstraction alone.

2. The two implementations

The harness uses BenchmarkDotNet. The methods, inputs, configuration, and
instructions for putting together a reproduction are included in this
article. Each operation receives one ReadOnlySpan<char> for the text and
another for the needle. The comparison is ordinal: it compares UTF-16 char
code units without culture-sensitive rules. Both implementations return the
first occurrence's index, or -1 if there is no match. A .NET char is a
UTF-16 code unit, not necessarily a user-perceived grapheme.

The baseline implements naive, or brute-force, search: try every starting
position and compare the needle character by character. The second method
calls the runtime API. These two methods drive the main explanation:

private static int SearchNaive(
    ReadOnlySpan<char> haystack,
    ReadOnlySpan<char> needle)
{
    if (needle.IsEmpty)
        return 0;

    int lastStart = haystack.Length - needle.Length;
    for (int start = 0; start <= lastStart; start++)
    {
        int offset = 0;
        while (offset < needle.Length &&
               haystack[start + offset] == needle[offset])
        {
            offset++;
        }

        if (offset == needle.Length)
            return start;
    }

    return -1;
}

private static int SearchRuntime(
    ReadOnlySpan<char> haystack,
    ReadOnlySpan<char> needle) =>
    haystack.IndexOf(needle, StringComparison.Ordinal);

BenchmarkDotNet measures them through these wrappers:

[Benchmark(Baseline = true)]
public int Naive() =>
    SearchNaive(_haystack.AsSpan(), _needle.AsSpan());

[Benchmark]
public int ReadOnlySpanIndexOf() =>
    SearchRuntime(_haystack.AsSpan(), _needle.AsSpan());

The first wrapper measures the naive loop above. The second measures
ReadOnlySpan<char>.IndexOf with ordinal comparison. To explain the observed
path, we use the .NET 10.0.12 runtime implementation:
SpanHelpers.IndexOf(ref char, int, ref char, int) in
SpanHelpers.Char.cs.
On this host, it uses a vectorized candidate filter and checks candidates
against the complete substring. This is not our own search algorithm, nor a
guarantee that another runtime version or CPU will choose the same path.

Before timing, GlobalSetup runs all four methods for each input and requires
the expected result. For example, a scenario labeled "missing" cannot enter
the benchmark if a search finds an accidental occurrence. Validation happens
before measurement:

int naive = SearchNaive(_haystack.AsSpan(), _needle.AsSpan());
int expected = Scenario switch
{
    SearchCase.RandomEarlyMatch => 0,
    SearchCase.RandomMiddleMatch => HaystackLength / 2,
    SearchCase.RandomLateMatch or SearchCase.RepeatedPrefixLate =>
        HaystackLength - _needle.Length,
    SearchCase.RandomMissing or SearchCase.RepeatedPrefixMissing or
        SearchCase.RepeatedAlternatingLateFalse => -1,
    _ => throw new ArgumentOutOfRangeException(nameof(Scenario))
};

VerifyResult(nameof(Naive), naive, expected);
VerifyResult(nameof(KnuthMorrisPratt),
    SearchKnuthMorrisPratt(_haystack.AsSpan(), _needle.AsSpan()), expected);
VerifyResult(nameof(BoyerMooreHorspool),
    SearchBoyerMooreHorspool(_haystack.AsSpan(), _needle.AsSpan()), expected);
VerifyResult(nameof(ReadOnlySpanIndexOf),
    SearchRuntime(_haystack.AsSpan(), _needle.AsSpan()), expected);

The benchmark compares a scalar, character-by-character search with the
runtime's optimized implementation. It does not isolate API-call overhead.
The question is what work the algorithms perform, not whether a particular
syntax or abstraction is inherently faster. KMP and Boyer–Moore–Horspool
appear at the end as a complementary comparison, not a replacement for the
main explanation.

3. Inputs: what did we test?

The harness combines seven scenarios with texts of 4,096 and 65,536
char elements. Inputs are built once during setup, outside the timed region.

Scenario	Text and needle	Expected result
RandomEarlyMatch	Pseudorandom text over a–h; needle abcdefghabcdefgh inserted at index 0.	index 0
RandomMiddleMatch	Same generator and needle, inserted halfway through the text.	index HaystackLength / 2
RandomLateMatch	Same generator and needle, inserted into the final 16 elements.	index HaystackLength - 16
RandomMissing	Same generator and alphabet, without inserting the needle.	-1, checked in setup
RepeatedPrefixMissing	Text consisting only of a; needle aaaaaaab.	-1
RepeatedPrefixLate	Text consisting only of a, with aaaaaaab replacing the final eight elements.	index HaystackLength - 8
RepeatedAlternatingLateFalse	Alternating ab text; 64-element needle alternating for the first 63 elements and ending in a.	-1; false candidates differ at the final element

The pseudorandom generator is deterministic. It starts at 0xC0FFEE and
updates a 32-bit state for each position using
state = state * 1664525 + 1013904223. The top three bits select one of the
eight characters a–h:

private static string CreateOrdinaryHaystack(int length)
{
    const string alphabet = "abcdefgh";
    var chars = new char[length];
    uint state = 0xC0FFEE;
    for (int i = 0; i < chars.Length; i++)
    {
        state = (state * 1664525) + 1013904223;
        chars[i] = alphabet[(int)(state >> 29)];
    }
    return new string(chars);
}

In matching scenarios, the corresponding text segment is replaced with the
needle. For the late match used in the opening, this is equivalent to:

const string needle = "abcdefghabcdefgh";
string haystack = CreateOrdinaryHaystack(length);

int matchIndex = length - needle.Length; // RandomLateMatch
haystack = haystack[..matchIndex]
    + needle
    + haystack[(matchIndex + needle.Length)..];

The missing scenario keeps the same alphabet, avoiding a trivial miss caused
by impossible characters. Setup verifies that the complete needle is absent.

The adversarial benchmark scenario

This measured case differs from both the opening and the teaching example in
sections 6–7. The text alternates a and b. The needle also alternates, but
its final char is changed to a:

private static string CreateAlternatingNeedleWithLateMismatch()
{
    const int length = 64;
    return string.Create(length, 0, static (chars, _) =>
    {
        for (int i = 0; i < chars.Length; i++)
            chars[i] = (i & 1) == 0 ? 'a' : 'b';
        chars[^1] = 'a';
    });
}

The runtime uses the first char, a, and searches backward for the last
needle element that differs from it. Positions 63 and 62 contain a, so the
selected position is 61, containing b. Both filters pass at every even start:
haystack[i] == 'a' and haystack[i + 61] == 'b'. The complete substring,
however, differs at its final element: the text has b at relative position
63, while the needle has a.

Text length	Expected false candidates	Result
4,096	2,017	-1
65,536	32,737	-1

Setup checks a conceptual one-bit-per-lane summary, 0x5555, the expected
one-bit-per-byte extracted mask, 0x33333333, and the total candidate count.
The first summary is neither the comparison vector nor an intermediate
runtime variable: each approved lane contains FFFF. This is a scalar
validation of the fixture, not a reading of runtime registers.

4. Measurement and results

We used BenchmarkDotNet 0.15.8, Release builds, .NET 10.0.12 (SDK 10.0.401),
Ubuntu 24.04.4 Linux x64, and an AMD EPYC 7763 at 2.45 GHz. BenchmarkDotNet
reported one CPU available to the process. The host exposed AVX2 and BMI1;
the assembly capture discussed here comes from this environment.

Two lengths, seven scenarios, and four methods yield 56 method/case
combinations in the broad ShortRun matrix. These attributes configure it:

[ShortRunJob]
[MemoryDiagnoser]
[DisassemblyDiagnoser(maxDepth: 3)]
public class SubstringSearchBenchmarks
{
    [Params(4096, 65536)]
    public int HaystackLength { get; set; }

    [Params(
        SearchCase.RandomEarlyMatch,
        SearchCase.RandomMiddleMatch,
        SearchCase.RandomLateMatch,
        SearchCase.RandomMissing,
        SearchCase.RepeatedPrefixMissing,
        SearchCase.RepeatedPrefixLate,
        SearchCase.RepeatedAlternatingLateFalse)]
    public SearchCase Scenario { get; set; }
}

The broad matrix used ShortRun: three warmup iterations and three measurement
iterations. For the late-match and adversarial scenarios, we also ran
MediumRun: ten warmups, fifteen measurement iterations, and two processes
per benchmark. This table reports MediumRun means and standard deviations;
units have been converted for readability:

Input length	Scenario	Naive: mean ± standard deviation	IndexOf: mean ± standard deviation	Ratio of means
4,096	Late match, pseudorandom text	3.443 ± 0.238 µs	323 ± 15 ns	10.7×
65,536	Late match, pseudorandom text	134.935 ± 24.518 µs	5.653 µs ± 389 ns	23.9×
4,096	Many candidates, final-element mismatch	149.369 ± 57.317 µs	7.645 µs ± 390 ns	19.5×
65,536	Many candidates, final-element mismatch	1.925 ± 0.202 ms	129.186 ± 7.864 µs	14.9×

The adversarial scenario has substantial dispersion, particularly in the
naive loop. We therefore report dispersion alongside means rather than treat
it as a typical case. Nor do we attribute the entire gain to SIMD: the C#
baseline examines positions with a different algorithm from IndexOf, which
also uses vector instructions. The supported conclusion is narrower:
on this host, for these inputs, the runtime implementation was faster.

In the original run, validation compared IndexOf, KMP, and BMH against the
naive baseline across 34,193 deterministic cases: all binary strings up to
eight char elements and needles up to five, plus 2,000 generated inputs
containing diverse characters, including NUL and surrogate code units.
Coverage included empty needles, needles longer than the text, injected
matches, and missing substrings.

In the original capture, adding --job Medium to a class annotated with
[ShortRunJob] ran both jobs. The reported values come from Job=MediumRun
rows. The reproduction at the end uses only [MediumRunJob] to run the two
selected scenarios without repeating the ShortRun matrix.

The project pins RuntimeFrameworkVersion to 10.0.12 and disables
roll-forward. Its configuration and commands are included below, without
depending on files outside this article.

5. The idea behind SIMD

SIMD applies the same operation to multiple data elements. In the observed
path, those elements are 16-bit UTF-16 code units. A 256-bit vector holds
16 char lanes:

lane:  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
char: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

That does not mean the entire search takes one instruction. The vector selects
several possible starts for verification. The path still iterates over blocks,
processes masks, and checks the complete substring.

6. Finding candidates

A small input for following the calculations

We use the same teaching fixture as the video: a 64-code-unit needle
inserted at index 6 of a 79-code-unit text, filled with x outside that
segment. The needle alternates a and b, except for its final element, a.
This reproduces the input; it is not a timed benchmark scenario:

char[] value = new char[64];
for (int i = 0; i < value.Length; i++)
    value[i] = (i & 1) == 0 ? 'a' : 'b';
value[63] = 'a';

char[] text = new char[79];
Array.Fill(text, 'x');
value.AsSpan().CopyTo(text.AsSpan(6));

int result = text.AsSpan().IndexOf(value.AsSpan(), StringComparison.Ordinal);
// result == 6

There are 79 - 64 + 1 = 16 valid starts, from 0 through 15, fitting one
16-lane window. The goal is to explain the path to a match, not depict the
data responsible for the benchmark timings.

Choosing two needle positions

The first position is value[0] == 'a'. For the second, the runtime searches
backward for an element different from the first:

needle position:     0    1   ...   61   62   63
value:               a    b   ...    b    a    a
                     ^              ^
                    ch1            ch2

Positions 63 and 62 contain a; position 61 contains b. Therefore,
ch1ch2Distance = 61. ch2 is not necessarily the final character:
it is the second position chosen for filtering.

These values are broadcast into vectors: ch1 contains 16 copies of a;
ch2, 16 copies of b. For start i, we ask whether text[i] == 'a' and
text[i + 61] == 'b'. If either fails, that start cannot be a complete match.

Offset, lane, and address are different concepts

offset is the start of the candidate window in the text. Lane j represents
start offset + j. Here, offset = 0:

Lane	Candidate start	First position	Second position
6	0 + 6 = 6	text[6] == 'a'	text[0 + 6 + 61], or text[67] == 'b'
8	0 + 8 = 8	text[8] == 'a'	text[0 + 8 + 61], or text[69] == 'b'

The runtime excerpt compares the second position first, then the first, then
combines them with AND. Variable types are omitted and line breaks adjusted:

cmpCh2 = Vector256.Equals(
    ch2, Vector256.LoadUnsafe(
        ref searchSpace, (nuint)(offset + ch1ch2Distance)));
cmpCh1 = Vector256.Equals(
    ch1, Vector256.LoadUnsafe(ref searchSpace, (nuint)offset));
cmpAnd = (cmpCh1 & cmpCh2).AsByte();

In this branch, searchSpace references ushort elements. Load offsets are
in 16-bit UTF-16 units, not bytes. The loads read text[61..77] and
text[0..16], with exclusive upper bounds. Adding the distance to the
displaced load keeps each candidate's two positions in the same lane: lane 6
relates text[6] to text[67], not elements belonging to different starts.

Comparing and combining all 16 lanes

Each equality produces FFFF when true and 0000 when false. In this table,
1 and 0 abbreviate those 16-bit values; they are not the integer values
stored in the vector. The operation remains == in every lane, even when its
result is false.

lane:        0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
text[i+61]:  b  a  b  a  b  a  b  a  a  x  x  x  x  x  x  x
ch2:         b  b  b  b  b  b  b  b  b  b  b  b  b  b  b  b
cmpCh2:      1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0

text[i]:     x  x  x  x  x  x  a  b  a  b  a  b  a  b  a  b
ch1:         a  a  a  a  a  a  a  a  a  a  a  a  a  a  a  a
cmpCh1:      0  0  0  0  0  0  1  0  1  0  1  0  1  0  1  0

cmpCh1:      0  0  0  0  0  0  1  0  1  0  1  0  1  0  1  0
cmpCh2:      1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0
AND:         0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0

Lane 6 passes both equalities: a == a and b == b. Lane 8 passes the first,
text[8] == 'a', but fails the second: text[69] contains a, so a == b
is false. AND retains only lane 6.

SIMD comparisons process lanes in parallel. Reading columns 6 and 8 merely
explains their results. AsByte() reinterprets the same bits as bytes;
it does not convert FFFF to the number 1.

cmpAnd != Vector256<byte>.Zero produces a scalar decision: a candidate
exists. It neither identifies the index nor confirms the substring. In the
captured benchmark assembly, vpcmpeqw, vpand, and vptest correspond to
the comparisons, combination, and test. This evidence belongs to the documented
host; it is not a guarantee of the same translation on every machine.

7. Locating and confirming the candidate

From one 16-bit lane to two mask bits

The runtime extracts the most significant bit of each byte:

uint mask = cmpAnd.ExtractMostSignificantBits();

There are 16 elements of 16 bits, reinterpreted as 32 bytes. In lane 6, the
true result contains two FF bytes; every other element contains two 00
bytes:

lane 6:                  FFFF
bytes in vector:         byte 12 = FF     byte 13 = FF
bits in each byte:                 11111111         11111111
most significant bit:             1                1
mask position:                    12               13

Lane 0 corresponds to bytes and bits 0–1; lane 1 to 2–3; lane 6 to 12–13.
The actual extracted mask is therefore 0x00003000:

index:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
bit:     0  0  0  0  0  0  0  0  0  0  0  0  1  1  0  0
index:  16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
bit:     0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

Indices increase from left to right, as in the video. This is not the
usual numeric binary notation: the least significant bit is on the left.
Each bit represents a byte of the result vector, not a character directly.
In the observed assembly, extraction corresponds to vpmovmskb.

Counting, converting, and adding the offset

The next calculation is:

nint charPos = (nint)(uint.TrailingZeroCount(mask) / sizeof(ushort));

Counting starts at bit 0 and finds 12 zeros before the first 1. Thus,
TrailingZeroCount(0x00003000) = 12. Dividing by sizeof(ushort), which is 2,
converts the byte position represented by that bit into an element position:

first set bit:    12
charPos:         12 / 2 = 6
index in text:   offset + charPos = 0 + 6 = 6

charPos is relative to the window; the text index includes offset. They
coincide here because offset is zero. In the captured assembly, the count
corresponds to tzcnt, and division by two to a bit shift.

Checking the entire sequence

Only now do we check complete equality. Here is the runtime excerpt:

if (valueLength == 2 ||
    SequenceEqual(
        ref Unsafe.As<char, byte>(ref Unsafe.Add(ref searchSpace, offset + charPos)),
        ref Unsafe.As<char, byte>(ref value), (nuint)(uint)valueLength * 2))
{
    return (int)(offset + charPos);
}

valueLength == 2 is false because our needle contains 64 elements.
SequenceEqual compares its 128 bytes with those of the segment starting at
text[6]. These ranges have exclusive upper bounds:

Needle segment	Corresponding text segment	Equal contents
value[0..16]	text[6..22]	abababababababab
value[16..32]	text[22..38]	abababababababab
value[32..48]	text[38..54]	abababababababab
value[48..64]	text[54..70]	abababababababaa

All four pairs are equal. The call returns true, and the method returns
offset + charPos = 6. The table organizes data, not instruction execution
order. Confirmation also uses SIMD in the captured assembly for the benchmark's
needle of this size. We do not need to walk through its implementation to
understand its role in the search.

If confirmation failed, the runtime would clear the candidate's two bits and
continue with the next marked pair, if any remained. That does not happen in
this fixture, which finds a match.

We can check the arithmetic without reading internal registers. Add this to
the C# example that constructs text and value in section 6:

uint expectedMask = 0;
for (int lane = 0; lane < 16; lane++)
{
    if (text[lane] == value[0] && text[lane + 61] == value[61])
        expectedMask |= 3u << (2 * lane);
}

if (expectedMask != 0x00003000 ||
    uint.TrailingZeroCount(expectedMask) / sizeof(ushort) != 6 ||
    !text.AsSpan(6, 64).SequenceEqual(value.AsSpan()) ||
    result != 6)
{
    throw new InvalidOperationException("Inconsistent teaching fixture.");
}

expectedMask is a scalar verification calculation, not an extraction from
the vector used internally by IndexOf.

8. Verify, do not assume

The teaching example has an occurrence at index 6. The adversarial scenario
measured in section 3 keeps the same needle but uses an entirely alternating
text, without inserting an occurrence. Every even start passes both filter
positions, but the complete comparison fails at the final element: the text
has b, while the needle ends in a.

Input	Candidates in the first window	Extracted one-bit-per-byte mask	Search result
Teaching example: 79 elements, inserted occurrence	Only lane 6	0x00003000	6
Adversarial: alternating ab text	Lanes 0, 2, 4, 6, 8, 10, 12, 14	0x33333333	-1

For the adversarial input, we could summarize approved lanes as 0x5555,
using one bit per lane. That is only a conceptual representation. Vector
results are FFFF/0000, and the extracted mask variable contains two set
bits per candidate. After rejecting start 0, clearing bits 0–1 changes
0x33333333 to 0x33333330. The next trailing-zero count is 4;
4 / 2 = 2 points to the next candidate. In the observed assembly,
two blsr instructions clear the two bits.

For a text containing 65,536 elements, there are
((65,536 - 64) / 2) + 1 = 32,737 even candidate starts. All are false and
fail at the final element. This counts distinct positions passing the filter,
not measured internal SequenceEqual calls: the final window can overlap
positions examined earlier.

During setup, the harness recomputes the expected first-block mask and total
candidate count with scalar code, and checks that all four methods return
-1. That validates the input and arithmetic; it does not read internal
runtime registers. The connection to instructions comes from the versioned
source and captured assembly. The first expected steps are:

Mask before	Trailing zeros	Position / 2	Confirmation
0x33333333	0	0	fails at relative element 63
0x33333330	4	2	fails at relative element 63
0x33333300	8	4	fails at relative element 63
0x33333000	12	6	fails at relative element 63

Finally, the approximately 24× opening result belongs to a third input:
a pseudorandom late match, with a 16-element needle and 65,536-element text.
It is neither the adversarial result nor a measurement of the teaching fixture.
The example explains the algorithm; each measurement belongs to its own input.

9. Advancing, finishing, and returning to the result

After checking a block, the algorithm advances by a vector width. If the next
advance would pass the last full candidate window, the loop clamps its offset
to that final window, overlapping the previous block to cover the remaining
starts without reading beyond the input. Inputs with fewer than eight possible
starts cannot use this host's 128-bit vector path and take the scalar path.
The exact bounds and branches come from the runtime source, not from the API's
name alone.

In this capture, the filter uses AVX2: word comparisons, AND, vector testing,
and mask extraction. tzcnt and blsr belong to BMI1, and confirmation also
uses vectorized byte comparisons. This observation applies to the documented
runtime, JIT, and CPU; another machine may take a different path. The opening
number shows that, in this experiment, the runtime finds candidates in parallel
and outperforms the scalar, character-by-character search. It does not prove
that less abstraction always costs more, or that SIMD always wins. Interpreting
a benchmark requires knowing which data and algorithms were measured.

Mapping the observed instructions

This table summarizes the capture on Linux x64 / EPYC 7763, .NET 10.0.12,
AVX2, and BMI1. It is neither a promise of one-to-one translation on other
CPUs or versions nor a new capture of the teaching fixture:

Operation	Observed instructions	Role
Broadcast ch1 and ch2	vmovd, vpbroadcastw	Repeat the value in 16 lanes of 16 bits.
Vector256.Equals	vpcmpeqw	Produce FFFF or 0000 per lane.
AND the results	vpand	Retain positions passing both comparisons.
Test the vector against zero	vptest and a branch	Skip mask extraction when there is no candidate.
ExtractMostSignificantBits	vpmovmskb	Extract 32 bits, one per byte.
TrailingZeroCount	tzcnt	Locate the first set bit.
Divide by 2	shr ..., 1	Convert a byte position to a UTF-16 element position.
Clear a rejected candidate's two bits	blsr, twice	Continue to another candidate.

For the adversarial case's 128-byte confirmation, the observed assembly
compares AVX2 chunks of 32 bytes. The first three chunks agree; the fourth
contains the final-element mismatch. This describes that capture, not a
requirement that SequenceEqual always execute four steps.

As a side note: what about KMP and Boyer–Moore?

After the main conclusion, a natural question is how the comparison changes
with algorithms that avoid restarting from scratch. We added two
implementations to the same harness:

• Knuth–Morris–Pratt (KMP): builds a needle prefix table and uses it to resume from the longest prefix that could still match. Search and preprocessing together cost O(n + m), where n is the text length and m the needle length.
• Boyer–Moore–Horspool (BMH): compares right to left and, after a mismatch, advances based on the window's final character and its position in the needle. Preprocessing costs O(m); search often skips positions, but its worst case remains O(nm).

For this one search per needle comparison, timed work includes building
each algorithm's tables on every call. KMP allocates and fills its prefix
table; BMH builds a sparse shift table, Dictionary<char, int>, before scanning.
The runtime receives the same needle and text without reused preprocessed
state. All four methods return the first index or -1; GlobalSetup checks
the expected result before measurement.

The additional benchmark code is:

[Benchmark]
public int KnuthMorrisPratt() =>
    SearchKnuthMorrisPratt(_haystack.AsSpan(), _needle.AsSpan());

[Benchmark]
public int BoyerMooreHorspool() =>
    SearchBoyerMooreHorspool(_haystack.AsSpan(), _needle.AsSpan());

private static int SearchKnuthMorrisPratt(
    ReadOnlySpan<char> haystack,
    ReadOnlySpan<char> needle)
{
    if (needle.IsEmpty)
        return 0;
    if (haystack.Length < needle.Length)
        return -1;

    var prefixLengths = new int[needle.Length];
    for (int i = 1, prefixLength = 0; i < needle.Length; i++)
    {
        while (prefixLength > 0 && needle[i] != needle[prefixLength])
            prefixLength = prefixLengths[prefixLength - 1];

        if (needle[i] == needle[prefixLength])
            prefixLength++;

        prefixLengths[i] = prefixLength;
    }

    for (int i = 0, prefixLength = 0; i < haystack.Length; i++)
    {
        while (prefixLength > 0 && haystack[i] != needle[prefixLength])
            prefixLength = prefixLengths[prefixLength - 1];

        if (haystack[i] == needle[prefixLength])
            prefixLength++;

        if (prefixLength == needle.Length)
            return i - needle.Length + 1;
    }

    return -1;
}

private static int SearchBoyerMooreHorspool(
    ReadOnlySpan<char> haystack,
    ReadOnlySpan<char> needle)
{
    if (needle.IsEmpty)
        return 0;
    if (haystack.Length < needle.Length)
        return -1;

    var shifts = new Dictionary<char, int>(needle.Length);
    for (int i = 0; i < needle.Length - 1; i++)
        shifts[needle[i]] = needle.Length - 1 - i;

    int lastStart = haystack.Length - needle.Length;
    int start = 0;
    while (start <= lastStart)
    {
        int offset = needle.Length - 1;
        while (offset >= 0 && haystack[start + offset] == needle[offset])
            offset--;

        if (offset < 0)
            return start;

        int shift = shifts.TryGetValue(
            haystack[start + needle.Length - 1], out int distance)
            ? distance
            : needle.Length;
        start += shift;
    }

    return -1;
}

Here is the final comparison for the two selected scenarios: MediumRun means
and standard deviations, with fifteen measurement iterations, ten warmups, and
two processes per benchmark. All four implementations received the same text
and needle. KMP and BMH include table construction on every call.
This comparison is an independent run from the historical measurement used in
the opening. Compare values within this table, not directly with the opening's
numbers.

Text length	Scenario	Naive loop	IndexOf	KMP	Boyer–Moore–Horspool
4,096	Pseudorandom late match	3.291 ± 0.093 µs	0.320 ± 0.016 µs	5.026 ± 0.189 µs	10.303 ± 0.223 µs
65,536	Pseudorandom late match	120.256 ± 7.345 µs	5.145 ± 0.267 µs	132.655 ± 6.025 µs	175.052 ± 8.051 µs
4,096	Alternating candidates, late mismatch	113.756 ± 10.486 µs	7.339 ± 0.273 µs	7.382 ± 0.476 µs	23.617 ± 0.225 µs
65,536	Alternating candidates, late mismatch	1,728.590 ± 66.428 µs	122.848 ± 5.355 µs	106.727 ± 6.830 µs	378.960 ± 8.429 µs

For the pseudorandom late match, IndexOf had the lowest mean among the four
methods. KMP and BMH were slower than the simple loop with table preparation
included. We did not measure searches with reused tables, so we have not
isolated how much of the difference comes from preprocessing versus searching.
For the 65,536-element adversarial fixture, KMP's mean was approximately 13%
lower than IndexOf's: 106.727 versus 122.848 µs. At length 4,096, their means
were effectively similar relative to the dispersion. BMH was slower than
IndexOf in all four measured cases.

This illustrates why the answer depends on the algorithm, input, and treatment
of preprocessing. It is not a universal ranking: these are teaching
implementations, and BMH uses Dictionary<char, int>, not a specialized
low-level table. MemoryDiagnoser also recorded per-call allocations: KMP
allocated 88 bytes for the 16-element needle and 280 bytes for the 64-element
needle; BMH allocated 472 and 1,552 bytes, respectively. Reusing a preprocessed
table would change the comparison and was not measured here.

Reproducing the two selected scenarios

To reproduce the experiment without accessing the article's repository,
create a console project using the .NET 10 SDK. Runtime version 10.0.12
must be installed because roll-forward will be disabled:

dotnet new console -n SubstringBenchmark --framework net10.0
cd SubstringBenchmark

Replace SubstringBenchmark.csproj with:

<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net10.0</TargetFramework>
    <RuntimeFrameworkVersion>10.0.12</RuntimeFrameworkVersion>
    <RollForward>Disable</RollForward>
    <ImplicitUsings>enable</ImplicitUsings>
    <Nullable>enable</Nullable>
  </PropertyGroup>
  <ItemGroup>
    <PackageReference Include="BenchmarkDotNet" Version="0.15.8" />
  </ItemGroup>
</Project>

Use the following structure in Program.cs. Inside the class, at the marked
location, copy the six methods already shown in this article:
SearchNaive, SearchRuntime, CreateOrdinaryHaystack,
CreateAlternatingNeedleWithLateMismatch, SearchKnuthMorrisPratt, and
SearchBoyerMooreHorspool. The four [Benchmark] wrappers are already included
below; do not copy them again. This avoids duplicating the implementations.

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkRunner.Run<SubstringSearchBenchmarks>(args: args);

[MediumRunJob]
[MemoryDiagnoser]
[DisassemblyDiagnoser(maxDepth: 3)]
public class SubstringSearchBenchmarks
{
    private string _haystack = "";
    private string _needle = "";

    [Params(4096, 65536)]
    public int HaystackLength { get; set; }

    [Params(SearchCase.RandomLateMatch, SearchCase.RepeatedAlternatingLateFalse)]
    public SearchCase Scenario { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        int expected;
        if (Scenario == SearchCase.RandomLateMatch)
        {
            _haystack = CreateOrdinaryHaystack(HaystackLength);
            _needle = "abcdefghabcdefgh";
            expected = HaystackLength - _needle.Length;
            _haystack = _haystack[..expected] + _needle;
        }
        else
        {
            _haystack = string.Create(HaystackLength, 0, static (chars, _) =>
            {
                for (int i = 0; i < chars.Length; i++)
                    chars[i] = (i & 1) == 0 ? 'a' : 'b';
            });
            _needle = CreateAlternatingNeedleWithLateMismatch();
            expected = -1;
        }

        if (Naive() != expected || ReadOnlySpanIndexOf() != expected ||
            KnuthMorrisPratt() != expected || BoyerMooreHorspool() != expected)
        {
            throw new InvalidOperationException("Unexpected setup result.");
        }

        if (Scenario == SearchCase.RepeatedAlternatingLateFalse)
        {
            uint mask = 0;
            int candidates = 0;
            for (int i = 0; i <= _haystack.Length - _needle.Length; i++)
            {
                if (_haystack[i] != _needle[0] || _haystack[i + 61] != _needle[61])
                    continue;
                candidates++;
                if (i < 16)
                    mask |= 3u << (2 * i);
            }
            if (mask != 0x33333333 ||
                candidates != ((HaystackLength - _needle.Length) / 2) + 1)
            {
                throw new InvalidOperationException("Inconsistent adversarial fixture.");
            }
        }
    }

    [Benchmark(Baseline = true)]
    public int Naive() => SearchNaive(_haystack.AsSpan(), _needle.AsSpan());

    [Benchmark]
    public int ReadOnlySpanIndexOf() => SearchRuntime(_haystack.AsSpan(), _needle.AsSpan());

    [Benchmark]
    public int KnuthMorrisPratt() => SearchKnuthMorrisPratt(_haystack.AsSpan(), _needle.AsSpan());

    [Benchmark]
    public int BoyerMooreHorspool() => SearchBoyerMooreHorspool(_haystack.AsSpan(), _needle.AsSpan());

    // Paste the six methods listed above here.

    public enum SearchCase
    {
        RandomLateMatch,
        RepeatedAlternatingLateFalse
    }
}

Run:

dotnet run -c Release -- --filter '*' --artifacts artifacts

This reproduction selects two scenarios × two lengths × four methods,
for 16 MediumRun benchmarks. Setup checks the results and adversarial
arithmetic; it does not replace the historical 34,193-case exhaustive and
generated-input validation described earlier. Tables and disassembly are
written to artifacts/results/. Assembly capture depends on the diagnoser's
support for your system; another CPU or runtime may generate different
instructions. Timings will also vary: reproducing the procedure does not
guarantee reproducing the historical numbers.

References

• .NET 10.0.12 — SpanHelpers.Char.cs
• Intel Intrinsics Guide, for the observed instructions: _mm256_cmpeq_epi16, _mm256_testz_si256, _mm256_movemask_epi8, _tzcnt_u32, and _blsr_u32. These describe equivalent semantics, not C/C++ calls made by the C# code.
• Knuth, Morris, and Pratt, “Fast Pattern Matching in Strings”, SIAM Journal on Computing 6(2), 1977.
• Boyer and Moore, “A Fast String Searching Algorithm”, Communications of the ACM 20(10), 1977.
• Horspool, “Practical fast searching in strings”, Software: Practice and Experience 10(6), 1980. The compared implementation is Boyer–Moore–Horspool, not the full Boyer–Moore algorithm.
• SIMD and hardware intrinsics in .NET
• MemoryExtensions.IndexOf API