Processamento de strings no serde_json fica 20% mais rápido

• O serde_json, usado como o parser JSON padrão do ecossistema Rust, obteve melhorias de desempenho de 10%, 23% e 32% em benchmarks com muitas strings apenas com pequenas otimizações internas
• O cálculo da posição de erro passou a usar memchr para encontrar o número de linhas e a última quebra de linha, em vez de percorrer diretamente o início da string, reduzindo a diferença do caminho de erro, que era mais de 2 vezes mais lento que o caminho de sucesso
• O loop central de parsing de strings agora verifica \, " e caracteres de controle de uma só vez com SWAR, em vez de procurá-los separadamente, garantindo baixa latência em strings curtas mesmo sem SIMD real
• A decodificação de escapes \u reduziu custos de branches e shifts com LUT, inteiros com sinal e uma tabela de shifts pré-computados; o parsing do JSON de War and Peace em russo ficou mais rápido, passando de 284 MB/s para 344 MB/s
• O gargalo posterior, a codificação UTF-8, foi resolvido com geração manual de UTF-8, evitando custos de inicialização e cópia de char::encode_utf8 e Vec::extend_from_slice, elevando o mesmo benchmark para 374 MB/s

---

Por que otimizar o serde_json tem grande impacto

• serde é o principal framework de serialização e desserialização do Rust, e serde_json é amplamente usado como a combinação oficial para processamento de JSON
• No momento da publicação, serde_json tinha 26.916 dependentes reversos, enquanto simd-json tinha 66
• Com esse nível de uso, até pequenas melhorias internas no serde_json podem gerar um efeito acumulado em todo o ecossistema Rust
• Em uma situação em que muitos usuários não trocam facilmente para outro parser JSON, otimizações de baixo risco dentro da biblioteca existente são práticas

Cálculo da posição de erro: de um loop simples para memchr

• Em benchmarks do caminho de erro, serde_json era mais de 2 vezes mais lento que o caminho de sucesso com os mesmos dados
  • Nos datasets canada, citm_catalog e twitter, o caminho de erro era 48% a 77% mais lento que o caminho de sucesso
• O gargalo era a função position_of_index(), que converte um índice em line/column para formatar mensagens de erro
  • A implementação anterior percorria self.slice[..i] byte a byte e atualizava line e column sempre que encontrava \n
• Ao dividir o cálculo em duas etapas, é possível aplicar memchr
  • Contar o número de \n dentro de self.slice[..i] para obter o número de line com base zero
  • Encontrar a posição do último \n e subtraí-la de i para obter o número de column
• memchr oferece uma implementação otimizada para busca e contagem de um único caractere e usa SIMD internamente
• Depois que o PR #1160 foi integrado, o desempenho do caminho de erro melhorou bastante
  • No DOM de canada, o caminho de erro subiu de 122 MB/s para 216 MB/s
  • Em citm_catalog com struct, subiu de 195 MB/s para 736 MB/s
  • O caminho de erro ainda era mais lento que o caminho de sucesso, mas a diferença diminuiu

Busca por escapes em strings: encontrar três condições de uma vez

• O loop central anterior do parsing de strings consultava a tabela ESCAPE e avançava por bytes que não eram escapes
  • Em strings JSON, os alvos de escape que precisam ser tratados são \, " e caracteres de controle ASCII até 0x1F
  • Pela especificação JSON, códigos de controle não são permitidos dentro de strings
• A primeira tentativa usava memchr2 para encontrar primeiro \ ou " e depois verificava caracteres de controle separadamente
  • Isso acabava percorrendo a string duas vezes, uma rápida e outra lenta, ficando mais lento que antes
  • Vetorizar apenas a metade simples e deixar o restante escalar não levou a uma melhoria geral
• A segunda tentativa combinava memchr2 com SIMD manual para verificar a ausência de caracteres de controle
  • Em strings curtas, o custo da chamada da função escolhida em tempo de execução se tornava pesado
  • Em strings longas, o problema de ler a memória duas vezes permanecia
• A implementação final foi organizada para encontrar \, " e caracteres de controle em uma única passada

Implementando processamento próximo a SIMD com SWAR

• Para evitar inserir código SIMD específico de plataforma, foi usada a técnica SWAR (SIMD Within A Register)
  • Em vez de SIMD de 128 bits, uma palavra de 64 bits é tratada como 8 bytes
  • Operações bit a bit verificam simultaneamente se cada byte satisfaz a condição
• A verificação de caracteres de controle transforma a condição c >= 0 && c < 0x20 em uma forma baseada em operações bit a bit
  • Em blocos de 8 bytes, isso é verificado com uma máscara no formato !c & (c - 0x2020202020202020) & 0x8080808080808080
  • O borrow de uma subtração de 64 bits pode se propagar para bytes superiores, mas isso não é um problema para o objetivo de encontrar o caractere de controle na posição mais baixa
• \ e " também são verificados de modo semelhante e combinados em uma única expressão
  • A expressão completa é composta por 9 operações bit a bit
  • Em SIMD x86 seriam necessárias 7 operações, portanto a vazão é menor, mas em strings curtas a latência é mais importante
• No json-benchmark, esse código SWAR foi mais eficiente que o código SIMD real
• Em strings muito curtas, SWAR pode ficar mais lento que o código escalar
  • Foi observada regressão em strings de cerca de 5 caracteres
  • Para proteger padrões comuns como a string vazia "" e escapes consecutivos \r\n, \uD801\uDC37, a implementação verifica se o primeiro caractere é um escape antes de entrar no loop SWAR
• O resultado da otimização de busca em strings variou conforme o dataset
  • twitter com struct foi de 638 MB/s para 785 MB/s, +23%
  • twitter DOM foi de 305 MB/s para 335 MB/s, +10%
  • citm_catalog com struct foi de 865 MB/s para 905 MB/s, +5%
  • Strings vazias ainda ficaram até 2% mais lentas em um microbenchmark específico

Otimização da decodificação de escapes Unicode

• serde_json processa tanto strings Unicode brutas quanto escapes \u
  • Por exemplo: "🥺" e "\ud83e\udd7a"
• A decodificação hexadecimal anterior usava uma LUT de 256 entradas para mapear cada caractere para um valor de 0 a 15
  • Processava '0'..='9', 'A'..='F' e 'a'..='f'
  • Caracteres inválidos eram marcados com um valor sentinela
• Como um escape \u lê 4 dígitos hexadecimais, o método anterior incluía shift, soma, comparação e branch condicional a cada repetição
• A implementação melhorada não retorna erro a cada iteração; ela processa os 4 caracteres e só depois verifica a validade
• A implementação final usa uma LUT [i8; 256] com dígitos inválidos como -1 e faz o cálculo com um inteiro de 32 bits
  • Em caso de sucesso, o resultado não é negativo; em caso de falha, torna-se negativo
  • Em x86, o load da memória e a extensão de sinal podem ser combinados em movsx
• Para reduzir a latência dos shifts, são usadas duas tabelas
  • HEX0: valor original
  • HEX1: tabela com o valor previamente deslocado 4 bits à esquerda
• A implementação foi organizada como decode_four_hex_digits(), com o loop claramente desenrolado
• Com essa otimização, o desempenho ao fazer parsing de War and Peace em russo no formato JSON-encoded subiu de 284 MB/s para 344 MB/s, uma melhoria de 21%

Gargalo de codificação UTF-8 e geração manual

• Após a decodificação de escapes Unicode, o gargalo passou a ser a codificação UTF-8
• UTF-8 codifica codepoints em 1 a 4 bytes, conforme o comprimento
  • 1 byte: 0xxxxxxx
  • 2 bytes: 110xxxxx 10xxxxxx
  • 3 bytes: 1110xxxx 10xxxxxx 10xxxxxx
  • 4 bytes: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
• char::encode_utf8 da biblioteca padrão do Rust escreve em um buffer &mut [u8], portanto o buffer já precisa conter valores u8 válidos
  • Não é possível escrever diretamente em um buffer não inicializado
  • Como UTF-8 é uma codificação de comprimento variável, é difícil para o LLVM eliminar a zeroização desnecessária
• serde_json processava isso com scratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes())
  • Usar um buffer local [0u8; 4] poderia, em tese, ajudar a análise de aliases
  • Na prática, por causa da cópia de comprimento variável de 1 a 4 bytes, o LLVM gerava uma chamada a memcpy
• Para evitar chamadas a memset e memcpy, o UTF-8 passou a ser gerado diretamente
  • O algoritmo em si é simples, mas exigiu unsafe
  • Junto com algumas pequenas mudanças, o benchmark de War and Peace melhorou mais +9%, de 344 MB/s para 374 MB/s

Resultado final

• Em benchmarks JSON com muitas strings, o desempenho do serde_json melhorou 10%, 23% e 32%, respectivamente
• Como muitos dados JSON contêm muitas strings, essa otimização pode impactar de forma ampla o código Rust que usa serde_json
• As melhorias vieram da remoção sequencial de gargalos diferentes, como cálculo de posição de erro, busca por escapes em strings, decodificação de escapes Unicode e codificação UTF-8

[GN⁺]

Comentários no Hacker News

• Esses truques de UTF-8 me deixam bem desconfortável, já vi ataques de confusão de parser demais
  o pessoal usa serde mais pela correção do que pela velocidade, então espero que tenham feito fuzzing até o fim com vários casos de strings UTF-8 inválidas

  • Felizmente, a estrutura do UTF-8 é bem simples em comparação com a de um parser médio
    isso não quer dizer que não haja bugs, mas o estado interno do parser não deveria ser grande, e parece possível até fazer testes exaustivos
  • Esse é exatamente o tipo de área em que eu gostaria de ver os resultados de um fuzzer
  • Se você lembrar de algum caso desse tipo de bug de imediato, pode compartilhar?

• É legal ver o serde andando tão rápido assim
  eu estava olhando o simdutf8 agora há pouco e descobri que o PR de parsing UTF-8 com suporte a SIMD está parado há quase 5 anos
  https://github.com/rust-lang/rust/issues/68455

• Esse blog me passou uma forte vibe de jart, então foi uma leitura divertida
  aquela parte de “talvez tenhamos que reinventar a roda, mas pensando bem isso é bem elegante” não sei se foi sincera ou irônica
  comecei a rir do autor enquanto lia, mas o resto da página parece ter bastante autodepreciação

  • Acho que isso quer dizer não que seja preciso reinventar a roda, mas que a abordagem é bem elegante
  • O que significa jart?

• Dizer que “ensinar a pensar é tão importante quanto ensinar a programar, mas quase nunca acontece”
  passa uma arrogância de achar que o outro não pensa

  • Não vejo arrogância nessa frase
    não é uma suposição de que os outros não pensam, e sim uma observação de que a maioria dos posts de blog e guias de uso mostra só o resultado final, e nem sempre mostra as etapas para chegar até lá
  • O autor não está fazendo essa afirmação
    ensinar a pensar significa que é preciso investigar e que essas etapas não podem ser puladas, e que ter investigado também não elimina a responsabilidade de tirar suas próprias conclusões
    é fácil pular uma das duas coisas, mas é a forma errada de fazer

• O serde_json ocupa 3 GB de dependências se você fizer um build de debug e outro de release
  se você usa serde em alguns projetos ativos, o espaço em disco vai embora rapidinho
  não entendo por que parsing de JSON precisaria de 3 GB de dependências, e sou a favor de reutilização de código, mas as dependências da parte de JSON do serde parecem bem bagunçadas
  se sair um exploit em uma dessas dependências, metade do ecossistema Rust fica vulnerável
  o Rust deveria ter JSON embutido

  • São só 5 dependências, uma delas opcional e outra é o próprio serde: https://github.com/serde-rs/json/blob/master/Cargo.toml
    indexmap = { version = "2.2.3", optional = true }
itoa = "1.0"
memchr = { version = "2", default-features = false }
ryu = "1.0"
serde = { version = "1.0.194", default-features = false }
    quando você fala em 3 GB de dependências, é bem possível que não tenha sido isso que foi medido de fato
    não posso ter certeza porque isso está sendo dito como fato sem evidência, mas meu palpite é que usaram muito #[derive(Serialize, Deserialize)], o que gerou uma grande quantidade de código, e depois mediram o tamanho do diretório target inteiro
    um build simples dá algo na casa de algumas dezenas de MB, como outros comentários mostraram
  • Não acho que embutir JSON no Rust seja uma abordagem sensata
    isso só seria uma forma de trazer inchaço, e a biblioteca padrão não tem vantagem sobre outros crates além da garantia de estabilidade
    no fim, isso só amarra o ciclo de release da biblioteca ao ciclo de release do compilador
    na prática, antigamente rustc-serialize era quase embutido, então o Rust já tentou seguir esse caminho
    e o serde_json padrão não é grande
    nem serde_json nem serde são grandes, e os dois mantêm um MSRV muito baixo, que outros crates muitas vezes não conseguem sustentar, então na prática eles nem podem ter muitas dependências
  • O inchaço de dependências é um problema do Rust como um todo
    a árvore de dependências de qualquer projeto Rust de tamanho razoável rapidamente fica bem assustadora, auditar todas essas dependências é inviável na prática, e a confiança em boa parte delas também é baixa
    depois de trabalhar com Rust por alguns anos, acho que não vou mexer com Rust de novo até o ecossistema amadurecer muito mais
    esse amadurecimento viria com adoção em grande escala por empresas grandes, ou então eu só usaria em projetos no-std, no-deps, como substituto puro de C
    embora, se o Zig estabilizar, ele talvez tire esse espaço do Rust também
  • O Rust cospe informação de debug em quantidade absurda
    fica tão bizarramente grande que eu presumiria que é simplesmente um bug
    não importa o que você compile, o diretório target vai acumulando gigabytes, mas isso não representa o artefato final depois que você remove a informação de debug ou pelo menos usa uma configuração menos detalhada
  • Em qualquer projeto com algum tamanho, parece que a pasta target literalmente sempre acaba tendo no mínimo alguns GB