mercredi 21 août 2013

JVM: Le prix de l'immutabilité




Je l'avoue, durant mes vacances au bord de l'eau, entre les apéritifs et les siestes syndicales, une question est venue me chatouiller: les évangélistes de la programmation fonctionnelle nous bassinent avec les avantages de l'immutabilité mais au bout du compte ça doit pas être gratuit cette affaire là? Combien ça coûte? Du coup je me suis fixé comme objectif pour ma rentrée de réunir des éléments permettant d'avoir un peu plus de recul sur cette question. Je vous propose de suivre ma démarche dans ce billet.


Tout d'abord, rappelons que la principale vertu de l'immutabilité est qu'un objet non modifiable peut être accédé par plusieurs threads sans nécessiter de verrouillage, permettant d'exclure toute situation de compétition (race condition) sur une ressource. Il semble que cela soit une des clefs permettant de passer de la gestion de la concurrence au parallélisme. Soit, toutefois les valeurs d'un objet doivent parfois être modifiées, impliquant la création d'une nouvelle entité immuable avec la ou les nouvelle(s) valeur(s), l'allocation d'une nouvelle instance et potentiellement la collecte de l'ancienne. C'est précisément ces effets de bord qui retiennent mon attention.


Le POC prend la forme de tests unitaires dans lesquels tous les objets d'une liste sont modifiés: une case class comprenant un membre unique de type Long et l'opération appliquée est l'ajout du nombre de nanosecondes contenue dans une journée. La situation est observée sous deux angles différents: l'objet est modifiable et sa variable d'instance est mise à jour ou l'objet est immuable et une nouvelle entité est créée. Le langage est Scala, le code est trivial et vous pouvez le trouver les détails sur Github (https://github.com/bleporini/immutabilityCost).


Les classes:


  case class Immutable(date:Long)
case class Mutable(var date:Long)
Les fonctions de modification:
    def addOneDay(from:Immutable):Immutable= Immutable(from.date+oneDayNs)

def addOneDay(from:Mutable):Mutable={
from.date = from.date + oneDayNs
from
}
L'application des fonctions:
mo /*la liste*/ map transformer /* la foncntion modifiante */

Le problème du micro benchmark


Le programme s'exécute sur la JVM, un environnement d'exécution "managé", c'est à dire qu'en plus de faire le ménage dans la mémoire (Garbage Collection), la machine virtuelle, et plus particulièrement le JIT (Just In Time compiler), réalise plein de choses à l'insu de notre plein gré à des fins d'optimisations, comme compiler du bytecode en code natif et l'intégrer dans les piles d'appel (OSR), "inliner" des méthodes, etc. Ce comportement peut contribuer de façon importante dans la difficulté à obtenir des temps d'exécution répétables.


Il ne me semble pas opportun de procéder à un paramétrage hasardeux visant à stabiliser les résultats. Mon approche s'atèle plutôt à observer le comportement de la JVM lors de l'exécution en boucle du test pour déterminer quand les manipulations sur le code sont stabilisées et les temps mesurés sont à peu près constants. En gros le chrono est déclenché quand la JVM est "chaude".


En ce qui concerne le GC, je m'assure simplement en analysant les logs produits par le paramètre -XX:+PrintGCDetails qu'il n'y a pas de collecte complète qui pourrait fausser les résultats.


Du côté de la manipulation de code, une exécution verbeuse (état d'avancement sur la sortie standard) du test en boucle conjuguée à l'affichage des informations de compilation (-XX:+PrintCompilation) me permet de visualiser à partir de quand le code n'est plus manipulé. Dans le cas étudié il faut moins d'une centaine d'itération pour que JIT calme ses ardeurs (les 700 premières manipulations vous sont graciées…):




[…]
704 75 scala.collection.Iterator$class::foreach (26 bytes)
704 65 scala.collection.TraversableLike$$anonfun$map$1::apply (6 bytes) made not entrant
704 66 scala.collection.TraversableLike$$anonfun$map$1::apply (20 bytes) made not entrant
711 76 blep.ImmutabilityTest$$anonfun$1$$anonfun$bencher$1$1::apply (9 bytes)
711 77 blep.ImmutabilityTest$$anonfun$1$$anonfun$bencher$1$1::apply (9 bytes)
713 78 blep.ImmutabilityTest$$anonfun$1::blep$ImmutabilityTest$$anonfun$$addOneDay$1 (23 bytes)
713 79 blep.ImmutabilityTest$Immutable::date (5 bytes)
713 80 blep.package$::oneDayNs (5 bytes)
714 81 scala.collection.TraversableLike$$anonfun$map$1::apply (6 bytes)
714 82 scala.collection.TraversableLike$$anonfun$map$1::apply (20 bytes)
720 83 java.lang.StringBuilder::append (8 bytes)
0 nth time: 15316 us
723 84 scala.collection.immutable.VectorBuilder::display1 (5 bytes)
724 85 scala.collection.immutable.VectorBuilder::depth (5 bytes)
724 86 scala.collection.immutable.VectorBuilder::display0_$eq (6 bytes)
724 87 scala.collection.immutable.VectorPointer$class::gotoNextBlockStartWritable (757 bytes)
728 88 scala.collection.immutable.VectorIterator::display0_$eq (6 bytes)
729 89 scala.collection.immutable.VectorPointer$class::gotoNextBlockStart (336 bytes)
752 90 scala.collection.immutable.VectorIterator::display1 (5 bytes)
100 nth time: 1423 us
200 nth time: 1394 us
300 nth time: 2639 us
400 nth time: 1362 us
500 nth time: 1369 us
600 nth time: 1419 us
Le calibrage issu de ces informations conduisent à effectuer l'expérimentation dans les conditions suivantes: la liste comprend 100000 éléments, l'application de la modification est effectuée 10000 fois sur la liste, chaque itération est chronométrée et une moyenne globale plus une sur les 100 dernières sont calculées. C'est un peu bourrin, mais cela permet de générer des résultats assez stables.


Dernier détail, il est évidemment important que le lanceur (SBT) "forke" la JVM pour les tests, il serait ballot que le comportement soit parasité par l'outil de build...


Je n'ai pas tenu compte des potentielles problématiques liées au cache L1/L2/L3 du socle matériel, si quelqu'un sait comment récolter ce genre d'informations sur Mac, merci de contribuer!


La partie la plus "velue" aura été d'ajuster les paramètres de lancement dans SBT (S pour simple, vous êtes sûrs?).


Les résultats


Venons en aux chiffres:

















































Méthode Itérations Max Min Moy Moy(100) GC Pauses Pauses Tot FGC Pauses
Mutable 10000 34620 951 2505 1111 66 0,52 0
Immutable 10000 45160 1137 4327 1417 126 1,76 0
30 % 20 % 73 % 28 % 91 % 238 %

Ce n'est donc pas une surprise, comparativement, le GC ramasse : il se déclenche deux fois plus pour le même travail et génère 3,4 fois plus de temps de pauses quand le traitement engendre de nouvelles entités à chaque modification.


Mais au fond, le résultat qui m'intéresse le plus est la différence au niveau du temps d'exécution, le nerf de la guerre, l'immutabilité dure à priori pas loin de 30% plus longtemps. Voilà, tu t'es fait attiré sur cet article au titre tendance, tu as suivi un geek qui fait mumuse avec des additions pour arriver à la conclusion que générer plus de travail prend plus de temps… tu peux retourner voir si les specs de l'iPhone 6 n'ont pas fuité!


Plus sérieusement, le temps d'exécution étant la finalité principale à mon sens, que peut-on tirer de ce chiffre de 30%?


30% d'augmentation du taux de chômage c'est considérable et c'est une catastrophe, 30% d'augmentation de salaire, ça change la vie. En revanche un ordinateur 30% plus puissant qu'un autre ça fait pas une grosse différence à l'utilisation et mon avis est que ce constat se transpose aux programmes informatiques. Je m'explique: quand je clique sur un bouton, que l'appli web réponde en 100ms ou 130ms, c'est rapide pourtant il y a 30% d'écart; si au contraire quand je clique et que la réponse arrive au bout de 10 min ou 13 min, ça rame la mort dans les deux cas! Donc 30% ce n'est pas négligeable mais cela ne nous fait pas changer de classification: on ne passe pas de "ça se traîne" à "ça envoie du bois".


Peut-on dès lors troller qu'adopter l'immutabilité entraîne 30% de dégradations sur les temps d'exécution? Je vois déjà le tweet ravageur:



D'une part, l'expérimentation zoome sur un point particulier et la différence entre les deux zones mesurées se résume à "allocation d'un Long et l'addition de deux Long" contre "allocation d'une instance de case class, d'un Long et addition de deux Long". Le trait est forcément grossi.


D'autre part, dans la plupart des applications, beaucoup plus de temps est potentiellement consommé dans les I/O (réseau ou disque), dans l'interrogation des systèmes de persistance, ou encore lors de la génération de vue ou de réponses, etc que dans l'allocation et la collecte. Dans la vraie vie, le gain de 30% n'est évidemment pas global.


De plus, si les entités mutables de votre application sont partagées entre plusieurs threads, vous êtes voués à recourir à l'utilisation de moniteurs pour synchroniser les accès (autant en lecture qu'en écriture), du coup le temps gagné sur l'immutabilité peut aisément être perdu, surtout que la programmation concurrente est souvent mal maîtrisée.


Sans compter que si des copies défensives (ça m'arrive jamais…) doivent sécuriser l'accès aux membres de vos classes, l'inconvénient de la gestion de la concurrence sera cumulé avec celui des allocations et collectes induites par les duplications d'objets...


Compte tenu de ces données, mon opinion est que l'immutabilité coûte certes plus, mais dans la plupart des situations la charge supplémentaire induite ne sera guère perceptible, sauf si vous avez la chance de travailler sur une application extrêmement exigeante dans laquelle la moindre latence est chassée, telle q'un automate temps réel…




7 commentaires:

Frédéric Martini a dit…

Je nuancerais quand même cela : tu fais la comparaison mais uniquement en te basant sur une utilisation "mutable" de ces objets.

Dans ce cas il est tout à fait logique que la version "immutable" soit moins performante.


A l'inverse si tu dois partager une instance entre plusieurs objets/méthodes, la version immuable sera plus performante car il n'y aura pas besoin de faire des copies de protection à tout bout de champs...



a++

Fabszn a dit…

Hello,

Article très intéressant merci!

clementd a dit…

En FP, la mutabilité n'est qu'une optimisation comme une autre. C'est là pour améliorer la perf (temps d'exec, space used, …) au détriment de la simplicité du programme.

La plupart du temps on considère que c'est une optimisation prématurée si on la met en place sans savoir qu'on en a besoin. (comme le déroulage de boucle, le tuilage, …), d'autant qu'un runtime adapté et le partage structurel permet d'éliminer pas mal d'overhead.

Donc comme toutes les optims, tu les mets en place quand tu en as besoin, en te basant sur du profiling, pas avant.

Brice Leporini a dit…

Le but de ma démarche n'était pas d'identifier une optimisation mais d'avoir une idée plus précise du coût qu'impose cette décision de conception.
Le cas monté est caricatural et l'overhead m'a semblé assez limité. C'est ce qui me pousse à penser de l'immutabilité n'est pas un sujet d'inquiétude dans la plupart des situations.

ouertani a dit…

Le but principale c'est d'avoir un code qui fonctionne correctement et ensuite les performances.
Le débat de mutable vs immutable ainsi que le choix du type de collection dans scala est bel est bien identifié :)
Ce que marque Scala vs les autre FP qui sont *pure* est le fait d'être hybride et tolérer les effets de bord.

ouertani a dit…

un exemple ou la concurrence et les perf sont en jeux :http://learningfunctionalprogramming.blogspot.ro/2012/05/importance-of-immutability-for.html

clementd a dit…

ouertani: si tu penses à Haskell, il ne t'interdit pas de mettre en place de la mutabilité au besoin, mais il t'oblige à le faire sainement (cf ST, qui existe aussi dans Scalaz BTW)
.