A GitHub conseguiu executar o folding de maiúsculas e minúsculas, ou Case Folding, a uma velocidade superior a 45 gigabytes por segundo em um único núcleo, redesenhando o loop de software para que ele não parasse no primeiro byte não ASCII, mas percorresse todo o buffer sem ramificações de controle dependentes dos dados. A empresa usa esse processo no mecanismo de busca de código Blackbird, que indexa mais de 180 milhões de repositórios e mais de 480 terabytes de código-fonte.
Alexander Neubeck e Greg Orzell apresentaram os detalhes desse design em uma publicação no blog da GitHub em 31 de julho de 2026. A publicação também anunciou a disponibilização do resultado em uma biblioteca Rust de código aberto chamada casefold.
Folding de maiúsculas e minúsculas não é apenas conversão para letras minúsculas
Mecanismos de busca e ferramentas de correspondência de texto precisam de uma representação padrão que torne iguais, para fins de comparação, strings que diferem apenas na capitalização. Isso aparece em buscas, expressões regulares que não diferenciam maiúsculas de minúsculas, nomes de usuário e nomes de host.
Mas converter o texto para letras minúsculas não produz o mesmo resultado. A conversão para minúsculas pode depender do idioma e do contexto, como a diferença na forma da letra sigma grega no fim e no interior de uma palavra, ou as regras diferentes para a letra I em turco. Já o folding de maiúsculas e minúsculas é projetado para comparação e, portanto, é independente do idioma e do contexto. O resultado também difere em casos como a letra alemã ß, a letra turca İ e a sigma grega final.
A biblioteca executa um folding simples de um para um, de acordo com as condições C e S do arquivo CaseFolding.txt pertencente ao banco de dados de caracteres Unicode. Ela não executa operações de folding de múltiplos caracteres, como converter ß em ss, nem operações de folding específicas do turco.
Remoção da otimização que estava deixando o loop mais lento
Como o código-fonte é composto em sua maior parte por caracteres ASCII, o caminho mais rápido se concentra em converter as letras latinas maiúsculas de A a Z em letras minúsculas. O design intuitivo parava assim que encontrava um byte não ASCII e então transferia o restante do texto para um caminho Unicode. Porém, testes em um processador Apple M4 mostraram que esse método não ultrapassava cerca de 3 gigabytes por segundo.
A principal causa eram as ramificações de controle dentro do loop. Em vez de testar cada byte e parar cedo, o algoritmo reúne o bit mais significativo de todos os bytes em uma única variável e testa o resultado depois que a varredura termina. Já o teste para verificar se o byte está no intervalo das letras maiúsculas é executado aritmeticamente, subtraindo a letra A com wraparound e comparando o resultado ao número 26. Depois, uma máscara aritmética é usada para definir o quinto bit do byte, convertendo a letra maiúscula em minúscula sem uma ramificação ou escrita condicional.
Essa estrutura permite que o compilador LLVM gere instruções vetoriais que processam 16 bytes por vez usando NEON no Apple M4. O resultado ultrapassa 45 gigabytes por segundo, aproximando-se do limite da largura de banda da memória. As medições da GitHub indicam que a remoção da saída antecipada foi o fator que permitiu a vetorização; manter a saída baseada nos dados impede a criação de instruções vetoriais, mesmo que o restante do loop fique sem ramificações.
Por que uma varredura combinada nem sempre é mais rápida?
A GitHub testou uma solução intermediária baseada na verificação de ASCII em blocos, seguida da conversão do prefixo ASCII. Esse método lê os dados duas vezes, mas atingiu cerca de 23 gigabytes por segundo, muito mais rápido que o loop ingênuo, mantendo a capacidade de parar no primeiro bloco não ASCII.
Já combinar a verificação e a conversão em um único loop que opera sobre blocos de 16 bytes foi mais lento, atingindo cerca de 8,7 gigabytes por segundo contra 23 gigabytes por segundo da solução de duas passagens. Segundo a publicação, uma ramificação de saída antecipada após cada bloco impede que o compilador desenrole o loop ou oculte o tempo de espera entre leitura, teste, conversão e escrita. Por isso, dois loops limpos e passíveis de vetorização superaram um único loop que toca os dados menos vezes, mas contém uma ramificação dependente do conteúdo.
Redução das alocações de memória
A função simple_fold recebe uma string String por propriedade, o que permite modificar seu buffer e devolvê-lo diretamente. Se o texto for inteiramente ASCII, a mesma memória é devolvida após a conversão das letras no próprio local, sem um segundo buffer ou cópia adicional.
Quando há caracteres não ASCII, o algoritmo só cria um novo buffer quando chega a um caractere cujo tamanho ou conteúdo muda. A publicação explica que a maioria das operações de folding preserva ou reduz o comprimento do UTF-8, mas os caracteres U+023A e U+023E podem aumentar, cada um, de dois para três bytes. Por isso, o algoritmo reserva uma única vez uma capacidade máxima equivalente a aproximadamente 1,5 vez o comprimento da entrada, em vez de expandir o buffer gradualmente e recopiá-lo.
Ele também transfere grupos de bytes que não foram alterados usando copy_nonoverlapping, em vez de copiá-los byte a byte. Alguns textos não latinos, como CJK, Hangul, Kana, árabe, hebraico e símbolos, permanecem em sua alocação original quando não contêm caracteres que exigem folding.
Processamento de Unicode no espaço dos bytes
O Unicode 16.0 contém 1484 operações simples de folding, mas a GitHub compactou sua tabela para 1776 bytes explorando a concentração de caracteres passíveis de folding em páginas de 64 pontos de código. Para testar se um caractere precisa de folding, o algoritmo usa um mapa de bits; se o bit correspondente não estiver ativado, o caractere é rejeitado imediatamente, sem decodificar o UTF-8 ou procurar em uma tabela hash.
Dentro das páginas que contêm operações de folding, o algoritmo armazena intervalos contíguos em vez de um registro separado para cada ponto de código. Os intervalos são descritos por início, fim, passo e diferença, reduzindo cerca de 1484 operações a 238 intervalos distribuídos por 59 páginas. Ele também usa uma comparação paralela com oito chaves ao mesmo tempo para determinar o intervalo adequado.
Depois de encontrar o intervalo, os caracteres dobrados são calculados somando bytes no nível do UTF-8 a uma constante específica do intervalo, em vez de decodificar o caractere em um ponto de código e depois recodificá-lo. Isso permite lidar com mudanças de comprimento, como converter U+212A, o símbolo do kelvin, de três bytes para o caractere k de um byte, ou converter U+023A em um caractere de três bytes.
Esse método pressupõe que a entrada seja UTF-8 válida e bem formada, uma garantia fornecida pelos tipos String e str do Rust. Já dados brutos provenientes de outras fontes devem ter sua validade verificada ou ser normalizados antes do uso desses cálculos.
Resultado e limites das medições
No caso comum de ASCII, a velocidade da biblioteca ultrapassa 45 gigabytes por segundo, mais de 50% superior à da função não exatamente equivalente str::to_lowercase, de acordo com as medições apresentadas na publicação. Nos piores casos de entrada, em que a maioria dos caracteres precisa de folding, as soluções baseadas em cálculos no espaço dos bytes foram aproximadamente duas vezes mais rápidas que o caminho otimizado de decodificação e recodificação do UTF-8.
A GitHub ressalta que os números e as porcentagens de comparação são indicativos e não podem ser transferidos literalmente entre processadores, pois dependem da vetorização automática, de SWAR, de cálculos de bytes em ordem little-endian, além da largura de banda da memória e da arquitetura do processador. A publicação resume a ideia em dois princípios: percorrer completamente o caminho comum sem ramificações e executar o caminho raro específico de Unicode no espaço dos bytes, em vez de decodificar e recodificar os caracteres.