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