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
                        c <- readM cs (Ix2 i j)
                        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
                        c <- readM cs (Ix2 i j)
                        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(..), 
    cloneGame, isRunning, nMovesGame, playK, mkGame, nextGame) where

...

{-# 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 :

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 ()
main = defaultMain 
    [ bench "mkGame" $ nfIO $ stToIO 
        (isRunning <$> mkGame PlayerR)
    , bench "mkGame+playK" $ nfIO $ stToIO 
        (isRunning <$> (mkGame PlayerR >>= playK 1 >>= playK 2))
    ]

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.