simdjson - Fazendo parse de JSON em GB/s
(github.com)-
Faz o parse usando o conjunto de instruções SIMD, com desempenho 2,5x maior que parsers existentes
-
Seleção automática, em tempo de execução, do parser otimizado para cada CPU: Haswell (AVX2) / Westmere (SSE4.2) / ARM64 / outros 64-bit
-
Suporte a validação completa de JSON e UTF-8
-
Um único arquivo .h + .cpp
-
Usa apenas 25% do conjunto de instruções em comparação com o RapidJSON e 50% em comparação com o sajson
4 comentários
Há várias bindings / ports, pelo visto
ZippyJSON: bindings em Swift para o projeto simdjson.
libpy_simdjson: bindings Python de alta velocidade para simdjson usando libpy.
pysimdjson: bindings Python para o projeto simdjson.
simdjson-rs: port para Rust.
simdjson-rust: wrapper para Rust (bindings).
SimdJsonSharp: versão em C# para .NET Core (bindings e port completo).
simdjson_nodejs: bindings Node.js para o projeto simdjson.
simdjson_php: bindings PHP para o projeto simdjson.
simdjson_ruby: bindings Ruby para o projeto simdjson.
fast_jsonparser: bindings Ruby para o projeto simdjson.
simdjson-go: port para Go usando assembly de Golang.
rcppsimdjson: bindings para R.
Versão em Rust - https://github.com/simd-lite/simd-json
Conteúdo da apresentação do desenvolvedor na QCon, "Parsing JSON Really Quickly: Lessons Learned"
https://www.youtube.com/watch?v=wlvKAT7SZIQ
Transcrição da palestra em vídeo no link:
https://www.infoq.com/presentations/simdjson-parser/
Fiquei curioso para saber como ele consegue alcançar uma velocidade tão alta e fui ler; parece mesmo uma verdadeira obra-prima de todo tipo de magia negra. Resumindo os pontos principais, fica mais ou menos assim.
[Introdução]
A maioria das bibliotecas de parsing de JSON é mais lenta do que a velocidade de leitura sequencial do drive
No drive do meu sistema (do palestrante, Daniel Lemire), a velocidade de leitura sequencial de arquivos de texto grandes é de 2.2 GB/s, mas a velocidade de parsing das principais bibliotecas JSON não acompanhava isso.
Como era raro encontrar bibliotecas que passassem de 1 GB/s de parsing, decidimos fazer a nossa própria.
Como resultado, conseguimos atingir uma taxa de processamento capaz de usar toda a largura de banda do drive. Fazendo as contas, usamos apenas 1.5 ciclos de CPU por byte de entrada. Como isso foi possível?
[Princípios diversos]
Evitar ao máximo desvios condicionais
Por exemplo, em um código simples que insere números aleatórios em um array, basta colocar um único
ifpara verificar se o número é ímpar e ele fica 5 vezes mais lento. Isso acontece porque o custo quando a predição de desvio da CPU falha é alto.Se removermos o
ifdo código acima usando operações de bits, a velocidade quase volta ao normal.É verdade que, ao executar o código repetidamente, a precisão da predição de desvio pode melhorar e a queda de desempenho pode diminuir, mas isso no fim é um comportamento não determinístico, então quando a predição de desvio entra em jogo fica difícil prever ou medir o desempenho.
Usar SIMD ativamente para trabalhar com palavras mais largas
Ao usar instruções SIMD, é possível trabalhar com registradores mais largos do que 64 bits, processando mais dados por ciclo. (Por exemplo, SSE e NEON usam 128 bits, AVX usa 256 bits.) Por isso, o SIMD foi usado de forma agressiva sempre que possível. Esse é o segredo de ter conseguido usar apenas 1.5 ciclos por byte de entrada.
Para usar SIMD, foram utilizadas funções intrínsecas dependentes de processador específico (
intrinsic functions). Não se recomenda usar assembly diretamente.Evitar alocação de memória/objetos
Medir o desempenho o tempo todo
O desenvolvimento foi guiado por benchmarks. O nosso CI inclui benchmarks de desempenho.
Aliás, ao fazer qualquer tarefa intensiva em CPU, é preciso ter em mente que a frequência de operação da CPU continua variando.
[Casos práticos]
Exemplo 1: validar se é UTF-8 correto
A tarefa de validar se dados arbitrários de entrada formam code points UTF-8 válidos normalmente envolve vários desvios condicionais.
Nós criamos um método com SIMD para validar 32 bytes como UTF-8 correto em no máximo 20 ciclos, sem nenhum desvio condicional.
Como os bytes de UTF-8 não podem ter valor inteiro maior que 244, basta colocar os dados em um registrador de 256 bits com instruções SIMD, subtrair o inteiro 244 de cada byte usando aritmética de saturação (
saturation arithmetic: operação que limita a faixa do resultado) e então verificar apenas se não há nenhum valor diferente de zero.Esse método é mais de 20 vezes mais rápido do que a abordagem com desvios condicionais!
Exemplo 2: classificar tipos de caracteres
Para fazer o parsing de JSON, é preciso classificar vários caracteres por tipo, como vírgulas, dois-pontos, parênteses, espaços em branco etc.
x86-64 e ARM NEON têm instruções que consultam de uma vez uma tabela de lookup de 16 bytes.
Divide-se 1 byte em 4 bits altos e 4 bits baixos, aplica-se duas tabelas de lookup previamente preparadas e depois faz-se uma operação AND no resultado.
O código pode até parecer sujo, mas com apenas 5 instruções é possível classificar 16 caracteres sem nenhum desvio condicional.
Exemplo 3: detectar caracteres de escape
Será que dá para detectar caracteres de escape, representados ao colocar o caractere de barra invertida (
\) antes, sem usar desvios condicionais? Em especial, também é preciso tratar casos em que várias barras invertidas aparecem em sequência para escapar a própria barra invertida.Nesses casos, existe um truque: basta olhar apenas para as barras invertidas em posições ímpares.
Mantendo como constante uma bitmask que representa posições pares e ímpares, e passando por operações de bits mais complexas, dá para filtrar os caracteres de escape sem desvios.
Depois de filtrar as aspas escapadas, o que sobra são as aspas que indicam strings.
Se tratarmos as posições dessas aspas como uma bitmask e repetirmos operações de bits com
xor, é possível obter uma bitmask que representa a posição das strings. Essa parte pode ser feita com uma única instrução na maioria dos processadores.Também há truques para relacionar conjuntos de bits e posições de strings, mas vou pular isso por falta de tempo.
Exemplo 4: fazer o parsing de números
Fazer parsing de números é uma operação extremamente cara. Em um benchmark de parsing de ponto flutuante com uma função C bem otimizada, a velocidade obtida foi um absurdo de 0.09 GB/s. Era claramente um gargalo.
A maior parte do código de parsing numérico costuma processar um byte por vez. Isso definitivamente não é rápido.
Se você pegar 8 caracteres, montar um inteiro de 64 bits e aplicar uma certa fórmula que o palestrante bolou tarde da noite de um sábado, dá para saber se esses 8 caracteres formam um número de 8 dígitos consecutivos. Isso é importante porque, especialmente em números com muitos dígitos, o parsing leva mais tempo.
Vi também no Stack Overflow um snippet de código para fazer parsing rápido de inteiros de 8 dígitos. Dá para melhorar mais com SIMD, mas o importante aqui é a ideia dessa estratégia de processar bastante dado de uma vez só.
[Outros]
Runtime dispatch
Como havia muito código dependente de hardware, acabaram surgindo funções otimizadas para cada processador, e foi bastante difícil fazer com que, em tempo de execução, fosse chamada a função adequada ao tipo de processador.
Talvez não fique claro por que isso é difícil, mas o problema era implementar isso de forma portável, sem depender do tipo de compilador. Alguns compiladores tinham bugs, e a própria linguagem também não oferece suporte a isso.
Esse ponto era importante porque o simdjson é uma biblioteca open source de arquivo de cabeçalho único, fácil de integrar em outros projetos.
Outros
Existem wrappers para várias linguagens.
Existe uma versão portada para Rust, e as portas para Go e C# estão em preparação, mas não há port para Java.
Várias das fórmulas matemáticas usadas neste projeto foram criadas em conjunto com o coautor Geoff Langdale, e um artigo relacionado foi publicado no VLDB Journal. ( https://doi.org/10.1007/s00778-019-00578-5 )
Uau, li com muito interesse. Obrigado!