IA de jeux, Performances de code, en Haskell
Voir aussi : video youtube - video peertube - code source
Cet article, de la série “IA de jeux”, aborde les performances d’exécution en Haskell. En effet, Haskell peut produire du code natif relativement rapide mais cela nécessite de comprendre certaines particularités du langage et du compilateur.
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
Optimiser l’exécution d’un code en Haskell
Bonnes pratiques classiques
Les bonnes pratiques classiques s’appliquent également aux projets Haskell : optimiser quand c’est nécessaire, choisir des algorithmes adaptés, mesurer les temps d’exécutions, etc (voir l’article sur les Performances de code, en C++).
Par exemple, il faut régler correctement les options de compilation. Ci-dessous, les temps d’exécution (en secondes) pour le programme de Puissance 4 compilé avec les options -O3 -fllvm -funbox-strict-fields
(à gauche) et sans option explicite (à droite).
Structures de données modifiables
Une des particularités de Haskell est d’être un langage purement fonctionnel. Par défaut, on utilise généralement des structures de données non modifiables, or pour certaines applications, cela peut conduire à de nombreuses copies mémoires, peu efficaces.
Pour notre jeu de Puissance 4, on avait utilisé les tableaux modifiables de la bibliothéque massiv
, avec la monade ST
. Ceci apporte un gain important par rapport à une implémentation à base de tableaux non modifiables :
Récursivité terminale
En Haskell, il est assez courant d’écrire des fonctions récursives et le compilateur est capable de les optimiser efficacement. Cependant, il est important de les écrire sous forme récursive terminale pour éviter d’avoir à empiler les appels récursifs. Cette technique s’appelle la Tail-Call Optimization et est assez classique dans d’autres langages également.
Par exemple, on avait écrit la fonction lineLength
suivante, qui contient une fonction (go
) récursive terminale : l’appel récursif à go
correspond directement à la valeur retournée. Pour cela, le dernier paramètre de la fonction go
sert d’accumulateur.
lineLength :: Int -> Int -> Int -> Int -> Cell -> Board s -> ST s Int
=
lineLength i0 j0 di dj c0 cs let go i j n = if not (checkIJ i j) then return n else do
<- readM cs (Ix2 i j)
c if c /= c0 then return n else go (i+di) (j+dj) (n+1)
in go (i0+di) (j0+dj) 0
Le code suivant est une implémentation équivalente mais récursive non-terminale. Ici la fonction go
n’a plus le paramètre accumulateur mais l’appel récursif effectue ensuite un calcul sur la valeur retournée, ce qui nécessite d’empiler les appels.
lineLength :: Int -> Int -> Int -> Int -> Cell -> Board s -> ST s Int
=
lineLength i0 j0 di dj c0 cs let go i j = if not (checkIJ i j) then return 0 else do
<- readM cs (Ix2 i j)
c if c /= c0 then return 0 else (+1) <$> go (i+di) (j+dj)
in go (i0+di) (j0+dj)
Ceci se remarque sur les temps de calculs : la version récursive non-terminale (à droite) est sensiblement plus lente.
Inlining
L’inlining d’une fonction est une technique classique où le compilateur ne crée pas la fonction mais copie explicitement le code aux endroits oú la fonction est appelée. Ceci permet d’éviter le mécanisme d’appel de fonction et peut permettre des optimisations supplémentaires.
Le compilateur GHC a une stratégie d’optimisation assez agressive concernant l’inlining. Par exemple, les fonctions non-exportées d’un module sont automatiquement inlinées et il possible d’indiquer explicitement des fonctions à inliner :
-- Game.hs
module Game (nI, nJ, Game(..), Player(..), Status(..),
where
cloneGame, isRunning, nMovesGame, playK, mkGame, nextGame)
...
{-# INLINE playK #-}
playK :: Int -> Game s -> ST s (Game s)
...
Ainsi, en explicitant les fonctions à exporter et en indiquant d’inliner certaines fonctions, on peut obtenir des gains de performances relativement importants :
Evaluation stricte
Enfin, certainement l’un des points les plus particuliers de Haskell est l’évaluation paresseuse : les calculs ne sont pas réalisés lorsque le code l’indique mais lorsque leurs résultats sont vraiment utilisés. L’évaluation paresseuse apporte des fonctionnalités intéressantes mais peut être néfaste pour les performances, c’est pourquoi il est classique d’utiliser de l’évaluastion stricte ponctuellement (par exemple, on utilise la fonction stricte foldl'
plutôt que son équivalent paresseux foldl
).
Haskell propose différentes fonctionnalités pour demander une évaluation stricte d’une expression (seq
, BangPatterns
, etc). Il est également courant d’indiquer des champs stricts pour les types (avec le symbole !
).
data Game s = Game
_status :: !Status
{ _currentPlayer :: !Player
, _firstPlayer :: !Player
, _moves :: !(U.Vector Int)
, _cells :: !(Board s)
, }
Une solution alternative est d’utiliser l’extension de langage suivante :
{-# Language Strict #-}
Par exemple, en utilisant cette extension pour les modules Game
et Bot
de notre Puissance 4, on obtient le gain suivant :
Pour résumer
Choisir des strutures de données adaptées et régler les options de compilation est important pour optimiser les performances d’un code en Haskell mais il faut également prendre en compte d’autres aspects comme la récursivité terminale, l’évaluation paresseuse et l’inlining.
A titre d’illustration, le graphique suivant regroupe les optimisations des trois sections précédentes : à gauche la baseline avec les optimisations, à droite une implémentation avec une fonction récursive non-terminale et sans indication d’inlining ni l’extension Strict
.
Pour aller plus loin
Il y a encore d’autres pistes à considérer pour améliorer les performances d’un code en Haskell : lazy pattern matching, unboxed values, bibliothèques optimisées, runtime system, multi-threading…
Quelques liens :
- Performance/GHC
- Faster: producing a program that runs quicker
- Optimizing Ray Tracing in Haskell
- Haskell High Performance Programming
Analyser l’exécution d’un code en Haskell
Profiling
Le compilateur GHC possède un système d’analyse d’exécution. Par exemple, on peut compiler avec les options -prof -fprof-auto -rtsopts "-with-rtsopts=-p -h -s"
puis exécuter le programme et obtenir des rapports d’analyse. On aura notamment un rapport sur la répartition du temps d’exécution (fichier .prof
) et une analyse de la gestion mémoire (fichier .hp
, que l’on peut convertir en fichier postscript avec la commande hp2ps -c
) :
Ce genre de graphique permet notamment de vérifier que les allocations mémoires proviennent des fonctions attendues et non à cause de copies mémoires évitables.
Enfin, un résumé de la gestion mémoire est affiché à la fin de l’exécution, ce qui permet de vérifier que le temps d’éxécution est bien consacré au code proprement dit (MUT
) et non au garbage collector (GC
) suite à une mauvaise gestion de la mémoire.
[nix-shell]$ cabal run prof-immut
Up to date
winR WinY tie ry ryt dt nGames
0.4 0.6 0.0 1.0 1.0 4.738555289 5
6,645,467,368 bytes allocated in the heap
100,066,080 bytes copied during GC
586,288 bytes maximum residency (62 sample(s))
42,000 bytes maximum slop
3 MiB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 6340 colls, 0 par 0.066s 0.067s 0.0000s 0.0001s
Gen 1 62 colls, 0 par 0.015s 0.015s 0.0002s 0.0006s
INIT time 0.000s ( 0.000s elapsed)
MUT time 4.658s ( 4.657s elapsed)
GC time 0.078s ( 0.079s elapsed)
RP time 0.000s ( 0.000s elapsed)
PROF time 0.003s ( 0.003s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 4.739s ( 4.740s elapsed)
%GC time 0.0% (0.0% elapsed)
Alloc rate 1,426,694,261 bytes per MUT second
Productivity 98.3% of total user, 98.3% of total elapsed
Par exemple, si on réduit volontairement la taille des zones mémoires allouées, le programme va passer son temps à faire des allocations, ce qu’on peut observer dans le résumé d’analyse.
[nix-shell]$ cabal run prof-immut-10k
Up to date
winR WinY tie ry ryt dt nGames
0.0 1.0 0.0 1.0 1.0 7.785284893 5
5,360,975,624 bytes allocated in the heap
2,413,760,512 bytes copied during GC
599,040 bytes maximum residency (446 sample(s))
40,504 bytes maximum slop
2 MiB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 1165313 colls, 0 par 2.470s 2.700s 0.0000s 0.0001s
Gen 1 446 colls, 0 par 0.077s 0.077s 0.0002s 0.0005s
INIT time 0.000s ( 0.000s elapsed)
MUT time 5.239s ( 5.010s elapsed)
GC time 2.545s ( 2.775s elapsed)
RP time 0.000s ( 0.000s elapsed)
PROF time 0.002s ( 0.002s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 7.786s ( 7.786s elapsed)
%GC time 0.0% (0.0% elapsed)
Alloc rate 1,023,258,862 bytes per MUT second
Productivity 67.3% of total user, 64.4% of total elapsed
Microbenchmarking
Haskell possède également des outils, notamment Criterion, pour mesurer l’exécution de petites sections de code. Ce genre d’analyse est délicat à réaliser car d’un côté il permet de mesurer finement les parties de code à optimiser mais d’un autre côté, mesurer des temps courts est difficile à faire de façon fiable. Criterion permet de faire cela, via des mesures répétées et une analyse statistisque. Par exemple, le programme suivant définit deux scénarios à mesurer :
import Game
import Control.Monad.ST
import Criterion.Main
main :: IO ()
= defaultMain
main "mkGame" $ nfIO $ stToIO
[ bench <$> mkGame PlayerR)
(isRunning "mkGame+playK" $ nfIO $ stToIO
, bench <$> (mkGame PlayerR >>= playK 1 >>= playK 2))
(isRunning ]
On lance ensuite le programme pour effectuer les mesurer et afficher l’analyse :
[nix-shell]$ cabal run bench -- --output mybench.html
benchmarking mkGame
time 38.63 ns (38.46 ns .. 38.85 ns)
1.000 R² (1.000 R² .. 1.000 R²)
mean 38.60 ns (38.43 ns .. 38.84 ns)
std dev 684.6 ps (479.9 ps .. 1.104 ns)
variance introduced by outliers: 24% (moderately inflated)
benchmarking mkGame+playK
time 113.8 ns (113.6 ns .. 114.0 ns)
1.000 R² (1.000 R² .. 1.000 R²)
mean 114.0 ns (113.7 ns .. 114.4 ns) std dev 1.181 ns (872.0 ps .. 1.723 ns)
On peut également générer un rapport HTML plus détaillé :
Conclusion
En Haskell, l’optimisation de code est un peu particulière. Si on retrouve des similitudes avec les langages plus classiques, certaines particularités, comme l’évaluation paresseuse et le fonctionnel pur, sont assez déroutantes. Ici encore, il est donc important d’utiliser les outils de mesure et d’analyse, et de lire les documentations dédiées.