Sur AMD64, n’envoyez pas de structures de plus de 16 octets

• La remontée de Neat dans le benchmark related_post_gen ne vient pas d’une optimisation de haut niveau, mais d’un petit changement d’ABI : passer un tableau comme 3 arguments pointeurs au lieu d’une structure de 24 octets
• À cause du comptage de références, les tableaux de Neat ont besoin, en plus des pointeurs de début et de fin, d’un pointeur basé sur l’objet tableau ; contrairement aux 16 octets des tableaux D, ils empruntent donc le chemin de passage en mémoire de l’ABI SystemV AMD64
• Certains agrégats de plus de 16 octets sont copiés sur la pile à l’appel puis transmis par pointeur, ce qui fait perdre les avantages du passage par registres et augmente fortement le coût de réorganisation de la pile
• Dans le benchmark d’exemple, si struct Vector { double x, y, z; } est passé comme structure, 1 milliard d’exécutions prennent 12,3 secondes ; en passant les champs comme arguments séparés, on descend à 5,3 secondes
• Une API C doit suivre l’ABI C, mais pour des types internes au runtime du langage comme les tableaux, tuples ou sum types, il peut valoir la peine de benchmarker un passage éclaté par champs au-delà de 16 octets

---

Le goulot d’étranglement révélé dans Neat

• Neat a gagné quelques places dans le benchmark related_post_gen
• Le gain de performance ne vient pas d’un nouveau passage d’optimisation de haut niveau, mais d’un changement dans la manière de passer les tableaux
  • Avant : un argument structure contenant 3 pointeurs
  • Après : 3 pointeurs passés chacun comme argument
• Par rapport à D, Neat était plus lent que prévu, et le profiler montrait de gros déplacements de pile pour préparer les appels de fonction
• Le goulot d’étranglement était moins le calcul lui-même que le coût de réagencement de la pile au moment de l’appel

Pourquoi les tableaux Neat font 24 octets

• Contrairement aux tableaux D, Neat utilise un comptage de références
• Un tableau Neat contient les 3 pointeurs suivants
  • pointeur de début
  • pointeur de fin
  • pointeur basé sur l’objet tableau où est stocké le compteur de références
• Trois pointeurs font 24 octets ; ils suivent donc un chemin différent des tableaux de 16 octets à 2 pointeurs dans les règles de passage d’arguments AMD64
• Si les tableaux D étaient rapides et ceux de Neat lents, c’est parce qu’à 24 octets ils franchissaient la barrière des 16 octets

La barrière des 16 octets dans l’ABI SystemV AMD64

• La spécification ABI SystemV AMD64 stipule que si la taille d’un agrégat dépasse deux eightbytes, l’argument entier est passé en mémoire
• Pour passer une structure en mémoire, l’appelant doit effectuer les opérations suivantes
  • allouer sur la pile un espace de la taille de la structure
  • remplir cet espace avec la valeur à transmettre
  • passer à la fonction un pointeur vers l’emplacement de cette structure
• Dans ce cas, la valeur doit obligatoirement se trouver sur la pile, ce qui laisse peu de marge d’optimisation à LLVM
• La valeur doit être copiée des registres vers la pile, et il faut aussi suivre quelles zones de la pile sont déjà utilisées et lesquelles peuvent être réemployées
• C’est sur ce suivi du réemploi de la pile que LLVM s’est mal comporté

Benchmark d’un vecteur de 3 double

• Le benchmark utilise un vecteur à 3 champs de la forme struct Vector { TYPE x, y, z; };
• TYPE est défini comme double
• Les deux fonctions effectuent la même addition, mais diffèrent par leur mode de passage des arguments
  • vector_add_struct(struct Vector left, struct Vector right) reçoit de grosses structures en argument
  • vector_add_fields(...) reçoit séparément left_x, left_y, left_z, right_x, right_y, right_z
• mode et la longueur d’exécution sont fournis en arguments de ligne de commande afin que l’optimiseur ne puisse pas réduire tout le calcul à des constantes
• impl.c est compilé séparément pour éviter l’inlining

clang -O3 impl.c -c -o impl.o
clang -O3 harness.c impl.o -o benchmark
time ./benchmark 0 1000000000
time ./benchmark 1 1000000000

• Résultat : 12,3 secondes avec passage par structure, contre 5,3 secondes avec passage séparé des champs

La différence visible dans l’assembleur

• La version avec passage par structure consacre beaucoup d’instructions au brassage de pile
• La version par champs est avantagée par le fait que les paramètres arrivent déjà dans des registres SSE à l’entrée de la fonction
• La version par structure doit recharger les valeurs depuis la pile à chaque fois
• L’ABI SystemV vise à faire passer les valeurs autant que possible par registres, mais ici cet avantage disparaît à cause des structures de plus de 16 octets
• Vu le nombre de registres disponibles sur AMD64, il aurait été utile de permettre aussi le passage par valeur pour les types de plus de 16 octets

Une situation qui ressemble à cdecl

• Écrire les champs sur la pile puis passer un pointeur revient au final à un comportement proche de l’ancien ABI x86 cdecl, où tout passait par la pile
• cdecl était réputé lent, et plusieurs conventions d’appel ont été créées pour l’accélérer
• Le problème est que l’ABI AMD64 System V, à cause de la taille des structures, se comporte ici comme cet ancien mode de passage sur pile

Les exceptions : inlining et LTO

• Dans du code réel, ces fonctions peuvent toutes être inlinées
• Avec la LTO activée dans gcc, la différence de performance entre les deux versions disparaît
• Avec clang, on n’obtient pas le même résultat
• Toutes les fonctions ne peuvent pas, ni ne doivent, être inlinées

Conseils pour les implémenteurs de langages et l’optimisation d’API

• Lorsqu’on appelle une API C, il faut suivre l’ABI C
• Mais pour les types de haut niveau internes à un langage non-C, même s’ils ressemblent à des structures pour le backend, rien n’impose de les représenter comme une seule structure
• Les implémenteurs de langages peuvent décider eux-mêmes comment passer les tableaux, tuples, sum types, etc.
• Dans Neat, le choix a été fait de passer séparément les champs de ces types au-delà de 16 octets, et le benchmark montre un gain
• Si vous implémentez un langage sur AMD64 ou faites de la micro-optimisation d’API, il vaut la peine de benchmarker si un découpage manuel des structures de plus de 16 octets peut aider
• En particulier dans les boucles internes, l’écart de performance peut être plus important que prévu

Remarque complémentaire : structures de double et SSE

• La question posée est la suivante : double appartient sur le papier à la classe SSE, alors pourquoi la structure n’est-elle pas passée dans des registres SSE ?
• La réponse est qu’on n’en connaît pas la raison, mais qu’en pratique ce n’est pas ainsi que cela se passe

[GN⁺]

Avis sur Hacker News

• Le problème ici, c’est la SysV amd64 ABI. Rien n’oblige à utiliser SysV comme ABI interne d’un langage. Si ce n’est pas exposé à des appelants C SysV, on peut utiliser la convention d’appel que l’on veut
  https://llvm.org/docs/LangRef.html#calling-conventions
  Pour les curieux, le changement correspondant dans neatlang est ici : https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5...
  Cela semble beaucoup plus compliqué que de simplement changer la convention d’appel émise par LLVM. L’auteur voulait probablement exposer ces types aux programmes C avec une convention d’appel déterministe

  • En fait, on peut dire cela de l’ABI dans son ensemble. Les programmeurs assembleur le savent : c’est l’un de ces fruits à portée de main où l’on peut facilement battre le compilateur
    Il ne faut pas suivre aveuglément les conventions, mais choisir ce qui a le plus de sens dans une situation donnée
  • La première question qui m’est venue à l’esprit avait déjà sa réponse. C’est intéressant de voir à quel point beaucoup de choses suivent des ABI conçues il y a longtemps
    Les ABI, en particulier, penchent souvent vers la compatibilité avec des CPU plus anciens, alors que des CPU plus récents pourraient offrir des marges d’amélioration grâce à des fonctionnalités comme les registres étendus, sans avoir à réduire la taille des structures. Un logiciel adapté à un matériel ou à une génération donnée ne fonctionnerait plus sur certaines machines, donc ce n’est pas très séduisant ; mais ce serait formidable d’avoir un compilateur capable de produire ce genre de sortie quand on veut optimiser le code à l’extrême pour les capacités matérielles de son propre système

• Le coût du passage des arguments est souvent mal compris, donc ce genre d’article est bienvenu. Même dans des endroits comme Google, il est courant de passer des objets de 24 octets par valeur, et ce coût est réparti dans toutes les fonctions, au point de ne pas bien apparaître dans les profileurs

  • Le passage par valeur et le passage par référence influent de fait sur l’ABI/API, ce qui représente une charge cognitive assez importante. Zig essaie de ne pas l’imposer : même si l’on “passe par valeur”, le compilateur peut décider de le passer réellement par référence
    Cela dit, ce genre de piège apparaît aussi : https://github.com/ziglang/zig/issues/5973#issuecomment-1330...
  • “Des endroits comme Google” : c’est quelque chose que vous avez vécu directement ? En tant qu’ancien Googler, je peux l’affirmer clairement : les recommandations disent de passer ce qui n’est pas un type primitif par pointeur ou par référence
    La seule exception qui me vient à l’esprit est à peu près string_view
  • C’est bien de souligner que les surcoûts largement distribués, comme ceux intégrés dans la convention d’appel, sont presque impossibles à trouver par profilage
  • Si l’on passe plutôt un objet de 24 octets par pointeur, il y a un compromis : il faudra déréférencer le pointeur au moment où l’on aura réellement besoin de l’objet. Or rien ne garantit que cet objet soit proche
    Avec un peu de malchance, on peut avoir un cache miss et attendre environ 100 nanosecondes le temps de récupérer l’objet de 24 octets depuis la mémoire principale. Si l’on transmet directement ce même objet, il est sur la pile et a donc plus de chances d’être dans le cache
  • Je me demande si l’ABI C++ fait aussi déborder sur la pile les objets de 24 octets à chaque appel. Je ne m’attends pas à ce que des paramètres std::string ou std::function soient rapides, mais c’est quand même surprenant

• Quand nous sommes passés pour la première fois à x64, le fait que les objets vec3 en graphisme (3 float) passent de sizeof()=12 à 16 octets m’inquiétait, donc nous avons énormément benchmarké le moteur graphique
  Sans surprise, grâce à l’alignement des lectures sur 8 octets, 16 octets étaient plus rapides que 12. En interne comme sur le GPU. Le vec3 est donc discrètement devenu un vec4, tout en conservant aussi un vec4 séparé. Comme toujours, il faut faire des benchmarks avec une vue d’ensemble, pas seulement des benchmarks locaux

  • Il y a aussi un très bon effet secondaire : cela s’aligne bien sur la taille SSE. On peut donc utiliser directement _mm_load_ps, le code devient plus propre et la vectorisation beaucoup plus simple
  • Ce n’est probablement pas beaucoup plus rapide. Et j’imagine que cela dépend aussi fortement du CPU, indépendamment de ce que l’on fait avec ces données
    Avec 16 octets, je comprends que beaucoup d’accès puissent devenir 2x8 octets alignés ou 1x16 octets, plutôt que 3x4 octets. Mais pour d’autres accès, ce sera peut-être moins vrai, et il y a aussi le problème de la pression accrue sur le cache
  • L’ABI x64 est tout de même nettement meilleure que l’ABI x86

• Intuitivement, les valeurs passées dans les registres peuvent être préchargées grâce à l’exécution spéculative, ce qui est plus rapide qu’une écriture sur la pile, et la manipulation de la pile est plus rapide qu’une allocation sur le tas
  C’est pourquoi du code spaghetti sale avec plein de variables globales peut être extrêmement rapide, tandis que des fonctions récursives élégantes ou des arguments sous forme de tuples/structures/listes peuvent être incroyablement lents. Le premier est beaucoup plus facile à optimiser en boucles assembleur compactes

  • À condition, bien sûr, que ce code spaghetti implémente le même algorithme que le code élégant
    Si le code élégant est en O(n) et le code spaghetti en O(n^2), on risque de sentir la différence. Il faut aussi tenir compte de la maintenabilité. D’une certaine manière, les compilateurs existent pour transformer nos solutions élégantes en code spaghetti
  • “Passez les paramètres dans des registres plutôt que sur la pile” relève presque du bon sens, mais “les paramètres de plus de 16 octets sont toujours passés sur la pile” est beaucoup moins évident
  • Certains CPU récents peuvent faire du renommage mémoire, ce qui peut rendre le coût du débordement sur la pile moins élevé
    Les objets globaux gênent aussi les optimisations du compilateur

• Pour référence, avec MSVC, la taille limite avant qu’une structure soit passée sur la pile est de 8 octets. C’est un détail d’ABI, il ne faut donc pas s’appuyer dessus dans du code portable
  Mais si la fonction n’est pas appelée souvent, inutile de trop s’en inquiéter. Pour une petite fonction appelée fréquemment comme dans l’exemple, il faut permettre au compilateur d’inliner le code, par exemple via LTO. Cela ouvre alors des optimisations bien plus utiles que le simple passage des arguments par registre

• Je classe ce genre d’article dans la catégorie « juste assez de connaissances pour causer des ennuis ». Même si l’on suit les instructions en compilant séparément pour forcer le compilateur à produire une fonction appelable via l’ABI, LTO peut annuler cette erreur.
  Si l’on construit ce programme avec LTO, il devient spectaculairement plus rapide dans les deux modes que n’importe quel mode du programme sans LTO. Pour un programme sensible aux performances, il faut profiler, optimiser les goulots d’étranglement jusqu’au bout, et seulement ensuite committer ce genre de bidouille consistant à éclater une structure en arguments.

  • C’est un bon conseil, mais je n’ai encore jamais vu de compilateur qui rende ce genre de chose visible. D’abord, c’est dispersé dans toute la base de code, et je n’ai pas non plus vu de profiler qui en montre l’impact, à moins d’avoir la chance que cela devienne un hotspot.
    Cela concerne presque tout le code généré par les compilateurs. Valgrind pourrait le mesurer, mais un profiler par échantillonnage ne le pourra probablement pas, et il n’existe pas d’outil qui mette en évidence les problèmes de génération de code dispersés.
  • En plus, il parle de l’importance absolue des performances tout en utilisant du comptage de références.

• Dans la convention d’appel cdecl par défaut de Windows, les structures de plus de 8 octets ne sont pas passées dans des registres [1]
  [1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...

• Sur amd64, même avec l’ABI SysV amd64, il est tout à fait possible de passer et de retourner par valeur des structures de plus de 16 octets. C’est juste lent.
  Cela dit, le passage par valeur vaut souvent le coup pour rendre le code plus clair. Bien sûr, ce n’est pas le cas ici, mais comme loeg l’a souligné, à l’intérieur de son propre langage on peut utiliser une ABI personnalisée, comme les compilateurs C++, Go, OCaml ou SBCL.

• Dans l’exemple fourni, on peut corriger cela sans affecter les appelants en changeant le type du paramètre de « struct Vector » à « const struct Vector & » pour le passer par référence.
  J’ai vu beaucoup de code C++ avec des bugs de pointeurs qui utilisait des pointeurs sans réelle nécessité, alors qu’un passage par référence aurait suffi et aurait été plus simple et plus sûr.

  • Non. En fait, c’est précisément le cœur du problème ici. À cause de l’ABI, le compilateur fait en pratique exactement cela.
    Puisque l’ABI impose de passer la valeur via un pointeur, il faut la stocker quelque part pour obtenir ce pointeur, et il se passe la même chose que si l’on avait explicitement écrit const-ref. Si l’on remplace la valeur de la structure par des arguments séparés, les arguments peuvent être passés dans des registres.
  • Quand j’ai découvert ce problème, le code contenait vingt ou trente alloca destinés à passer des pointeurs vers du byval. Chaque fonction commençait par un alloca distinct pour chaque paramètre transmis à l’appel.
    J’avais toujours plus ou moins supposé que LLVM nettoierait bien ce genre de choses, mais il s’est avéré que non.
  • Malgré tout, pour transmettre un pointeur de structure à l’appelé, le compilateur doit sérialiser les trois registres sur la pile.
    L’avantage décrit consiste justement à éviter toute sérialisation des registres vers la pile, et le passage par référence ne semble pas permettre de l’éviter.
  • Ce n’était pas un exemple C++, mais un exemple C99. Dans beaucoup d’environnements, on ne peut pas changer d’outils librement, ne serait-ce qu’à cause de l’inertie minimale.
    Si l’on autorise C++, on dispose de davantage d’options, comme les arguments par déplacement pour réduire les copies.

• En C++, la règle empirique que j’ai toujours entendue est que tout ce qui n’est pas un type primitif doit être passé par référence, sauf s’il existe une bonne raison de le passer par valeur, et par pointeur seulement si c’est vraiment nécessaire.
  C’est à la fois à cause de l’ABI et pour éviter les constructeurs de copie ou de déplacement. Ce sont des détails bas niveau ennuyeux, mais si l’on veut les meilleures performances en C++, il faut s’en soucier. Pour être clair, il ne s’agit que d’une optimisation de performance : le code qui passe des structures fonctionne correctement, il est simplement moins rapide.