Como ReadOnlySpan<char>.IndexOf encontra uma substring com SIMD

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.

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.

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.

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:

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:

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:

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.

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:

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:

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.

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