Journal OpenJDK 8, JEP 142 & False Sharing

Posté par .
30
2
avr.
2014
Ce journal a été promu en dépêche : OpenJDK 8, JEP 142 & False Sharing.

Sommaire

Java 8 est sorti ce mois-ci; tu as même eu droit à une dépêche ici même qui parle des lambdas, la stream API etc.

Cependant derrière ces gros changements qui impactent le monde hétérogène des devs Java, il y a des petits changements qui eux servent plutôt aux devs qui font des briques de base, de l'infra ou du code qui va vite. Je te propose donc d'explorer quelques JDK Enhancement Proposals d'OpenJDK.

Pour ce premier journal, on commence avec la JEP 142: Reduce Cache Contention on Specified Fields soit l'annotation @Contended qui vise à proposer une solution aux problèmes de false sharing.

C'est quoi le false sharing ?

Le false sharing est un problème de performance en environnement parallèle qui est causé par une « leaky abstraction » du matériel. La présentation suivante est extrêmement grossière et ne vise qu'à faire comprendre le problème aux gens ne connaissant pas du tout le domaine.

En tant que développeur on aime se représenter la mémoire comme un espace d'adressage continu. Plus on travaille dans un langage de haut niveau plus cela est vrai. Par exemple les problèmes d'alignement sont une notion totalement inconnue pour beaucoup. Cependant dans ce monde idéal la réalité du matériel refait surface périodiquement.

Un CPU étant beaucoup plus rapide que la mémoire vive et le principe de localité ayant été découvert, il dispose de caches mémoire. Ce sont des petits morceaux de mémoire tampon travaillant à une vitesse beaucoup plus proche du CPU. Le pari étant qu'une fois l'accès couteux à la mémoire centrale effectué cette valeur va être réutilisée et on ira alors la chercher dans ce cache et donc gagner beaucoup beaucoup de temps.

Le problème du false sharing vient de deux choses:

  • L'architecture des caches. Un cache est composé d'un certain nombre de lignes de taille fixe (64 octets par exemple). Lorsqu'une modification est faite, elle affecte la ligne entière.
  • Le CPU doit gérer la cohérence entre ces caches à l’aide d’un protocole de cohérence. Il s'agit de s'assurer que lorsqu'un CPU/core fait une modification elle sera visible par les autres. Chaque architecture à son propre modèle de cohérence, le X86 étant par exemple particulière fort. Ce modèle est exposé dans les langages de bas niveau, mais les langages de haut niveau décrivent souvent leur propre memory model. Charge au compilateur de traduire celui du langage vers celui de la plate-forme.

Si l'on met ces deux choses ensembles, on arrive au false sharing: deux variables théoriquement indépendantes se retrouvent sur la même ligne de cache. Chacune est accédée/modifiée par un CPU distinct, cependant ils doivent passer leur temps à se synchroniser ce qui écroule les performances.

Bref notre bel espace mémoire uniforme vient d'en prendre un coup. Coller ou espacer deux variables peut faire varier d'un à plusieurs ordre de grandeur la performance de notre structure de donnée.

Exemple

Commençons avec un benchmark très simple: Une classe avec un seul membre ainsi que de 4 threads. Le premier lit en permanence la valeur de ce membre, les trois autres ne font rien. Le benchmark est écrit avec JMH

  @State(Scope.Benchmark)
  public static class StateNoFalseSharing {
    public int readOnly;
  }

  @GenerateMicroBenchmark
  @Group("noFalseSharing")
  public int reader(StateNoFalseSharing s) { return s.readOnly; }

  @GenerateMicroBenchmark
  @Group("noFalseSharing")
  public void noOp(StateNoFalseSharing s) { }

qui nous donne le résultat suivant:

Benchmark                                        Mode   Samples         Mean   Mean error    Units
g.c.Benchmarks.noFalseSharing:noOp               avgt        18        0.297        0.002    ns/op
g.c.Benchmarks.noFalseSharing:reader             avgt        18        0.743        0.003    ns/op

Comme on pouvait s'y attendre c'est très rapide et on aura du mal à mesurer quelque chose de plus petit.

Maintenant faisons évoluer notre benchmark. Nous ajoutons un deuxième membre qui va être accéder par les trois threads qui
ne faisaient rien. Le premier thread ne change absolument pas et si les caches n'étaient pas organisés en ligne il n'y aurait aucune raison que sa performance soit affectée.

  @State(Scope.Group)
  public static class StateFalseSharing {
    int readOnly;
    volatile int writeOnly;
  }

  @GenerateMicroBenchmark
  @Group("falseSharing")
  public int reader(StateFalseSharing s) {
    return s.readOnly;
  }

  @GenerateMicroBenchmark
  @Group("falseSharing")
  public int writer(StateFalseSharing s) {
    return s.writeOnly++;
  }

Regardons les résultats:

Benchmark                                        Mode   Samples         Mean   Mean error    Units
g.c.Benchmarks.falseSharing:reader               avgt        18        5.038        0.617    ns/op
g.c.Benchmarks.falseSharing:writer               avgt        18       78.530        3.598    ns/op

On vient presque de prendre un facteur 10.

Nous pouvons vérifier la disposition mémoire de notre objet StateBaseline avec jol pour voir que nos deux variables ont bien été collées par le compilateur:

gist.contended.Benchmarks.StateFalseSharing object internals:
 OFFSET  SIZE  TYPE DESCRIPTION                    VALUE
      0    12       (object header)                N/A
     12     4   int StateFalseSharing.readOnly     N/A
     16     4   int StateFalseSharing.writeOnly    N/A
     20     4       (loss due to the next object alignment)
Instance size: 24 bytes (estimated, the sample instance is not available)
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

Sans rentrer dans les détails, statistiquement il y a de fortes chances qu'ils se retrouvent dans la même ligne de cache.

@Contended

La solution à notre problème est donc simplement d'espacer ces deux variables quitte à perdre de l'espace. Ça parait simple mais avant OpenJDK 8 cela demande de très sérieusement connaitre/lutter contre la VM.

Fort du principe de localité, le comportement logique de la VM est d'essayer d'entasser autant que possible les différents membres comme bon lui semble. Le layout d'un objet peut changer selon beaucoup de critères et l'utilisation d'un GC n'aide pas puisqu'il peut décider de déplacer un peu tout et n’importe quoi (notamment les tableaux utilisés pour padder). Bref trouver une stratégie qui marche, est une source d'amusement inépuisable. Aleksey Shipilёv en a documenté quelques-unes dans un benchmark JMH de même que Martin Thompson.

La JEP 142 propose d'ajouter une annotation @Contended pour identifier les variables, ou classes, qui doivent se retrouver seules sur une ligne de cache pour éviter le false sharing.

Essayons de l'utiliser:

  @State(Scope.Group)
  public static class StateContended {
    int readOnly;
    @Contended volatile int writeOnly;
  }

  @GenerateMicroBenchmark
  @Group("contented")
  public int reader(StateContended s) {
    return s.readOnly;
  }

  @GenerateMicroBenchmark
  @Group("contented")
  public int writer(StateContended s) {
    return s.writeOnly++;
  }

Vérifions avec jol puis avec JMH

gist.contended.Benchmarks.StateContended object internals:
 OFFSET  SIZE  TYPE DESCRIPTION                    VALUE
      0    12       (object header)                N/A
     12     4   int StateContended.readOnly        N/A
     16   128       (alignment/padding gap)        N/A
    144     4   int StateContended.writeOnly       N/A
    148     4       (loss due to the next object alignment)
Instance size: 152 bytes (estimated, the sample instance is not available)
Space losses: 128 bytes internal + 4 bytes external = 132 bytes total


Benchmark                                        Mode   Samples         Mean   Mean error    Units
g.c.Benchmarks.contented:reader                  avgt        18        0.742        0.006    ns/op
g.c.Benchmarks.contented:writer                  avgt        18       70.811        3.572    ns/op

On observe que la variable a bien été décalée et on retrouve les performances initiales.

Limitations

@Contended est une JEP d'OpenJDK, c'est à dire qu'il ne s'agit pas d'une spécification de Java ou de la JVM. L'annotation se trouve dans un package privé d'Oracle et l'annotation n'est disponible que pour les classes du JDK par défaut (comme beaucoup de chose que le JDK se réserve précieusement). Si on veut l'utiliser, et donc se lier à OpenJDK, il faut passer l'option -XX:-RestrictContended.

Bien entendu vu l'impact sur la consommation mémoire et la possibilité de réduire l’efficacité du cache il faut bien savoir ce qu'on fait et utiliser avec parcimonie.

Comment détecter un cas de false sharing

Notre exemple était très simple et nous connaissions le problème. Malheureusement dans la vraie vie ce n'est pas aussi évident et il n'existe pas à ma connaissance d'outil simple permettant de détecter le false sharing, quel que soit le langage. On peut suivre les conseils d'Intel et les appliquer avec leur outil ou avec perf mais ça reste assez empirique.

Si on garde le principe du false sharing en tête, cela permet de surveiller les mauvais patterns dans les bouts d'infrastructure qui peuvent être affectés. En général il faut que ça commence à aller sérieusement vite, donc structure de données dédiée, pour que ça commence à devenir un problème.

Cas courants

Identiquement à notre exemple un même objet possède deux membres qui sont utilisés par deux threads différents. Ça arrive par exemple qu'en un objet tient des statistiques. Dans ce cas on va annoter le membre avec @Contended.

On peut avoir aussi le cas de plusieurs instances d'une même classe qui préférerait être chacune être dans sa propre ligne de cache. Dans ce cas on va annoter la classe. Cela fonctionne aussi si l'on met les instances dans un tableau. Cas courant lorsque fait travailler plusieurs threads en parallèle.

Le dernier cas est du calcul de type matriciel avec plusieurs threads. Dans ce cas l'annotation ne peut rien et il faut concevoir son algorithme pour en tenir compte (tout comme on itère dans le bon sens). Dr doobs fourni un tel exemple.

J’ai essayé de fournir quelques exemples dans le benchmark.

Conclusion

@Contended ne devrait pas changer la vie de grand monde hormis pour celle des gens qui pondent l’infra de service à haute performance. Mais elle ouvre la porte à une revendication de longue date : marier les bénéfices de la JVM avec les besoins des applications haute performance en ouvrant l’accès au matériel et à des techniques contre l’esprit initial de Java mais requises.

Cette annotation ne répond absolument pas au besoin de pouvoir contrôler le layout d’un objet ou de choisir quels membres d’un objet doivent être regroupés ensemble. Il ne résout pas non plus les problèmes d’indirection dus aux références pour les objets. Mais la pression monte doucement avec le nombre d’application qui passe en off-the-heap ou en mmap lorsque nécessaire.

Enfin le false sharing n'est pas le seul problème liés aux caches. Un autre exemple.
Et bien entendu exploiter les caches correctement a un impact certain sur les performances d'une application.

  • # attention au microbenchmark

    Posté par . Évalué à 5.

    Les microbenchmark ne veulent pas dire grand chose.

    J'avais fait une étude de pire cas pour un code pour avion. Quand on fait un microbenchmark (temps d’exécution d'une fonction, au lieu du soft entier), il peut y avoir une différence d'un ordre de grandeur entre un cache 'chaud' et un cache 'froid'. Le cache est vraiment chaud à partir de 3 itérations du même code (cela se voit si on trace une courbe de temps vs numéro d'itération), un cache froid est obtenu en manipulant une grande quantité de donné qui n'a rien à voir avec le 1er code (il faudrait aussi tenir compte d'une grande quantité de code pour les miss du cache instructions).

    La réalité est située entre ces 2 extrêmes. L'optimisation proposée ici, peut consommer tellement de mémoire que le taux de miss peut monter en flèche, et détruire tout intérêt pour la méthode.

    Vu les vitesses des CPU par rapport au bus mémoire, dans le cas multithread, il faut faire en sorte que chaque cpu ne touche qu'à ses seuls données. Linux 2.4 avait du mal à passer à 4 cpu, Linux 2.6 peut monter à 256 cpu et plus, surtout car chaque processeur dispose de ces données en privés.

    "La première sécurité est la liberté"

    • [^] # Re: attention au microbenchmark

      Posté par (page perso) . Évalué à 3.

      Le cache est vraiment chaud à partir de 3 itérations du même code (cela se voit si on trace une courbe de temps vs numéro d'itération), un cache froid est obtenu en manipulant une grande quantité de donné qui n'a rien à voir avec le 1er code (il faudrait aussi tenir compte d'une grande quantité de code pour les miss du cache instructions).

      C'est vrai et ça dépend aussi de la politique de « Garbage Collection » et de l'architecture matérielle, mais globalement il me semble que le « G1 » introduit avec le jdk 7 fait l'unanimité. J'ai entendu un dev java, qui fait le backend d'un site Web à gros trafic, parler de 2/3 heures de transition pour le « chauffage » des caches Java. J'étais un peu surpris, mais apparemment sans ce « pré-chauffage » les machines tombent tout simplement sous la charge en production, alors qu'elles tiennent cette charge avec un cache « chaud ». Aussi je pense qu'on est à plus que 3 itérations dans ce cas précis qui, je pense, fait intervenir plusieurs niveaux de gros caches. Ce qui conforte ton point de vue :)

      • [^] # Re: attention au microbenchmark

        Posté par . Évalué à 2.

        Ici, tu parles de la compilation du code java en code natif, et de la stabilisation de la mémoire avec le GC (qui sépare les données persistantes et les autres). Cela n'a rien à avoir avec les caches des cpu.

        "La première sécurité est la liberté"

        • [^] # Re: attention au microbenchmark

          Posté par (page perso) . Évalué à 3.

          Je ne suis mélangé avec les différents caches, et en me relisant je m'aperçois que mon message n'est pas clair :)

          Explications : J'ai pris la mauvaise habitude de parler de caches pour les générations d'objets utilisées par le GC Java, c'est ce que j'appelle « caches java » et qui est différent du cache CPU visé par « @contented ».

          Ce que je voulais dire, c'est que ton propos (attention au microbenchmark !) est d'autant plus pertinent, pour moi, avec une approche verticale, c'est à dire que l'on considère la corrélation de l'action du GC, du JIT et des caches CPU. Ma théorie étant que le comportement du GC et du JIT ont un effet sur les caches CPU (puisqu’ils travaillent en amont). C'est ce que j'appelle l'approche verticale (on considère toute la pile logicielle jusqu'aux instructions données au CPU).

          C'est plus clair ? :)

    • [^] # Re: attention au microbenchmark

      Posté par . Évalué à 2.

      Les microbenchmark ne veulent pas dire grand chose.

      Peut-être que son microbenchmark est une simplification d'un cas réél qu'il a rencontré ?
      Par ex j'avais prévu d'écrire un journal sur perf avec un microbenchmark mais en ayant pris soin de vérifier que les résultats du microbench étaient cohérents avec ceux de la vraie application.

      En tout cas merci à l'auteur pour ce journal, très intéressant :)

    • [^] # Re: attention au microbenchmark

      Posté par . Évalué à 3.

      Je suis d'accord avec toi, j'ajouterai juste qu'il ne faut pas se focaliser sur les perfs au début. C'est à la fin d'un projet qu'il faut voir si les perfs conviennent ou non. Dans le second cas, il faut faire du profiling pour chercher où gagner des perf. Il vaut mieux gagner 1% de perf dans une routine utiliser 50% du temps que 30% dans une utilisé 1% du temps. Ca semble évident, mais ça ne l'ai pas lors de l'analyse.
      Sur les perf, le cache joue mais pas que. J'avais benchmark une petite routine il y a une dizaine d'année sur un power PC. Au premier passage elle prenait 2µs. A partir du second 1.8µs le code était dans le cache instruction. Au 18ième passage, on passait d'un coup à 800ns, dû à la mise en route de la prédiction de branchement et au non vidage des caches.

      Une chose me semble évidente, c'est qu'un compilateur fera toujours mieux que nous. Sauf peut-être à passer 2 mois sur 50 lignes de code.

      • [^] # Re: attention au microbenchmark

        Posté par . Évalué à 4.

        "C'est à la fin d'un projet qu'il faut voir si les perfs conviennent ou non."

        Il vaut toujours mieux un code maintenable à un code rapide, c'est évident. Mais si le code est énorme, et que la lenteur est du à des erreurs d'architectures, c'est impossible de corriger.

        Le cas typique est le lancement de fonctions de rafraichissement ou de mise à jour qui nécessite la relecture de toutes les données. Avec de grosses données, c'est la catastrophe.

        "La première sécurité est la liberté"

        • [^] # Re: attention au microbenchmark

          Posté par (page perso) . Évalué à 3.

          Dans certain code de calcul, par exemple code hybride MPI/OpenMP, si la performance n'est pas prise en compte dès le début, cela ne marchera pas dans la plupart des cas. En effet, c'est pas toujours évident de rendre un code hybride s'il n'a pas été conçu pour dès le début.

          • [^] # Re: attention au microbenchmark

            Posté par . Évalué à 1.

            Je pense que l'auteur voulait à l'origine faire la différence entre une architecture fait pour la performance (découpe en tache parralélisable, structure de donné correct, usage de map au lieu de liste), par rapport à faire du hack (réécriture de conteneur, option de gc, mise à plat d'objet, usage de static final, enlever les getter/Setter, etc…)

            "La première sécurité est la liberté"

          • [^] # Re: attention au microbenchmark

            Posté par . Évalué à 2.

            Ça semble évident que si la performance est le principal critère, que tu développes une architecture adaptée. Mais dans 99% des cas, les performances sont suffisante en faisant attention à ce qu’on fait. Pour un tri, on peut choisir le tri à bulle pour des petites quantités, mais sinon un bon quicksort c’est mieux.
            Mon propos était surtout sur le codage. Si l’architecture ne répond pas au besoin, de toute façon, tu es mal.

            On peut optimiser ce genre de chose en C par exemple, je mets côte à côte des champs de structure proche pour le sens, voir des structure de structure. Mais on peut aussi déstructurer pour mettre côte à côte les éléments souvent accédé ensemble… ça rend la structure moins lisible, mais comme les champs on de grande chance d’être sur la même ligne de cache, on gagne en performance. On peut aussi faire du prefetch ça évite de trop déstructurer. On peut aussi éloigner les éléments accédés par des thread différents, surtout si on défini des affinités sur les CPU/cœur.

            Mais rendre le code moins lisible doit toujours venir en dernier recours, après l’architecture et le choix des algorithmes ayant les complexités les plus efficaces pour le problème traité.

    • [^] # Re: attention au microbenchmark

      Posté par . Évalué à 7.

      Je suis totalement d'accord avec toi.

      Les microbenchmark sont juste la pour avoir des exemples de code très concis et obtenir des chiffres facilement pour valider le problème. Ils ne reflètent pas du tout la réalité et ne cherche pas à simuler un problème du monde réel en particulier.

      Je suis aussi d'accord que @Contended peut faire potentiellement plus de mal que de bien surtout si des couillons comme moi commence à l'expliquer, ce qui implique qu'il va être abusé dans tous les sens. En pratique 99% des developpeurs ne devraient jamais avoir à y toucher, et pour les autres c'est un usage exceptionnel. Si je vois ca dans du code business je pars en courant de même que si une brique d'infra l'utilise à plus de 1, 2, 5 fois.

      Pour ceux qui veulent un exemple plus concret issu du monde réel, LMAX avait très bien documenté le problème sur un ring buffer utilisé pour structure d'échange de donnée entre threads ou typiquement les variable head and tail vont se retrouver sur la même ligne de cache alors qu'elles sont massivement utilisées par des threads différents. Ca se voit par ce que la structure est méchamment optimisée pour ne jamais avoir de lock et une seule barrière mémoire.

      Donc oui dans la vraie vie, si tu ne travailles pas sur ce genre de strucuture n'utilise pas @Contented.

  • # Quid du jdk oracle ?

    Posté par (page perso) . Évalué à 3.

    Merci pour ce journal, bien écrit, technique sur Java !

    Je connaissais le problème du « false sharing », mais je n'avais pas suivi l'introduction le l'annotation « @contended ».

    J'ai souvent du mal à défendre l'openjdk dans les projets java sur lesquels je travaille (essentiellement pour des raisons historiques), et d'après ce que j'ai compris (mais j'ai du mal à trouver des sources fiables) cette annotation n'est pas encore implémentée par le jdk d'Oracle. Ce qui m'étonne, mais qui semble bien être le cas.

    Quelqu'un peut confirmer/infirmer ? ou quelqu'un a plus d'informations ?

    • [^] # Re: Quid du jdk oracle ?

      Posté par (page perso) . Évalué à 3.

      J'ai souvent du mal à défendre l'openjdk dans les projets java sur lesquels je travaille (essentiellement pour des raisons historiques)

      vu que OpenJDK est désormais l'implémentation officielle de Java (ce n'était pas le cas avec Java 1.6, c'est le cas depuis Java 1.7), quelle difficulté resterait à mettre en avant OpenJDK ? cf. OpenJDK je cite « OpenJDK is the official Java SE 7 reference implementation ». Confirmé encore par Mark Reinhold au fosdem 2014 :-)

      • [^] # Re: Quid du jdk oracle ?

        Posté par (page perso) . Évalué à 2.

        Très juste BAud!

        En fait, je viens de me rendre compte qu'il n'y a qu'un jdk 8 (oracle-jdk8 = open-jdk8). Ce qui doit logiquement aussi être le cas pour le jdk7.

        Sinon, les industriels avec lesquels j'ai travaillé ne sont pas encore passés au jdk 7, c'est pour cela que je parle de raison historique et de jdk mutiples :)

        Phrase débile que j'ai déjà entendue : « s'il existe une version open source et une version closed source, c'est forcément que la closed est meilleure, sinon pourquoi faire deux versions ? »

        Mais bon, cela n'est plus d'actualité, alors tant mieux !

        • [^] # Re: Quid du jdk oracle ?

          Posté par (page perso) . Évalué à 4.

          Phrase débile que j'ai déjà entendue : « s'il existe une version open source et une version closed source, c'est forcément que la closed est meilleure, sinon pourquoi faire deux versions ? »

          tout simplement parce qu'en 1.6 Sun avait encore gardé ses "mauvaises" habitudes d'utiliser du code propriétaire, repris de sous-traitants (genre pour les fontes, le chiffrement…) pour lequel ils avaient des accords commerciaux, valides pour une diffusion en propriétaire mais inexploitable en libre. Cela a sans doute été réécrit en libre ou libéré pendant tout le temps de développement de la 1.7.

          Sinon, les industriels avec lesquels j'ai travaillé ne sont pas encore passés au jdk 7

          pour tous ceux restés en 1.4 (oui, j'en croise aussi…) autant qu'ils passent à la 8 pour avoir 2 fois plus de performance :-)

        • [^] # Re: Quid du jdk oracle ?

          Posté par . Évalué à 3.

          oracle-jdk8 est complètement base sur open-jdk8 auquel il rajoute des choses.

          Oracle rajoute des babioles vérolées comme le plugin Java pour les navigateurs (a l'origine de nombreuses failles de sécurité), des fontes et des algorithmes propriétaires pour des trucs graphiques dans AWT et Swing, bref des choses qui n’intéressent pas grand monde et qu'IcedTea a remplacé en libre.

          Par contre Oracle vient de rajouter Mission Control (qui vient de JRockit) a son JDK, mais pas a OpenJDK. :(

  • # off-heap

    Posté par . Évalué à 2.

    off-heap
    http://stackoverflow.com/questions/6091615/difference-between-on-heap-and-off-heap

    Pour palier aux déficiences du GC qui ralentit inutilement le CPU lorsque trop d'objets sont sur la heap.
    On décide d'en sérialiser une partie (statiquement?), et de les envoyer dans un espace mémoire non soumis au GC.
    En gros, on libère le CPU d'un travail de GC trop conséquent.

    Histoire d'aller au bout de ma ***
    wikipedia.org/wiki/Mmap

    La dépêche est intéressante, merci !
    Surtout l'introduction au false sharing, après .. bah. bref quoi, c'est le monde Java.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.