points de vue

Pour commencer, le benchmark a été réalisé sur deux machines différentes :

• un portable Toshiba Satellite Pro A40 équipé d’un processeur Pentium 4 Mobile 2,9GHz, de 2Go de RAM, d’un disque dur 7200TPM de 100Go, le tout tournant sous GNU/Linux ArchLinux ;
• et un portable Acer 8942G doté d’un processeur i7 720QM (1.6GHz), de 6Go de RAM et d’un disque SSD Intel de 80Go, le tout tournant sous GNU/Linux KUbuntu 12.04.

Afin que les implémentations avec et sans récursivité soient suffisamment comparables, j’ai pris le choix de partir avec le même code de tri des sous listes autour du pivot. Le choix fait pour le second axe a été de remplacer la récursivité simplement par une boucle sur une pile dans laquelle les indexes des seuils de chaque sous-liste sont empilés puis dépilés au fur et à mesure du traitement. Vous trouverez les programmes dans un de mes dépôts Git sur Gitorious.

Pour chaque langage, le test a été exécuté plusieurs fois jusqu’à obtenir une déviation la plus petite possible et une certaine stabilité dans les résultats.

Le test a d’abord été réalisé avec le langage C et ceci selon les deux axes présentés ci-dessus. Les mesures du programme en C sont là pour établir une base de comparaison pour les différents langages. Il a été compilé classiquement avec l’option -O2 de GCC. L’outil de build utilisé est ici le traditionnel Make.

Toshiba Satellite Pro A40, GCC 4.7.2 :

Recursive quicksort -> mean time over 100 samples: 14ms with as standard deviation: 4.690416ms
Non-recursive quicksort -> mean time over 100 samples: 12ms with as standard deviation: 1.732051ms

Acer 8942G, GCC 4.6.3 :

Recursive quicksort -> mean time over 100 samples: 9ms with as standard deviation: 0.000000ms
Non-recursive quicksort -> mean time over 100 samples: 8ms with as standard deviation: 0.000000ms

Compte tenu de la déviation, sur le vieux PC portable, les deux versions du tri rapide ont des résultats proches. Quoiqu’il en soit, sur les deux configurations, la version du tri rapide sans récursivité présente de meilleurs performances, et ceci bien que le compilateur supporte le tail-recursion (optimisation des appels récursifs en queue, c’est-à-dire en fin de fonction). Je constate aussi que le tri non récursif est moins sujet à la variance des 100 mesures sur le Toshiba, confirmé à chaque exécution du test. Chose intéressante, je n’obtiens pas de variances entre les mesures dans le test sur le portable PC récent.

Quitte à tester le programme en C, faisons le aussi avec le même programme mais en Go, le langage développé par des concepteurs même du C (Rob Pike et Ken Thompson). Évidemment, le langage étant récent, je ne m’attend pas à une grande surprise. A noter que j’ai pris prétexte du benchmark pour essayer ce langage.

Toshiba Satellite Pro A40, Go 1 :

Recursive quicksort -> mean time over 100 samples: 26ms with as standard deviation: 5.247003228167484ms
Non recursive quicksort -> mean time over 100 samples: 29ms with as standard deviation: 2.783526440973752ms

Acer 8942G, Go 1 :

Recursive quicksort -> mean time over 100 samples: 13ms with as standard deviation: 0.5799725093485035ms                                                                                                                         
Non recursive quicksort -> mean time over 100 samples: 14ms with as standard deviation: 0.43859390055038383ms

Première remarque, compte tenu de la déviation sur le vieux PC portable, le temps d’exécution des deux versions sont là aussi proches. Mais, au contraire de la version C, c’est le tri récursif qui présente de meilleurs performances. Ceci ne doit pas surprendre car le compilateur Go de Google implémente aussi le tail-recursion mais de façon, semble t’il, plus efficace que le compilateur GCC. Au vue du résultat, finalement, il n’y a pas lieu de se triturer les méninges pour remplacer la récursivité lorsque celle-ci est naturelle à l’algorithme et qu’elle est en queue d’une fonction. Seconde remarque, les performances du programme en Go sont derrières celles de celui en C mais, au regard de la jeunesse du langage, elles sont plutôt bonnes et laissent présager de belles surprises à l’avenir. De plus, la déviation standard est relativement faible, ce qui démontre une certaine stabilité dans l’exécution du programme.

Maintenant, passons à Java (version 1.6.0 ici) qui lui ne supporte pas l’optimisation tail-recursion. La différence cette fois-ci avec les deux précédents langages est qu’en Java nous pouvons exprimer le tri sur des éléments de plus haute abstraction. En l’occurrence, les fonctions de tri sont définies pour des éléments qui satisfont l’interface java.lang.Comparable. L’outil de build utilisé ici est Maven (version 3.0.4) et le plugin exec-maven-plugin est utilisé pour exécuter le programme une fois celui-ci compilé.

Toshiba Satellite Pro A40, Java OpenJDK 1.6.0 Update 24 :

Recursive quicksort -> mean time over 100 samples: 184ms with as standard deviation: 23.958297101421877ms
Non-recursive quicksort -> mean time over 100 samples: 201ms with as standard deviation: 30.56141357987225ms

Acer 8942G, Java Sun HotSpot 1.6.0 Update 29:

Recursive quicksort -> mean time over 100 samples: 17ms with as standard deviation: 3.3166247903554ms
Non-recursive quicksort -> mean time over 100 samples: 21ms with as standard deviation: 3.1622776601683795ms

Les résultats du programme en Java m’ont surpris. En effet, la version du tri non-récursif est bien moins performante que celle récursive alors que le compilateur Java ne supporte pas le tail-recursion. Une explication peut être trouvée à la lecture du bytecode de chacune des versions du tri. En effet, on remarque un plus grand nombre d’appels de type invokeinterface et invokestatic dans le tri non-récursif ; par exemple, j’ai compté 21 invokeinterface contre 10 dans le tri récursif. De plus, les deux seuls appels invokestatic dans la version récursive correspond justement aux deux appels récursifs du tri. En remplaçant l’utilisation d’une instance Deque par un tableau pour représenter la pile dans le tri non récursif, on améliore les performances pour s’approcher de celles de la version récursive (18ms en temps moyen avec la même déviation standard). Sinon, vis à vis des mesures, le programme Java présente une variance des mesures plus importante que sa contre-partie en C ou en Go, mais reste toutefois modérée.

Passons maintenant au programme en Scala. Ici, SBT est utilisé comme outil de build. Comme avec Java, le langage nous permet d’exprimer une plus grande abstraction dans la définition de la fonction de tri ; elle peut s’appliquer sur toute liste ou tableau d’éléments qui satisfont le trait Ordered. Les traits apportent une plus forte expressivité que les interfaces dans Java. Ceux-ci, couplés avec la généricité, permettent de représenter des types algébriques avec lesquels différent typage de second ordre contraint peut être défini, dont celui F-Bound caractéristique de la programmation objet. On obtient alors une plus haute abstraction. Contrairement avec les autres langages, ce n’est ici plus les aspects récursif et non-récursif qui m’ont intéressé mais les approches impératives et fonctionnelles que supportent le langage Scala.

Toshiba Satellite Pro A40, Scala 2.9.2 :

Imperative quicksort -> mean time over 100 samples: 489ms with as standard deviation: 38.98717737923585ms
Functional quicksort -> mean time over 100 samples: 1093ms with as standard deviation: 22.715633383201094ms

Acer 8942G, Scala 2.9.1 :

Imperative quicksort -> mean time over 100 samples: 83ms with as standard deviation: 11.704699910719626ms
Functional quicksort -> mean time over 100 samples: 128ms with as standard deviation: 22.24859546128699ms

Les deux formes utilisent la récursion et le compilateur Scala supporte l’optimisation tail-recursion. L’approche fonctionnelle utilise l’aptitude du langage à exprimer clairement l’idée sous-jacente au tri rapide mais avec toutefois des performances plutôt déplorable. Quoiqu’il en soit, nous remarquons que le programme équivalent à son pendant en Java est bien moins performant. A côté de ceci, les variances entre les mesures sont fortes.

Comparons maintenant le programme en Scala sous sa forme fonctionnelle avec celui équivalent mais en Haskell. Celui-ci est un langage fonctionnel qui offre un niveau abstraction inégalé comparé aux langages impératifs. Ici, une bibliothèque dédiée aux tests de performances, Criterion, est utilisée et permet d’avoir des chiffres bien plus pertinents. Parce que la génération aléatoire de la liste à trier est une des fonctions avec la laquelle est composée l’appel à la fonction de tri, il a été nécessaire de mesurer son temps de génération afin d’en déduire celui du tri. Il a fallu faire aussi avec les propriétés paresseuses du langage : tant que les éléments de la liste ne sont pas accédés, ceux-ci ne sont pas générés. L’utilisation de la fonction nf de Criterion pour mesurer les performances du tri permet justement de forcer le tri de la liste et donc aussi sa génération.

Toshiba Satellite Pro A40, GHC 7.6.1 :

warming up
estimating clock resolution...
mean is 5.211127 us (160001 iterations)
found 286073 outliers among 159999 samples (178.8%)
  147056 (91.9%) low severe
  139017 (86.9%) high severe
estimating cost of a clock call...
mean is 1.061649 us (49 iterations)

benchmarking random list generation
collecting 100 samples, 1 iterations each, in estimated 33.02100 s
mean: 2.250232 ms, lb 2.241430 ms, ub 2.258059 ms, ci 0.950
std dev: 42.47253 us, lb 36.00341 us, ub 50.80494 us, ci 0.950
found 5 outliers among 100 samples (5.0%)
  4 (4.0%) low mild
variance introduced by outliers: 11.368%
variance is moderately inflated by outliers

benchmarking quicksort
collecting 100 samples, 1 iterations each, in estimated 69.37261 s
mean: 711.1199 ms, lb 704.3110 ms, ub 722.0640 ms, ci 0.950
std dev: 43.62053 ms, lb 28.08513 ms, ub 67.92878 ms, ci 0.950
found 2 outliers among 100 samples (2.0%)
  2 (2.0%) high severe
variance introduced by outliers: 58.505%
variance is severely inflated by outliers

Acer 8942G, GHC 7.4.1 :

warming up
estimating clock resolution...
mean is 1.646377 us (320001 iterations)
found 2196 outliers among 319999 samples (0.7%)
  1636 (0.5%) high severe
estimating cost of a clock call...
mean is 43.42828 ns (11 iterations)
found 1 outliers among 11 samples (9.1%)
  1 (9.1%) high severe

benchmarking random list generation
collecting 100 samples, 1 iterations each, in estimated 18.22550 s
mean: 1.115150 ms, lb 1.078057 ms, ub 1.169435 ms, ci 0.950
std dev: 227.4210 us, lb 168.8725 us, ub 315.9030 us, ci 0.950
found 8 outliers among 100 samples (8.0%)
  4 (4.0%) high mild
  4 (4.0%) high severe
variance introduced by outliers: 94.661%
variance is severely inflated by outliers

benchmarking quicksort
collecting 100 samples, 1 iterations each, in estimated 27.53069 s
mean: 266.7308 ms, lb 265.7461 ms, ub 267.7269 ms, ci 0.950
std dev: 5.064837 ms, lb 4.531545 ms, ub 5.731438 ms, ci 0.950
variance introduced by outliers: 12.268%
variance is moderately inflated by outliers

Le tri est réalisé en 709ms environ avec la vieille machine tandis que celui-ci est bouclé en 266ms sur la machine plus récente. On a ici des résultats mitigés : bien plus performant sur le portable Toshiba que le programme en Scala, le programme en Haskell l’est moins sur le portable Acer. Toutefois, si la variance est modérée sur la machine récente, elle est bien plus importante sur la plus vieille machine. Globalement, le programme en Haskell est moins performant que ce à quoi je m’attendais, et il faudra probablement user de techniques particulières pour atteindre de meilleures performances (mais à quel prix ? Et avec quelle complexité ?)

Si vous les programmes du benchmark vous intéresse, vous les trouverez dans un de mes dépôts Git sur Gitorious. Amusez-vous bien …