Case-folding a 45 GiB/s: otimização de baixo nível no GitHub

Alexander Neubeck e Greg Orzell, do GitHub, publicaram em 31 de julho o “Don’t Stop Early”, sobre como acelerar a conversão de caixa de texto no Blackbird, o motor de busca de código do GitHub. O índice, segundo eles, tem 480 TB de código em 180 milhões de repositórios, e todo byte passa por case-folding, a normalização para comparar texto sem diferenciar maiúsculas de minúsculas.

A ideia central: tirar a saída antecipada

O caminho rápido para ASCII removia três ramificações. A primeira trocava if (b >= 0x80) break por um acumulador high_bit_acc |= *b, testado só depois do laço. A segunda transformava a detecção de maiúscula em aritmética: b.wrapping_sub(b'A') < 26. A terceira aplicava a conversão com uma operação de bits: *b |= u8::from(is_upper) << 5. Sem desvios, o compilador consegue vetorizar o laço.

O que a medição mostra

Os números são de um Apple M4, em texto ASCII puro:

• versão com ramificação e saída antecipada: 3,1 GiB/s, zero instruções vetoriais;
• corpo sem ramificação, mas mantendo o break: 2,6 GiB/s;
• sem ramificação e sem break: 7,6 GiB/s, vetorização parcial;
• versão final: mais de 45 GiB/s, com 41 instruções vetoriais.

Note que remover só as ramificações do corpo piorou o resultado. O ganho veio de eliminar também o break.

O caminho para Unicode

Para o resto do Unicode, eles usam uma estrutura de 1.776 bytes, sem decodificar e recodificar: um bitmap de páginas (248 bytes) para testes negativos rápidos, faixas por runs (238 bytes) que comprimem 1.484 conversões, e uma tabela de deltas (952 bytes). Na comparação, o simple_fold fez mais de 45 GiB/s em ASCII puro contra 1,21 GiB/s do simd_normalizer e 213 MiB/s de um HashMap. Em CJK sem conversões foram 2,95 GiB/s. No pior caso, com tudo precisando de conversão, 869 MiB/s, ligeiramente abaixo dos 922 MiB/s do simd_normalizer.

Limites declarados

O resultado depende da arquitetura: largura do vetor, banda de memória e endianness. O código exige UTF-8 bem formado e em forma mais curta, o que o &str do Rust garante. Não implementa conversões completas como ß para ss nem localidades turcas. O código foi aberto como o crate casefold. O post não informa quanto isso reduziu o tempo de indexação ou a latência de consultas no Blackbird.