Os caracteres devem ser codificados em bits de alguma forma. A maioria das strings na Internet, incluindo esta postagem no Habré, são codificadas em UTF-8. O formato UTF-8 representa "caracteres" em um, dois, três ou quatro bytes. Esta é uma generalização para o padrão ASCII, que usa apenas um byte por caractere. Ou seja, a string ASCII também é uma string UTF-8.
Na verdade, é um pouco mais complicado porque, tecnicamente, o UTF-8 descreve pontos de código. Um personagem visível como um emoji pode consistir em vários pontos de código ... mas a maioria dos programadores não precisa dessas palavras pedantes.
Existem outros padrões também. Algumas linguagens de programação mais antigas, como C # e Java, contam com UTF-16. Ele usa dois ou quatro bytes por caractere. Parecia uma boa ideia na época, mas agora o consenso está se movendo para usar o UTF-8 a qualquer hora, em qualquer lugar.
A maioria das codificações tem restrições aplicáveis. Em outras palavras, nem toda sequência de bits aleatória pode ir para UTF-8. Portanto, você precisa validar as strings - verifique se é realmente UTF-8.
O que isso importa? Ótimo. Por exemplo, o servidor web da Microsoft tem essa vulnerabilidade: ele aceita um URI que parece ser válido e seguro, mas quando interpretado pelo servidor, dá ao invasor acesso remoto ao disco. Mesmo deixando de lado as questões de segurança, você quase certamente não deseja armazenar linhas inválidas em seu banco de dados.
Assim, linguagens de programação, servidores web, navegadores e motores de banco de dados estão constantemente validando o UTF-8.
Se suas strings são na maioria apenas ASCII, as verificações são muito rápidas e a verificação UTF-8 não é um problema. Já se foi o tempo em que a maioria das strings era codificada em ASCII. Vivemos em um mundo de emojis e muitos alfabetos nacionais.
Em 2018, eu me perguntei:com que rapidez as strings UTF-8 podem ser validadas ? Naquela época, encontrei uma opção de validação com vários ciclos de CPU por símbolo. Alguém poderia ficar calmo com isso, mas essa resposta não me satisfez.
O trabalho demorou anos, mas parece que agora conseguimos uma versão próxima do ideal. O novo algoritmo é uma ordem de magnitude mais rápido do que outras opções de pesquisa rápida. Preparamos um white paper: "Validação UTF-8 em menos de uma instrução por byte" (a ser publicado em Software: Practice and Experience ) e também publicamos um utilitário de benchmarking .
Todos os detalhes são explicados em um artigo científico, portanto, não entraremos em detalhes aqui, mas apenas consideraremos brevemente a essência. A parte principal da validação UTF-8 é feita procurando por pares de bytes consecutivos. Depois de verificar todos os pares de bytes e identificar todas as possíveis violações que podem ser encontradas a partir dessas informações, resta relativamente pouco a fazer.
Todos os processadores possuem instruções SIMD rápidas. Eles trabalham com registros amplos (128 bits, 256 bits, etc.). A maioria dos conjuntos tem uma instrução de "pesquisa vetorial" que pega, digamos, valores de 16 bytes (variando de 0 a 16) e os pesquisa em uma tabela de 16 bytes. Nos processadores Intel e AMD, esta descrição corresponde à instrução
pshufb... Um valor entre 0 e 16 às vezes é chamado de nibble e abrange 4 bits. O byte é composto por dois nibble (baixo e alto).
Em nosso algoritmo de busca, a instrução de busca vetorizada é chamada três vezes: uma vez para nibble baixo, uma vez para nibble alto e uma vez para nibble alto para o próximo byte. Temos três tabelas de pesquisa de 16 bytes correspondentes. Se selecionado corretamente, o AND bit a bit das três pesquisas encontra qualquer erro.
Consulte o artigo científico para obter mais detalhes , mas a validação UTF-8 quase completa é feita com apenas cinco linhas de código C ++ rápido sem ramificações ... e essas cinco linhas verificam blocos de até 32 bytes por vez ...
simd8 classify(simd8 input, simd8 previous_input) {
auto prev1 = input.prev<1>(previous_input);
auto byte_1_high = prev1.shift_right <4>().lookup_16(table1);
auto byte_1_low = (prev1 & 0x0F).lookup_16(table2);
auto byte_2_high = input.shift_right <4>().lookup_16(table3);
return (byte_1_high & byte_1_low & byte_2_high);
}Embora não seja imediatamente óbvio, esta validação é suficiente e 100% segura. Realmente é . Restam apenas algumas etapas técnicas adicionais de baixo custo.
Como resultado, em processadores Intel / AMD recentes, leva um pouco menos de uma instrução por byte para verificar até mesmo a entrada aleatória mais inútil. Como o código é extremamente otimizado, você pode ir até três instruções por ciclo e ainda mais. Ou seja, usamos uma pequena parte do ciclo (menos de um terço) por byte de entrada em uma CPU moderna. Assim, a velocidade de processamento é mantida de forma confiável em mais de 12 GB / s.
A lição é que as tabelas de pesquisa regulares são úteis, mas as tabelas vetorizadas são os blocos de construção fundamentais para algoritmos de alta velocidade.
Se você precisar usar o recurso de validação UTF-8 rápido na produção, recomendamos a biblioteca simdjson (versão 0.5 ou superior). Ele é bem testado e possui recursos internos úteis, como envio em tempo de execução. Embora a biblioteca seja projetada para analisar JSON, você pode usá-la puramente para validação UTF-8, mesmo se não houver JSON. Ele oferece suporte a processadores ARM e x64 de 64 bits e também possui processamento de fallback para outras CPUs. Nós o empacotamos em um arquivo de cabeçalho junto com um arquivo de origem; então você pode simplesmente colocá-lo em seu projeto C ++.
Trabalho prévio... O principal mérito na popularização do método de classificação vetorial, que é a chave do algoritmo de busca, pertence a Mula. Pelo que eu sei, Keizer foi o primeiro a propor nossa estratégia de busca tripla. O primeiro algoritmo de validação UTF-8 prático baseado em SIMD foi criado por K. Willets. Várias pessoas, incluindo Z. Wegner, fizeram melhorias nele. Travis Downs teve ideias inteligentes sobre como acelerar algoritmos convencionais.
Leitura adicional . Se você gosta deste trabalho, pode gostar de outros artigos sobre tópicos relacionados: "Codificação e decodificação em Base64 em velocidade quase de cópia na memória" (Software: Practice and Experience, 50 (2), 2020) e "Analisando Gigabytes de JSON por segundo" ( VLDB Journal, 28 (6), 2019).