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:

Related posts

What a forward deployed AI engineer actually does

Not a solutions engineer, not a researcher. A working definition of the forward deployed AI engineer role, drawn from do

0dev.to

How to Get Your First Freelance Client When You Have No Experience

A digital marketing learner from Kerala on the practical steps between “I have skills” and “someone is paying me.” Every

0dev.to

Best shadcn registries for ready-made blocks in 2026

Checked against official sites on November 2, 2026. You need a pricing section, a hero and a footer. The useful question

0dev.to

How we score an election forecast (and what the score does not measure)

How we score an election forecast (and what the score does not measure) TL;DR: We score the reasoning before the outcome

0dev.to

Handling Failures as Values in Agent-Generated Code

I am Jake Burwick, a high school student, and I built Vow, an open source programming language under the MIT license des

0dev.to

My Favourite Laptop

Article URL: https://blog.jsbarretto.com/post/laptop Comments URL: https://news.ycombinator.com/item?id=50339815 Points:

0Hacker News