IA de jeux, Performances de code, en C++
Voir aussi : video youtube - video peertube - code source
Cet article, de la série “IA de jeux”, présente et illustre quelques méthodes et outils qu’il peut être intéressant d’utiliser pour améliorer les performances d’un code (ou pas).
Articles de la séries IA de jeux :
- Introduction
- Implémenter un Puissance 4, en C++
- Implémenter une IA basique, en C++
- Implémenter une IA arborescente, en C++
- Performances de code, en C++
- Implémenter un Puissance 4, en Haskell
- Implémenter une IA basique, en Haskell
- Implémenter une IA arborescente, en Haskell
- Performances de code, en Haskell
- Conclusion
Généralités
La priorité d’un développement logiciel est d’implémenter correctement les fonctionnalités prévues. Il peut également être intéressant d’optimiser les performances mais généralement ceci est à réaliser dans un deuxième temps, et lorsque c’est nécessaire (d’autant plus que ce travail peut rapidement devenir compliqué).
Avant d’optimiser un code, il faut déjà définir la performance désirée et être capable de la mesurer. Si on constate que le code n’est pas suffisamment performant alors on peut essayer de l’optimiser, selon le processus suivant (inspiré de la vidéo citée à la fin de cet article).
Un point important de ce processus est son approche itérative : à chaque fois qu’on modifie le code pour optimiser les performances, il faut vérifier que le logiciel fonctionne toujours correctement et améliore bien les performances.
On peut distinguer les macro-optimisations (réécritures importantes : algorithme, structures de données, architecture, etc) des micro-optimisations (modifications plus localisées : préallocation mémoire, utilisation de référence au lieu de copie, réordonnancement de tests/branchements, corrections de défauts de cache, etc).
Matériel et système
Il est intéressant de connaitre le matériel qui doit exécuter le logiciel car, selon le matériel disponible, on pourra utiliser différentes techniques de programmation (par exemple de la parallélisation : instructions vectorielles, multi-core, GPU, système distribué, etc). Plus généralement, le système peut influencer l’exécution du logiciel de nombreuses façons : multi-tâche, gestion d’énergie, gestion de température, etc.
Sur Linux, on peut avoir des informations intéressantes via le
fichier /proc/cpuinfo
.
$ cat /proc/cpuinfo
vendor_id : AuthenticAMD
cpu cores : 8
flags : fpu sse sse2 avx ... ...
Bonnes pratiques de programmation
Les “bonnes pratiques” de programmation peuvent influencer les performances, positivement (passage d’objets par référence plutôt que par copie), négativement (fonctions virtuelles, exceptions) ou indirectement (lisibilité du code, tests automatisés).
Et bien-sûr, ne pas oublier de régler correctement les options de compilation.
Par exemple avec l’implémentation du jeu de Puissance 4 présentée dans les
articles précédents, on obtient les temps d’exécution suivants (avec “no
optim” = -O0
et “full” = -O3 -flto -march=native
).
Objectif de performances
Il y a de nombreux critères possibles pour définir la performance désirée d’un logiciel : temps total d’un calcul, temps de latence, consommation mémoire, etc.
Concernant les IA de jeux, un critère classique est de maximiser l’efficacité de l’algorithme lors du temps de calcul imparti. Par exemple sur le Puissance 4, le bot MCTS est plus efficace que le bot Monte-Carlo :
Bien-sûr, il faut s’assurer que les temps de calculs utilisés par les deux algorithmes sont comparables.
Mesure de performance
Il est généralement facile de mesurer un temps de calcul mais le faire de façon fiable et robuste est un peu plus délicat. Pour cela, on peut réduire au maximum les autres tâches qui s’exécutent sur le système, appeler des fonctions de mesure adéquates à l’intérieur du code, mesurer des calculs suffisamment longs et répéter les mesures (d’autant plus si le code met en jeu de l’aléatoire).
$ ./cmp3.out
cmp3: run Mc/Mcts player against Random
usage: <mc/mcts> <nsims> <ngames> <nrepeat>
$ ./cmp3.out mcts 600 100 4
winR winY tie ry ryt dt nGames
0 1 0 1 1 0.363736 100
0 1 0 1 1 0.363282 100
0 1 0 1 1 0.358584 100 0 1 0 1 1 0.349753 100
Exemple de code pour mesurer le temps d’exécution :
// cmp.cpp
std::tuple<double, double, double, double> run(Bot & botR, Bot & botY, int nGames) {
auto t0 = std::chrono::steady_clock::now();
// ...
auto t1 = std::chrono::steady_clock::now();
const double dt = std::chrono::duration<double>(t1 - t0).count();
return { winR, winY, tie, dt };
}
Exemple
Pour illustrer le processus d’optimisation, imaginons que la fonction
getMoves
de notre Puissance 4 retourne un tableau par valeur (copie
mémoire d’un attribut).
// Game.hpp (copy)
class Game {
private:
std::vector<int> _moves;
...
public:
std::vector<int> getMoves() const;
...
On optimise cette fonction en retournant désormais une référence vers l’attribut (sans copie mémoire donc).
// Game.hpp (reference)
class Game {
private:
std::vector<int> _moves;
...
public:
const std::vector<int> & getMoves() const;
...
Pour tester cette optimisation, on peut relancer les tests unitaires puis lancer une série de mesures et comparer les temps d’exécution avant et aprés la modification.
On remarque que l’utilisation de références à la place de copies améliore
effectivement les performances. L’amélioration est même assez significative
pour MCTS car cet algorithme fait beaucoup d’appels à getMoves
.
Profilage de code
Enfin, pour trouver ou confirmer une idée d’optimisation intéressante, on peut utiliser des outils de profilage et analyser plus finement l’exécution du logiciel (consommation du temps de calcul, nombres d’appels de fonction, etc). Il existe différents types d’outils (analyse statistique, comptage exhaustif, etc), qui sont plus ou moins fiables, intrusifs, intuitifs…
Les sections suivantes présentent quelques outils et utilisations simples à mettre en oeuvre. Il s’agit ici d’analyseurs dynamiques, qui “surveillent” une exécution d’un code ou en faire ensuite un rapport.
Valgrind memcheck
Valgrind peut analyser l’utilisation mémoire, notamment en comptant les allocations et les libérations. Ceci est utile pour tester la gestion de la mémoire mais peut également être un indicateur intéressant pour comprendre les performances du logiciel.
Par exemple, si on reprend l’implémentation de getMoves
par copie, on
remarque que le nombre d’allocations/libérations mémoires est important.
$ valgrind ./cmp30.out mcts 100 100 1
==16503== Memcheck, a memory error detector
...
==16503== HEAP SUMMARY:
==16503== in use at exit: 0 bytes in 0 blocks
==16503== total heap usage: 1,911,583 allocs, 1,911,583 frees, 66,939,824 bytes allocated
==16503==
==16503== All heap blocks were freed -- no leaks are possible
==16503==
==16503== For lists of detected and suppressed errors, rerun with: -s ==16503== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
En revanche, la version par référence est beaucoup plus sobre : on passe de presque 1,9M à seulement 237k allocations/libérations, sur les exécutions mesurées.
$ valgrind ./cmp3.out mcts 100 100 1
==16521== Memcheck, a memory error detector
...
==16521== HEAP SUMMARY:
==16521== in use at exit: 0 bytes in 0 blocks
==16521== total heap usage: 237,223 allocs, 237,223 frees, 22,377,460 bytes allocated
==16521==
==16521== All heap blocks were freed -- no leaks are possible
==16521==
==16521== For lists of detected and suppressed errors, rerun with: -s ==16521== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Igprof
Igprof permet (entre autres) de chercher les fonctions les fonctions les plus consommatrices de temps de calcul. Pour cela, on lance la mesure sur une exécution du logiciel puis on lance l’analyse de cette mesure.
Par exemple avec la version de getMoves
par copie, on remarque que les
fonctions d’allocations et de libérations mémoire consomment une partie non
négligeable du temps de calculs.
$ igprof ./cmp30.out mcts 1200 100 4
...
$ igprof-analyse -d -v -g igprof.cmp30.out.16170.1622549362.002162.gz
...
----------------------------------------------------------------------%)
Flat profile (self >= 0.01
% total Self Function
23.80 1.04 Game::playK(int) [7]
17.73 0.77 BotMcts::genmove(Game const&) [5]
14.07 0.61 Game::checkLine(int, int, int, int) const [clone .constprop.1] [8]
11.21 0.49 _int_free [10]
7.67 0.33 int std::uniform_int_distribution<int>::operator()<...
6.86 0.30 __ieee754_log_fma [13]
6.06 0.26 malloc [12]
3.66 0.16 std::mersenne_twister_engine<unsigned long, ...
1.83 0.08 __libc_free [15]
1.60 0.07 _int_malloc [16]
1.49 0.06 operator new(unsigned long) [11]
1.26 0.05 playoutRandom(Game&, std::mersenne_twister_engine<...
1.03 0.04 _init [19]
0.57 0.02 __memmove_avx_unaligned_erms [22]
0.34 0.01 __memmove_avx_unaligned [24]
0.34 0.01 std::vector<std::unique_ptr<Node, std::default_delete<Node> >, ...
0.23 0.01 malloc [26]
0.11 0.00 std::vector<std::unique_ptr<Node, std::default_delete<Node> >, ...
0.11 0.00 log@@GLIBC_2.29 [27] 0.00 0.00 <spontaneous> [1]
Avec la version de getMoves
par référence, les fonctions d’allocations et de
désallocations mémoire sont beaucoup moins consommatrice de temps d’exécution.
Ici le temps de calcul est principalement consommé dans la gestion de jeu
(playK
et checkLine
), dans la génération de coup par l’IA (genmove
) et
dans la génération de nombre aléatoire
(uniform_int_distribution<int>::operator()
).
$ igprof ./cmp3.out mcts 1200 100 4
...
$ igprof-analyse -d -v -g igprof.cmp3.out.16040.1622549285.695945.gz
...
----------------------------------------------------------------------%)
Flat profile (self >= 0.01
% total Self Function
34.11 1.02 Game::playK(int) [6]
22.41 0.67 Game::checkLine(int, int, int, int) const [clone .constprop.1] [7]
20.57 0.61 BotMcts::genmove(Game const&) [5]
7.86 0.23 int std::uniform_int_distribution<int>::operator()<...
4.18 0.12 __ieee754_log_fma [9]
3.51 0.10 std::mersenne_twister_engine<...
2.51 0.07 _int_free [13]
1.67 0.05 _int_malloc [17]
0.67 0.02 __libc_free [20]
0.50 0.01 std::vector<std::unique_ptr<Node, std::default_delete<Node> >, ...
0.50 0.01 malloc [16]
0.50 0.01 std::vector<std::unique_ptr<Node, std::default_delete<Node> >, ...
0.50 0.01 log@@GLIBC_2.29 [21]
0.33 0.01 std::vector<std::unique_ptr<Node, std::default_delete<Node> >, ...
0.17 0.00 std::vector<std::unique_ptr<Node, std::default_delete<Node> >, ... 0.00 0.00 <spontaneous> [1]
Valgrind callgrind
Valgrind permet également d’analyser les appels de fonctions, via l’outils
callgrind
.
$ valgrind --tool=callgrind ./cmp30.out mcts 100 100 1
Le rapport d’exécution généré peut ensuite être visualisé graphiquement, par
exemple avec kcachegrind
.
On a ainsi une vue intéressante des appels de fonctions et de la répartition du
temps de calculs. On retrouve notamment les allocations/libérations mémoire
dans la version de getMoves
par copie (ci-dessus) mais qui ne sont plus
significatives dans la version par référence (ci-dessous).
Conclusion
De façon générale, optimiser les performances d’un code nécessite une expertise particulière, qui doit se justifier par rapport au besoin du projet. Ceci nécessite des méthodes et des outils particuliers notamment pour vérifier qu’on n’introduit pas d’erreurs dans le logiciel et qu’on améliore effectivement les performances.
Cependant, on peut tout de même tenir compte des performances, sans y consacrer trop d’effort : respecter les bonnes pratiques de programmation, réfléchir aux algorithmes et aux structures de données, lancer des analyses d’exécution, etc.
Voir également : CPPFrUG 44 - Performance et optimisation - Clément Grégoire