Comparaison de fonctions avec Criterion

Date de publication : 13/09/2019 21:45:05

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é à 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éhensions 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:

• criterion website : Le site internet de référence de Criterion.

• criterion tutorial : Un tutoriel très précis sur l'installation et l'utilisation de criterion.

Matériel

Ce test sera réalisé sur une machine tournant sous Linux Debian 10 avec un processeur AMD FX-8350 8 cœurs (FD8350FRW8KHK) avec 32Go de mémoire DDR3

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ésultats 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 :

• reportFile permet de générer un rapport html avec un template définit par template.

• csvFile permet de conserver les résultats détaillés dans un fichier csv.

• Les autres options permettent de régler certaines caractéristiques de la séquence de test comme la limite de temps (timeLimit), le nombre de répétitions de la fonction à effectuer (resamples), …

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

• De trouver les temps mis par chaque fonction pour obtenir chaque valeur et comparer les fonctions entre elles.

• De voir comment ce temps évolue avec des valeurs de plus en plus grandes et vérifier si cette évolution est la même pour chaque fonction.

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 ont été effectués, un rapport au format html est généré, il ne reste plus qu'à analyser les données recueillis.

Analyse des données.

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 fonctions est 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.