Benchmarks

Comparatif HsIndex

Lorsque j'ai commencé à développer sérieusement avec Haskell, je n'avais pas l'expérience que j'ai actuellement et j'ai pris certaines habitudes qui ne sont pas forcément les bonnes. Afin d’accroître encore mon niveau j'ai décidé de vérifier l'impact de ces choix sur mes programmes afin d'en tirer un enseignement pour la suite.

Lorsque j'ai commencé à programmer HsIndex il y a maintenant 3 ans, j'ai utilisé le type String pour manipuler les mots et créer les lignes de texte à inclure dans le fichier à inclure dans LaTeX. Pour manipuler du texte, la bibliothèque text incluse dans haskell-plateform permet théoriquement d'avoir de meilleurs performances tout en apportant des fonctions permettant de modifier du texte plus facilement qu'avec le type String1.

Je souhaiterais également améliorer mon parser afin de rendre le programme plus rapide. Lorsque je l'ai écrit, je l'ai fait un peu à la va-vite sans trop réfléchir ni prendre le temps de l'optimiser.

Je souhaiterais donc voir quel est l'influence de ces optimisations et les gains en temps et en mémoire utilisée par rapport à la version de départ. J'en profiterais également pour voir quelle est l'influence des optimisations natives offertes par le compilateur ghc. De mémoire elles étaient d'environ 10 à 20% par rapport à une version non optimisée mais j'aimerais en avoir le cœur net.

Méthodologie

Versions du programme

Pour cela, il est nécessaire de compiler les différentes versions du programme d'après les sources avec les options adéquates. Pour l'étude détaillée des performances de chaque fonction, il est nécessaire d'utiliser une version du programme compilée avec une option spécifique pour faire du profiling (investigation). Ceci permettra d'obtenir pour chaque appel de fonction le temps qu'elle a mis pour s’exécuter et la mémoire qui lui a été allouée.

On utilisera également des versions compilées sans ces options de profiling pour effectuer des tests de vitesses.

On compile donc les versions profiling avec :

ghc -O0 hsindex.hs -prof -fprof-auto -fprof-cafs  -fforce-recomp

ghc -O2 hsindex.hs -prof -fprof-auto -fprof-cafs  -fforce-recomp
-O0 : 

Produit une version sans optimisation.

-O2 : 

Produit une version avec toutes les optimisations possibles.

-fforce-recomp : 

Force la recompilation de tous les fichiers sources du .programme

et les versions standard avec :

ghc -O0 hsindex.hs -fforce-recomp

ghc -O2 hsindex.hs -fforce-recomp

On aura donc 16 versions différentes du programme à analyser

0.9.1 : 

Version de référence.

0.9.1opti : 

Version avec le parser optimisé.

0.10.0 : 

Version avec le type Text.

0.11.0 : 

Version avec le parser optimisé et le type Text.

Fichiers de test

Pour évaluer les performances du programme, je vais utiliser 4 fichiers d'index idx différents. Deux seront issus de LaTeX (l'original) et deux autres de XeLaTeX sa version améliorée. Pour chacun, je prendrais un fichier français et russe (avec les caractères non ascii)

Les différents fichiers sont:

  • Générés avec LaTeX :

    • Fichier français :

    • Fichier Russe :

  • Générés avec XeLaTeX :

    • Fichier français :

    • Fichier Russe :

Ces fichiers ont le même nombre de ligne (2200). Un nombre plus important aurait été préférable mais le nombre de mot russes étant limitant, il n'a pas été possible d'avoir des fichiers plus gros.

Commandes

Les programmes seront lancés en batch avec BASH avec les commandes suivantes:

  • Les versions normales seront lancées avec les commandes time pour obtenir le temps d’exécution:

    { time ./hsindex.0.9.1-O2  french --style="essai1.sty" -i indexes/motsfr.latex.idx -o motsfr.0.9.1-O2.latex.ind ; }  2>> timefr.latex.log 
    { time ./hsindex.0.9.1-O2  russian --style="essai1.sty" -i indexes/motsru.latex.idx -o motsru.0.9.1-O2.latex.ind ; }  2>> timeru.latex.log 
    

    Les accolades permettent de récupérer les sorties de la commande time et non de la commande hsindex.0.9.1-O0

  • Les version de profiling seront lancées avec les commandes:

    ./hsindex.0.9.1-O2-prof  french --style="essai1.sty" -i indexes/motsfr.latex.idx -o motsfr.0.9.1-O2-prof.latex.ind  +RTS -p -pohsindex.0.9.1-O2-prof-fr-latex
    ./hsindex.0.9.1-O2-prof  russian --style="essai1.sty" -i indexes/motsru.latex.idx -o motsru.0.9.1-O2-prof.latex.ind  +RTS -p -pohsindex.0.9.1-O2-prof-ru-latex
    

    L'option +RTS est spécifique aux versions profiling et permet de passer des options dédiées à ce mode. -p et -po permettent d’extraire les résultats détaillés sous forme d'arborescence vers un fichier texte.

Test

Pour obtenir les temps d’exécution, on fait tourner chaque version du programme avec les 4 fichiers de tests en prenant soit de sauver les résultats dans des logs.

Les tests seront effectués :

  • Sur la même machine.

  • En mode uni-processeur.

  • Sans autres tâche en cours d’exécution sur ma machine.

Résultats

Résultats version profiling

Les résultats synthétisés sous forme de tableaux sont:

0.9.1-O0-prof

0.9.1-O2-prof

0.9.1opti-O0-prof

0.9.1opti-O2-prof

0.10.0-O0-prof

0.10.0-O2-prof

0.11.0-O0-prof

0.11.0-O2-prof

parseIeC

2,818

2,338

#N/D

#N/D

3,253

2,555

#N/D

#N/D

lstParseIeC.\

0,195

0,160

0,016

0,010

0,197

0,166

0,015

0,009

lstParseIeC

#N/D

#N/D

0,042

0,037

#N/D

#N/D

0,046

0,033

concatPagesItems.(...)

0,227

0,222

0,270

0,204

0,201

0,294

0,232

0,314

concatPagesItems.(...).\

0,227

0,065

0,249

0,077

0,120

#N/D

0,102

0,010

parseSymbol

0,127

0,089

#N/D

#N/D

0,098

0,118

#N/D

#N/D

braces

#N/D

#N/D

0,022

0,020

#N/D

#N/D

0,023

0,030

parseAnything

0,068

#N/D

0,049

0,034

0,073

#N/D

0,058

0,044

total time (secs)

3,980

3,080

0,840

0,480

4,280

3,380

0,670

0,530

0.9.1-O0-prof

0.9.1-O2-prof

0.9.1opti-O0-prof

0.9.1opti-O2-prof

0.10.0-O0-prof

0.10.0-O2-prof

0.11.0-O0-prof

0.11.0-O2-prof

parseIeC

10,618

8,655

#N/D

#N/D

13,200

10,173

#N/D

#N/D

lstParseIeC.\

0,202

0,102

4,672

3,847

#N/D

#N/D

5,761

4,186

lstParseIeC

#N/D

#N/D

0,137

0,118

#N/D

#N/D

0,196

0,132

concatPagesItems.(...)

0,240

0,215

0,247

0,210

0,282

0,239

0,204

0,263

concatPagesItems.(...).\

0,190

#N/D

0,253

0,065

#N/D

#N/D

0,114

#N/D

parseSymbol

#N/D

#N/D

#N/D

#N/D

#N/D

#N/D

#N/D

#N/D

braces

1,188

1,054

1,363

1,049

1,673

1,266

1,705

1,304

parseAnything

#N/D

#N/D

#N/D

#N/D

#N/D

#N/D

#N/D

#N/D

total time (secs)

12,640

10,230

6,850

5,380

15,640

11,940

8,160

5,980

0.9.1-O0-prof

0.9.1-O2-prof

0.9.1opti-O0-prof

0.9.1opti-O2-prof

0.10.0-O0-prof

0.10.0-O2-prof

0.11.0-O0-prof

0.11.0-O2-prof

parseIeC

2,852

2,353

#N/D

#N/D

3,227

2,614

#N/D

#N/D

lstParseIeC.\

0,224

0,135

#N/D

#N/D

0,199

0,182

#N/D

#N/D

lstParseIeC

#N/D

#N/D

0,039

0,028

#N/D

#N/D

0,039

0,025

concatPagesItems.(...)

0,322

0,196

0,248

0,221

0,203

0,268

0,217

0,293

concatPagesItems.(...).\

0,241

0,049

0,248

0,063

0,114

#N/D

0,105

0,025

parseSymbol

0,110

0,113

#N/D

#N/D

0,135

0,138

#N/D

#N/D

braces

#N/D

#N/D

0,020

0,021

#N/D

#N/D

0,019

0,024

parseAnything

0,057

0,046

0,052

0,050

0,063

#N/D

0,063

0,052

total time (secs)

4,080

3,060

0,790

0,470

4,230

3,440

0,620

0,490

0.9.1-O0-prof

0.9.1-O2-prof

0.9.1opti-O0-prof

0.9.1opti-O2-prof

0.10.0-O0-prof

0.10.0-O2-prof

0.11.0-O0-prof

0.11.0-O2-prof

parseIeC

2,908

2,445

#N/D

#N/D

3,288

2,597

#N/D

#N/D

lstParseIeC.\

0,213

0,153

#N/D

#N/D

0,188

0,171

#N/D

#N/D

lstParseIeC

#N/D

#N/D

0,024

0,025

#N/D

#N/D

0,044

0,032

concatPagesItems.(...)

0,258

0,160

0,246

0,198

0,243

0,242

0,243

0,266

concatPagesItems.(...).\

0,254

0,063

0,222

0,072

0,094

#N/D

0,127

0,020

parseSymbol

0,115

0,100

#N/D

#N/D

0,128

0,111

#N/D

#N/D

braces

#N/D

#N/D

0,020

0,013

#N/D

#N/D

0,023

0,019

parseAnything

0,086

0,034

0,064

0,043

0,077

0,037

0,063

0,045

total time (secs)

4,090

3,130

0,740

0,440

4,270

3,360

0,660

0,450

Résultats version standard

0.9.1-O0

0.9.1-O2

0.9.1opti-O0

0.9.1opti-O2

0.10.0-O0

0.10.0-O2

0.11.0-O0

0.11.0-O2

latex fr

2,806

2,005

0,772

0,53

2,783

2,232

0,735

0,541

latex ru

7,295

5,177

4,038

2,938

7,797

6,304

4,135

3,304

xetex fr

2,779

1,961

0,765

0,53

2,793

2,086

0,645

0,477

xetex ru

2,801

1,985

0,762

0,539

2,798

2,148

0,643

0,477

Comparatif des versions profiling

Gain de temps comparé à la version 0.9.1-O2

0.9.1-O2-prof

0.9.1opti-O2-prof

0.10.0-O2-prof

0.11.0-O2-prof

latex fr

100,0%

-84,4%

9,7%

-82,8%

latex ru

100,0%

-47,4%

16,7%

-41,5%

xetex fr

100,0%

-84,6%

12,4%

-84,0%

xetex ru

100,0%

-85,9%

7,3%

-85,6%

Gain mémoire comparé à la version 0.9.1-O2

0.9.1-O2-prof

0.9.1opti-O2-prof

0.10.0-O2-prof

0.11.0-O2-prof

latex fr

100,0%

-93,1%

11,6%

-92,6%

latex ru

100,0%

-45,9%

21,3%

-36,6%

xetex fr

100,0%

-93,7%

11,6%

-93,3%

xetex ru

100,0%

-93,8%

11,5%

-93,5%

Comparatif des versions normales

Gain de temps comparé aux version -O0

0.9.1-O2

0.9.1opti-O2

0.10.0-O2

0.11.0-O2

latex fr

-28,5%

-31,3%

-19,8%

-26,4%

latex ru

-29,0%

-27,2%

-19,1%

-20,1%

xetex fr

-29,4%

-30,7%

-25,3%

-26,0%

xetex ru

-29,1%

-29,3%

-23,2%

-25,8%

Gain de temps comparé à la version 0.9.1-O2

0.9.1-O2

0.9.1opti-O2

0.10.0-O2

0.11.0-O2

latex fr

100,0%

-73,6%

11,3%

-73,0%

latex ru

100,0%

-43,2%

21,8%

-36,2%

xetex fr

100,0%

-73,0%

6,4%

-75,7%

xetex ru

100,0%

-72,8%

8,2%

-76,0%

Analyse des résultats

version 0.9.1opti (Parser opti)

On constate une diminution très importante du temps d’exécution de 43% à 73%. Cette diminution est moins importante pour le fichier russe issu de LaTeX. Cela s'explique par le fait que ce fichier contient presque exclusivement des chaînes \IeC {\cyrr } dont l'analyse nécessite plus de temps.

version 0.10.0 (Text)

On constate une augmentation des temps d’exécution (6% à 22%) et de mémoire avec la version 0.10.0, ou le type String a été remplacé par le type Text et ou le parser n'a pas été optimisé. On note que cette augmentation est plus importante pour le fichier russe issu de LaTeX.

Cette augmentation est surprenante car l'utilisation du module text avait pour vocation d'accélérer le programme et non de le ralentir.

version 0.10.0 (Text + Parser opti)

On constate une diminution des temps d’exécution de 36% à 76% qui est du même ordre que la version 0.9.1opti avec ces quelques nuances:

  • Les fichiers venant de LaTeX sont traités un peu plus lentement que la version 0.9.1opti.

  • Les fichiers venant de XeTeX sont traités un peu plus rapidement que la version 0.9.1opti.

Interprétation

La diminution de la vitesse d’exécution pour les versions 0.9.1opti et 0.11.0 sont parfaitement explicables à cause de l'optimisation du parser. L'augmentation des temps d’exécution pour la version 0.10.0 et 0.11.0 avec les fichiers issus de LaTeX pourrait s'expliquer par la combinaison parsec plus text. En effet, si on regarde l'implémentation de la bibliothèque parsec, on remarque que la bibliothèque fonctionne nativement avec le type String. Une conversion du type Text vers le type String est donc effectuée ce qui provoque un ralentissement.

Pour en avoir le cœur net, J'ai procédé à une modification de la version 0.11.0 pour forcer le programme à lire les fichiers avec le type String et à les faire analyser avec le type String par parsec. Voyons les résultats de cette version 0.11.1

0.9.1-O0

0.9.1-O2

0.9.1opti-O0

0.9.1opti-O2

0.10.0-O0

0.10.0-O2

0.11.0-O0

0.11.0-O2

latex fr

2,806

2,005

0,772

0,53

2,783

2,232

0,735

0,541

latex ru

7,295

5,177

4,038

2,938

7,797

6,304

4,135

3,304

xetex fr

2,779

1,961

0,765

0,53

2,793

2,086

0,645

0,477

xetex ru

2,801

1,985

0,762

0,539

2,798

2,148

0,643

0,477

Gain de temps comparé à la version 0.9.1-O2

0.9.1-O2

0.9.1opti-O2

0.10.0-O2

0.11.0-O2

0.11.1-O2

latex fr

100,0%

-73,6%

11,3%

-73,0%

-75,2%

latex ru

100,0%

-43,2%

21,8%

-36,2%

-44,4%

xetex fr

100,0%

-73,0%

6,4%

-75,7%

-75,4%

xetex ru

100,0%

-72,8%

8,2%

-76,0%

-75,8%

Cette version semble bien avoir amélioré les performances pour les fichiers générés avec LaTeX.

Comparaison avec xindy

J'ai développé HsIndeX afin de palier l'absence de xindy sur ma machine de l'époque. Maintenant que xindy est a nouveau disponible sur ma machine, il serait intéressant de comparer la vitesse d’exécution des deux programmes.

Cette comparaison est à titre informatif car l'implémentation des deux programmes n'est pas identique et HsIndex contient des fonctionnalités absentes de xindy.

time texindy -L french -C utf8 -o testfr.xindy.ind indexes/motsfr.latex.idx

s’exécute correctement en 2,493sec

time texindy -L russian -C utf8 -o testru.xindy.ind indexes/motsru.latex.idx

plante au bout de 16,978sec avec le message d'erreur suivant:

Processing index...
ERROR: CHAR: L'index 0 doit être plus petit que la longueur de la chaîne.

Si on compare ces résultats avec HsIndex, on trouve les gains suivant:

0.9.1-O2

0.11.1-O2

latex fr

19,4%

80,0%

latex ru

69,5%

83,1%

xetex fr

10,2%

77,9%

xetex ru

39,8%

85,5%

HsIndex est donc beaucoup plus rapide que xindy. Même la version non optimisée 0.9.1

Développer HsIndex n'était donc pas inutile. D'autant plus que les fichiers russes issus de LaTeX semblent causer problème avec xindy.

Conclusion

Ce travail de profiling m'a permis de mettre en évidence les fonctions à améliorer dans mon programme et de quantifier les gains obtenus.

Le parser était donc bien la fonction à optimiser en priorité et non le passage à text dont les gains pour ce programme sont discutables.

Ce travail m'a également montré qu'un parser écrit avec parsec était un peu plus lent si on le faisait travailler avec le type Text.


Notes

1.

Qui rappelons-le, est une liste de Char.