Flashback #

Dans la partie 1, j’ai montré à quel point les flags du compilateur pouvaient affecter la vitesse : 40x.

Tout ce qui a été optimisé l’a été via une optimisation statique, ce qui est correct et suffisant pour la plupart des cas.

Mais avant de plonger dans le code, peut-on extraire encore un peu de performance ?

PGO : Profile Guided Optimization #

Ce que fait PGO est assez simple : il exécute votre code avec des compteurs de performance (logiciels). Les appels aux fonctions seront comptés, et ce faisant, le programme produira un « résumé » de la façon dont votre code s’est exécuté.

Vous ne devriez pas pousser ces builds en production.

Votre compilateur (j’utilise clang) utilisera ces données pour inliner des fonctions, guider la disposition des branchements, et séparer vos chemins chauds/froids.

Générer un build PGO #

Pour commencer, votre build doit être un build PGO. C’est en fait assez simple : compilez-le simplement avec -fprofile-generate et c’est terminé.

Si vous utilisez meson, l’option est encapsulée dans -Db_pgo=generate

Compilez-le d’abord avec meson :

meson setup build-pgo --buildtype=release -Dcpp_args="-march=native -ffast-math -funroll-loops -ffp-contract=fast -fno-stack-protector -DNDEBUG" -Db_pgo=generate
meson compile -C build-pgo

Puis exécutez-le :

optim episode-2 ? ❯ ./build-pgo/sph 500 --headless 1500

Reconfigurez, et compilez avec :

meson configure build-pgo -Db_pgo=use
meson compile -C build-pgo

C’est aussi shrimple que ça.

Benchmarking #

Maintenant que nous avons notre binaire avec PGO, exécutons-le :

PGO utilisé :

headless: 500 particles, 1500 frames
frame    0 |    3.40 ms/step | rho avg 900.2 [513.1..1433.4] | max speed 1.44
frame   30 |    3.02 ms/step | rho avg 804.8 [223.7..1008.6] | max speed 3.92
frame   60 |    3.04 ms/step | rho avg 777.1 [207.1..1042.8] | max speed 2.19
frame   90 |    3.16 ms/step | rho avg 798.6 [197.9..1052.3] | max speed 2.12
frame  120 |    3.21 ms/step | rho avg 844.2 [195.8..1147.9] | max speed 2.42
frame  150 |    3.26 ms/step | rho avg 857.0 [195.8..1118.9] | max speed 3.16
// ...
frame 1320 |    3.43 ms/step | rho avg 882.2 [230.7..1087.6] | max speed 3.27
frame 1350 |    3.41 ms/step | rho avg 886.6 [223.8..1088.8] | max speed 2.28
frame 1380 |    3.43 ms/step | rho avg 890.8 [243.7..1082.2] | max speed 2.63
frame 1410 |    3.43 ms/step | rho avg 879.6 [350.5..1064.3] | max speed 3.62
frame 1440 |    3.41 ms/step | rho avg 892.3 [406.6..1082.1] | max speed 3.77
frame 1470 |    3.42 ms/step | rho avg 886.2 [368.0..1074.9] | max speed 2.37
frame 1499 |    3.43 ms/step | rho avg 883.8 [334.6..1088.3] | max speed 1.91
avg 3.45 ms/step over 1500 frames

Et qu’en est-il du build sans PGO ?

headless: 500 particles, 1500 frames
frame    0 |    3.10 ms/step | rho avg 900.2 [513.1..1433.4] | max speed 1.44
frame   30 |    3.07 ms/step | rho avg 804.8 [223.7..1008.6] | max speed 3.92
frame   60 |    3.07 ms/step | rho avg 777.1 [207.1..1042.8] | max speed 2.19
frame   90 |    3.14 ms/step | rho avg 798.6 [197.9..1052.3] | max speed 2.12
frame  120 |    3.27 ms/step | rho avg 844.2 [195.8..1147.9] | max speed 2.42
frame  150 |    3.34 ms/step | rho avg 857.0 [195.8..1118.9] | max speed 3.16
// ...
frame 1320 |    3.44 ms/step | rho avg 887.1 [199.5..1122.8] | max speed 3.20
frame 1350 |    3.50 ms/step | rho avg 883.4 [233.8..1075.8] | max speed 2.16
frame 1380 |    3.57 ms/step | rho avg 889.9 [230.6..1078.1] | max speed 2.17
frame 1410 |    3.54 ms/step | rho avg 885.4 [197.7..1101.6] | max speed 3.95
frame 1440 |    3.42 ms/step | rho avg 890.3 [195.9..1092.9] | max speed 2.07
frame 1470 |    3.49 ms/step | rho avg 889.6 [203.3..1094.8] | max speed 1.92
frame 1499 |    3.50 ms/step | rho avg 898.0 [199.4..1098.1] | max speed 2.64
avg 3.46 ms/step over 1500 frames

Oups. C’est décevant, pour le moins qu’on puisse dire.

En l’exécutant quelques fois de plus, on obtient un gain de performance moyen de 3 %, ce qui est bienvenu, évidemment.

Mais pourquoi ? 🐧

Profiling #

Nous sommes des ingénieurs logiciels, et des ingénieurs dans l’âme. Un simple « gain de perf de 3 % » ne suffit pas.

Nous devons mesurer et comprendre pourquoi. Et nous avons un outil pour ça : perf.

Exécutons-le d’abord sur le build optimisé avec PGO :

perf stat -e branches,branch-misses ./sph 500 --headless 1000
avg 3.40 ms/step over 1000 frames

 Performance counter stats for './sph 500 --headless 1000':

     3,313,498,538      branches:u
        34,560,076      branch-misses:u

       3.406098485 seconds time elapsed

       3.393040000 seconds user
       0.000980000 seconds sys

Puis le non-PGO :

Performance counter stats for './sph 500 --headless 1000':

     3,314,636,274      branches:u
        34,849,095      branch-misses:u

       3.454936810 seconds time elapsed

       3.431571000 seconds user
       0.001985000 seconds sys

Donc, comme discuté plus tôt, c’est plutôt décevant. Le changement est minime. 0,8 % de miss en moins.

Mais que dit le flame graph ?

Non-PGO :

PGO :

Aucun changement, vraiment.

Et qu’en est-il de LTO ? #

Le Link Time Optimization de LLVM est une optimisation intégrée à LLVM, et donc au compilateur Clang.

Le LLVM Link Time Optimizer offre une transparence complète pendant l’optimisation intermodulaire, au sein de la chaîne d’outils du compilateur. Son objectif principal est de permettre au développeur de tirer parti des optimisations intermodulaires sans avoir à apporter de changements significatifs à ses makefiles ou à son système de build. Ceci est réalisé grâce à une intégration étroite avec le linker. Dans ce modèle, le linker traite les fichiers bitcode LLVM comme des fichiers objets natifs et permet de les combiner entre eux. Le linker utilise libLTO, un objet partagé, pour gérer les fichiers bitcode LLVM. Cette intégration étroite entre le linker et l’optimiseur LLVM permet de réaliser des optimisations impossibles dans d’autres modèles. L’entrée du linker permet à l’optimiseur d’éviter de s’appuyer sur une analyse d’échappement conservative.

Chaque symbole (disons une fonction) est défini dans un module : par exemple, math.c, gui.c, ou main.c.

Il va analyser chaque module et effectuer un certain nombre d’optimisations, par exemple éliminer les symboles inutilisés.

C’est pourquoi c’est une bête puissante quand c’est utilisé avec PGO : si le compilateur sait qu’une branche n’est jamais prise, il peut éliminer les symboles et blocs correspondants, dégageant le chemin chaud.

Pourquoi ça n’a pas fonctionné #

Le logiciel #

En regardant mon code, il y a quelque chose à remarquer. C’est une simulation. Chaque calcul effectué le sera dans une boucle. On ne peut pas optimiser ses branchements s’il n’y a pas de branchements pour commencer.

C’est aussi simple que ça.

Le matériel #

En revanche, les CPU modernes sont plutôt efficaces et intelligents.

Tout d’abord :

Je vous suggère de jeter un œil à Demystifying Intel Branch Predictors par Milena Milenkovic, Aleksandar Milenkovic, et Jeffrey Kulick.

En cherchant à optimiser leurs CPU, Intel, AMD, et d’autres fabricants ont compris que réduire la taille du silicium, ajouter des instructions, et les optimiser ne suffisait pas.

Ils devaient réduire le nombre de chargements. Les instructions du CPU (vos briques de base en assembleur) sont chargées par le CPU et stockées dans le cache. Comme les caches ne sont pas si grands, les CPU vont essayer de ne sélectionner que ce dont ils ont besoin. C’est là qu’intervient le prédicteur de branchement.

Grâce à une analyse spéculative, le CPU va déterminer quelles branches sont les plus utilisées (vos chemins chauds) et les mettre en cache, en les gardant prêtes pour la prochaine itération. Ça fonctionne incroyablement bien dans les boucles.

Au final, PGO pré-optimise quelque chose que le CPU fait déjà (build PGO ou non !) plutôt bien. C’est pourquoi on n’extrait pas autant de performance qu’on l’aurait souhaité.

Il y a aussi le cas de l’inlining (les corps de fonctions sont intégrés dans leurs appelants, supprimant le besoin d’un appel coûteux).

Enfin, PGO va aussi aider le compilateur avec le hot/cold splitting. Je vous suggère de jeter un œil à cette présentation de Ruijie Fang, de Princeton.

TL;DR : certains blocs d’instructions ne sont jamais utilisés, d’autres le sont fréquemment. En séparant les blocs les plus utilisés des moins utilisés, votre cache d’instructions sera principalement rempli d’instructions (blocs) provenant des chemins chauds.

Où ça pourrait fonctionner #

Simplement : du code avec beaucoup de branchements.

Pensez à une machine virtuelle. Le CPU ne peut pas vraiment analyser les programmes à cette échelle. Mais en l’exécutant vous-même, vous pouvez prédire les instructions les plus utilisées, et quand cette instruction atterrit dans un if, la branche « pop » (probablement, j’invente ça) sera celle que le flux de contrôle emprunte le plus souvent.

Ce qui vient ensuite #

Il existe d’autres fonctionnalités du compilateur qui pourraient être utilisées pour améliorer les performances. Une véritable méthodologie de benchmark/profiling pourrait aussi être bénéfique. De plus, je n’ai pas exploré cette partie, mais vous pouvez informer le compilateur des branches les plus susceptibles d’être utilisées avec __builtin_expect.

Mais je veux plonger dans le code et l’optimiser moi-même : SIMD, Multithreading, SoA, AoS, et plus encore.