DEV Community: Pedro Sakuma Travi

How ReadOnlySpan.IndexOf finds a substring with SIMD

Pedro Sakuma Travi — Sun, 18 Oct 2026 22:43:33 +0000

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

Como ReadOnlySpan.IndexOf encontra uma substring com SIMD

Pedro Sakuma Travi — Sun, 18 Oct 2026 22:36:25 +0000

Read in English.

Este artigo acompanha a sequência de ideias do vídeo: o vídeo anima os estados;
aqui podemos pausar em cada diagrama e consultar o código e o assembly.
O walkthrough usa o mesmo exemplo didático, separado das entradas medidas.
O número do gancho vem de um MediumRun selecionado, mas ainda se refere a uma
máquina e a um cenário específicos. A comparação com KMP e BMH ao final é
material complementar, fora da montagem principal do vídeo.

1. O resultado que intriga

Uma busca escrita com um loop parece ter menos custo que uma chamada a uma API
de nível mais alto. Para testar essa intuição, comparamos duas implementações
que procuram a primeira ocorrência de uma substring e retornam seu índice,
ou -1 quando não há match.

Este é o resultado do caso usado como gancho: uma substring de 16 chars
inserida no fim de um texto pseudoaleatório de 65.536 chars.

Implementação	Média por busca	Desvio padrão
Loop ingênuo	134,935 µs	24,518 µs
`ReadOnlySpan<char>.IndexOf`	5,653 µs	389 ns

Neste cenário e neste host, a média do loop foi cerca de 23,9× a média de
IndexOf. Isso não é uma previsão para qualquer string, CPU ou versão do
runtime. Mais adiante veremos que o loop e o runtime também usam algoritmos
diferentes; o benchmark não isola somente o custo da abstração.

2. Os dois códigos comparados

O harness usa BenchmarkDotNet; os métodos, entradas, configuração e instruções
para montar uma reprodução estão neste artigo. Cada operação
recebe um ReadOnlySpan<char> para o texto e outro para a needle. A comparação
é ordinal: compara unidades char UTF-16 sem regras culturais. As duas
implementações têm o mesmo contrato: retornar o índice da primeira ocorrência,
ou -1 se não houver match. Em .NET, cada char representa uma unidade de
código UTF-16, e não necessariamente um grafema percebido como um caractere.

O baseline implementa busca ingênua (naive/brute-force): tenta cada posição
e compara a needle caractere a caractere. O segundo método é a chamada à API
do runtime. Estes são os dois métodos que conduzem a explicação principal:

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);

E o BenchmarkDotNet mede os resultados desses métodos por meio destes
wrappers:

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

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

No primeiro wrapper, portanto, medimos o loop ingênuo mostrado acima. No
segundo, medimos ReadOnlySpan<char>.IndexOf com comparação ordinal. Para
explicar o caminho observado no segundo método, usamos a implementação do
runtime .NET 10.0.12: SpanHelpers.IndexOf(ref char, int, ref char, int) em
SpanHelpers.Char.cs.
Nesse host, o método usa filtro de candidatos vetorizado e confirma os
candidatos comparando a substring completa; não é um algoritmo implementado
por nós nem uma garantia de que outras versões ou CPUs escolherão o mesmo
caminho.

Antes de cronometrar, o GlobalSetup executa os quatro métodos para cada
entrada e exige que todos retornem o resultado esperado. Assim, por exemplo,
um cenário chamado “miss” não entra no benchmark se uma das buscas encontrar
uma ocorrência acidental. A validação é feita antes das medições:

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);

O benchmark compara uma busca escalar caractere a caractere com a
implementação otimizada do runtime; não isola somente o custo de chamar uma
API. A pergunta, portanto, é qual trabalho os dois algoritmos fazem, não se
uma sintaxe ou uma abstração é intrinsecamente mais rápida. Ao final, incluímos
KMP e Boyer–Moore–Horspool como uma resposta complementar à pergunta sobre
outros algoritmos; eles não substituem o fio principal do vídeo.

3. Entradas: o que foi testado?

O harness combina sete cenários com textos de 4.096 e 65.536 chars.
As entradas são construídas uma vez no setup, fora da região cronometrada.

Cenário	Texto e needle	Match esperado
`RandomEarlyMatch`	Texto pseudoaleatório no alfabeto `a`–`h`; needle `abcdefghabcdefgh` inserida no índice 0.	índice 0
`RandomMiddleMatch`	Mesmo gerador e needle, inserida no meio do texto.	índice `HaystackLength / 2`
`RandomLateMatch`	Mesmo gerador e needle, inserida nos últimos 16 `char`s.	índice `HaystackLength - 16`
`RandomMissing`	Texto do mesmo gerador/alfabeto, sem inserir a needle.	`-1`, conferido no setup
`RepeatedPrefixMissing`	Texto formado só por `a`; needle `aaaaaaab`.	`-1`
`RepeatedPrefixLate`	Texto formado só por `a`, com `aaaaaaab` substituindo os oito `char`s finais.	índice `HaystackLength - 8`
`RepeatedAlternatingLateFalse`	Texto `ab` alternado; needle de 64 `char`s alternados nos primeiros 63 e terminando em `a`.	`-1`; falsos candidatos falham no último `char`

O gerador pseudoaleatório é determinístico: começa em 0xC0FFEE e, para cada
posição, atualiza um estado de 32 bits com
state = state * 1664525 + 1013904223; os três bits mais altos selecionam um
dos oito caracteres a–h. Este é o código usado para gerar o texto:

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);
}

Nos cenários de match, o trecho correspondente é substituído pela needle.
Para o caso tardio usado no gancho, o código equivale a:

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

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

No cenário ausente, o mesmo alfabeto é mantido, evitando um miss trivial por
caracteres impossíveis: o setup confirma que a needle completa realmente não
aparece.

O cenário adversarial do benchmark

Este caso medido é diferente tanto do gancho quanto do exemplo didático das
seções 6–7. O texto alterna a e b; a needle alterna também, mas seu último
char é alterado para a. A função do benchmark constrói essa needle assim:

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';
    });
}

O runtime compara o primeiro char (a) e procura, de trás para a frente, o
último char da needle que difere dele. Como os chars 63 e 62 são a, esse
ponto é o índice 61, que contém b. No texto alternado, ambos os filtros
passam para todo início par: haystack[i] == 'a' e
haystack[i + 61] == 'b'. A substring inteira, porém, falha só no último
char, porque o texto contém b no índice relativo 63 e a needle contém a.

Tamanho do texto	Candidatos falsos esperados	Resultado
4.096	2.017	`-1`
65.536	32.737	`-1`

O setup calcula e confere a compactação conceitual de um bit por lane
(0x5555), a máscara esperada após extrair um bit por byte (0x33333333) e a
contagem total de candidatos. A primeira compactação não é o vetor de
comparação nem uma variável intermediária do runtime: cada lane aprovada
contém FFFF. O cálculo é uma validação escalar do fixture, não uma leitura
dos registradores do runtime.

4. Medição e resultados

Usamos BenchmarkDotNet 0.15.8, build Release, .NET 10.0.12
(SDK 10.0.401), Linux Ubuntu 24.04.4 x64 e AMD EPYC 7763 a 2,45 GHz. O
BenchmarkDotNet expôs 1 CPU ao processo. O host disponibilizou AVX2 e BMI1; a
captura do assembly usada no walkthrough é desse ambiente.

O fixture combina dois tamanhos e sete cenários. Cada combinação é executada
pelos quatro métodos, totalizando 56 combinações método/caso na matriz ShortRun.
Os atributos que configuram os benchmarks são:

[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; }
}

A matriz ampla usou ShortRun (3 aquecimentos, 3 medições). Para o match
tardio e o caso adversarial, também rodamos MediumRun (10 aquecimentos, 15
medições, 2 processos por benchmark). A tabela mostra as médias e desvios
padrão do MediumRun; as unidades foram convertidas para facilitar a leitura:

Entrada	Caso	Ingênua: média ± desvio padrão	`IndexOf`: média ± desvio padrão	Razão das médias
4.096	Match no fim, texto pseudoaleatório	3,443 ± 0,238 µs	323 ± 15 ns	10,7×
65.536	Match no fim, texto pseudoaleatório	134,935 ± 24,518 µs	5,653 ± 389 ns	23,9×
4.096	Muitos candidatos, falha no último `char`	149,369 ± 57,317 µs	7,645 ± 390 ns	19,5×
65.536	Muitos candidatos, falha no último `char`	1,925 ± 0,202 ms	129,186 ± 7,864 µs	14,9×

O cenário adversarial tem dispersão considerável, especialmente no loop
ingênuo; por isso mostramos a dispersão junto à média e evitamos tratá-lo como
um caso típico. Também não atribuímos todo o ganho a SIMD: o baseline percorre
posições em C#, enquanto IndexOf usa outro algoritmo, além de instruções
vetoriais. O dado sustenta uma conclusão delimitada: neste host, para estas
entradas, a implementação do runtime foi mais rápida.

Na execução original, a validação comparou IndexOf, KMP e BMH com o baseline ingênuo em
34.193 casos determinísticos: todas as strings binárias de até 8 chars e
needles de até 5, mais 2.000 entradas geradas com caracteres diversos,
incluindo NUL e unidades surrogate. Ele inclui needle vazia, needle maior que o
texto, matches injetados e misses.

Na captura original, adicionar --job Medium à classe com [ShortRunJob]
executou os dois jobs; os números reportados são das linhas Job=MediumRun.
A reprodução ao final usa apenas [MediumRunJob], para executar os dois
cenários selecionados sem repetir a matriz ShortRun.

O projeto fixa RuntimeFrameworkVersion em 10.0.12 e desativa roll-forward.
Sua configuração e os comandos estão na seção de reprodução, sem depender
de arquivos externos ao artigo.

5. A ideia de SIMD

SIMD aplica uma mesma operação a vários elementos de dados. No caminho
observado, os elementos são chars UTF-16 de 16 bits. Um vetor de 256 bits pode
conter 16 lanes char:

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

Isso não significa que toda a busca acontece numa única instrução. O vetor
seleciona vários inícios possíveis para verificação; o caminho ainda percorre
blocos, processa máscaras e confirma a substring completa.

6. Encontrar candidatos

Uma entrada pequena para acompanhar as contas

Usamos a mesma fixture didática do vídeo: uma needle de 64 unidades UTF-16,
inserida no índice 6 de um texto de 79 unidades, preenchido com x
fora desse trecho. A needle alterna a e b, exceto pelo último elemento,
que é a. Este código reproduz a entrada; não é um cenário cronometrado:

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

Há 79 - 64 + 1 = 16 inícios válidos, de 0 a 15: cabem em uma janela de
16 lanes. O objetivo é explicar o caminho até um match, não representar os
dados responsáveis pelos tempos do benchmark.

Escolher dois pontos da needle

O primeiro ponto é value[0] == 'a'. Para o segundo, o runtime procura de trás
para a frente um elemento diferente do primeiro:

posição na needle:   0    1   ...   61   62   63
valor:               a    b   ...    b    a    a
                     ^              ^
                    ch1            ch2

As posições 63 e 62 contêm a; a posição 61 contém b. Portanto,
ch1ch2Distance = 61. ch2 não significa necessariamente o último
caractere, mas o segundo ponto escolhido para filtrar.

Os valores são replicados em vetores: ch1 contém 16 cópias de a, e ch2,
16 cópias de b. Para um início i, perguntamos se text[i] == 'a' e
text[i + 61] == 'b'. Se alguma condição falhar, esse início não pode ser
uma ocorrência completa.

Offset, lane e endereço não são a mesma coisa

offset é o início da janela de candidatos no texto. A lane j representa o
início offset + j. Nesta janela, offset = 0:

Lane	Início candidato	Primeiro ponto	Segundo ponto
6	`0 + 6 = 6`	`text[6] == 'a'`	`text[0 + 6 + 61]`, isto é, `text[67] == 'b'`
8	`0 + 8 = 8`	`text[8] == 'a'`	`text[0 + 8 + 61]`, isto é, `text[69] == 'b'`

O recorte do runtime executa primeiro a comparação do segundo ponto, depois
a do primeiro e finalmente o AND. Abaixo, os tipos das variáveis foram
omitidos e as quebras ajustadas:

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();

Neste ramo, searchSpace referencia elementos ushort: os deslocamentos
das cargas são em unidades UTF-16 de 16 bits, não em bytes. As cargas leem
text[61..77] e text[0..16], usando limites finais exclusivos. Somar a
distância na segunda carga mantém os dois pontos de cada candidato na mesma
lane: a lane 6 relaciona text[6] e text[67], não elementos de inícios
diferentes.

Comparar e combinar as 16 lanes

Cada igualdade produz FFFF quando verdadeira e 0000 quando falsa.
Na tabela, 1 e 0 são abreviações desses valores de 16 bits, não os
valores inteiros gravados no vetor. A operação continua sendo == em todas
as lanes, inclusive quando seu resultado é falso.

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

A lane 6 passa nas duas igualdades: a == a e b == b. Na lane 8, a
primeira passa (text[8] == 'a'), mas a segunda falha: text[69] contém a,
e a == b é falso. O AND mantém apenas a lane 6.

As comparações SIMD processam as lanes em paralelo; a leitura das colunas
6 e 8 apenas explica seus resultados. AsByte() reinterpreta os mesmos bits
como bytes, sem converter FFFF no número 1.

O teste cmpAnd != Vector256<byte>.Zero produz uma decisão escalar: há
candidato. Ele não informa o índice nem confirma a substring. No assembly
capturado do benchmark, vpcmpeqw, vpand e vptest correspondem às
comparações, combinação e teste. Essa evidência é do host documentado, não
uma garantia de tradução para qualquer máquina.

7. Localizar e confirmar o candidato

De uma lane de 16 bits a dois bits na máscara

O runtime extrai o bit mais significativo de cada byte:

uint mask = cmpAnd.ExtractMostSignificantBits();

São 16 elementos de 16 bits, reinterpretados como 32 bytes. Na lane 6, o
resultado verdadeiro contém dois bytes FF; nos demais elementos, ambos
os bytes são 00:

lane 6:              FFFF
bytes no vetor:      byte 12 = FF     byte 13 = FF
bits de cada byte:            11111111         11111111
bit mais significativo:      1                1
posição na máscara:          12               13

A lane 0 corresponde aos bytes e bits 0–1; a lane 1, a 2–3; a lane 6, a
12–13. Logo, a máscara efetivamente extraída é 0x00003000:

índice:  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
índice: 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

Aqui os índices crescem da esquerda para a direita, como no vídeo.
Não é a escrita binária numérica usual: o bit menos significativo está à
esquerda. Cada bit representa um byte do vetor de resultados, não diretamente
um caractere. No assembly observado, a extração corresponde a vpmovmskb.

Contar, converter e somar o offset

O próximo cálculo no código é:

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

A contagem começa no bit 0 e encontra 12 zeros antes do primeiro 1. Portanto,
TrailingZeroCount(0x00003000) = 12. Dividir por sizeof(ushort), que vale 2,
converte a posição do byte representado pelo bit em posição de elemento:

primeiro bit marcado: 12
charPos:              12 / 2 = 6
início no texto:      offset + charPos = 0 + 6 = 6

charPos é relativo à janela; o índice no texto inclui offset. Os valores
coincidem neste exemplo porque o offset é zero. No assembly capturado, a
contagem corresponde a tzcnt e a divisão por dois a um deslocamento de bits.

Confirmar a sequência inteira

Só agora verificamos a igualdade completa. O recorte do runtime é:

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);
}

O teste valueLength == 2 é falso, pois nossa needle tem 64 elementos.
SequenceEqual compara seus 128 bytes com os do trecho iniciado em
text[6]. Os intervalos abaixo têm limite final exclusivo:

Trecho da needle	Trecho correspondente do texto	Igualdade
`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`

Os quatro pares são iguais: a chamada retorna true, e o método retorna
offset + charPos = 6. A tabela organiza os dados, não a ordem de
execução das instruções. A confirmação também usa SIMD no assembly capturado
para a needle desse tamanho no benchmark; não precisamos abrir sua
implementação para entender seu papel na busca.

Se a confirmação falhasse, o runtime limparia os dois bits do candidato e
continuaria com o próximo par marcado, se ainda houvesse algum. Isso não
acontece nesta fixture, que encontra o match.

Podemos conferir a matemática sem ler registradores internos. Acrescente
este trecho ao exemplo C# que constrói text e value na seção 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("Fixture didática inconsistente.");
}

expectedMask é um cálculo escalar de verificação, não a extração do vetor
usado internamente por IndexOf.

8. Confirmar, não presumir

O exemplo didático tem uma ocorrência no índice 6. O cenário adversarial
medido na seção 3 mantém a mesma needle, mas usa um texto inteiramente
alternado, sem inserir a ocorrência. Nesse texto, todo início par passa nos
dois pontos do filtro, mas a comparação completa falha no último elemento:
o texto contém b, enquanto a needle termina em a.

Entrada	Candidatos na primeira janela	Máscara extraída por byte	Resultado da busca
Didática: 79 elementos, ocorrência inserida	Apenas lane 6	`0x00003000`	6
Adversarial: texto `ab` alternado	Lanes 0, 2, 4, 6, 8, 10, 12 e 14	`0x33333333`	`-1`

No adversarial, poderíamos resumir as lanes aprovadas como 0x5555, usando
um bit por lane. Essa é apenas uma representação conceitual; os resultados
vetoriais são FFFF/0000, e a variável mask extraída contém dois bits
marcados por candidato. Por exemplo, depois de rejeitar o início 0, limpar
seus bits 0–1 muda a máscara de 0x33333333 para 0x33333330. A próxima
contagem dá 4; 4 / 2 = 2 aponta ao candidato seguinte. No assembly observado,
dois blsr fazem a limpeza dos dois bits.

No texto de 65.536 chars, há
((65.536 - 64) / 2) + 1 = 32.737 inícios pares candidatos. Todos são falsos
e falham no elemento final. A contagem refere-se às posições distintas que
passam no filtro, não a uma medição de chamadas internas de SequenceEqual;
a última janela pode sobrepor posições já examinadas.

O harness recalcula escalarmente, a partir do fixture, a máscara esperada do
primeiro bloco e a contagem total de candidatos no setup, além de verificar
que os quatro métodos retornam -1. Isso valida os dados e o cálculo do caso,
não lê registradores internos do runtime; essa ligação vem do código
versionado e do assembly capturado. Os primeiros passos esperados são:

Máscara antes	Zeros à direita	Posição / 2	Confirmação
`0x33333333`	0	0	falha no elemento relativo 63
`0x33333330`	4	2	falha no elemento relativo 63
`0x33333300`	8	4	falha no elemento relativo 63
`0x33333000`	12	6	falha no elemento relativo 63

Por fim, o resultado de aproximadamente 24× da abertura pertence a uma
terceira entrada: match tardio pseudoaleatório, com needle de 16 elementos
e texto de 65.536. Não é o resultado do adversarial nem da fixture didática.
O exemplo explica o algoritmo; cada medição pertence à sua própria entrada.

9. Avançar, terminar e voltar ao resultado

Depois de verificar um bloco, o algoritmo avança por uma largura vetorial. Se
o próximo avanço ultrapassaria o último início que ainda cabe, o loop volta ao
offset do último bloco completo, sobrepondo parte do bloco anterior para
examinar as posições finais sem ler além da entrada. Entradas com menos de
oito inícios possíveis não cabem no caminho vetorial de 128 bits deste host e
seguem o caminho escalar. Os limites e branches exatos estão no código-fonte
do runtime, não são inferidos apenas pelo nome da API.

No assembly desta execução, o filtro usa AVX2: comparação de words, AND,
teste de vetor e extração de máscara; tzcnt e blsr pertencem a BMI1, e a
confirmação também usa comparações vetoriais de bytes. Essa observação vale
para a versão do runtime, JIT e CPU registrados; outras máquinas podem usar
outro caminho. O número inicial mostra que neste experimento o runtime
encontra candidatos em paralelo e supera a busca escalar caractere a
caractere. Não demonstra que menos abstração sempre custa mais ou que SIMD
sempre vence. Para interpretar qualquer benchmark, precisamos saber quais
dados e qual algoritmo foram medidos.

Relação com as instruções observadas

Esta tabela resume a desassemblagem capturada no host Linux x64 / EPYC 7763,
.NET 10.0.12, AVX2 e BMI1. Não é uma promessa de tradução um-para-um para
outras CPUs ou versões, nem uma nova captura da fixture didática:

Operação	Instruções observadas	Papel
Replicar `ch1` e `ch2`	`vmovd`, `vpbroadcastw`	Repetir o valor em 16 lanes de 16 bits.
`Vector256.Equals`	`vpcmpeqw`	Produzir `FFFF` ou `0000` por lane.
AND dos resultados	`vpand`	Manter quem passou nas duas comparações.
Teste do vetor contra zero	`vptest` e salto	Evitar extrair máscara quando não há candidato.
`ExtractMostSignificantBits`	`vpmovmskb`	Extrair 32 bits, um por byte.
`TrailingZeroCount`	`tzcnt`	Localizar o primeiro bit marcado.
Divisão por 2	`shr ..., 1`	Converter posição de byte para elemento UTF-16.
Limpar dois bits do candidato rejeitado	`blsr`, duas vezes	Prosseguir para outro candidato.

Para a confirmação de 128 bytes do caso adversarial, o assembly observado
compara trechos AVX2 de 32 bytes. Os três primeiros trechos coincidem; o
quarto contém a divergência no elemento final. Isso descreve a captura desse
caso, não uma exigência de que SequenceEqual sempre execute quatro passos.

A título de curiosidade: como se saem KMP e Boyer–Moore?

Depois da conclusão principal, vale a curiosidade: como a comparação se
comportaria contra algoritmos que evitam recomeçar a busca do zero? Para isso,
acrescentamos duas implementações ao mesmo harness:

Knuth–Morris–Pratt (KMP): constrói a tabela de prefixos da needle e a usa para retomar do maior prefixo que ainda pode coincidir. Busca e pré-processamento têm custo O(n + m) no total, onde n é o texto e m a needle.
Boyer–Moore–Horspool (BMH): compara da direita para a esquerda e, após uma falha, avança conforme a posição do último caractere da janela na needle. O pré-processamento custa O(m); a busca costuma saltar posições, mas o pior caso permanece O(nm).

Para esta comparação de uma busca por needle, o tempo cronometrado inclui
construir as tabelas de cada algoritmo em cada chamada. Assim, o KMP aloca e
preenche a tabela de prefixos, e o BMH monta sua tabela esparsa de saltos
(Dictionary<char, int>) antes de percorrer o texto. O runtime recebe a mesma
needle e o mesmo texto, sem estado pré-processado reutilizado. Os quatro
métodos retornam o primeiro índice ou -1; o GlobalSetup confere todos
contra o resultado esperado antes da medição.

O código adicional do benchmark é:

[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;
}

Esta é a comparação final para os dois cenários escolhidos. São médias e
desvios padrão do MediumRun (15 medições, 10 aquecimentos, 2 processos por
benchmark); todas as quatro implementações receberam o mesmo texto e needle.
As colunas KMP e BMH incluem a construção das tabelas em cada chamada.
Esta rodada comparativa é independente da medição histórica usada no gancho;
os tempos da tabela devem ser comparados entre si, não diretamente com os
números da abertura.

Texto	Cenário	Loop ingênuo	`IndexOf`	KMP	Boyer–Moore–Horspool
4.096	Match tardio pseudoaleatório	3,291 ± 0,093 µs	0,320 ± 0,016 µs	5,026 ± 0,189 µs	10,303 ± 0,223 µs
65.536	Match tardio pseudoaleatório	120,256 ± 7,345 µs	5,145 ± 0,267 µs	132,655 ± 6,025 µs	175,052 ± 8,051 µs
4.096	Candidatos alternados, mismatch tardio	113,756 ± 10,486 µs	7,339 ± 0,273 µs	7,382 ± 0,476 µs	23,617 ± 0,225 µs
65.536	Candidatos alternados, mismatch tardio	1.728,590 ± 66,428 µs	122,848 ± 5,355 µs	106,727 ± 6,830 µs	378,960 ± 8,429 µs

No match tardio pseudoaleatório, IndexOf teve a menor média entre os quatro
métodos; KMP e BMH foram mais lentos que o loop simples com a preparação das
tabelas incluída. Não medimos essas buscas com tabelas reutilizadas, portanto
não isolamos quanto da diferença vem do pré-processamento e quanto vem da
busca. No fixture adversarial de 65.536 chars, KMP
ficou cerca de 13% abaixo da média de IndexOf (106,727 contra 122,848 µs);
no tamanho 4.096, suas médias ficaram praticamente iguais diante da
dispersão. BMH foi mais lento que IndexOf nos quatro casos medidos.

Isso ilustra por que a resposta depende do algoritmo, da entrada e de como o
pré-processamento é contabilizado. Não é um ranking universal: são
implementações didáticas, e o BMH usa uma tabela baseada em
Dictionary<char, int>, não uma tabela especializada de baixo nível.
MemoryDiagnoser também registrou alocações por chamada: KMP alocou 88 bytes
para a needle de 16 chars e 280 bytes para a de 64; BMH alocou 472 e 1.552
bytes, respectivamente. Reutilizar uma tabela pré-processada mudaria essa
comparação e não foi medido aqui.

Reprodução dos dois cenários selecionados

Para montar uma reprodução sem acessar o repositório do artigo, crie um
projeto de console com SDK .NET 10. A versão de runtime 10.0.12 precisa
estar instalada, pois o roll-forward estará desativado:

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

Substitua SubstringBenchmark.csproj por:

<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 a estrutura abaixo em Program.cs. Dentro da classe, no local
indicado, copie os seis métodos já apresentados neste artigo:
SearchNaive, SearchRuntime, CreateOrdinaryHaystack,
CreateAlternatingNeedleWithLateMismatch, SearchKnuthMorrisPratt e
SearchBoyerMooreHorspool. Os quatro wrappers [Benchmark] já estão abaixo;
não os copie novamente. Assim não precisamos duplicar as implementações no
texto.

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("Resultado inesperado no setup.");
        }

        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("Fixture adversarial inconsistente.");
            }
        }
    }

    [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());

    // Cole aqui os seis métodos indicados acima.

    public enum SearchCase
    {
        RandomLateMatch,
        RepeatedAlternatingLateFalse
    }
}

Execute:

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

Essa reprodução seleciona dois cenários × dois tamanhos × quatro métodos,
totalizando 16 benchmarks MediumRun. O setup verifica os resultados e
a matemática do adversarial; ele não substitui a validação exaustiva histórica
de 34.193 casos descrita anteriormente. As tabelas e a desassemblagem são
gravadas em artifacts/results/. A captura de assembly depende do suporte
do diagnoser no sistema; outra CPU ou runtime pode gerar outras instruções.
Os tempos também variarão: reproduzir o procedimento não garante reproduzir
os números históricos.

Referências

.NET 10.0.12 — SpanHelpers.Char.cs
Intel Intrinsics Guide, para as instruções observadas: _mm256_cmpeq_epi16, _mm256_testz_si256, _mm256_movemask_epi8, _tzcnt_u32 e _blsr_u32. São referências de semântica equivalente, não chamadas C/C++ feitas pelo código C#.
Knuth, Morris e Pratt, “Fast Pattern Matching in Strings”, SIAM Journal on Computing 6(2), 1977.
Boyer e 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. A implementação comparada é Boyer–Moore–Horspool, não Boyer–Moore completo.
SIMD e hardware intrinsics no .NET
API MemoryExtensions.IndexOf

Microsoft-Decision-1 in practice: probabilities for AIOps decisions

Pedro Sakuma Travi — Tue, 13 Oct 2026 14:09:12 +0000

Microsoft-Decision-1 isn't a chat model. You send a state plus typed questions, and it returns numbers: a probability for yes/no (noul), a probability per option (choice), or a position on an ordered scale (score). No prose, no rationale, about 1 output token per call. That makes it a natural candidate for the decisions around an operations stack: "is this block of logs anomalous?", "which service is the root cause?".

We tested it on two public AIOps datasets against gpt-4.1-nano, a reasoning model (gpt-6.1-sol) and non-LLM baselines. This post walks through the signals, how we framed what to detect, and the results, including a first attempt that did not work. The code is on GitHub.

Highlights

Root-cause ranking was a strong fit. Decision-1 picked the root-cause service in 94% of 90 failure cases, beating a "largest metric deviation" heuristic (82%, p=0.013), at about a third of the chat baseline's latency.
Log anomaly detection needed work. The first framing scored 49%. With a computed summary, a better question and a calibrated threshold it reached 86% and led the other LLMs.
A small trained classifier still wins when you have labels: 95% with 50 labeled blocks.
Cheap and fast: about 240 ms p50, and cents for a full run at the prices we found (unverified).

Part 1: HDFS log anomaly detection

The signal: what a block's log looks like

The Loghub HDFS_v1 dataset (free for research use; Xu et al., SOSP'09; Zhu et al., ISSRE'23) groups the logs of a Hadoop distributed file system by block: every block gets an identifier, and everything the cluster logged about it forms one session. Parsed into 29 event templates, the sequence for one block tells a story:

The NameNode allocates the block.
Three DataNodes (replication factor 3) each start receiving it and, when done, log that they received it.
Each replica's PacketResponder terminates, acknowledging the write.
Each DataNode reports the block to the NameNode, which logs the block map update (addStoredBlock).
Later, deletions may appear.

We do not reproduce raw log lines: the dataset is unsanitized and licensed for research. We work with event templates and counts only. The dataset also has a Type column derived from the label, so we do not use it (it would leak the answer). Labels come from the dataset's own rules plus manual review.

Sampling matters: real prevalence of anomalies is about 2.9%. Our test set is balanced (600 normal, 600 anomalous), so accuracy here is not what you would see in production.

What "anomalous" really means

Looking at 300 blocks from our calibration split (150 normal, 150 anomalous) shows that "contains an error" is a bad definition:

Pattern	Normal	Anomalous
Complete lifecycle (1 allocation, 3 receives, 3 acks), no error message	112	14
Complete receive/ack, but an error message is present	38	45
Truncated: 1 or 2 receives, no acks	0	65
Extra receive attempts (4 or 5)	0	26

38 of 150 normal blocks contain a "got exception while serving" message: a benign event.
14 anomalous blocks look complete and log no error at all. In the ones we inspected, the NameNode block-map update appears once instead of three times, meaning only one replica was registered.
Truncated blocks are short, often 4 events, with a "writeBlock received exception".

So the real signal is the lifecycle: expected steps, repeated three times, and a count of what is missing. A rule like "any exception event" gets 71% on the test split (it flags the benign exceptions and misses the quiet anomalies).

A first attempt that failed

Our first prompt was the obvious one. The state was the list of event templates with counts, and the question was "does this block's activity indicate an anomaly?". Decision-1 scored 49% (AUC 0.68), worse than the 71% rule. Looking at the saved outputs:

Its probability correlated 0.43 with the number of events, but only 0.14 with the label.
Short blocks (10 events or fewer), all anomalies, got a mean P(anomaly) of 0.45. Blocks of 15 to 20 events, 99% normal, got 0.66.
Error keywords ("exception") pushed the probability up, whether or not they mattered.

The model reacts to lexical cues and volume, and treats missing events as healthy. That is a framing problem, not a reason to discard the model.

Modeling what we want to detect

We changed two things, and tested them on the calibration split (never the test split):

State: we added a computed lifecycle_summary (expected replicas = 3; allocations; replica writes started and completed; terminated acks; replicas registered with the NameNode; missing lifecycle steps; error events). This is feature engineering from HDFS domain knowledge, not something the model derives.
Question: instead of "is it abnormal?", ask the positive, structural one: "is the block's lifecycle complete?"

Here is a real (short) block as sent. The first-attempt request carried only the part up to event_counts; the enriched one adds lifecycle_summary. This is a hard one: the lifecycle looks complete, and there is one "Unexpected error" event, but the dataset labels the block anomalous. The same pattern is also common among normal blocks (see the table above), which is why error keywords alone are a weak signal.

{
  "model": "Decision-1",
  "state": {
    "system": "HDFS (Hadoop distributed file system), log events for a single data block",
    "total_events": 20,
    "event_counts": {
      "BLOCK* NameSystem allocateBlock:": 1,
      "Receiving block src: dest:": 3,
      "Received block of size from": 3,
      "PacketResponder for block terminating": 3,
      "BLOCK* NameSystem addStoredBlock: blockMap updated: is added to size": 3,
      "BLOCK* NameSystem delete: is added to invalidSet of": 3,
      "Deleting block file": 3,
      "Unexpected error trying to delete block BlockInfo not found in volumeMap": 1
    },
    "lifecycle_summary": {
      "expected_replicas": 3,
      "block_allocations": 1,
      "replica_writes_started": 3,
      "replica_writes_completed": 3,
      "pipeline_acks_terminated": 3,
      "replicas_registered_with_namenode": 3,
      "missing_lifecycle_steps": [],
      "exception_or_error_events": 1
    }
  },
  "questions": {
    "q": {
      "type": "noul",
      "instructions": "Did this block complete the normal HDFS write lifecycle on all expected replicas (allocated, written, acknowledged and registered)?"
    }
  }
}

The answer is a single probability that the lifecycle is complete; the anomaly score is 1 - P(complete). For a truncated block, missing_lifecycle_steps would instead list entries such as "write completed on every replica".

Variant (200 calibration blocks)	Accuracy @0.5	AUC
"abnormal?", raw counts	49.5%	0.65
"is the lifecycle complete?", raw counts	60.5%	0.82
"abnormal?", counts + lifecycle summary	73.5%	0.91
choice normal / anomalous / uncertain + summary	79.0%	n/a
"lifecycle complete?" + summary	70.5%	0.97

Both the state and the wording matter. The last variant ranks best (AUC 0.97, mean P(complete) 0.96 for normal and 0.48 for anomalous blocks), but 0.5 is the wrong threshold for it, so it needs calibrating.

Results on 1,200 held-out blocks

We picked the best variants on the calibration split and scored them on the full test split, with the same enriched state for every LLM and the threshold chosen on the calibration split only:

Model	"Complete?" @0.5	"Complete?", calibrated	Choice with abstain	AUC
Decision-1	69%	86% (thr 0.15)	79%	0.964
gpt-4.1-nano	65%	79%	66%	0.839
gpt-6.1-sol (n=100)	66%	66%	79%	0.790

The choice variant never abstained (0 of 1,200). The reasoning model ran on only 100 blocks (CI roughly 70 to 86%), and its self-reported confidence was too coarse for calibration to help.

Against non-LLM references on the same blocks:

Reference	Accuracy
Rule: any exception event	70.8%
Logistic regression, 50 labeled blocks	95.1%
Logistic regression, 200 labeled blocks	97.5%
Logistic regression, 8,000 labeled blocks	99.7%

Note: the logistic regression is not a like-for-like comparison. It is a trained classifier: it needs labeled examples (the rows above are trained on 50, 200 and 8,000 labeled blocks), a training step, and a stable event schema, and it only sees raw event counts. Decision-1 and the other LLMs ran zero-shot with no training; we used labels only to pick a threshold (150 + 150 blocks), and they received our computed lifecycle summary on top of the counts.

Decision-1 beat the rule (p<0.0001) but not a logistic regression on event counts. If you have labels and a stable schema, train a classifier. A zero-shot decision model fits when you do not have labels, or when the schema changes too often to retrain.

Part 2: root-cause analysis on microservices

The signal

RCAEval RE2-OB (MIT license) injects faults into the Online Boutique demo (11 microservices on Kubernetes) and records three kinds of telemetry while it does:

Metrics: CPU, memory, sockets, disk, request latency (p50/p90) and error rate per service.
Traces: how long each service's spans take.
Logs: how many log lines per second each service emits.

Each case injects one fault into one service, at a known moment. There are 5 root-cause services (checkout, currency, email, product catalog, recommendation) and 6 fault types (CPU, memory, disk, socket exhaustion, added delay, packet loss), each repeated 3 times: 90 cases.

What an on-call engineer would see

We do not hand the model raw time series. A script reduces each case's telemetry to a compact JSON state, and that state is the only thing Decision-1 sees:

Window: the 12 minutes before and the 12 minutes after the injection time. The state says an alert fired at the start of the "after" window; in a real incident you would use your alert time, which is less exact than the dataset's.
Metrics: for every service and metric (CPU, memory, sockets, disk, latency p50/p90, errors) we compare the after-mean with the before-mean, scaled by how much the metric varied before the fault. Only the 10 largest shifts are kept, each with its before, after and % change.
Traces: mean span duration per service before and after, keeping the 6 largest relative changes.
Logs: log lines per second per service before and after, keeping the 6 largest relative changes.

We compute these deltas ourselves because Decision-1 is weak at arithmetic over raw numbers. The metric list is already sorted by that shift score, so the first entry is exactly the pick of the baseline rule below. What Decision-1 adds is combining that list with the trace and log evidence.

A clear case: CPU fault on checkout. The top change is the checkout service's CPU going from 0.43 to 18.3 (+4,160%), followed by its memory (+38%) and sockets (+22%); the entries that follow are changes of a few percent. One service lights up on its own metrics: the signature is easy to read.

A harder case: added delay on the email service. The email service's own p90 latency rises +4,500%, but the service that calls it, checkout, also slows down (p90 +106%, p50 +195%), and checkout's span time triples (14 to 43 ms) while email's own span time barely moves (0.17 to 0.18 ms). Both services appear in the top changes, and a reader can mistake the caller for the culprit.

Packet loss is noisy. Loss on the product catalog service pushes latency up on the services that depend on it (recommendation p90 +68,900%), and the frontend starts reporting errors, so the loudest symptoms are not on the service at fault.

What we ask

Two questions per case, and each is a choice question:

Which of the 11 services is the root cause?
Which of the 6 fault types was injected?

This is the whole request for the first question (lists shortened). The case id, which contains the true service and fault, is never sent:

{
  "model": "Decision-1",
  "state": {
    "system": "Online Boutique microservices on Kubernetes (11 services). An alert fired at the start of the 'after' window; telemetry is summarized as before vs after.",
    "minutes_before_and_after": [12.0, 12.0],
    "top_metric_changes": [
      {"service": "checkoutservice", "metric": "cpu", "before": 0.429, "after": 18.3, "change_pct": 4160.0}
    ],
    "trace_span_duration_by_service": [
      {"service": "checkoutservice", "mean_span_ms_before": 12.1, "mean_span_ms_after": 340.5, "change_pct": 2714.0}
    ],
    "log_volume_by_service": [
      {"service": "frontend", "log_lines_per_s_before": 9.8, "log_lines_per_s_after": 14.2, "change_pct": 44.9}
    ]
  },
  "questions": {
    "q": {
      "type": "choice",
      "instructions": "Which service is the root cause of the incident?",
      "criteria": {
        "adservice": "The ad service is the origin of the fault",
        "checkoutservice": "The checkout service is the origin of the fault"
      }
    }
  }
}

The second call reuses the same state and asks "What kind of fault was injected into the root-cause service?" with the options cpu, mem, disk, delay, loss and socket. The response is a probability per option, and we take the highest. The chat baselines receive the same state and options as prompt text.

The non-LLM reference is a "largest shift" rule: pick the service of the single metric that moved most relative to its pre-fault variability (the first entry in the state). It needs no training, and it is right 82% of the time.

Results (90 cases)

Task	Decision-1	gpt-4.1-nano	gpt-6.1-sol	Reference rule
Root-cause service (11 options)	94%	91%	100%	82%
Fault type (6 options)	51%	47%	54%	40%
p50 latency per call	240 ms	728 ms	2,052 ms	n/a

Decision-1 beat the heuristic on the service (McNemar p=0.013). Differences against the two LLMs are not significant (vs gpt-4.1-nano p=0.55, vs gpt-6.1-sol p=0.06), and fault-type differences are not significant for anyone. Only 5 of the 11 services ever appear as a true root cause, which makes the task somewhat easier than it looks.

Where the model helps, and where it does not

Service (85 of 90 right). The heuristic and Decision-1 disagree on 17 cases. In 14, Decision-1 is right and the rule is wrong: the rule had picked a symptom (the frontend in 9 of them, an email or other service in the rest), mostly on packet-loss and delay faults, where the loudest numbers sit downstream of the fault. In 3, the rule is right and Decision-1 is wrong: all three are the email-delay case above, where Decision-1 named checkout, the caller. Its other two errors were a packet-loss case (it chose the frontend) and a product-catalog loss case (it chose recommendation). Those are the same "symptom versus cause" confusions.

Fault type (46 of 90 right). Per-type results show a clear split:

Injected fault	Correct (of 15)	Most common wrong answer
CPU	13	disk (2)
Delay	13	memory, disk (1 each)
Memory	9	CPU (4)
Disk	9	memory (4)
Packet loss	0	memory (9), delay (5)
Socket	2	CPU (8)

CPU and delay leave a distinctive trace. Packet loss and socket exhaustion do not: the same latency and error symptoms show up as other faults, and Decision-1 never answered "loss" once and chose "socket" only twice. Nothing in the state we give it says "packets were dropped", so this is as much a limit of our summary as of the model. The other two LLMs landed at 47% and 54%, so this is a hard task for all of them.

Takeaway for practice. Use it to rank where to look, not to name the fault. It narrowed 11 services to the right one 94% of the time in a quarter of a second; telling you why is a job for a human, or for richer state.

Cost and latency

Token counts from the main run (1,380 calls for Decision-1 and gpt-4.1-nano, 280 for the reasoning model; calibration calls excluded), at list rates we have not verified (Decision-1 as reported by third-party aggregators, gpt-6.1-sol from OpenAI's list; Azure prices may differ, and hidden reasoning tokens may add to the reasoning model's bill):

Model	Input / output tokens	Approx. cost	Per call
Decision-1 (about $0.042 per 1M input, output free)	353k / 1.4k	~$0.015	~$0.00001
gpt-4.1-nano (~$0.10 in / $0.40 out per 1M)	402k / 18k	~$0.05 to 0.07	~$0.00004
gpt-6.1-sol ($2 in / $10 out per 1M)	192k / 18k	~$0.56	~$0.002

At equal volume the reasoning model would cost about two orders of magnitude more than Decision-1, plus 2 s of latency per call versus 0.24 s. Check Azure Cost Management for the real bill.

Caveats

The HDFS lifecycle summary was written by us from domain knowledge (replication factor 3), so it is feature engineering. We tried five variants and chose after seeing calibration results, which makes the headline 86% somewhat optimistic. The sample is balanced and the reasoning model ran on 100 blocks only.
Our pattern table comes from a 300-block calibration split; the 14 "quiet" anomalies were inspected by us and are not proof of a general rule.
RCA has 90 cases and only 5 true root-cause services; samples are small and margins wide. The state is pre-ranked by the same shift score the baseline rule uses, and uses the dataset's exact injection time.
One baseline per model family, temperature 0, our prompt, no few-shot examples. The chat models' "probability" is self-reported confidence, so it is coarser than Decision-1's.
We did not verify published scores for these datasets, so we cite none. Prices are unverified.
Decision-1 returns no explanation, so keep a human in the loop for consequential decisions.

Takeaways

Decision-1 works best when the state already contains the facts that matter. Compute lifecycle checks and deltas instead of handing it raw counts.
Ask the structural question ("is the lifecycle complete?"), not the vague one ("is this abnormal?").
Calibrate the threshold on held-out labeled data; 0.5 was a poor default.
With labeled data and a stable schema, a small trained classifier beat every LLM on HDFS. Use a decision model where you have no labels, and for fast gates like root-cause ranking.
Test every gate on your own data before you automate it.

The pool that got slower the more we shared it

Pedro Sakuma Travi — Tue, 14 Jul 2026 18:08:47 +0000

How a 15-minute chat with an LLM found a hidden ArrayPool<byte>.Shared
contention point that no static analyzer would ever flag — and why the fix
had nothing to do with adding a lock.

The ticket

"CPU on market-data-gateway climbed ~20% after we added a broadcast fan-out
path last sprint. No new allocations, no GC pressure, nothing obviously
wrong in the diff. Can someone take a look before we scale out more pods?"

Nobody had touched anything that looked like a synchronization primitive.
The diff that shipped the week before only touched a buffer-pooling helper —
swapping a bespoke byte-array cache for the "obviously correct" BCL default,
ArrayPool<byte>.Shared. That refactor was reviewed and merged specifically
because it removed custom code in favor of a well-known, heavily optimized
framework type. If anything, it should have been a free win.

This is the kind of regression static analysis is structurally blind to: no
analyzer rule says "using ArrayPool<T>.Shared across threads is suspicious."
It's the recommended way to pool buffers in .NET. The problem isn't in the
code you'd read in a diff — it's in a runtime behavior that only shows up
under a specific, easy-to-miss usage pattern.

The investigation, as it actually happened

This is the real value proposition of dotnet-diagnostics-mcp:
none of what follows required attaching a debugger, adding instrumentation, or
redeploying anything. It's a live conversation with an LLM that has MCP tools
wired to the running process.

Step 1 — orient.

user> Can you check what's going on with pid 41213? CPU looks high.

assistant> Let me look at the process first.
→ inspect_process(view="triage", processId=41213)

{
  "processId": 41213,
  "resolvedProcess": { "name": "market-data-gateway", "runtime": "net10.0" },
  "summary": "CPU 78% (host has 16 cores). No memory growth trend. No recent
               GC pause anomalies. Consider a CPU sample to see where time goes.",
  "hints": [
    "collect_sample(kind=\"cpu\", processId=41213, durationSeconds=10)"
  ]
}

Nothing screaming "leak," nothing screaming "GC." CPU is just... busy. Time to
see where.

Step 2 — sample.

assistant> Taking a 10-second CPU sample.
→ collect_sample(kind="cpu", processId=41213, durationSeconds=10, topN=20)

{
  "processId": 41213,
  "totalSamples": 18545,
  "summary": "Hottest self-time method: System.Threading.Monitor.Enter_Slowpath
              (2933 exclusive, 15.8% of samples). Rank self-time with
              query_snapshot(view=\"top-methods\") or walk the call path with
              view=\"call-tree\".",
  "handle": "A0CKKWH5VVS9Q68AH3GG",
  "hints": [
    "query_snapshot(handle=\"A0CKKWH5VVS9Q68AH3GG\", view=\"caller-callee\", rootMethodFilter=\"Monitor.Enter_Slowpath\")"
  ]
}

That's the first real surprise. 15.8% of all CPU samples land inside
Monitor.Enter_Slowpath. Nobody wrote a lock statement in this service.
grep -r "lock (" across the whole repo returns nothing relevant. So where is
a contended monitor coming from?

Step 3 — trace the lock back to its call site.

assistant> There's no explicit lock in this codebase. Let's see who's calling
into the monitor slow path.
→ query_snapshot(handle="A0CKKWH5VVS9Q68AH3GG", view="caller-callee",
                  rootMethodFilter="Monitor.Enter_Slowpath")

{
  "method": "System.Threading.Monitor.Enter_Slowpath(System.Object)",
  "exclusiveSamples": 2933,
  "exclusivePercent": 15.82,
  "callers": [
    {
      "method": "MarketData.BufferPool.Return(byte[])",
      "samples": 1478,
      "percent": 7.97
    },
    {
      "method": "MarketData.Broadcaster+<>c__DisplayClass.<ConsumeLoop>b__0()",
      "samples": 1455,
      "percent": 7.85
    }
  ]
}

Both callers are our code — a thin wrapper method calling .Rent() on one
side, and a per-connection consume loop calling .Return() on the other.
Not a ThreadPool internal, not GC. The lock is being taken
inside ArrayPool<byte>.Shared itself, and it's the pool, not any
business logic, that's contended.

Step 4 — read the actual lock, not a guess about it.

ArrayPool<byte>.Shared's internals are in System.Private.CoreLib — no
source, no PDB for the private implementation type. This is exactly what the
companion server, dotnet-assembly-mcp,
is for: static navigation and on-demand decompilation of compiled assemblies,
including the BCL itself.

assistant> Let's not guess. I'll look up the actual pool implementation
in the runtime binary you're running.
→ find_method(mvidOrPath="System.Private.CoreLib.dll", namePattern="^Return$")

{
  "summary": "5 match(es) for /^Return$/.",
  "matches": [
    { "typeFullName": "System.Buffers.SharedArrayPool`1", "methodName": "Return",
      "signature": "void System.Buffers.SharedArrayPool`1.Return(!0[], bool)",
      "handle": "m:e8c78f6b-...:0x060038A7" }
  ]
}

assistant> Decompiling the real Return method for this exact runtime build.
→ decompile_method(moduleVersionId="e8c78f6b-...", metadataToken="0x060038A7")

public override void Return(T[] array, bool clearArray = false)
{
    // ...
    SharedArrayPoolThreadLocalArray[] array2 = t_tlsBuckets ?? InitializeTlsBucketsAndTrimming();
    // ... same-thread fast-path slot swap ...
    if (array3 != null)
    {
        flag2 = (_buckets[num] ?? CreatePerCorePartitions(num)).TryPush(array3);
    }
    // ...
}

assistant> And the fallback path that pushes to a per-core partition:
→ find_method(mvidOrPath="System.Private.CoreLib.dll", namePattern="^TryPush$")
→ decompile_method(moduleVersionId="e8c78f6b-...", metadataToken="0x060038B3")

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public bool TryPush(Array array)
{
    bool result = false;
    Monitor.Enter(this);
    // ... push onto a small fixed-size array-backed stack ...
    Monitor.Exit(this);
    return result;
}

There it is — Monitor.Enter(this), in the flesh, in the exact binary
this process is running: the actual internal type backing
ArrayPool<byte>.Shared in this runtime build is SharedArrayPool<T>, and
its per-core fallback is guarded by a plain CLR monitor. This is why the
call-tree pointed straight at Monitor.Enter_Slowpath: it's a real, ordinary
monitor, contended by every thread whose Return misses the per-thread
cache.

To be clear: dotnet/runtime's source is public on GitHub — nothing here was
hidden. The point isn't that the source was unreachable, it's the ergonomics
of the query. Getting the same answer the "normal" way means: know (or guess)
which internal type backs ArrayPool<T>.Shared today, find the right tag in
dotnet/runtime that matches the exact SDK/runtime patch this process is
actually running, navigate to the right file, and read enough surrounding
code to trust you're looking at the live behavior and not a since-changed
version. decompile_method(moduleVersionId, metadataToken) collapses all of
that into one call, scoped to the exact assembly loaded in the exact process
under investigation — no version-matching, no guessing a type name, no
context-switch out of the chat.

Checking the application code (only now, after both tools already
pointed at the exact mechanism, not before):

// One dedicated broadcaster thread — the ONLY thread that ever Rents.
while (running)
{
    var buffer = ArrayPool<byte>.Shared.Rent(FrameSize);
    FillFromMarketFeed(buffer);
    channel.Writer.TryWrite(buffer);
}

// N per-connection consumer tasks — each may Return a buffer it never Rented.
await foreach (var buffer in channel.Reader.ReadAllAsync())
{
    await connection.WriteAsync(buffer);
    ArrayPool<byte>.Shared.Return(buffer); // <-- always a different thread than Rent
}

Exactly the pattern the tool output implied: one thread rents, many other
threads return.

Why this is invisible without live evidence

ArrayPool<T>.Shared isn't a naive shared bag — its current .NET 10
implementation, SharedArrayPool<T>, keeps a single-slot cache stored
per-thread ([ThreadStatic] buckets): if the same thread that rented a
buffer also returns it, the operation is a plain field swap, no
synchronization at all. The moment a different thread returns it, that fast
path can't apply (the slot belongs to another thread), so the buffer falls
through to a small set of per-core partitions, each guarded by a plain
Monitor. With a handful of cores and dozens of consumer threads all
returning concurrently, those few partitions become a genuine contention
point.

None of this is a bug in ArrayPool<T>. It's working exactly as designed —
optimized for the common case (rent-use-return on one thread, e.g. inside a
single request handler), and gracefully degrading, but not silently free,
for the cross-thread fan-out case. There is no compiler warning, no analyzer
rule, and no code-review heuristic for "you are about to violate an
implicit performance assumption of a BCL type you didn't write." The only way
to know, for certain, what this process, running this runtime build, is
actually doing is to watch where the CPU goes and read the exact binary it's
running.

Fix and verification

The fix isn't "add a lock" (there's nothing to protect) — it's swap the pool
implementation to one designed for the actual ownership pattern: many threads
returning items nobody-in-particular rented, i.e., a plain lock-free queue.

public sealed class CrossThreadBufferPool
{
    private readonly ConcurrentQueue<byte[]> _pool = new();
    public byte[] Rent(int size) => _pool.TryDequeue(out var buf) ? buf : new byte[size];
    public void Return(byte[] buffer) => _pool.Enqueue(buffer);
}

Isolated cost, before/after (BenchmarkDotNet, 20,000 cross-thread
Return calls, buffers pre-rented on a background thread outside the timed
region so only Return itself is measured):

Scenario	Mean time (20,000 calls)	vs. contended baseline
`ArrayPool.Shared.Return`, cross-thread (the bug)	~4.3–5.1 ms	1x (baseline)
`ConcurrentQueue<byte[]>` `Return`, cross-thread (the fix)	~126–146 µs	~34x faster
`ArrayPool.Shared` full Rent+Return, same thread — theoretical best case	~115–150 µs	~34–40x faster

The last row is the ceiling: the one scenario with genuinely zero
synchronization, because the per-thread cache slot is always hit. Comparing
it to the ConcurrentQueue fix shows exactly how much overhead our own fix
still carries: ~126 µs vs. ~115 µs — roughly 10% above the theoretical
best, for a data structure built to be used safely by an arbitrary number
of unrelated threads. That's the honest cost of "general-purpose
thread-safe," and it's a rounding error next to the 34x we recovered.

A single cross-thread Return call on the unfixed pool costs more than an
entire same-thread Rent+Return round trip. That's how disproportionate the
fast-path miss is.

Live re-check after the fix — same 2-thread (1 producer / 1 consumer)
topology, same CPU sampler, before touching anything else:

Metric	`ArrayPool.Shared` (cross-thread)	Lock-free pool (cross-thread)	Same-thread control
Throughput	~3.2M ops/s	~6.6M ops/s	~20M ops/s
`Monitor.Enter_Slowpath` in CPU sample	15.8% exclusive	0% — gone entirely	n/a (no shared pool contention path)

assistant> With the lock-free pool under the same load:
→ collect_sample(kind="cpu", processId=41213, durationSeconds=8, topN=20)

{
  "summary": "Hottest self-time method: System.Threading.Thread.Sleep(int32)
              (3972 exclusive, 40.6% of samples). No Monitor frames in the
              top 20 hotspots.",
  ...
}

No Monitor.Enter_Slowpath anywhere in the profile. The contention didn't
move — it disappeared, because the pool that produced it is gone.

The obvious follow-up question: is pooling even worth it here?

ArrayPool<T>.Shared itself exists as an optimization over the naive
baseline — just calling new byte[size] and letting the GC reclaim it. A
fair objection to everything above: if the shared pool is this contended
under cross-thread Return, maybe the honest fix is to drop pooling
entirely, not swap in a different pool. Mean latency might even look
competitive, since a plain allocation has zero synchronization of any kind —
but the expectation is that Gen0/Gen1 GC pressure would show up in the tail
(P99), not the mean.

We tested it — same 2-thread producer/consumer topology, only the pool
implementation swapped for one that allocates fresh on every Rent and does
nothing on Return:

Scenario	Throughput	`Monitor` contention
`ArrayPool.Shared`, cross-thread	~3.2M ops/s	15.8% (Monitor)
Lock-free queue pool, cross-thread	~6.6M ops/s	0%
No pooling (`new byte[size]` every call)	~180K ops/s	0%

No pooling isn't a tail-latency-only regression — it's ~18x slower on raw
throughput, worse than the contended ArrayPool.Shared baseline we started
from. The reason shows up immediately in a live GC pause capture over the
same window:

assistant> Let's check what removing the pool entirely does to GC.
→ collect_events(kind="gc", processId=41213, durationSeconds=10)

{
  "summary": "134 collection(s), max pause 69.9ms, total pause 5118.1ms."
}

assistant> Breaking that down:
→ query_snapshot(handle="...", view="pauseHistogram")

{
  "totalCollections": 134,
  "maxPauseTime": "00:00:00.0698743",
  "buckets": [
    { "label": "<1ms",      "count": 0 },
    { "label": "1-10ms",    "count": 0 },
    { "label": "10-100ms",  "count": 134 },
    { "label": "100-1000ms","count": 0 },
    { "label": ">=1s",      "count": 0 }
  ]
}

assistant> And by generation:
→ query_snapshot(handle="...", view="byGeneration")

{
  "generations": [
    { "bucket": "gen1", "count": 134, "totalPause": "00:00:05.1180759",
      "meanPause": "00:00:00.0381945", "maxPause": "00:00:00.0698743" }
  ]
}

134 gen1 collections in a 10-second window — 13.4 per second, every single
one landing in the 10–100ms bucket — for 5.12 seconds of accumulated pause
time inside those 10 seconds. Over half the wall clock is GC pause, not
application throughput. That's not a tail-latency footnote; it dominates the
mean too, once allocation volume is high enough to keep pushing 4KB buffers
into gen0 fast enough to promote and collect on a ~130ms cadence.

So the honest ranking, worst to best, for this specific cross-thread
fan-out pattern is: no pooling (worst, by both mean and tail) → shared pool
with cross-thread Return (contended but bounded) → a pool built for the
actual ownership shape (best on every axis measured). ArrayPool<T>.Shared
being contended here doesn't mean pooling was the wrong call — it means the
specific pool's ownership assumption (same-thread Rent/Return) didn't match
this workload's shape. The fix was never "go back to allocating"; it was
"pool it the way this workload actually uses it."

The takeaway

Static analysis, linters, and code review are excellent at catching shapes
of bugs — a missing await, a lock around the wrong object, an O(n²)
loop. They cannot catch a case where the code is a textbook-correct call into
a well-designed BCL type, and the only thing wrong is a runtime ownership
pattern that BCL type happens to be sensitive to. You either know this
specific gotcha already, or you find it by watching the process — there is no
third option.

dotnet-diagnostics-mcp exists so that "watching the process" is a normal
step in an LLM-driven investigation, not a specialized skill gated behind
whoever on the team happens to know dotnet-trace by heart. Every dynamic
step above — inspect_process, collect_sample, query_snapshot — is a
single MCP tool call an assistant can make on its own, against a real running
.NET process, with no code changes and no redeploy. And when the trail leads
into a BCL type nobody on the team has source for, its companion server,
dotnet-assembly-mcp,
picks up exactly where live tracing stops: real decompiled source of the
exact binary the process is running, not a recollection of how some type
used to work.

The reproduction and all numbers in this post are in a small, standalone,
open repro you can run yourself — no proprietary code involved. The
investigation pattern itself (fix unrelated to this repro) is inspired by a
real production change in B3MarketDataPlatform,
a public repo, commit ac2dc9f.

dotnet-diagnostics-mcp is open source: github.com/pedrosakuma/dotnet-diagnostics.
It ships both an MCP server (for your LLM client of choice) and a standalone
CLI (dotnet-diagnostics-cli) for scripting the same investigations by hand.