La maquette Google

De nouveaux résultats

Ces quelques pages décrivent une nouvelle étape (nos premiers résultats sont toujours disponibles ici) de notre participation à l’état des lieux proposé par R.Hundt dans son article Loop Recognition in C++/Java/Go/Scala. Il y compare quatre langages : Java, scala, go et C++ via un cas concret d’utilisation.

Introduction

Quand, parmi les conclusions de R.Hundt, nous avons lu :

We find that in regards to performance, C++ wins out by a large margin. However, it also required the most extensive tuning efforts, many of which were done at a level of sophistication that would not be available to the average programmer.

nous avons décidé d’inscrire Cawen dans cet amical derby.

Si vous souhaitez reproduire nos résultats, consulter les sources C++, les sources Cawen et les sources C99/C++ qu’ils génèrent n’hésitez pas à télécharger notre archive.

Le seul prérequis est l’installation de la librairie des Judy arrays.

Présentation des différentes versions en compétition

Les quatre versions C++
La version originale de Robert Hundt (rhundt_1)

Elle est téléchargeable avec un client svn :

svn checkout http://multi-language-bench.googlecode.com /svn/trunk/ multi-language-bench-read-only
La version de Robert Hundt optimisée (rhundt_2)

R.Hundt n’a pas souhaité mettre en ligne la version « pro » de la maquette car elle utilise des sources propriété de Google. En revanche, il décrit assez précisément le chemin conduisant de la version originale à la version finale. Nous avons choisi d’appliquer les plus simples de ses recommandations, à savoir :

  • Additional gain for getting rid of BasicBlockMap and storing dfs_numbers on the BasicBlocks themselves.
  • Converted BasicBlockSet from set<> to vector<>.
  • Changed node_pool from a list<> to a vector<>. Moved definition out of the loop to recycle it.
  • Changed LoopSet from set<> to vector<>.
  • Changed LoopList from list<> to vector<>.
  • Changed EdgeList from list to vector.
La version de Russel Cox (rcox)

disponible ici.

La version de Anthony C. Hay (anthay)

téléchargeable dans son article.

Les 8 versions Cawen

Pour chacune des versions C++, nous avons codé deux versions Cawen. La première est une traduction litérale de la version C++ correspondante. La seconde est une optimisation (pour ce qui est du temps d’exécution seulement) de la première.

Nous avons testé les 4 versions C++ et les 8 versions Cawen avec ces trois types d’entrées et de traitements, que nous appellerons bench, random_10000 et random_50000.

Présentation des différentes plateformes

Nous avons mené nos tests sur 4 plateformes que nous avons appelées :

  • freebsd 1 : gcc 4.2.2 / FreeBSD 8.3 / Intel Celeron /32b/ 2,66 GHz / 1G RAM
  • freebsd 2 : gcc 4.2.1 / FreeBSD 8.2 / Intel Core i5-2300/64b/2.80GHz /16G RAM
  • cygwin : gcc 4.5.3 / Cygwin6.0/ Intel Pentium Dual-Core T4200 /64b/2GHz /4G RAM
  • mac osx : gcc-4.0.1 / Mac OS X 10.5.8/ Intel Core 2 Duo /32b/ 2,4GHz /2G RAM
  • cygwin2 : gcc 3.4.4 / version Cygwin DLL is 1.7.16-1 / Intel Core 2 Duo CPU P8600 /32b/2.40GHz /3.45G RAM (résultats collectés par François Bluteau, merci Fanch!)

Les mesures

Temps d’exécution :

Nous avons procédé à 7 exécutions. Nous avons fait la moyenne des sommes des résultats “usr” et “sys” de la commande time.

Mémoire utilisée :

Pour rester cohérents avec les résultats de R.Hundt, nous avons pris une meusre “top” par seconde pendant la durée de chaque exécution et avons moyenné les mesures.

Cette méthode n’est pas assez précise, particulièrement quand les temps d’exécution sont très courts. Utilisée sur deux exécutions du même processus, elle peut donner des résultats sensiblement différents.

Nous avons tenté de résoudre le problème :

  • en utilisant l’outil massif de valgrind (with –pages-as-heap=yes , see http://valgrind.org/docs/manual/ms-manual.html ) sur les plateformes où valgrind était disponible (freebsd 1 & freebsd 2)
  • sur les autres plateformes, pour les tests “bench” dont la consommation mémoire atteint naturellement un plateau, nous avons exécuté 7 fois chaque binaire en prenant une mesure toutes les secondes. La moyenne calculée est celle des mesures cohérentes. Sur cygwin nous avons pris la mesure RES et la mesure RSIZE sur mac osx.

C’est certainement la moins fine des mesures collectées ici. Une différence de quelques pourcents n’est pas significative.

Nombres de lignes

Nous avons été surpris de ne pas trouver, pour chacun des langages étudiés, d’outils dénombrant le nombres de lignes utiles voire de statements. C’est à dire, d’outils ayant une connaissance suffisante de la grammaire des langages pour faire la différence entre un commentaire, une ligne blanche et une instruction.

Il est probable que nous n’ayons pas suffisamment cherché.

Nous nous contentons donc de la méthode utilisée par R.Hundt : nous comptons toutes les lignes avec

wc -l;

Pour rester honnête vis à vis de C++, il nous a donc fallu reporter tous les commentaires et jusqu’aux erreurs d’indentation..

Temps de compilation:

Nous n’avons installé notre précompilateur que sur la plateforme freebsd 2. Sur les autres, la génération se limite à la compilation des sources C99 générées.

Les résultats

Les résultats bruts sont disponibles sous forme de tableau.

Nombre de lignes & temps de compilation
Code sizes [number of lines] - Bench

Code sizes [number of lines] – Bench

Code sizes [number of lines] - Random

Code sizes [number of lines] – Random

Compilation times [seconds] - Bench

Compilation times [seconds] – Bench

Compilation times [seconds] - Random

Compilation times [seconds] – Random

Cawen semble légèrement moins verbeux que C++, nous y reviendrons plus tard.

En revanche, les temps de précompilation sont énormes en Cawen et ce, même sur une plateforme assez généreusement dotée. Nous travaillons sur ce point et pensons pouvoir encore progresser (-30 % le mois dernier !;-).

Taille du binaire
Binary size [bytes] - FBSD 1 - Bench

Binary size [bytes] – FBSD 1 – Bench

Binary size [bytes] - FBSD 1 - Random

Binary size [bytes] – FBSD 1 – Random

Binary size [bytes] - FBSD 2 - Bench

Binary size [bytes] – FBSD 2 – Bench

Binary size [bytes] - FBSD 2 - Random

Binary size [bytes] – FBSD 2 – Random

Binary size [bytes] - OS X - Bench

Binary size [bytes] – OS X – Bench

Binary size [bytes] - OS X - Random

Binary size [bytes] – OS X – Random

Binary size [bytes] - Cygwin - Bench

Binary size [bytes] – Cygwin – Bench

Binary size [bytes] - Cygwin - Random

Binary size [bytes] – Cygwin – Random

Les binaires issus des versions Cawen rhundt 1 & 2 sont plus volumineux que les binaires des versions C++ correspondantes, c’est l’inverse pour les versions rcox et anthay.

Les fichiers sources C99 que nous produisons sont acceptés par g++. Cependant, tous les résultats que nous présentons ci-dessous ont été obtenus avec des binaires générés par gcc…

Ce que l’on peut dire pour le moment, c’est que, sur freebsd 2, les binaires issus d’une compilation g++ sont moins volumineux que ceux produits par gcc (nous enquêterons) et, dans la plupart des cas, que les binaires issus des versions C++ correspondantes.

Nous étudierons dans un second temps quel peut être l’impact d’une compilation g++ sur les performances.

Les performances

Les premiers tests que nous avons menés sur freebsd 2 confirment ce qu’ A.C Hay avait déjà remarqué : en ce qui concerne les temps d’exécution et la consommation mémoire, l’ordre d’arrivée des versions varie suivant le type de données d’entrée :

Memory [Mbytes] / execution time [sec.] - Bench

Memory [Mbytes] / execution time [sec.] – Bench

Memory [Mbytes] / execution time [sec.] - Random 10000

Memory [Mbytes] / execution time [sec.] – Random 10000

Memory [Mbytes] / execution time [sec.] - Random 50000

Memory [Mbytes] / execution time [sec.] – Random 50000

 

Rhunt_1, Rhunt_2, rcox, anthay…A vous de désigner la version gagnante !…

Nous essayons ici d’évaluer Cawen et les graphiques suivants sont sans doute plus pertinents. Nous avons réuni tous les résultats obtenus sur les différentes machines et avons calculé le delta (exprimé en %) entre les versions C++ et leur traduction litérale en Cawen.

Résultats globaux pour la version originale Cawen

Execution time variation x [%] / Memory variation y [%] cwn compared to cpp

Execution time variation x [%] / Memory variation y [%] cwn compared to cpp

 

Dans 73% des cas (44 tests sur 60 : 5 machines * 4 algos * 3 types d’entrée), la version originale Cawen est plus rapide et consomme autant ou moins de mémoire que la version C++ correspondante.

Dans 96% des tests (58 sur 60 tests), Cawen consomme moins ou autant de mémoire que C++.

Les résultats pour le test de Robert Hundt

Dans 100% des cas de test des traitements de Robert Hundt (tests “bench”), la version Cawen est plus rapide et consomme autant ou moins de mémoire que la version C++ correspondante. La diminution observée pour le temps va de 2% à 77% et pour la mémoire de 3 (égalité) à 32%. En d’autres termes, la course organisée par R.Hundt a un nouveau vainqueur.

Champagne pour tous !

Les résultats pour les graphes aléatoires

Le gain en rapidité et réduction de la consommation mémoire est particulièrement impressionnant sur les tests des versions Robert Hundt 1 & 2. Par exemple, pour rhundt 2/random_50000, Cawen utilise 89,73% moins de temps et 93,02% moins de mémoire que C++.

Un grand merci à Douglas L. Baskins et ses Judy arrays pour ces excellents résultats !

En revanche, Cawen a quelques sérieux problèmes avec les versions rcox et anthay utilisées sur des entrées aléatoires.

Optimisation des performances
Dérouler les boucles

Sur les versions rcox et anthay avec des entrées aléatoires, Cawen est largement battu. Gprof montre clairement que le problème se situe dans la fonction de recherche de valeur dans un tableau.

0.05 15.57 23216774/23216774 FindLoops_LoopFinder [4]
 [5] 78.3 0.05 15.57 23216774 govel_find_all1 [5]
 15.57 0.00 23216774/23216774 govel_find_in_container_contiguous1

78,3 % du temps d’exécution est consacré à une fonction qui n’est rien d’autre qu’une boucle de recherche d’une valeur parmi les éléments d’un tableau. Une des façons d’accélérer ce genre de boucle est de la dérouler :

en remplaçant :

if (!@contains(yprime,@pAt(w,&non_back_preds)))

par :

if (!@contains{unrollCount=16}(yprime,@pAt(w,&non_back_preds)))

nous obtenons une réduction de 44% du temps d’exécution et repassons devant C++.

Les vecteurs de govel ont manifestement besoin d’être optimisés…

Les allocateurs

La plupart des versions C++ bouclent sur la construction/destruction des mêmes objets. Dans ce type de situation, l’utilisation d’allocateurs peut s’avérer payante.

Nous avons utilisé deux sortes d’allocateurs.

Pour les versions rhundt_1 & rhundt_2, nous avons redirigé toutes les allocations de 64 octets et moins vers le même allocateur. En Cawen, cela s’écrit :

#typeDef(aggPool_t, aggHmgPool, M4, maxSize = 64, chunkCount=5000);
aggPool_t usedAlloc;
#paramDef(
   memory::reserve, 
   memory::release,
   memory::resize,
   govel::del,
   govel::new, 
   govel::newDecl  
         $pAllocator &usedAlloc);

Pour rcox et anthay, nous avons utilisé un allocateur spécifique pour l’exécution de notre équivalent de l’opérateur “new”.

#typeDef(hmgPool1_t, hmgPool, Flag, exactSize, M4, chunkByteCount = sizeof(Loop), chunkCount = 10000); 
hmgPool1_t loopAlloc; 
// (...) 
@newDecl(Loop,l,&loopAlloc);
Changer la densité des vecteurs

Govel (notre STL en herbe) permet à l’utilisateur de modifier la façon dont s’accroit la mémoire allouée par un vecteur. Le paramètre de templatage density indique quelle doit être la densité minimale (nombre d’éléments utilisés/nombre d’éléments alloués, densité exprimée en pourcentage) après une extension de la mémoire du vecteur.

#typeDef(Edge_Vector,heapArray,M4,valType=Edge,density=30);
// (...)
#typeDef(LoopBlock_Vector,heapArray,M4,valType=LoopBlock,density=100);
La version Cawen optimisée

Ce graphique illustre la différence entre la version Cawen originale et la version Cawen optimisée. C’est à dire, le résultat de nos efforts d’optimisation :

Execution time variation x [%] / Memory variation y [%] cwn optimized compared to cwn

Execution time variation x [%] / Memory variation y [%] cwn optimized compared to cwn

 

L’optimisation d’anthay s’est limitée au déroulement de la boucle de recherche, on peut vérifier sur le graphique qu’elle n’a pas eu d’impact sur la consommation mémoire. L’utilisation d’allocateurs conduit à une augmentation de la consommation mémoire pour rhundt 1 & 2…Mais pas pour rcox…

La comparaison avec les versions cpp devient :

Execution time variation x [%] / Memory variation y [%] cwn optimized compared to cpp

Execution time variation x [%] / Memory variation y [%] cwn optimized compared to cpp

 

Dans 91% des cas, les versions Cawen optimisées sont plus rapides et consomment autant ou moins de mémoire que les versions C++ correspondante.

Dans 100% des cas, les versions Cawen optimisées sont plus rapides que les versions C++ correspondantes.

La réduction du temps d’exécution varie entre 4 et 98%.

Ce que la maquette laisse entrevoir du langage Cawen

Nombre de lignes

Si l’on compare les différentes implémentations, Cawen semble légèrement moins verbeux que le C++(de 5 à 9%). Dans le cadre de cet exercice, c’est avant tout parce que :

  • nous utilisons un “foreach” (disponible en C0x11)
@foreach(elements,v,back_preds_w) 
{
    if (v:=>val != w) 
        @append(find_root_union_find(v:=>val,&preorder_set),&p); 
    else 
        @at(w,&type) = self; 
};
  • les fonctions d’écriture dans nos containers acceptent tout type de donnée comme paramètre “origine”.
// Copy node_pool to worklist. 
@here( HavlakLoopFinder_NodeList,worklist); 
@append(&node_pool,&worklist);
  • la directive #include n’est nécessaire que dans le fichier principal.

Pour donner une idée plus juste de l’expressivité de Cawen, on peut ajouter que Govel, notre bébé STL maison, qui contient un tableau en pile, un tableau en tas, une liste à double-chainage et les encapsulations de Judy1 et JudyL, les itérateurs associés, les différents foreach (runtime & précompilation) ainsi qu’une politique de copie et de libération ne compte que 10081 lignes de code.

Activation d’une libération automatique

On peut exprimer en Cawen des demandes du type :”chaque fois qu’on entre dans le code d’un fonction exécuter ce traitement de précompilation” ou “avant/après chaque typedef exécuter ce traitement” ou “chaque fois que la portée d’une variable se termine, lancer ce traitement”…

C’est cette dernière possibilité que nous avons utilisée pour coder la libération automatique en fin de scope. On l’active ainsi :

#defCodePointOn goodbyeVar;

Cette politique de libération, qui tient en 330 lignes de Cawen, appartient à govel (notre collection de containers) et ne fait donc pas partie du langage proprement dit.

Conclusion

La démarche de R.Hundt nous a paru très intéressante. Bien souvent, le débat autour des langages de programmation, leurs défauts et leurs avantages respectifs tourne rapidement à la guerre de religion.

Merci donc à R.Hundt de rappeler avec ces tests que les langages informatiques servent avant tout à exprimer simplement des traitements potentiellement complexes puis à les exécuter efficacement et qu’il existe donc des critères objectifs permettant de mesurer leur pertinence dans un contexte donné.

En s’en tenant à ces principes, nous pensons avoir montré qu’il reste encore beaucoup de place pour de nouvelles solutions…

Nous sommes très conscients qu’à ce jour Cawen reste très perfectible et qu’un long travail nous attend encore…Cependant, même si nous ne savons pas jusqu’où ira le petit Cawen, peut-on s’accorder à dire que ses premiers pas semblent prometteurs ?

Commentaires

  1. Bonjour,
    je me permets de vous répondre suite à un message laissé sur notre site internet.
    je vous revoie vers l’association Green Code Lab pour débattre davantage sur les sujets d’écoconception sur lesquels nous travaillons.
    Notre vocation n’est pas débattre sur le langage utilisé même si nous avons nos préférences (et même si le petit cawen semble très performant en effet !) . second point, nous nous intéressons à l’ensemble du cycle de vie du logiciel et pas seulement à la phase d’usage. Lors de cette phase, la consommation est une des parties à laquelle nous nous intéressons via l’analyse statique de code et via la mesure énergétique générée par le delta entre 2 versions d’applications intégrant des corrections du référentiel d’écoconception que nous avons mis au point. Nous nous intéressons à la performance car elle est « souvent » corrélée avec une moindre consommation des ressources au final (mais pas toujours !).
    Je pense que vos travaux et nos travaux vont dans le même sens. Je vous invite à nous rejoindre lors de la grand messe national de l’écoconception à Nantes le 18 octobre à l’école des Mines de Nantes. Il doit rester quelques places !
    Un échange avec le GCL pourrait également être vertueux dans les prochains mois (peut-être travailler sur l’aspect consommation de Cawen ?).
    A bientôt
    Thierry

    • Gwenaël Chailleu :

      Bonjour Thierry !

      Nous avons certainement beaucoup à apprendre sur les différents aspects de l’éco-conception.

      « L’ensemble du cycle de vie du logiciel », « analyse statique de code », la corrélation « partielle » des performances avec la consommation finale de ressources, sont des points qui nous intriguent et donc nous intéressent particulièrement.

      Dans l’immédiat, nous serions évidemment très désireux de pouvoir mesurer la consommation des différentes versions dont nous avons mis le source en ligne…

      N’hésitez pas à nous contacter sur nos mails individuels et à bientôt sur Green Code Lab !

      Thomas & Gwen

Répondre

*


+ trois = 6

-Votre adresse ne sera pas visible-