OpenJDK 8, JEP 142 & False Sharing

Posté par . Édité par Davy Defaud, ZeroHeure, Florent Zara, palm123, tuiu pol et Benoît Sibaud. Modéré par ZeroHeure. Licence CC by-sa
28
2
avr.
2014
Java

Java 8 est sorti ce mois‐ci et vous avez même eu droit à une dépêche, ici‐même, qui parle des lambdas, de l’API flux (stream API), etc.

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

Pour cette première dépêche, 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.

NdM : merci à ckyl pour son journal.

Sommaire

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 processeur é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 de celle du processeur. Le pari étant qu’une fois l’accès coûteux à la mémoire centrale effectué, cette valeur va être réutilisée et on ira alors la chercher dans ce cache en gagnant énormément 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 processeur 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 processeur ou un cœur fait une modification, elle sera visible par les autres. Chaque architecture a son propre modèle de cohérence, le x86 étant, par exemple, particulièrement fort. Ce modèle est exposé dans les langages de bas niveau, mais les langages de haut niveau décrivent souvent leur propre modèle mémoire. Charge au compilateur de traduire celui du langage vers celui de la plate‐forme.

Si l’on met ces deux choses ensemble, on arrive au false sharing : deux variables théoriquement indépendantes se retrouvent sur la même ligne de cache. Chacune est lue ou modifiée par un processeur distinct, cependant les processeurs doivent passer leur temps à se synchroniser, et les performances s’écroulent.

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

Exemple

Commençons avec un banc d’essai très simple : une classe avec un seul membre et quatre fils d’exécution (threads). Le premier lit en permanence la valeur de ce membre, les trois autres ne font rien. Le banc d’essai 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) { }

Ce 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 banc d’essai. Nous ajoutons un deuxième membre qui va être accédé par les trois fils d’exécution qui ne faisaient rien. Le premier fil 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 gagner un facteur 10.

Nous pouvons vérifier l’agencement mémoire de notre objet StateBaseline avec jol, pour voir que nos deux variables ont bien été juxtaposé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’elles 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 paraît simple, mais, avant OpenJDK 8, cela demandait de très sérieusement connaître la machine virtuelle Java (ou lutter contre elle).

Fort du principe de localité, le comportement logique de la machine virtuelle Java est d’essayer d’entasser autant que possible les différents membres comme bon lui semble. La disposition (layout) d’un objet peut changer selon beaucoup de critères. Et l’utilisation d’un ramasse‐miettes n’aide pas, puisque ce dernier peut décider de déplacer un peu tout et n’importe quoi (notamment les tableaux utilisés pour les aligner). Bref, trouver une stratégie qui marche, est une source d’amusement inépuisable. Aleksey Shipilёv en a documenté quelques‐unes dans un banc d’essai 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 l’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 machine virtuelle Java (JVM). L’annotation se trouve dans un paquet privé d’Oracle, et elle n’est disponible que pour les classes du kit de développement Java (JDK) par défaut (comme beaucoup de choses que le JDK se réserve précieusement). Si l’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 l’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 l’outil qu’ils fournissent ou avec perf, mais ça reste assez empirique.

Si l’on garde le principe du false sharing en tête, cela permet de surveiller les mauvaises pratiques dans les bouts d’infrastructure qui peuvent être affectés. En général, il faut que ça commence à aller sérieusement vite, donc avec des structures de données dédiées, 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 fils d’exécution différents. Ça arrive, par exemple, quand 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éreraient chacune être dans leur 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 l’on fait travailler plusieurs fils d’exécution en parallèle.

Le dernier cas est le calcul de type matriciel avec plusieurs fils d’exécution. 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 fournit un tel exemple.

J’ai essayé de fournir quelques exemples dans le banc d’essai.

Conclusion

@Contended ne devrait pas changer la vie de grand monde, hormis celle des gens qui pondent l’infrastructure de service à haute performance. Mais, elle ouvre la porte à une revendication de longue date : marier les bénéfices de la machine virtuelle Java 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 nécessaires.

Cette annotation ne répond absolument pas au besoin de pouvoir contrôler l’agencement d’un objet ou de choisir quels membres d’un objet doivent être regroupés. Elle 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’applications qui passent en off‐the‐heap ou en mmap lorsque nécessaire.

Enfin, le false sharing n’est pas le seul problème lié aux caches, il y a d’autres exemples.
Et, bien entendu, exploiter les caches correctement a un impact certain sur les performances d’une application.

  • # Sens de la phrase rayée

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

    Le premier à me donner le sens de la phrase rayée, gagnera ma haute estime! ensuite on la corrigera!

    "La liberté est à l'homme ce que les ailes sont à l'oiseau" Jean-Pierre Rosnay

    • [^] # Re: Sens de la phrase rayée

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

      Ça ne serait pas une expression maladroite pour indiquer qu'on peut stocker des données statistiques (ex. compteur d'accès) dans un objet? Ce qui ferait une donnée souvent accédée et modifiée, liaison avec les caches, etc.

      Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

    • [^] # Re: Sens de la phrase rayée

      Posté par . Évalué à 2.

      A posteriori l'exemple que j'ai choisi n'est pas forcément le plus pertinent ni le plus facile à comprendre (et la phrase ne veut rien dire).

      Le sens initial de la phrase était quelque chose du genre: Tu as un objet en version 1 qui se fait accéder fréquemment et de manière standard. Tout va bien. En v2 tu ajoutes un champ comme un compteur d'accès, un timestamp qui va être écrit par un autre thread. Les performances en lecture des autres threads s'écroulent.

      L'exemple n'est pas forcément bien choisi car dans la réalité le false sharing ne s'observe que sur des structures sensibles et largement optimisées au préalable. Autrement il se retrouve largement noyé dans la "lenteur" générale. Un exemple réel bien plus simple est dispo .

  • # Pas sympa le 'false sharing'

    Posté par . Évalué à 2.

    J'ai entendu parler des recherches sur des algorithmes qui utilisent efficacement les caches quelque soit leur taille, mais je ne crois pas qu'ils tiennent compte du false sharing/

    Ça me rappelle une discussion sur les spinlock ( http://lwn.net/Articles/531254/ ) et leur impacts sur le comportement des caches, je m'étais demandé si ça ne vaudrait pas le coup de mettre les spinlock dans leur propre ligne de cache..

  • # JEP 145: Cache Compiled Code

    Posté par . Évalué à 1.

    Cool, merci pour la news.
    Toujours dans la section perf, est-ce que quelqu'un sait si la JEP 145: Cache Compiled Code a des chances d'être implémentée? Je n'ai pas l'impression qu'il y ait beaucoup de mouvement autour de cette JEP.

    L'idée est d'éviter le syndrome du jour de la marmotte (je parle du film, http://fr.wikipedia.org/wiki/Un_jour_sans_fin) : on repart du code compilé d'un précédent run plutôt que d'attendre la fin du warmup pour avoir de bonnes perfs.

Suivre le flux des commentaires

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