Analyser du protobuf à plus de 2 Go/s : pourquoi j’ai fini par adorer les tail calls en C (2021)

• Tail call : appel de fonction effectué juste avant le retour d’une fonction. Lorsqu’une optimisation de tail call se produit, l’instruction jmp est utilisée pour réduire la pile d’appels.
• Avantages :
  • Réduit l’utilisation de mémoire de pile de O(n) à O(1).
  • Élimine le surcoût de performance des appels de fonction, ce qui permet de l’utiliser comme structure de contrôle itérative efficace.

Problèmes de la boucle d’interpréteur

• Problèmes :
  • Plus une fonction grossit et plus le flux de contrôle se complexifie, plus il devient difficile de conserver les données importantes dans les registres.
  • Lorsque le chemin rapide et le chemin lent sont mélangés, la qualité du code se dégrade.

Améliorer la boucle d’interpréteur avec les tail calls

• Solution : utiliser des tail calls pour séparer chaque tâche en petites fonctions, chaque fonction appelant la tâche suivante via un tail call.
• Avantages :
  • Permet de contrôler l’allocation des registres.
  • Maintient la qualité du code en séparant le chemin rapide du chemin lent.
  • Permet d’optimiser des séquences d’instructions indépendantes.

Limites

• Problème en présence d’appels non tail call : s’il existe des appels qui ne sont pas des tail calls, des stack frames sont créées et les données sont stockées sur la pile, ce qui dégrade les performances.
• Gestion d’exceptions complexe : lorsque la gestion des exceptions est complexe, la duplication du code et sa complexité augmentent.
• Problème de portabilité : l’attribut musttail n’étant pas standard, il n’est pas pris en charge par tous les compilateurs.

Résumé GN⁺

• L’optimisation des tail calls joue un rôle important dans l’amélioration des performances, avec des résultats particulièrement marquants pour l’analyse de Protobuf.
• Cette technique peut aussi s’appliquer aux principaux interpréteurs de langages écrits en C (Python, Ruby, PHP, Lua, etc.).
• Le problème de portabilité de l’attribut musttail reste un point à résoudre.
• Parmi les projets offrant des fonctionnalités similaires, on peut citer LuaJIT et l’interpréteur WebAssembly wasm3.

[GN⁺]

Discussion sur Hacker News

• Une proposition pour la norme C inclut les appels de queue sous la forme return goto (expression);

  • Plutôt que de standardiser [[musttail]], cela garantit la durée de vie des objets locaux et n’exige pas d’analyse d’échappement étendue

• Pour les amateurs de Rust, il existait une ancienne RFC visant à ajouter le mot-clé become

  • Elle avait été reportée pour se concentrer sur les objectifs de l’édition 2018, mais elle est récemment revenue dans les discussions
  • Elle pourrait réapparaître

• En C++, les interpréteurs accélèrent principalement en utilisant des computed goto

  • Cela permet d’éviter les problèmes de convention d’appel
  • Utiliser un style computed goto ou un style tail call peut réduire la pression sur le prédicteur de branchement

• Le problème du changement de contexte via des appels de queue nécessite des fonctions qui utilisent des conventions d’appel

  • Cela gaspille des registres pour restaurer l’état à la fin de la fonction
  • Le blog sur le remake de LuaJIT propose des alternatives et une analyse

• Espoir de voir l’attribut [[musttail]] se diffuser à GCC, Visual C++ et d’autres compilateurs populaires

  • L’ajout de l’attribut [[musttail]] à GCC est en cours

• En évoquant le support C++, il est souligné que C++ a très peu d’appels de queue

  • Par exemple, retourner un objet d’une classe avec destructeur n’est pas un appel de queue

• Quelqu’un se demande ce qui se passe si une exception est levée dans une fonction C++ [[musttail]]

  • Il demande si la pile d’exceptions est complètement séparée

• Il est noté que, pour des exemples simples, __attribute__((musttail)) n’est pas nécessaire pour obtenir une bonne génération de code

  • On ne se soucierait probablement pas beaucoup de la vitesse d’appel des fonctions de gestion d’erreur
  • Certaines structures génèrent de manière fiable une table de saut

• Quelqu’un s’interroge sur la vitesse d’une approche utilisant un trampoline, où un pointeur de fonction retourné est appelé depuis une boucle externe

  • Cette méthode a l’avantage d’être du C portable

• Une demande vise à clarifier l’exemple d’un chemin d’exception encapsulé avec [[musttail]]

  • Il est expliqué que [[musttail]] empêche la construction de frames de pile et le spill des registres
  • La construction de frames de pile et le spill des registres ne se produisent que lorsque le chemin d’exception est réellement appelé
  • Comme le chemin d’exception est rarement appelé, cela n’affecte pas beaucoup les performances
  • À cause des effets du prédicteur de branchement, la possibilité d’un travail supplémentaire peut ralentir le chemin rapide