Analisando protobuf a mais de 2 GB/s: por que aprendi a amar tail calls em C (2021)

• Tail Call: chamada de função feita imediatamente antes de a função retornar. Quando ocorre a otimização de Tail Call, a instrução jmp é usada para reduzir a pilha de chamadas.
• Vantagens:
  • Reduz o uso de memória da pilha de O(n) para O(1).
  • Remove o overhead de desempenho das chamadas de função, permitindo uso como uma estrutura eficiente de controle de repetição.

Problemas do loop de interpretador

• Problemas:
  • Quanto maior a função e mais complexo o fluxo de controle, mais difícil é manter dados importantes nos registradores.
  • Quando caminhos rápidos e lentos se misturam, a qualidade do código piora.

Melhorando o loop de interpretador com Tail Call

• Solução: usar Tail Call para separar cada tarefa em pequenas funções, com cada função chamando a próxima tarefa por meio de Tail Call.
• Vantagens:
  • Permite controlar a alocação de registradores.
  • Separa caminhos rápidos e lentos para manter a qualidade do código.
  • Permite otimizar sequências de instruções independentes.

Limitações

• Problema na presença de non-tail calls: se houver chamadas que não sejam Tail Call, frames de pilha são criados e os dados são armazenados na pilha, causando perda de desempenho.
• Tratamento complexo de exceções: quando o tratamento de exceções é complexo, aumentam a duplicação de código e a complexidade.
• Problema de portabilidade: como o atributo musttail não é padrão, ele não é suportado por todos os compiladores.

Resumo do GN⁺

• A otimização de Tail Call desempenha um papel importante no ganho de desempenho e mostra resultados especialmente fortes no parsing de Protobuf.
• Essa técnica também pode ser aplicada a importantes interpretadores de linguagens escritos em C, como Python, Ruby, PHP e Lua.
• O problema de portabilidade do atributo musttail continua sendo um desafio a resolver.
• Projetos com funcionalidade semelhante incluem LuaJIT e o interpretador WebAssembly wasm3.

[GN⁺]

Comentários no Hacker News

• A proposta do padrão C inclui chamadas de cauda na forma return goto (expression);

  • em vez de padronizar [[musttail]], isso garante a vida útil dos objetos locais e não exige uma análise de escape ampla

• Para os entusiastas de Rust, havia um RFC antigo para adicionar a palavra-chave become

  • foi adiado para focar na meta da edição de 2018, mas recentemente voltou a ser discutido
  • pode reaparecer

• Em C++, a forma como interpretadores geralmente ganham velocidade é usando goto computado

  • isso pode evitar problemas de convenção de chamada
  • usar o estilo de goto computado ou o estilo de cauda pode reduzir a pressão sobre o preditor de desvios

• O problema de trocar contexto usando chamadas de cauda exige funções que usem a convenção de chamada

  • isso desperdiça registradores para restaurar o estado ao encerrar a função
  • o blog do remake do luajit fornece alternativas e análise

• Há esperança de que o atributo [[musttail]] se espalhe para GCC, Visual C++ e outros compiladores populares

  • o atributo [[musttail]] está em processo de ser adicionado ao GCC

• Ao mencionar suporte a C++, aponta-se que em C++ quase não há chamadas de cauda

  • por exemplo, retornar um objeto de uma classe com destrutor não é uma chamada de cauda

• Há curiosidade sobre o que acontece se uma exceção for lançada em uma função C++ [[musttail]]

  • pergunta-se se a pilha de exceções fica completamente separada

• Menciona-se que um exemplo simples não precisa de __attribute__((musttail)) para gerar bom código

  • provavelmente não haveria muita preocupação com a velocidade de chamadas de função para tratamento de erro
  • certa estrutura gera uma tabela de saltos confiável

• Há curiosidade sobre a velocidade de usar trampolins, retornando um ponteiro de função para ser chamado em um loop externo

  • essa abordagem tem a vantagem de ser C portável

• Há um pedido para esclarecer um exemplo de caminho de exceção encapsulado com [[musttail]]

  • explica-se por que [[musttail]] impede a criação de stack frames e o spill de registradores
  • a criação de stack frames e o spill de registradores só acontecem quando o caminho de exceção é realmente chamado
  • como o caminho de exceção é chamado raramente, isso não afeta muito o desempenho
  • por causa dos efeitos de predição de desvios, a possibilidade de trabalho extra pode tornar o caminho rápido mais lento