Comparaison de fonctions avec Criterion

Problématique

Dans le cadre du développement de MarkIt, j’ai eu besoin d’une fonction pour générer une numérotation alphabétique permettant la conversion suivante:

1 -> A
2 -> B
3 -> C
...
25 -> Y
26 -> Z
27 -> AA
28 -> AB
29 -> AC
...

Après avoir cherché a modifier une fonction trouvée sur internet pour générer une numérotation en chiffres romain sans succès, j’ai demandé conseil sur stackoverflow. Après quelques incompréhension sur ce que je souhaitais faire et quelques mauvaises réponses, il m’a été proposé deux fonctions répondant à mon besoin. Mais comment faire un choix entre ces deux fonctions? Laquelle est la meilleure? Quelle est la plus rapide?

Pour cela j’ai utilisé Criterion, une bibliothèque permettant de tester les performances de fonctions écrites avec Haskell. Pour plus de détails sur Criterion je vous invite à consulter les pages suivantes:

Préparation.

Tout d’abord, il est préférable de créer un fichier source contenant les deux fonctions à tester. Le fichier source est :

import Criterion.Main
import Criterion.Types
import Data.List(unfoldr)
import Statistics.Types

functionA :: Int -> String
functionA = reverse . fmap (toEnum . (64 +)) . unfoldr f
  where
    f 0 = Nothing
    f n = Just (mod (n - 1) 26 + 1, div (n - 1) 26)


functionB :: Int -> String
functionB = reverse . rawCellName . subtract 1

rawCellName :: Int -> String
rawCellName x | x < 0 = []
rawCellName x         = toEnum (fromEnum 'A' + r) : rawCellName (q - 1)
  where (q, r) = x `quotRem` 26

On peut alors charger ce fichier avec ghci ou bien le compiler avec ghc lorsque la fonction main aura été écrite (Voir plus loin).

Test des résultats

Tout d’abord, vérifions le résultat de ces fonctions. Regardons ce que donnent les 100 premiers résultat de la fonction A.

Je doute d’avoir besoin un jour d’une conversion pour ces valeurs mais sur le principe, il vaut mieux tester une fonction en profondeur.

*Main> map functionA [1..100]
["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T"
,"U","V","W","X","Y","Z","AA","AB","AC","AD","AE","AF","AG","AH","AI","AJ","AK"
,"AL","AM","AN","AO","AP","AQ","AR","AS","AT","AU","AV","AW","AX","AY","AZ","BA"
,"BB","BC","BD","BE","BF","BG","BH","BI","BJ","BK","BL","BM","BN","BO","BP","BQ"
,"BR","BS","BT","BU","BV","BW","BX","BY","BZ","CA","CB","CC","CD","CE","CF","CG"
,"CH","CI","CJ","CK","CL","CM","CN","CO","CP","CQ","CR","CS","CT","CU","CV"]

Cela correspond exactement à ce que je souhaite. Voyons, si les résultats de la fonction B sont équivalents.

*Main> map functionA [1..10000] == map functionB [1..10000]
True

Tout est bon, passons à la suite.

Comparaison des vitesses d’exécution.

Pour tester les vitesses d’exécution de ces fonctions et les comparer, j’utilise une fonction main appelant une fonction spéciale de la bibliothèque criterion.

main = defaultMainWith
  myConfig
  [ bgroup
      "fonction A"
      [ bench "1" $ whnf functionA 1
      , bench "10" $ whnf functionA 10
      , bench "100" $ whnf functionA 100
      , bench "1000" $ whnf functionA 1000
      , bench "5000" $ whnf functionA 5000
      , bench "10000" $ whnf functionA 10000
      , bench "100000" $ whnf functionA 100000
      ]
    , bgroup
      "fonction B"
      [
        bench "1" $ whnf functionB 1
      , bench "10" $ whnf functionB 10
      , bench "100" $ whnf functionB 100
      , bench "1000" $ whnf functionB 1000
      , bench "5000" $ whnf functionB 5000
      , bench "10000" $ whnf functionB 10000
      , bench "100000" $ whnf functionB 100000
      ]
  ]

myConfig :: Config
myConfig = Config { confInterval = mkCL 0.95
                  , timeLimit    = 10
                  , resamples    = 1000
                  , regressions  = []
                  , rawDataFile  = Nothing
                  , reportFile   = Just "report.html"
                  , csvFile      = Just "csv.log"
                  , jsonFile     = Nothing
                  , junitFile    = Nothing
                  , verbosity    = Verbose
                  , template     = "default"
                  }

La fonction defaultMainWith permet de lancer deux groupes de tests bgroup appelés “fonction A” et “fonction B”. Chacun de ces groupes contient une série de benchmark bench permettant de lancer la fonction qui doit être testée.

Je ne détaillerais pas ici tous les détails de la configuration mais :

Pour comparer chaque fonction de façon exhaustive et de manière égale, j’ai évalué les performance sur une série de valeurs identiques en entrée de chaque fonction et avec des valeurs de plus en plus grande. Le but est :

Une fois le fichier source créé et compilé, on lance l’exécutable et on attend que les tests s’exécutent (Cela peut prendre un certain temps). Lorsque tous les tests on été effectués, un rapport au format html est généré, il ne reste plus qu’a analyser les données recueillis.

Analyse des données.

Résultat de Criterion
Résultat de Criterion

Le résultat complet du benchmark est disponible ici : Rapport Criterion

Comme on peut le voir dans le récapitulatif du rapport, la fonction B a des temps d’exécution significativement plus faibles que la fonction A. Le rapport entre les temps d’exécution des deux fonction d’environ 2 dans tous les cas de figure ce qui n’est pas négligeable.

Valeur Fonction A Fonction B ratio B / A
1 253ns 145ns 0.573
100 406ns 219ns 0.539
1000 548ns 283ns 0.516

La fonction B est donc plus rapide que la fonction A.