Analisando protobuf acima de 2GB/s: projeto de um interpretador de alta velocidade em C usando tail call (2021)

• Com a adição de musttail ao Clang, passou a ser possível usar tail calls garantidas também em linguagens da família C, e isso foi aplicado a um parser de protobuf para demonstrar desempenho de mais de 2GB/s
• A ideia central é fazer a chamada de função se comportar mais como um jmp do que como um call, reduzindo o uso de pilha em chamadas encadeadas de O(n) para O(1) e tratando isso como um laço de repetição
• O wire format do protobuf interpreta tags/valores e precisa desviar para campos em ordem arbitrária, então a estrutura tradicional com while + switch enfrenta um problema de otimização parecido com o de despacho de opcodes em interpretadores
• O parser experimental do upb conecta pequenas funções de parsing por meio de tail call, em vez de usar uma única função grande, evitando no caminho rápido uso de pilha, register spill e prólogo/epílogo
• Essa abordagem perde muita qualidade de código quando há mistura com non-tail calls, e musttail é uma extensão não padronizada, então colocar um parser rápido em produção exige disciplina de chamada e medidas de portabilidade

---

Parsing de protobuf em alta velocidade com o musttail do Clang

• O branch principal do Clang passou a incluir o atributo de instrução [[clang::musttail]] / __attribute__((musttail)), que permite obter garantia de tail call em C, C++ e Objective-C
• Aqui, tail call não é usada como técnica de programação funcional, mas como ferramenta de otimização para reduzir o custo de desvios em parsers e interpretadores
• Ao aplicar essa técnica ao parsing de protobuf, o autor demonstrou desempenho de mais de 2GB/s em upb pull/310
  • O resultado é apresentado como mais de duas vezes mais rápido que o melhor nível anterior
  • Como várias técnicas contribuíram juntas, não seria correto interpretar isso como “ficou 2x mais rápido só por causa de tail call”
  • A tail call foi um dos elementos centrais que tornaram esse ganho possível
• Mudanças posteriores são discutidas em A Tail Calling Interpreter For Python (And Other Updates)

Por que tail call funciona como uma estrutura de repetição

• Tail call é a última chamada de função executada imediatamente antes de uma função retornar
• Quando a otimização de tail call é aplicada, o compilador gera uma instrução jmp no lugar de um call comum
  • Isso evita criar um novo stack frame e salvar o endereço de retorno
  • A chamadora f() salta diretamente para a chamada g()
  • g() retorna diretamente para a função que havia chamado f()
• Por causa dessa propriedade, tail calls podem substituir estruturas de repetição
  • Mesmo com n tail calls consecutivas, o uso de pilha cai de O(n) para O(1)
  • O overhead de call desaparece, então a chamada de função pode ser tratada como um desvio comum
• A ideia não é nova, e remonta ao artigo de Guy Steele de 1977 e aos “Lambda Papers” de 1975 a 1980
• O Clang já conseguia otimizar tail calls em builds com otimização como -O2, mas esse comportamento anterior era mais próximo de best-effort
  • Em builds sem otimização, era bem possível que o código fosse compilado como call real
  • Para usar tail calls com segurança como estrutura de repetição, a otimização precisa ser garantida em todos os modos de build
  • musttail fornece essa garantia

O mesmo gargalo em loops de interpretadores e parsers de protobuf

• Mike Pall, do LuaJIT, escreveu o interpretador do LuaJIT 2.x em assembly em vez de C, e apontava isso como uma das principais razões para sua velocidade
• Compiladores C sofrem especialmente com dois problemas no loop principal de um interpretador
  • Quanto maior a função e mais complexo o fluxo de controle, mais difícil fica para o alocador de registradores manter dados importantes nos registradores
  • Quando caminho rápido e caminho lento ficam misturados dentro da mesma função, o caminho lento pode degradar a qualidade do código até mesmo do caminho rápido
• O wire format do protobuf também tem uma estrutura parecida com a de um interpretador
  • O wire format é uma sequência de pares tag/valor
  • A tag inclui o número do campo e o wire type
  • A tag funciona de forma parecida com um opcode que informa como os dados daquele campo devem ser analisados
  • Como os números de campo podem chegar em ordem arbitrária, o código precisa estar pronto para despachar para qualquer ponto relevante
• Parsers tradicionais de protobuf normalmente usavam uma estrutura com switch dentro de um loop while, e essa foi a abordagem de mais alto nível durante a maior parte da existência do protobuf
• No parsing real, exceções como wire type incompatível, dados corrompidos ou fim do buffer podem ocorrer em quase todas as etapas
  • O caminho rápido precisa permanecer o mais curto e estável possível
  • Casos difíceis exigem código de fallback maior e mais complexo, às vezes com chamadas out-of-line

Projeto do parser do upb baseado em tail call

• O parser experimental do upb não usa uma única função grande de parsing; ele separa cada operação em uma pequena função
• Cada função chama a próxima operação por tail call
  • Graças à convenção de chamada do x86-64, os argumentos comuns do parsing são passados em registradores
  • Todas as funções de parsing usam o mesmo conjunto de argumentos para reduzir a movimentação de valores entre chamadas
• No exemplo, a função de parsing de campo fixed-width de 4 bytes segue o fluxo abaixo
  • Decodifica as informações do campo a partir de data
  • Se o wire type não corresponder, faz MUSTTAIL return para fallback()
  • Avança pela tag e grava os dados na mensagem
  • Lê a próxima tag e faz tail call de dispatch() para desviar ao parser de campo apropriado
• O assembly gerado pelo Clang não tem prólogo, epílogo, register spill nem uso de pilha no caminho rápido
  • Os únicos pontos de saída são jmp para fallback ou dispatch
  • Como os argumentos já estão nos registradores corretos, não é necessário código adicional para passar parâmetros
• Conceitualmente, essa estrutura trata o grande loop do interpretador como uma única função complexa, mas a implementação real o divide em funções no nível de bloco básico e transfere o fluxo de controle com tail calls
• Ao separar caminho rápido e caminho lento em funções diferentes, mudanças no código de fallback têm menos chance de afetar a qualidade do código do caminho rápido
  • Se necessário, é possível impedir inlining com noinline
  • Na prática, dá para quase fixar a sequência de assembly do caminho rápido

Qualidade de geração de código em C no exemplo do LuaJIT

• Aplicando o mesmo padrão ao exemplo do LuaJIT, é possível obter em C um resultado próximo de assembly escrito à mão
• A função de exemplo ADDVN executa as operações abaixo
  • Extrai do comando os registradores e o índice da constante
  • Em caso de falha na verificação de tipos, desvia para fallback
  • Soma a constante ao valor do registrador
  • Lê o próximo opcode e faz tail call para a função correspondente na tabela de opcodes
• No assembly gerado, os pontos restantes para melhoria são relativamente pequenos
  • Surge um jmp separado após o desvio condicional
  • Em vez de jmp qword ptr [rsi + 8*rax], o código faz load em rax e depois usa jmp rax
• Esses pontos são tratados como pequenos problemas de geração de código que podem ser melhorados no Clang

Restrições: non-tail call e portabilidade

• O maior cuidado dessa abordagem é que, se aparecer uma non-tail call dentro da função, a qualidade do assembly piora bastante
  • Uma única non-tail call força a criação de stack frame
  • Muitos dados podem acabar sofrendo spill para a pilha
• Para evitar isso, é preciso disciplina: ou fazer inline das outras chamadas de função, ou usar apenas tail calls
• No parsing de protobuf, o processamento de varint é um dos principais pontos difíceis
  • O caso comum e rápido é um varint de 1 byte
  • Varints mais longos não são erro, mas são menos comuns
  • Se esse tratamento excepcional for feito inline, a qualidade do código do caminho rápido pode piorar
  • Se ele for enviado por tail call a uma função de fallback, não fica fácil retomar depois a operação original, então o fallback precisa concluir a operação por conta própria
  • Isso acaba gerando duplicação de código e mais complexidade
• A atualização de 2025-01-27 acrescenta uma forma de aliviar esse problema por meio da convenção de chamada
  • __attribute__((preserve_most)) pode ser usado em funções de fallback e transfere para a callee a responsabilidade de preservar quase todos os registradores, movendo o custo de spill para o lado do fallback
  • Um bug de crash do Clang relacionado a esse atributo foi corrigido em 2023
  • __attribute__((preserve_none)) pode ser usado em funções que fazem tail calling, removendo a carga de preservação de registradores e usando mais registradores para argumentos
  • Entre as duas opções, preserve_none é avaliado como a menos intrusiva e, portanto, a melhor escolha
• Outra limitação é que musttail é uma extensão de compilador não padronizada
  • A expectativa é que se espalhe para GCC, Visual C++ e outros compiladores, e eventualmente seja padronizada, mas isso não deve acontecer tão cedo
  • Sem musttail, é necessário pelo menos um return real a cada iteração conceitual do loop
  • O upb ainda não implementou esse fallback, e a expectativa é usar uma macro que faça tail call para o dispatch quando musttail estiver disponível, ou simplesmente retorne quando não estiver

Estado da adoção no upb e possibilidade de expansão

• O parser de mais de 2GB/s foi enviado ao upb, uma pequena biblioteca de protobuf escrita em C
• O código funciona por completo e passa em todos os testes de conformidade do protobuf, mas, no momento em que foi escrito, ainda não havia sido implantado em nenhum lugar
• A versão C++ do protobuf não implementou esse projeto
• Mais tarde, o upb foi atualizado para usar musttail, removendo uma das grandes barreiras para levar esse parser rápido à produção
• A mesma técnica também pode trazer ganhos significativos de desempenho para grandes interpretadores de linguagem escritos em C, como Python, Ruby, PHP e Lua

[GN⁺]

Opiniões no Hacker News

• Há uma proposta para o padrão C com uma sintaxe para chamadas de cauda, na forma return goto (expression);
  O que eu gosto mais nela do que o [[musttail]] padrão é que ela garante que a vida útil dos objetos locais termine. Assim, dá para implementar sem uma análise de escape ampla
  [0] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5...

  • Fico curioso por que return goto seria mais fácil de implementar. O [[musttail]] também parece encerrar a vida útil dos objetos locais
    Dando uma olhada rápida, diz que a função chamada em posição de cauda precisa ter o mesmo tipo que o alvo da chamada. É uma condição para garantir que não seja necessária conversão do valor de retorno e que o espaço de passagem de argumentos e a convenção de chamada sejam preservados
    Uma reclamação que vi com frequência sobre o [[musttail]] que implementei no Clang é que essa restrição é desnecessariamente rígida. Algumas arquiteturas permitem chamadas de cauda mesmo quando os tipos não batem perfeitamente: https://github.com/llvm/llvm-project/issues/54964
    Dizer “então o código deixa de ser portável” está correto, mas a própria otimização de chamada de cauda não é inerentemente portável. Por exemplo, alguns targets, como WASM sem a extensão de chamadas de cauda, fundamentalmente não dão suporte à otimização de chamada de cauda
  • É animador, mas também bem preocupante, ver ganhar força de novo o movimento para adicionar novos recursos ao C
    É animador porque há mudanças e adições que realmente precisam entrar, e até ideias que precisam ser esclarecidas, mas o ciclo agressivo de atualizações do C++ parece ter acabado virando uma forma de remendo em cima de remendo
    O problema é especialmente quando os recursos interagem mal entre si muito antes do esperado. Espero que o processo de padronização não dependa apenas de documentos de justificativa, e escolha de forma muito conservadora, testando suficientemente os recursos em bases de código grandes e variadas

• Se você se interessa pelo lado do Rust, existe uma RFC antiga que tentava adicionar a palavra-chave become, oferecendo otimização de chamada de cauda garantida
  Originalmente ela foi adiada para concentrar esforços nas metas da edição 2018, e essa decisão foi correta, mas recentemente a ideia voltou a ser analisada. Pode acabar retornando
  [0]: https://github.com/rust-lang/rfcs/pull/1888
  [1]: https://github.com/rust-lang/rfcs/pull/3407

• Em C++, o jeito como interpretadores normalmente conseguem esse tipo de ganho de velocidade é usando goto computado. Assim, no caminho de um opcode para o próximo opcode não há ruído relacionado à convenção de chamada
  O principal motivo de a abordagem com goto computado ou com chamadas de cauda ser mais rápida do que um loop switch clássico é reduzir a carga sobre o preditor de desvios. Estaticamente, passa a haver um desvio indireto por opcode, em vez de uma estrutura com apenas um único desvio indireto estático

  • Como o texto também diz, mesmo usando goto computado, o grafo de fluxo de controle da função fica complexo demais, o que torna frágil a alocação de registradores para variáveis usadas com frequência
    Quando cada função é pequena e recebe variáveis importantes como argumentos, a alocação de registradores fica muito menos frágil
  • Fiquei curioso com a expressão “um desvio indireto estático por opcode”. Seria bom explicar um pouco mais, em comparação com um único desvio indireto, o que isso significa e como é alcançado
  • Ouvi dizer que essa abordagem saiu de moda por um tempo. A ideia era que os preditores de desvios ficaram bons o suficiente para ela não ser mais necessária
    Mas fico curioso se isso continua valendo quando o interpretador cresce

• O problema que resta ao usar chamadas de cauda para troca de contexto é que você está usando funções que precisam seguir uma convenção de chamada. Infelizmente, registradores são desperdiçados para restaurar o estado ao sair da função
  Uma análise detalhada e uma alternativa usando um compilador intermediário estão no blog do remake do LuaJIT: https://sillycross.github.io/2022/11/22/2022-11-22/

  • Nos últimos anos, vi algumas linguagens removerem uma camada de JIT e depois recolocá-la. Em parte isso se deve à capacidade dos programadores e às lições aprendidas, mas em parte também a mudanças de gerações de CPU
    Como em todo o resto da ciência da computação, quando o equilíbrio de custos entre tipos de operação muda, o melhor algoritmo pode voltar a ser o que se usava 15 ou 20 anos atrás. Por isso a programação muitas vezes parece seguir modas. Ressuscitar algo não quer dizer que não haja motivo, mas esquecer por que aquilo não foi uma panaceia da última vez continua sendo um problema
    Se o JIT principal fica mais rápido ou mais lento, o benefício em relação ao custo de execução muda, e os limiares que disparam seu uso também são ajustados. Com isso, a quantidade de código executada em outras camadas muda, e o custo amortizado dessas camadas também pode piorar. É como equilibrar um pêndulo duplo
    Se for possível tornar uma camada de JIT rápida e grosseira o suficiente, dá para pular completamente o interpretador. Visto de fora, a carga cognitiva de equilibrar as contas entre o interpretador e talvez dois JITs parece alta, então algumas linguagens parecem ter deixado o interpretador de lado e usado um JIT otimizado para tempo de compilação, não para velocidade do código gerado
    Não lembro qual linguagem era, mas sei que pelo menos uma equipe acabou removendo também o compilador intermediário por causa desse problema de equilíbrio. Era melhor se concentrar em duas camadas do que lidar com três
  • Recentemente entrou no Clang uma nova convenção de chamada que torna esse tipo de chamada de cauda muito mais barata. Ela evita a necessidade de o chamador preservar alguns registradores
    Sempre confundo o nome, mas deve ser preserve_all ou preserve_none. A questão é do ponto de vista de quem se fala em preservação

• Pelo que sei, o atributo musttail está em processo de ser adicionado ao GCC. O patch está em revisão, e a semântica é compatível com a do Clang

  • Fico curioso sobre o que acontece com o atributo preserve_most. Será que há chance de algo parecido entrar no GCC? Sem isso, chamadas que não são de cauda acabam estragando o interpretador
  • É um problema difícil. Muitas ABIs não conseguem fazer chamadas de cauda nem em casos extremamente básicos, como chamadas a funções externas em que os argumentos e o tipo de retorno batem
    O Clang parece ter heurísticas que alteram a sequência de chamada para chamadas musttail. Por exemplo, em i686 ele as transforma em chamadas noplt. Isso não está na documentação do Clang: https://clang.llvm.org/docs/AttributeReference.html#musttail
    Na prática, o que parece possível é o compilador emitir uma mensagem de diagnóstico quando não puder gerar uma chamada de cauda. Para muitos usuários, isso provavelmente já seria suficiente. Garantir chamadas de cauda como no Scheme parece pouco provável
  • O GNUC tem bastante coisa parecida com Scheme, então é surpreendente que esteja ficando para trás nesse recurso

• Também se menciona suporte a C++, mas em C++ acho que haverá pouquíssimas chamadas de cauda
  Por exemplo, foo() { auto a = SomeClassWithADestructor(); return bar(); } não é uma chamada de cauda, porque a destruição de a acontece depois da chamada a bar()

  • Se o compilador conseguir provar que não há efeitos colaterais à distância entre essas linhas, ele não poderia chamar o destrutor antes de executar bar?
    Fico curioso se o padrão C++ diz que o destrutor precisa necessariamente ser chamado no fim do bloco, ou se ele pode ser chamado assim que a variável não for mais usada

• Talvez o exemplo seja simples demais, mas não parece que __attribute__((musttail)) seja indispensável para gerar bom código
  Se a função de tratamento de erro estiver em um caminho raro, a velocidade da chamada também não deve importar muito
  Uma estrutura como if (unlikely(malformed)) return error(); switch (data_type) { case x: return handle_x(); case y: return handle_y(); } parece produzir uma boa tabela de saltos de forma bastante confiável

  • É claro que compiladores fazem eliminação de chamadas de cauda há muito tempo, mas, nessa técnica, “gerada de forma bastante confiável” não basta. Ela precisa ser garantida, ou a compilação deve falhar
    Caso contrário, essa estrutura não funciona e a pilha estoura imediatamente. O ponto de [[musttail]] é que a eliminação da chamada de cauda é obrigatória. O compilador não tem outra opção
  • Como mostra a desmontagem no texto, o motivo de o caminho de fallback ser um problema não é a velocidade da chamada em si. Só a existência dessa chamada já pode fazer o compilador criar um stack frame para a função inteira e despejar registradores nele. Isso afeta inclusive o caminho rápido
    Claro que dizer “força” talvez não seja exatamente correto. Não há nada que determine que o compilador precise ter uma única estrutura de stack frame para todos os caminhos de execução de uma função, nem que funções com ligação interna ou funções em namespace anônimo cujo endereço não é tomado precisem usar a ABI padrão. Mas todos os compiladores que vi, incluindo o Clang, fazem isso na prática. Por isso é preciso ter um jeito de dizer a ele para não se preocupar com a ABI e não perder tempo preservando registradores entre chamadas
    A tabela de saltos, claro, é bem gerada. Mas, se você rodar o resultado em algo como perf report e o bytecode de teste não representar um loop curto, vai ver uma de duas coisas: ou há falha de predição de desvio a cada despacho, ou o compilador pensa “parece que você quer escrever um interpretador” e move o salto indireto para o fim de cada case. Já vi isso no Clang. Em qualquer dos casos, é bem provável que a alocação de registradores do código resultante seja, em geral, péssima

• Fico curioso para saber quão rápido seria usar um trampoline, isto é, retornar a próxima função como um ponteiro de função e chamá-la em um loop externo. A vantagem é que isso é C portável

  • C é frequentemente usado como linguagem-alvo para compiladores de linguagens de alto nível
    A linguagem de programação Scheme exige que todas as chamadas de cauda não aumentem a pilha. Por isso, implementadores exploraram várias técnicas, incluindo trampolines
    Não tenho uma fonte para citar, mas a resposta provavelmente pode ser encontrada em artigos sobre compilar Scheme para C. Se a linguagem-alvo não garante otimização de chamadas de cauda, o programa gerado ficará mais lento
    Além disso, esse é também um dos motivos pelos quais implementadores de linguagens de alto nível, em especial, reclamam da remoção da otimização de chamadas de cauda da especificação JavaScript. Há também soluções que mantêm tanto a otimização de chamadas de cauda quanto a verificação de pilha
    https://github.com/schemedoc/bibliography/blob/master/page8....
  • Acho que a otimização de chamadas de cauda é rápida porque o loop resultante é previsível, então o prefetch de instruções da CPU e o prefetch de memória funcionam bem
    Se você saltar por meio de ponteiros de função, provavelmente isso não será tão previsível, e será difícil obter o mesmo ganho
    Claro, é preciso medir, e eu ainda não fiz isso

• Já escrevi um decodificador/codificador de Protobuf em C, um parser de IML e bindings para Python, e tenho algo a dizer sobre medições de velocidade de parsing
  Se essa biblioteca for oferecida apenas como bindings para linguagens gerenciadas, surge uma variável adicional que domina todo o resto em termos de desempenho. Não sei quanto a Ruby ou PHP, mas em Python vi um ganho de velocidade dramático quando não se usam enumeradores. Se você converte enumeradores do Protobuf em enums do Python, qualquer ganho obtido no código C é atropelado pelo tempo de criação de vários objetos Python. A diferença é de várias ordens de grandeza. Além disso, dá até para implementar todas as estruturas de dados auxiliares em C e expor ao Python apenas uma interface mínima. É difícil responder o quão justa é essa comparação com código que usa estruturas nativas do Python
  O parser de Protobuf do Google para Python ainda pode ser “mais rápido” do que mais de 2 GB/s. O motivo é que ele não faz parsing de nada além da mensagem de nível superior. A estrutura interna da mensagem é parseada quando necessário. Se o código ler imediatamente todo o conteúdo parseado, provavelmente será mais lento que 2 GB/s, mas a questão é como comparar essas duas abordagens de forma prática. Como os resultados reais variam conforme a natureza da aplicação, não há uma resposta clara
  No caso geral, o parsing de Protobuf não pode ser feito em streaming por causa do tratamento de duplicatas. Na prática, o código que faz parsing de conteúdo Protobuf esbarra no gargalo de I/O. Isso porque é preciso esperar pelo fim da mensagem antes de começar o parsing. Separadamente, dependendo das mensagens Protobuf típicas da aplicação, pode ser possível paralelizar o parsing, o que provavelmente superaria a maioria dos parsers single-thread. Mas, como nos exemplos anteriores, não dá para dizer que essa seja uma estratégia vencedora em geral
  Normalmente é muito mais eficiente combinar o parsing com a criação de objetos de domínio. A aplicação quase sempre precisa passar por essa etapa. A forma como o parser permite acessar esse recurso muitas vezes decide qual parser vai vencer
  Em conclusão, Protobuf — e talvez parsers em geral — não é um bom alvo para medição de velocidade e comparação. É de nível baixo demais e tem um design ruim demais para servir como base de benchmark de desempenho

  • Não entendi a parte de que “no caso geral, o parsing de Protobuf não pode ser feito em streaming por causa do tratamento de duplicatas”
    Gostaria que explicassem em mais detalhes como a regra de que o último campo vence impede o parsing em streaming

• GCC e Clang já têm há muito tempo a opção -foptimize-sibling-calls, então era possível obter chamadas de cauda até em builds de debug
  Claro que padronizar esse recurso, torná-lo garantido e controlável no nível da função é uma grande melhoria
  [1] https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
  [2] https://clang.llvm.org/docs/ClangCommandLineReference.html#t...