Construindo um parser JSON de alto desempenho

 (dave.cheney.net)
1 pontos por GN⁺ 2023-11-06 | 1 comentários | Compartilhar no WhatsApp
  • A apresentação de Dave Cheney na GopherCon Singapore 2023 aborda o processo de projetar um parser JSON em streaming em Go, mantendo uma API parecida com encoding/json, mas com maior throughput e menos alocações
  • JSON não tem indicação de comprimento, então é preciso ler toda a entrada até o fim; o limite inferior de desempenho é no mínimo read(N)+parse(N), e as principais restrições são reduzir revisitas a bytes e tokens, cópias, alocações e chamadas de função no hot path
  • encoding/json.Decoder.Token retorna tokens como interface{}, o que é conveniente, mas faz com que valores concretos escapem para o heap e criem alocações proporcionais ao número de tokens; até um único token "hello" gera 3 allocs/op
  • pkg/json reduz o custo do hot path com NextToken, que retorna subslices de []byte da entrada, uma janela deslizante em byteReader, inlining manual, chamadas diretas de métodos de estado e remoção de bounds checks
  • No fim, pkg/json.Scanner tokeniza sem alocação quando recebe um buffer, Decoder.Token é de 2 a 3 vezes mais rápido que encoding/json.Decoder.Token, e Decoder.NextToken, com menos alocações, é de 8 a 10 vezes mais rápido

Objetivos e restrições básicas

  • O objetivo é criar um parser JSON de alto desempenho como estudo de caso de design de pacotes em Go
  • Há três metas de projeto
    • oferecer processamento em streaming sem carregar toda a entrada na memória
    • fornecer maior throughput e menos alocações, mantendo compatibilidade razoável com a API de alto nível json.Decoder de encoding/json
    • oferecer, além da API de encoding/json, APIs mais eficientes com zero alocação ou com limite superior de alocação
  • Se toda a entrada for bufferizada antes na memória, há risco de disponibilidade quando o tamanho da entrada é desconhecido ou infinito, além de aumentar a latência antes do processamento
  • A leitura em streaming processa os dados assim que chegam e permite sobrepor leitura e processamento

Complexidade temporal do parsing de JSON

  • JSON não tem marcador de comprimento, então só dá para saber quanto ler consumindo toda a entrada
  • Para fazer o parsing do milésimo elemento de um array JSON, também é preciso ler e processar os 999 elementos anteriores, então não há como pular o processamento da entrada
  • O limite inferior de desempenho é proporcional ao tamanho da entrada e, como não basta apenas ler, mas também passar pela máquina de estados do JSON para encontrar início e fim dos tokens, o mínimo é read(N)+parse(N)
  • Os critérios para reduzir custo adicional são os seguintes
    • se N bytes foram lidos, cada byte deve ser processado, se possível, apenas uma vez
    • o mesmo token também deve ser processado apenas uma vez
    • no hot path de Scanner ou Decoder, o número de chamadas de função deve ficar em O(tokens), não em O(bytes)
    • reduzir cópias para diminuir quantas vezes os mesmos bytes são revisitados
    • reduzir alocações para diminuir custo de alocação no heap, acesso a estruturas compartilhadas, locks, contenção de cache e GC

Tokenização e design de API

  • Um decodificador JSON se divide, em linhas gerais, em duas etapas
    • um scanner ou tokenizador que transforma um fluxo de bytes em um fluxo de tokens JSON
    • um unmarshaller que aplica o fluxo de tokens JSON a objetos Go
  • encoding/json.Decoder.Token retorna o token como interface{}
    • strings são representadas como string, números como float64, booleanos como bool, null como nil e delimitadores como json.Delim
    • essa abordagem é prática porque expressa ao mesmo tempo o valor e o tipo do token
  • Essa conveniência tem custo
    • Brad Fitzpatrick chamou a API Token de garbage factory
    • pelo design da API Decoder.Token, o valor concreto alocado para cada token escapa para o heap
    • o número de alocações fica vinculado ao número de tokens da entrada
  • No benchmark de um único token "hello", encoding/json mostra 355ns/op, 19.7MB/s, 37.0B/op e 3.00 allocs/op
  • O design da API determina as alocações, e alocações podem impactar diretamente o desempenho

Tokens []byte e informação de tipo implícita

  • O tipo de um token JSON pode ser identificado apenas pelo primeiro caractere
    • {, }: início e fim de objeto
    • [, ]: início e fim de array
    • t: true
    • f: false
    • n: null
    • ": string
    • -, 0~9: número
  • A API Decoder.NextToken de pkg/json não converte o []byte de entrada em valores Go; ela retorna diretamente da entrada uma subslice com os bytes que representam o token
  • O primeiro byte do []byte retornado informa o tipo do token
  • Essa API tem restrições
    • a saída não é uma cópia, mas uma subslice da entrada, então tem validade limitada
    • isso é parecido com a API de bufio.Scanner
    • para lidar com o tipo do token ou com valores reais de string e número de maneira mais conveniente, é preciso uma abstração de nível superior

Leitura eficiente: byteReader

  • A abordagem tradicional com io.Reader.Read copia dados do reader para um buffer, e essa cópia em si tem custo
  • io.Reader.Read delega ao chamador o gerenciamento do buffer
    • se a leitura for feita um byte por vez, pode ser necessário armazenar ou voltar para bytes já lidos
    • a abordagem de ler em um buffer grande e então procurar o início e o fim do token exige muito gerenciamento, cópia e expansão de buffer quando o fim do token não está no buffer
  • Como alternativa, é usado byteReader, inspirado no iopipe de Steven Schveighoffer e em ideias de Phil Pearl
  • byteReader fornece uma janela deslizante sobre io.Reader; ele lembra bufio.Reader, mas oferece uma API mais eficiente
    • window() retorna a janela atual de dados ainda não lidos
    • release(n) descarta os primeiros n bytes da janela
    • extend() lê mais dados do reader subjacente e amplia a janela
  • O benchmark de busca por espaço em branco é a linha de base que visita cada caractere apenas para verificar se é whitespace, e mostra cerca de 2.04~2.07GB/s em várias entradas
  • O código de exemplo do contador de whitespace está em github.com/davecheney/whitespace

Otimizações do scanner

  • Scanner.Next pula whitespace intermediário, identifica o token pelo primeiro caractere da janela e então lê até o fim do token
  • O desempenho inicial de Scanner.Next fica em cerca de 1/4 a 2/5 da linha de base de whitespace
    • exemplo: Scanner/canada 510MB/s, citm_catalog 677MB/s, sample 837MB/s
  • A primeira otimização é trocar atualizações do campo s.offset por uma variável local offset
    • s.offset é 0 na entrada e na saída da função, então alterações internas não são visíveis externamente
    • usar variável local evita que o compilador faça escritas temporárias em memória
    • citm_catalog cai de 2.52ms para 1.80ms, uma redução de 28.46%, e sample cai de 828µs para 528µs, redução de 36.24%
  • O motivo de o efeito variar por entrada é a diferença na quantidade de whitespace
    • canada tem apenas 33 espaços em branco
    • citm tem 1,227,563
  • A segunda otimização é fazer inlining manual de Scanner.token dentro de Scanner.Next
    • por causa do for e da complexidade das funções, o compilador Go não consegue inline automático de Scanner.token, parseString, parseNumber e Scanner.Next
    • como Scanner.Next e Scanner.token são chamados para cada token da entrada, isso impõe o custo de duas chamadas de função por token
  • Após o inlining manual, o throughput melhora de 9% a 24%
    • canada sobe de 512MB/s para 642MB/s, aumento de 24.50%
    • citm_catalog sobe de 960MB/s para 1105MB/s, aumento de 15.16%
    • sample sobe de 1.33GB/s para 1.46GB/s, aumento de 9.11%
  • O efeito das otimizações pode ser resumido em dois pontos
    • reduzir a atualização de s.offset de uma vez por byte para uma vez por token
    • evitar chamadas de função no hot path pode melhorar o desempenho

Validação e Decoder.NextToken

  • O scanner por si só consegue dividir tokens, mas para um processamento JSON completo é necessária validação de estado
  • JSON é uma máquina de estados, e os tokens que podem vir a seguir dependem do token atual
    • por exemplo, depois de ler { e "username", apenas : é válido
  • Decoder.NextToken adiciona lógica de estado sobre Scanner.Next para verificar se a sequência de tokens é válida
  • Os estados incluem valor, string de chave de objeto, dois-pontos de objeto, valor de objeto, vírgula de objeto, valor de array, vírgula de array e estado final
  • Mesmo na implementação inicial de validação, pkg/json já mostra resultado de 8 a 10 vezes mais rápido que encoding/json
    • canada: pkg/json 399MB/s, encoding/json 34.6MB/s
    • citm_catalog: pkg/json 713MB/s, encoding/json 87.1MB/s
    • sample: pkg/json 1.23GB/s, encoding/json 216MB/s

Otimização de transições de estado

  • No centro de Decoder.NextToken há um switch
  • Um switch comum pode acabar sendo implementado como uma sequência de if, o que divide o fluxo de instruções e sobrecarrega o preditor de branches da CPU
  • Também seria possível usar uma tabela para encontrar o método de estado a partir do valor do estado, mas a implementação de exemplo não compila por causa do loop de inicialização
  • Em vez disso, usa-se method expression do Go para armazenar diretamente em d.state o método, e não um valor enumerado de estado
    • Decoder.NextToken faz a chamada direta do método do estado atual com return d.state(d, tok)
  • Só essa abordagem de computed goto não traz grande melhora de desempenho
    • em algumas entradas quase nada muda, e em twitter, code e example há pequena piora
    • em sample, há ganho de 1.15%
  • Essa mudança, porém, viabiliza a otimização seguinte: outlining

Outlining e remoção de bounds checks

  • Após o outlining, Decoder.NextToken passa a fazer apenas return d.state(d), e cada método de estado chama d.scanner.Next() diretamente
  • Como tok deixa de ser passado como argumento para o método de estado, a pilha de chamadas economiza 3 words
  • Com a verificação len(tok) < 1 e o switch tok[0] na mesma função, torna-se possível a remoção de bounds checks
    • antes, a checagem de len(tok) ficava em Decoder.NextToken, e o método de estado era chamado via method expression, sem inlining
    • por isso, tok[0] dentro do método de estado ainda exigia bounds check
    • quando a checagem de tamanho ocorre na mesma função, o compilador consegue provar que tok tem comprimento mínimo 1
  • O próprio Decoder.NextToken também fica simples o bastante para ser inline
    • em vez de dec.NextToken(), o chamador passa a enxergar, na prática, uma chamada direta ao método de estado atual
    • o custo da chamada de função é eliminado

Resultados finais de benchmark

  • O pkg/json.Scanner de nível mais baixo faz tokenização em streaming sem alocação quando recebe um buffer de alguns KB
    • canada: 638.78MB/s, 0 B/op, 0 allocs/op
    • citm_catalog: 1110.51MB/s, 0 B/op, 0 allocs/op
    • sample: 1471.01MB/s, 0 B/op, 0 allocs/op
  • pkg/json.Decoder.Token é de 2 a 3 vezes mais rápido que encoding/json.Decoder.Token
    • canada: 101.98MB/s vs 33.19MB/s
    • citm_catalog: 333.23MB/s vs 82.71MB/s
    • sample: 788.59MB/s vs 209.12MB/s
  • pkg/json.Decoder.NextToken tem muito menos alocações e é de 8 a 10 vezes mais rápido
    • canada: 466.52MB/s, 136 B/op, 3 allocs/op vs 34.42MB/s, 17,740,399 B/op, 889,106 allocs/op
    • citm_catalog: 798.58MB/s, 136 B/op, 3 allocs/op vs 86.08MB/s, 5,661,597 B/op, 324,692 allocs/op
    • sample: 1346.85MB/s, 1144 B/op, 9 allocs/op vs 217.44MB/s, 723,781 B/op, 26,095 allocs/op
  • Na API de nível mais alto, pkg/json também consegue fazer unmarshal para objetos Go da mesma forma que encoding/json
    • canada: 82.08MB/s vs 58.70MB/s
    • citm_catalog: 215.66MB/s vs 104.00MB/s
    • sample: 615.99MB/s vs 128.04MB/s
  • O link da apresentação está em dave.cheney.net/paste/gophercon-sg-2023.html, e o código está em github.com/pkg/json

Temas extraídos do design

  • Alocações afetam o desempenho

    • ainda que o GC consiga alocar rápido e coletar com eficiência, não alocar continua sendo sempre mais rápido
    • o design da API pode eliminar alocações
    • a maior parte do ganho de velocidade deste pacote vem da redução de alocações
    • o tempo não gasto no caminho de alocação no heap e nos ciclos de GC passa a ser usado no scanning
    • a API encoding/json.Decoder exige alocações porque retorna valores primitivos como interface{}
    • os valores escapam para o heap e, na prática, viram ponteiros para os valores
    • em processamento de dados, alocação pode ser o maior custo de desempenho do algoritmo
    • reduzir com cuidado o custo por byte e o custo por token foi o segundo maior fator de melhora
    • é importante trocar chamadas de função por byte por chamadas por token
    • o ponto de partida foi a hipótese de que encoding/json pode ser mais lento por causa da API; se for aceitável adotar outra API, é possível obter ganho de 2 a 3 vezes em alguns caminhos de unmarshal e de 8 a 10 vezes na tokenização

Leituras relacionadas

1 comentários

 
GN⁺ 2023-11-06
Comentários do Hacker News

  • Parece bem bom. Ao longo da minha carreira já criei parsers JSON até demais, mas é muito bom ter um material de referência que mostra passo a passo como projetar um parser JSON razoável e rápido
    Dito isso, JSON não precisa necessariamente de um tokenizador explícito. Dá para eliminar o conceito de tokens e fundir completamente parsing e tokenização. Normalmente é assim que se faz, e o conjunto fica mais simples
    Em linguagens como ECMAScript isso é muito mais difícil, porque há casos que parecem ser um subconjunto da sintaxe de expressões entre parênteses, como funções de seta, e só se confirmam dependendo de aparecer ou não um =>, o que pode exigir lookahead arbitrariamente longo

    • Fico curioso para saber que tipo de trabalho alguém fez para poder dizer que criou “parsers JSON demais” ao longo da carreira

  • É um texto bom de acompanhar, e o fluxo de “se você for implementar, faça assim” está bem estruturado
    Se a meta em produção for desempenho puro, também vale olhar o https://github.com/simdjson/simdjson do Daniel Lemire. Também existe o port para Go da MinIO, https://github.com/minio/simdjson-go

    • Se o formato do JSON for sempre o mesmo, talvez dê para fazer melhor do que um parser JSON genérico
    • Quando comparei o desempenho de vários parsers JSON no passado, os parsers baseados em SIMD foram decepcionantemente lentos, mais do que eu esperava
    • A biblioteca JSON mais rápida em Go é feita pela empresa por trás do TikTok
    • O simdjson já deixou de ocupar o posto de mais rápido há muito tempo

  • O que aprendi criando parsers JSON rápidos mistura muitas particularidades de cada linguagem, mas, generalizando, é isto
    Na tokenização, é preciso evitar alocação no heap. É melhor que o tokenizador retorne uma struct alocada na stack, ou que seja uma função que retorne um token int64 empacotando posição inicial, tamanho, offset de tipo etc. do token
    No parsing também é preciso evitar alocação no heap, e dá para oferecer interfaces como getString(key String) para clientes que queiram fatiar o buffer
    Ao desserializar para objetos cujos campos são conhecidos em tempo de compilação, normalmente se gera um switch com base no tamanho da chave antes de comparar valores de string
    Em pipelines de dados que processam muito JSON, só a escolha da biblioteca JSON podia causar uma diferença de desempenho de 3 a 10 vezes, e os principais parsers em geral tentam alocar objetos
    Quando as classes a serializar/desserializar são conhecidas em tempo de compilação, o Jackson do Java se sai bem, mas com código cuidadoso e profiling dá para extrair algo como mais 2x
    Por outro lado, ao processar JSON arbitrário, os parsers populares tendem a fazer muitas alocações; um parser próprio, mais intrusivo, pode evitar isso, e o ganho de desempenho fica muito grande ao processar de milhares a milhões de objetos por segundo

  • Com uma abordagem parecida, criei um tokenizador e parser de GraphQL, e ele também não faz alocações de memória e é bem rápido. Se quiser ver o código, confira https://github.com/wundergraph/graphql-go-tools

    • Meu monstrinho também pode valer uma olhada: https://github.com/graph-guard/gqlscan
      Também fiz uma apresentação sobre esse tema, mas infelizmente não foi gravada. Quase enlouqueci tentando extrair o máximo possível em Go :D
    • Fico curioso para saber o quanto isso é realmente um problema em um servidor GQL baseado em allowlist, onde todas as queries já são conhecidas de antemão. Dá para cachear ou memorizar o resultado do parsing da AST, então imagino que o desempenho só seja um problema nos primeiros minutos após o contêiner iniciar
      Ou fico curioso se isso afeta de outras formas

  • No n2[1] eu precisava de um tokenizador rápido e enfrentei o mesmo problema de gerador de lixo. Basicamente, era a mistura entre um conjunto de tokens constantes como json.Delim e strings que causam alocação
    Uma solução que considero bem decente é tornar o tokenizador genérico sobre algum T e receber uma função que transforma um slice de bytes em T, usando T no lugar de string
    Assim, quando o chamador tem uma representação mais eficiente, por exemplo uma com menos alocações, ele pode fornecê-la; ao mesmo tempo, em testes unitários dá para usar confortavelmente uma função identidade para testar o tokenizador
    Em certo sentido, é parecido com fundir o tokenizador e o parser em tempo de build, mas, graças aos genéricos, o tokenizador pode manter a separação de camadas sem conhecer a representação do parser
    [1] https://github.com/evmar/n2

  • É possível melhorar em relação à biblioteca padrão com um design de API melhor, mas, ao criar um parser totalmente streaming, é praticamente difícil não sair no meio depois de já ter preenchido parcialmente uma struct antes de descobrir um erro. A biblioteca padrão parece tratar isso também como uma restrição explícita de design

  • Posso ter deixado passar algo, mas o autor repete que criou um parser “streaming” sem explicar o que isso realmente significa
    Em especial, não há explicação sobre como chaves repetidas foram tratadas na “tabela hash”. Se aparecer uma chave repetida, fico curioso se o código sink é chamado duas vezes ou se ele espera ler a “tabela hash” inteira para então chamar o código sink
    Na minha opinião, JSON é hierárquico, não se sabe o tamanho de antemão e, acima de tudo, há chaves repetidas, então ele é intrinsecamente inadequado para streaming
    Dá para tornar alguns subconjuntos de JSON mais amigáveis a streaming, mas, se for para isso, não vejo motivo para consertar JSON. Se a solução é mudar JSON, acho melhor usar logo outro formato que não seja JSON

  • Fico feliz em ver Phil Pearl mencionado
    https://github.com/bytedance/sonic também vale uma olhada

  • É surpreendente que não exista uma forma de dizer “faça mesmo inline desta função” para uma função grande demais para ser inlineada
    Operações básicas de contar e procurar caracteres de espaço em branco parecem poder ficar muito mais rápidas se forem vetorizadas com SIMD, embora eu entenda que isso esteja fora do escopo do autor

    • Claro que é possível forçar inline

  • A afirmação “é irrealista esperar que seja possível manter toda a entrada em memória” está errada para a maioria das aplicações

    • A maioria das aplicações lê JSON da rede, e isso é um stream. Mesmo que o JSON seja relativamente pequeno, bufferizar a requisição inteira na memória e ficar mexendo nela aumenta bastante a latência
    • Verdade, mas, em aplicações que precisam fazer transformações estilo ETL em datasets grandes, streaming é uma estratégia extremamente útil
      Dá para dizer que Go não é a ferramenta certa para esse trabalho, mas, com otimizações desse tipo, não vejo por que não poderia ser
    • Se você está criando uma biblioteca, precisa declarar explicitamente as limitações ou dar suporte a streaming
      Já empurrei dados JSON na casa dos gigabytes, então sou grato por parsers streaming. Além disso, dar suporte a streaming também é um sinal de que o autor conhece vários casos de uso e faz uma engenharia melhor
      Memória só é barata e quase grátis na teoria; na prática, não é assim
    • Se basta que “caiba no disco”, mmap() também não seria uma opção possível? Casos em que streaming de verdade é necessário, por exemplo quando é preciso processar cedo dados iniciais em um único arquivo JSON, como um stream de transações ou tarefas, são outra questão
    • O corpo de uma requisição HTTP também conta como parte da entrada?