Les secrets des algorithmes à haute fréquence en Java (et autre)

GNU/Linux Magazine

n°

184

juillet 2015

Par

Prados Philippe

Algo

Tag(s)

Java

Les articles du mois dernier faisant du teasing pour révéler les secrets des algorithmes à haute fréquence, les voici enfin ! Nous illustrons nos propos à l'aide d'extrait de code de la JVM. Vous trouverez les liens vers les sources originaux pour creuser un peu plus les algorithmes si le cœur vous en dit.

Depuis plus de 15 ans, chaque nouvelle génération de la JVM Java optimise les performances des applications. Des améliorations dans la machine virtuelle elle-même, lors de la compilation à la volée ou dans l'implémentation des librairies permettent de bénéficier des dernières avancées technologiques des meilleurs chercheurs. Dans cet article nous parcourons les 14 secrets découverts dans les sources de la JVM.

1. Modèle d'algorithme à haute fréquence

Il existe différents types d'algorithmes à haute fréquence, suivant l'avancement de tous les traitements.

Les algorithmes lock-free garantissent qu'à tout moment, si un thread est bloqué, tous les autres threads, virtual cores, coresou socketscontinuent à calculer. Une routine lock-free garantit le progrès d'au moins l'un des threads. Ainsi, le débit de calcul est amélioré. Afin d'être efficace, les bases de données utilisent en interne ce type d'algorithme à différents niveaux.

Pour schématiser, un verrou classique c'est un feu rouge. Un lock-free c'est l'insertion sur une autoroute.

Les algorithmes wait-free garantissent en plus que tous les CPUs continuent de faire un travail utile. Aucun calcul n'est bloqué par un autre calcul. Une procédure wait-free peut terminer en un nombre fini d'étapes, quelles que soient les vitesses relatives des autres threads. Les garanties sont plus fortes qu'avec un algorithme lock-free. Ils garantissent un débit maximum, sans sacrifier de transaction. Le noyau Linux utilise un algorithme lock-free pour la gestion des pages de caches [1].

Notez qu'il existe des classifications [2] plus fines des algorithmes. Nous présentons les deux plus importants.

Il est très difficile de concevoir, coder, tester et déverminer ce type d'algorithmes. Les comprendre est un vrai régal pour les amateurs de beau code.

Pour rappel un node est une machine physique.

Un socket est un support pour un microprocesseur.

Un core est un processeur présent en plusieurs exemplaires dans un socket. Un virtualcoreest un artifice permettant d’exécuter simultanément plusieurs instructions indépendantes dans le même core.

Un node possède plusieurs sockets, ayant chacun généralement 2 ou 4 core, proposant 2 virtual core. Différents niveaux de caches sont partagés ou non entre les virtuals cores, les cores, les sockets avant d’atteindre la RAM.

2. Patterns pour algorithme à haute fréquence

Dans les algorithmes proposés par les meilleurs d’entre nous (Doug Lea [3], Dmitry Vyukov [4], etc), nous trouvons plusieurs astuces pour améliorer les performances. Nous vous proposons de les parcourir, avec des exemples concrets que vous utilisez sans le savoir. En suivant les différents liens, vous arriverez généralement sur du code de la librairie Java ou sur la JVM Hotspot.

2.1 Registre

Le premier secret des algorithmes à haute fréquence consiste à utiliser autant que possible les registres du processeur, et à éviter les lectures/écritures redondantes.

Un modèle comme celui-ci

1 Cell[] as=cells;

2   if (as != null )
3   {
4     …
5   }

N’est pas efficace. En effet, du point de vu du processeur, il y a trois étapes :

lecture de l'attribut cells ;
valorisation de la variable as en ligne 1 ;
ensuite, en ligne 2, lecture de la même variable as pour la comparer à null.

Cela correspond à trois instructions.

Une écriture comme la suivante est plus efficace.

1 Cell[] as;

2   if ((as = cells) != null )
3   {
4     …
5   }

En effet, il y a :

lecture de l'attribut cells ;
valorisation de la variable as ;
et immédiatement comparaison avec null, car le registre du processeur est déjà valorisé.

Cet exemple est une simplification d'un code équivalent présent dans la méthode add() de la classe LongAdder de la JVM.

// LongAdder
86 if ((as = cells) != null || !casBase(b = base, b + x)) {

87 boolean uncontended = true;

88 if (as == null || (m = as.length - 1) < 0 ||

89 (a = as[getProbe() & m]) == null ||

90 !(uncontended = a.cas(v = a.value, v + x)))

91 longAccumulate(x, null, uncontended);

92 }

93 }

On retrouve cette approche en ligne 86, 88, 89 et 90.

En théorie, les compilateurs pourraient détecter cela pour réécrire les instructions. Mais ce n’est pas toujours si simple. Il n’est pas toujours possible de le faire. Un compilateur JIT n’a pas non plus toujours les moyens d’effectuer des optimisations avancées, car il doit être rapide.

De plus, ce modèle permet de mieux contrôler l'ordre des lectures et des écritures, et donc l'impact sur les caches des processeurs. Cela garantie que les données seront visibles dans le bon ordre lors du flushdes caches.

Les processeurs X86 et x64 réordonnent les lectures par rapport aux écritures, afin d’optimiser le débit sur le bus system vers la RAM et réduire le nombre de trames à envoyer sur le bus. Comprenez bien que cela est invisible pour le thread qui manipule les données. Les impacts sont visibles dans les autres threads, et particulièrement, les autres threads sur les autres sockets. Les caches L1 et L2 sont partagés entre virtual cores. Ils sont spécifiques à chaque core. Les caches L3 sont partagés entre sockets. La mémoire virtuelle est partagée entre les sockets.

2.2 Sélection des instructions

Le deuxième secret consiste à sélectionner les instructions assembleurs les plus rapides.

Historiquement, les algorithmes de Hashtable utilisent des tableaux dont la taille est un nombre premier. En effet, il a été démontré que cela permet de réduire les risques de collisions lors de l’alimentation du dictionnaire. Pour cela, les algorithmes calculent le reste de la division entre la valeur de hash de l’objet à injecter et la taille du tableau (hash % size-1).

Comme l’opération de MODULO est trente fois moins rapide qu’un simple AND binaire, les nouveaux algorithmes fonctionnent autrement.

Les instructions sont soit câblées et peuvent être exécutée en un seul cycle horloge, soit micro-codées et demandent plusieurs cycles pour exécuter le petit bout de code correspondant.

Pour les algorithmes à haute fréquence, la taille du tableau de hash est maintenant un multiple de 2 [5].

// ConcurrentHashMap.java
692 private static final int tableSizeFor(int c) {

693 int n = c - 1;

694 n |= n >>> 1;

695 n |= n >>> 2;

696 n |= n >>> 4;

697 n |= n >>> 8;

698 n |= n >>> 16;

699 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

700 }

Un masque est appliqué à la valeur de hash pour ne prendre qu’un certain nombre de bits de poids faibles correspondant à la taille du tableau (hash & (size-1)).

Ce changement se retrouve dans tous les algorithmes à haute fréquence, et par exemple, dans l’algorithme utilisé par Java pour gérer les LondAdder [6] ou ConcurrentHashMap [7] en ligne 226.

// Striped64.java
226 if ((a = as[(n - 1) & h]) == null) {
227 if (cellsBusy == 0) { // Try to attach new Cell

Pour que cela fonctionne, il est préférable d’avoir une bonne répartition des valeurs lors du calcul du hash. Éventuellement, un algorithme complémentaire [8] est appliqué, pour améliorer la répartition des bits.

// ConcurrentHashMap.java
684 static final int spread(int h) {

685 return (h ^ (h >>> 16)) & HASH_BITS;

686 }

Certains algorithmes utilisent une transformation Jenkins [9] de la valeur de hash. Elle garantit [10] l'impact de chaque bit d'entré sur tous les bits de sortie.

// NonBlockingHashMap.java
112 private static final int hash(final Object key) {

113 int h = key.hashCode(); // The real hashCode call

114 // Spread bits to regularize both segment and index locations,

115 // using variant of single-word Wang/Jenkins hash.

116 h += (h << 15) ^ 0xffffcd7d;

117 h ^= (h >>> 10);

118 h += (h << 3);

119 h ^= (h >>> 6);

120 h += (h << 2) + (h << 14);

121 return h ^ (h >>> 16);

122 }

Ainsi, même si l’algorithme de hash de l’objet est faible, la distribution est finalement correcte.

2.3 Injection de code assembleur

Le troisième secret consiste à exploiter les instructions proposées par les processeurs pour nous aider.

Les processeurs possèdent des instructions ou des combinaisons d’instructions spécifiques aux algorithmes à haute fréquence. Comment les exploiter dans un code Java ? Comment s’assurer que le code reste portable ?

Pour proposer cela, la classe Unsafe [11] de Java propose une série de méthodes orientées assembleur. Ces méthodes reçoivent un objet (considéré comme une adresse mémoire) et un offset vers un attribut, obtenu via objectFieldOffset() [12]. Avec ces deux informations, différentes combinaisons sont proposées pour valoriser les attributs, avec ou sans invalidation des caches du processeur.

A priori, il ne semble pas efficace d’invoquer une méthode, avec son lot de construction de contexte, de sauvegardes dans la pile de l’adresse de retour, etc. En fait, le compilateur JIT de Java connaît parfaitement la classe Unsafe et ses méthodes. Lorsqu’il rencontre une de ces méthodes, il est capable de remplacer [13] l’invocation de la méthode par un code assembleur équivalent. Il applique des injections différentes suivant les processeurs et les OS [14] :

// atomic_linux_x86.inline.hpp
86 inline jint Atomic::cmpxchg(jint exchange_value, volatile jint* dest, jint compare_value) {

87 int mp = os::is_MP();

88 __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"

89 : "=a" (exchange_value)

90 : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)

91 : "cc", "memory");

92 return exchange_value;

93 }

En x86, AtomicLong.incrementAndGet() est compilé en LOCK INC, AtomicLong.getAndIncrement() est compilé en LOCK XADD, etc. Le préfixe LOCK devant une instruction assembleur permet de demander le flush des caches mémoires avant d’exécuter l’instruction.

C’est ainsi une technique efficace pour injecter du code assembleur dans une routine Java à haute fréquence. Les implémentations des classes du package java.util.concurrent utilisent abondamment cette approche.

2.4 Exploitation des caches

Les différents niveaux de cache des sockets sont d’autant plus rapides qu’ils sont proches du core. En même temps, manipuler une donnée dans une ligne de cache et la partager avec tous les coresentraîne l’envoi d’un broadcast sur le bus à tous les coreset les sockets, pour leurs demander d’invalider la même zone mémoire de leurs caches.

2.4.1 Volatile

Le quatrième secret consiste à contrôler le vidage des caches des cores.

Java et C/C++ proposent des variables volatiles. Initialement, il s’agissait de variables ne pouvant être placées dans des registres du processeur par le compilateur. Chaque modification devait avoir un impact sur la mémoire réelle, afin que les autres threads puissent en prendre connaissance.

Maintenant, les variables volatiles entraînent également qu’un message soit envoyé sur le bus présent entre les sockets, pour invalider les caches des autres. Ainsi, il y a une garantie que la donnée sera en mémoire physique (la RAM), et que tous les threads de tous les socketsen soient informés.

Cela a un impact important sur les performances. Mais dans les faits, pas autant [15] qu'on pourrait le croire.

Pour éviter l’invalidation des caches à chaque accès à ces variables, les algorithmes à haute fréquence préfèrent exploiter la classe Unsafe du JDK. Celle-ci permet d’avoir des méthodes indiquant s’il faut ou non invalider les caches. Les invocations de cette classe sont directement converties en assembleur par le compilateur Just-In-Time (JIT).

Au début de la classe [16], des offsets vers les attributs sont obtenus :

// ConcurrentHashMap.java
6287 static {

6288 try {

6289 U = sun.misc.Unsafe.getUnsafe();

6290 Class<?> k = ConcurrentHashMap.class;

6291 SIZECTL = U.objectFieldOffset

6292 (k.getDeclaredField("sizeCtl"));

6293 TRANSFERINDEX = U.objectFieldOffset

6294 (k.getDeclaredField("transferIndex"));

Ensuite, suivant les besoins [17] getObjectVolatile(obj,offset) [18] et ses variantes sont utilisées.

Par exemple, la valorisation d’une variable dans le constructeur ne nécessite pas d’invalider le cache. La classe Anticoncurrentielle utilise Unsafe pour initialiser un Node, sans flusher [19] les caches.

// ConcurrentLinkedQueue.java
188 Node(E item) {

189 UNSAFE.putObject(this, itemOffset, item);

190 }

Il est également possible d'utiliser Atomic(Int|Long|Reference).lazySet() [20] pour valoriser une donnée, sans le signaler aux autres core. La modification peut être perdue !

2.4.2 Cache-oblivious

Le cinquième secret consiste à utiliser des algorithmes naturellement copains avec tous les caches des processeurs.

Il existe des algorithmes récursifs pour distribuer [21] les traitements d’un ensemble de telle sorte que l’exploitation des caches soit optimale, et sans avoir à en connaître la taille. Ils sont conçus pour s’adapter très bien à toutes les situations, sans avoir de connaissance des spécificités des processeurs.

Les problèmes sont divisés récursivement en problèmes plus petits, puis encore plus petits et ainsi de suite. Ainsi, les différents coreset les différents socketsutilisent des zones mémoires les plus éloignées possibles lors des traitements parallèles. Les collisions sur l’accès aux mêmes zones mémoires sont réduites.

2.4.3 Une variable dans une ligne de cache de niveau 1

Le sixième secret consiste à garder une ligne de cache du node pour une seule variable.

Si deux variables atomiques A et B sont proches en mémoire, il y a un fort risque que l’écriture sur B invalide toute la zone mémoire du cache de niveau 1, et donc invalide également A. C’est ce que l’on appelle le faux-partage (false-sharing [22]). Les corespensent avoir détectés un partage des variables A ou B par plusieurs cores, alors que ce n’est pas le cas.

Puisque A et B sont éjectés du cache cela a un impact important sur les performances (de 1 à 10 [23]). Tous les efforts pour proposer un algorithme à haute fréquence peuvent être ruinés.

Pour éviter cela, il faut réussir à n’avoir qu’une seule variable dans une ligne de cache de niveau 1. Il suffit alors d’entourer A d’un certain nombre de long (correspondant à la taille du cache du processeur) et faire de même pour B. Ainsi, il y a la garantie que A et B seront dans des lignes de caches différents. C'est cette approche qu'utilise hotspot [24].

// synchronizer.cpp
452 struct SharedGlobals {

453 // These are highly shared mostly-read variables.

454 // To avoid false-sharing they need to be the sole occupants of a $ line.

455 double padPrefix [8];

456 volatile int stwRandom;

457 volatile int stwCycle;

458

459 // Hot RW variables -- Sequester to avoid false-sharing

460 double padSuffix [16];

461 volatile int hcSequence;

462 double padFinal [8];

463 } ;

Dans certains scénarios, cela permet d’avoir une variable par core. Chaque corepossède une ligne de cache différent des autres. Il n’y a plus de collision.

Pour répondre à cela dans toutes les situations, Java propose une annotation spéciale : @sun.misc.Contended. Cette annotation fait polémique à cause de son nom. Elle peut être appliquée à toute une classe ou à un attribut. Elle indique à la JVM qu’il faut ajouter suffisamment d’octets entre l’attribut et le suivant pour qu’il soit seul dans la ligne de cache. En fait, 128 bytes séparent deux variables. Cela correspond à deux fois une ligne de cache.

Dans Java 8, seules cinq classes utilisent cette annotation (Thread, Striped64, ConcurrentHashMap, Exchanger et ForkJoinPool).

Dans les sources de Java, on retrouve les deux approches : utiliser l’annotation ou ajouter des longs entres deux variables atomiques.

Des micro-benchmarks [25] montrent les gains en performance.

Utiliser cette approche est très efficace pour éviter les contentions, mais demande un surplus important de mémoire. Java utilise entre autre cette approche dans la classe LongAdder [26] qui permet l’incrémentation d’une variable par plusieurs threads, via un algorithme lock-free :

// LongAdder
120 @sun.misc.Contended static final class Cell {

121 volatile long value;

122 Cell(long x) { value = x; }

123 final boolean cas(long cmp, long val) {

124 return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);

125 }

En réalité, chaque thread possède une variable unique dans une ligne de cache. Elle est incrémentée sans devoir invalider les caches des autres cores. Lors de la lecture, toutes les variables de tous les threads rencontrés sont ajoutées pour produire la somme totale.

L’algorithme actuellement proposé n’est pas optimal en terme de CPU et de consommation mémoire. En effet, il utilise une hash-table pour gérer les variables des différents threads. Plus il y a de threads, plus il y a de lignes de cache de consommées.

Une approche basée sur le nombre de coresserait bien plus efficace. En effet, ce nombre n’évolue pas et reste de taille raisonnable.

2.4.4 Plusieurs variables dans une ligne de cache

Le septième secret consiste à co-localiser les variables devant être utilisées ensembles dans la même ligne de cache.

Les accès aléatoires à la mémoire sont fortement préjudiciables aux performances des applications.

Il est parfois judicieux de rapprocher des variables dans la même ligne de cache. Ainsi, une seule ligne est nécessaire, et les demandes d'accès à la mémoire physique sont limitées. En dehors des types primitifs, ce n'est pas facile avec Java, car les objets sont réparties dans la mémoire.

On retrouve cette approche dans la classe ConcurrentHashMap de Java. Afin d'éviter d'invoquer les objets du conteneur pour connaître leurs hashcode, la valeur est mémorisée [27] dans l'instance Node dans un attribut.

// ConcurrentHashMap.java
619 static class Node<K,V> implements Map.Entry<K,V> {

620 final int hash;

621 final K key;

622 volatile V val;

623 volatile Node<K,V> next;

Ainsi, lorsque le Node est dans un cache, toutes les informations pertinentes pour vérifier [28] si un élément est présent sont disponibles. Il n'est pas nécessaire de traverser l'élément key.

Java utilise également cette approche pour les allocations mémoires. En effet, la stratégie [29] de l'allocateur est la suivante :

Pour chaque thread, un bloc de mémoire est proposé afin d'y stocker les nouveaux objets (Thread Local Allocation Buffer – TLAB).
Les objets sont alors alloués dans ce bloc, simplement en incrémentant un compteur. Ainsi, lors de la construction d'une instance String, on retrouve l'objet String au début du bloc, immédiatement suivi du tableau de caractères. Ces deux objets sont alors dans la même ligne de cache de niveau 2 ou 3, et éventuellement dans plusieurs lignes de cache de niveau 1. Comme chaque thread utilise un bloc différent, les caches peuvent être dans des socketsou des coresdifférents. Cela ne pollue pas le bus entre les sockets, car il n’y a pas de synchronisation nécessaire.
Si le TLAB est plein, un nouveau est créé.

Plus tard, le ramasse-miettes peut déplacer les objets dans les autres espaces mémoires, en maintenant ou non la proximité des objets construits ensemble. Il profite du nettoyage pour regrouper les objets, et donc réduire la fragmentation de la mémoire. Cela réduit les besoins de cache des processeurs.

L'utilisation de pool d'instance est également une stratégie permettant d'améliorer l'utilisation des caches. Cela réduit la pression sur l'accès à la mémoire physique.

2.5 Compare-And-Set (CAS)

Lors d’un algorithme lock-free, devant accepter plusieurs écrivains sur la même case mémoire, le modèle Compare-And-Set (CAS) est généralement utilisé. Ce pattern peut être appliqué dans deux approches.

2.5.1 Boucle simple

Le huitième secret consiste à boucler sans fin pour apporter des modifications à la mémoire.

Une instruction assembleur standard ne peut être interrompue en son milieu. Elle est dite atomic.

Le modèle consiste à boucler jusqu’à l’obtention de l’écriture attendue (SpinLock [30]). Par exemple, pour obtenir un verrou, une boucle de ce type peut être pratiquée :

static AtomicBoolean semaphore=new AtomicBoolean(false) ;

void lock()

{
while ( !mutex.compareAndSet(
  false, // Valeur attendue
  true   // Valeur valorisée
  ));

}

Il s’agit d’une boucle qui attend que le sémaphore passe à false pour le passer à true et prendre le verrou.

Ce pattern évoque plusieurs questions. Il part de l’hypothèse qu’un autre thread peut valoriser le sémaphore à false à tout moment. C’est en effet possible si ce dernier est exécuté dans un autre coreet/ou un autre socket.

Mais si l’autre thread est un soft-thread, c’est-à-dire un thread simulé par l’OS, et dans le même core, il ne pourra le faire que si une interruption de la boucle est effectuée par le scheduler. Pendant la période de temps accordé au thread courant, généralement 10ms, cela ne peut arriver. La CPU est alors consommée à fond dans une boucle active sans fin pendant 10ms. Ce n’est pas optimal [31].

Les meilleures performances nécessitent que l’OS répartisse les traitements sur plusieurs coreset non sur le même.

Une approche plus tolérante consiste à essayer plusieurs cycles de la boucle, puis à forcer le scheduler à passer régulièrement.

void lock()

{
  int numberOfLoopBeforeTryWithASoftThread=40 ;
  int cnt=0 ;
  while ( !semaphore.compareAndSet(
    false, // Valeur attendue
    true // Valeur valorisée
    ))
    if (++cnt== numberOfLoopBeforeTryWithASoftThread)
    { cnt=0;
      Thread.yield(); // Force a context switch

}
}

Hotspot utilise cela [32] pour la gestion des synchronisations.

// synchronizer.cpp
495 while (obj->mark() == markOopDesc::INFLATING()) {

496 // Beware: NakedYield() is advisory and has almost no effect on some platforms

497 // so we periodically call Self->_ParkEvent->park(1).

498 // We use a mixed spin/yield/block mechanism.

499 if ((YieldThenBlock++) >= 16) {

500 Thread::current()->_ParkEvent->park(1);

501 } else {

502 os::NakedYield();

503 }

504 }

Attention, ces boucles peuvent entraîner un trafic important sur le bus de communication entre les sockets. D'autre part, avoir une succession de Thread.Yield() n'est pas non plus efficace vis-à-vis du context switch. Le code risque de passer son temps dans le kernel à changer de contexte, en espérant tomber sur le soft-thread pouvant débloquer la situation. Il existe justement un paramètre à la JVM pour éviter cet excès (‑XX:+DontYieldALot).

Une autre stratégie consiste à attendre un petit moment, puis de plus en plus, à l'aide de Thread.sleep().

Vous comprenez maintenant pourquoi il n'est pas judicieux d'avoir plus de threads que de cores. Si un algorithme à haute fréquence est utilisé - c’est le cas régulièrement dans une JVM - ajouter des threads risque d’être contre performant. C'est ce que nous préconisons pour les architectures réactives.

2.5.2 Compare-Compare-and-Set

Le neuvième secret consiste à boucler dans un premier temps avec un simple test, puis avec un CAS.

void lock()

{

for (;;)

{ while (semaphore.get()) {} ;

if (!semaphore.compareAndSet(false,true)) return ;

}

La première boucle consulte le cache local, sans envoyer d'invalidation du cache sur le bus. Le cache local est rafraîchi si un autre socketou un autre corele demande. Ensuite, un CAS est appliqué. Entre temps, le sémaphore peut avoir été pris. Si c'est le cas, on recommence.

2.5.3 Read-Modify-Write (RMW)

Le dixième secret consiste à copier une variable, puis préparer spéculativement une modification et enfin à essayer de l’écrire en mémoire (RMW [33]). En cas d’échec, il faut recommencer depuis le début.

C’est un cas qui arrive, par exemple, pour valoriser le pointeur head d’une liste chaînée.

AtomicReference <Node> head;
void insert(int x)
{
Node newNode=new Node(x);
Node currentHead;

  do
  {
    newNode.next= (currentHead=head) // Ici
  } while (!currenthead.compareAndSet(currenthead,newNode)) // Là

}

Le modèle est différent du simple CAS. Si un hard-thread ou un soft-thread intervient entre ici et là, le compareAndSet() échoue. Un autre thread a modifié head. Au prochain essai, il devrait réussir s’il n'y a pas trop de coreà vouloir modifier la même donnée.

Si rien ne se passe entre ici et là, la modification réussie du premier coup. Il n’est pas nécessaire d’injecter un Yield dans la boucle pour donner la main à un autre soft-thread. C’est pour cela qu’il n’y a pas de stratégie pour réduire la pression sur le CPU dans ce type de boucle.

2.6 Problème ABA

Le modèle Read-Modify-Write (RMW) doit résister au problème appelé ABA [34]. Il arrive lorsque la donnée A est modifiée en B, puis immédiatement en A. Une boucle de type RMW peut alors se faire avoir, car la comparaison sur la valeur A est valide. Le programme ne se rend pas compte qu’il y a eu la modification vers B avant la modification vers A.

Le cas le plus courant arrive lorsque qu’un thread d’un programme en langage C décide de supprimer la tête d’une liste chaînée et de libérer la mémoire associée. Puis, un nouveau Node est ajouté en tête. Pour cela, le programme alloue la mémoire nécessaire au nouveau Node. Cela tombe bien, l’allocateur vient justement de libérer la mémoire du Node précédant. Il donne alors la même adresse au nouveau Node. La boucle RMW n’a pas conscience que si l’adresse mémoire est identique, il ne s’agit pas du même Node.

Pour résoudre cela, il y a plusieurs approches de proposées. Cela va de l’utilisation d’un pool de Node, à l’ajout d’un octet de plus s’il est possible de rester atomique, à l’utilisation de quelques bits de l’adresse mémoire pour indiquer un numéro de version à chaque adresse.

Une chance, le langage Java n’est pas confronté à ce problème car il utilise un ramasse miette.

2.6.1 Load-Link/Store-Conditional (LL/SC)

Une approche plus radicale consiste à utiliser des instructions spécifiques [35] de certains processeurs. En effet, spécifiquement pour gérer ces situations, les processeurs Alpha [36], PowerPC [37], MIPS [38], et ARM [39] proposent des instructions spécifiques. Notez l’absence de la famille x86.

L’instruction de lecture de la mémoire (LL) signale que la zone de cache correspondante doit être traitée avec attention. Par la suite, si le cache est écrit, quelle que soit la valeur, l’instruction CAS d’écriture conditionnelle échoue. Ce n'est plus la valeur qui compte, mais la présence du cache.

Les implémentations techniques sont différentes suivant les architectures, mais l’approche du point de vue du développeur est similaire.

2.7 Conteneur immuable

Le onzième secret consiste à exploiter les approches des langages fonctionnels.

Nous avons montré les différentes techniques avancées pour optimiser au maximum les algorithmes. Une approche plus simple à comprendre et à utiliser consiste à utiliser des conteneurs immuables, comme ceux utilisés dans les langages fonctionnels. L'idée est de rendre le maximum de données immuables. On n'ajoute plus un élément dans un conteneur, on construit un autre conteneur avec toutes les données, plus une. Du point de vue du développement, c'est bien ainsi qu'il faut le comprendre. Techniquement, les structures de données sont conçues pour que le conteneur original et le conteneur cible partagent le maximum de données.

Par exemple, une simple liste chaînée peut être enrichie en ajoutant les éléments toujours en tête. Cela n'a aucun impact sur les threads parcourant la liste.

Avec ce modèle, il y a la garantie qu'il n'est pas nécessaire de poser un verrou pour parcourir le conteneur avec plusieurs threads. Les lectures peuvent être simultanées sans aucun risque.

Les différents threads peuvent consulter des versions différentes du conteneur au même moment.

Les difficultés arrivent lors de l'écriture du pointeur référençant le conteneur. En effet, ce dernier est le verrou qui défini la version à prendre en compte comme point de départ pour sa consultation. En reprenant l'exemple de la liste chaînée, le pointeur sur la tête de liste est celui qui définit le nouvel état du conteneur.

Si l'algorithme est certain de n'avoir qu'un seul thread écrivain, tout va bien. Un attribut volatile permet de montrer la modification à tous les autres threads.

Si par contre, plusieurs threads peuvent ajouter simultanément un élément dans le conteneur, il faut s'assurer que des éléments ne vont pas disparaître. Deux stratégies peuvent être utilisées :

Obtenir un verrou avec un CAS sur un boolean, ajouter un élément dans le conteneur pour en obtenir un nouveau, valoriser le pointeur vers le nouveau conteneur et enfin, relâcher le verrou. Le verrouillage est relativement long, car il intègre la création du nouveau conteneur immuable (potentiellement, cela peut invoquer un nettoyage complet de la mémoire par le GC lors du new).
Dans une boucle do / while, ajouter l’élément pour obtenir un nouveau conteneur immuable, essayer de modifier le pointeur vers le conteneur via un CAS, recommencer tout en cas d'échec. Il n'y a alors aucun verrou de posé, mais il est possible de devoir construire plusieurs fois un nouveau conteneur.

Ces deux stratégies sont pertinentes, mais dépendent de l'usage réel de l'application et de la pression exercée sur le pointeur du conteneur. Seuls des benchmarks permettront de choisir une approche plutôt qu'une autre.

Quel est l'impact de ces approches sur les caches des processeurs ? Les structures de données utilisées dans les conteneurs immuables sont conçues pour mutualiser un maximum de données. Ainsi, si un thread dans un cored'un socketest en train de parcourir le conteneur, une bonne partie des informations est présente en cache. Les nouvelles structures ajoutées ne sont utilisées que pour un seul core, tant que la référence sur le conteneur n'est pas visible des autres threads.

En résumé, les conteneurs immuables sont très bons si l'algorithme effectue essentiellement des lectures et peu d'écritures. C'est une solution simple à envisager dans cette situation. Il y a quand même une plus forte pression sur le garbage collector et sur l'allocation mémoire.

S'il existe une pression forte sur les écritures, des conteneurs lock-free seront probablement plus efficace.

2.8 Transaction en mémoire

Le douzième secret consiste à exploiter des transactions en mémoire.

Le modèle CAS peut être généralisé et simplifié via des librairies permettant des transactions en mémoire. Scala [40] ou Closure [41] proposent cette approche. Ces frameworks permettent une modification d'une structure de données sans impact sur les données consultées. Puis, lors de l'intégration des modifications dans la structure, pour que les autres threads puissent en prendre connaissance, les frameworks essayent d'apporter les modifications. C’est le commit de la transaction. En cas d'échec, les modifications sont abandonnées, la transaction est roll-backée et les modifications sont rejouées avec le nouvel état de la structure. En cas de forte contention, un délai aléatoire est ajouté avant de tenter à nouveau sa charge.

C'est une généralisation du modèle Read-Modifiy-Write.

Cette approche est efficace s'il n'y a pas trop de contention sur les structures. Si les modifications s'effectuent dans des zones différentes de la structure en mémoire, c'est une bonne idée. Sinon, les performances peuvent être inférieures à l'utilisation d'un verrou classique.

3. Affinité de threads avec les sockets

Le treizième secret consiste à exploiter des variables dédiées à chaque core et ou chaque socket.

Comme nous l'avons vu, les algorithmes à haute fréquence sont conçus pour être efficaces avec plusieurs core et/ou plusieurs sockets.

Java ne permet pas de jouer avec les affinités des threads. Il existe des librairies [42] pour cela (OpenHFT), compatibles Linux et Windows. L'extrait suivant permet d'allouer, si possible, chaque thread sur un socket différent :

private static final ExecutorService ES =
  Executors.newFixedThreadPool(
    Runtime.getRuntime().availableProcessors(),
    new AffinityThreadFactory("bg", DIFFERENT_SOCKET,DIFFERENT_CORE, ANY));

Cela peut être important pour certains algorithmes. Par exemple, l'implémentation LongAdder de Java8 utilise un identifiant par thread pour utiliser un entier par ligne de cache L1.

// Striped64.java
185 static final int getProbe() {

186 return UNSAFE.getInt(Thread.currentThread(), PROBE);

187 }

Cela est complexe et pourrait être optimisé en utilisant un entier par core. Il manque à Java la notion de variable de core et de variable de socket.

Il faut faire attention avec cette approche. Les processus et les threads sont distribués entre les processeurs. Le scheduler de l'OS est autorisé à migrer [43] un thread d'un core vers un autre. Un algorithme à haute fréquence qui récupère le numéro du core courant, n'est pas certain, en théorie, d'avoir la bonne valeur un peu plus tard.

En fait si. En effet, la migration d'un thread d'un core à un autre est un processus coûteux (perte des caches du core source, alimentation des caches du core destination), les schedulers évitent de le faire en dehors des IO, et encore, après un certain temps d’inactivité.

Donc, un algorithme qui ne fait que de la CPU peut assumer que le numéro du core n'évolue pas. Il est même possible de saturer un core alors que les autres ne font rien, avec des threads ne consommant que de la CPU ! Il est très difficile de déloger un thread s'il travaille.

Si le flag SD_WAKE_IDLE est présent, le scheduler peut chercher un processeur libre pour migrer le thread immédiatement, à la condition qu'il s'agisse d'une migration au niveau virtual core, afin de garder le bénéfice des caches.

L'algorithme de LongAdder gagnerait à bénéficier de ce modèle, afin d'éviter de multiplier les variables dans des lignes de caches. Cela simplifierait l'implémentation, car le nombre de cores est fixe. De plus, cela réduirait la consommation de lignes de cache.

3.1 Synchronize java

Le quatorzième secret consiste à utiliser synchonized avec Java. C'est maintenant rapide pour un traitement sans IO ! Si vous avez besoin de verrouiller des zones mémoires ou des objets, il est quand même possible d’utiliser en dernier ressort, les syntaxes de Java.

Avec Hotspot 8 [44], la JVM utilise des stratégies efficaces [45] pour gérer les verrous. Dans l’en-tête de chaque objet, il y a des informations pour gérer les verrous sur l’instance. On y trouve un bit pour signaler l’état de l’instance, des bits d’états et une référence sur le thread possédant le verrou. Pour être efficace et compacte, les threads sont alloués en bas de la mémoire de la JVM. Cela permet de garantir que l’adresse mémoire correspondante tient dans moins de bits qu’une adresse standard (54 or 23 bits utiles pour des JVM de respectivement 64 et 32 bit). Les détails de l’algorithme sont décrits ici : http://www.oracle.com/technetwork/java/biasedlocking-oopsla2006-wp-149958.pdf. Cela laisse des bits disponibles pour une utilisation d'un CAS (Compare-and-set).

Un verrou est posé si le thread arrive à indiquer une référence sur lui-même (valoriser les bits dédiés vers son adresse mémoire).

Pour cela, plusieurs stratégies sont utilisées. De la plus rapide à la plus lente, au fur et à mesure des échecs successifs.

La première tentative consiste à utiliser une opération de Compare-and-swap (CAS). C’est très efficace et peut être traduit en une seule instruction assembleur (e.g cmpxchg). L’idée est de demander la modification de la donnée si elle est toujours conforme à la valeur attendue. Dans la grande majorité des cas, cela fonctionne. Mais, si plusieurs cores partagent la même zone mémoire, les performances sont dégradées.

Si un autre thread est justement en train de demander la même chose, l’un des deux échoue. Plusieurs essais sont effectués. Régulièrement, la main est redonnée aux autres threads via un Thread.yield().

S’il y a une forte contention sur le verrou. Une autre stratégie est nécessaire. Le thread est endormi et mis en file d’attente via une liste chaînée lock-free.

Lors du déverrouillage, le processus regarde s’il n’y a pas un thread en attente du verrou pour lui donner la main. Cela permet de s’assurer que les threads vont se réveiller dès que possible.

L’approche par synchronize est efficace si le verrou est relâché très vite. Évitez les IO avec un verrou.

4. Des containeurs à lock-free

En cherchant un peu, on trouve facilement des implémentations de conteneurs lock-free, résultats de thèses de chercheurs. Ces derniers sont plus ou moins efficaces suivant les conditions d'usages. Certaines sont plus efficaces avec peu d'écritures et beaucoup de lectures ; sont spécialisées lors de scenarii avec un seul écrivant et beaucoup de lecteurs ; d'autres dans une situation inverse, etc.

Par exemple, le conteneur de message utilisé par le framework d'acteur AKKA [46], assume qu'il n'y a qu'un seul lecteur (l'acteur) et plusieurs écrivant (les autres acteurs). La méthode push() utilise un XCHG et une écriture et pas de boucle. La méthode pop() lit l'information et c'est tout.

Les conteneurs de Java de type Blocking* ou Concurrent* sont implémentés avec les techniques que nous avons évoquées. Les travaux continuent sur ces sujets. Par exemple, l'implémentation de ConcurrentHashMap de Java8 est une ré-implémentation complète de la version de Java7. Il y a même quelques scories pour garantir la compatibilité. L'implémentation de Java7 demandait un paramètre d'estimation du nombre de threads souhaitant simultanément un accès. Ce paramètre ne sert plus à rien pour l'implémentation de Java8.

L'implémentation actuelle sous Java8 n'a pas besoin de verrous tant qu'il n'y a pas de collision sur la valeur de hash mais continue à en utiliser si deux valeurs doivent partager le même slot du container. Des implémentations plus efficaces [47] sont disponibles.

Dans certains benchmarks [48], des implémentations sont bien plus rapides que des bases de données en RAM. Par exemple, une comparaison entre SharedHashMap de OpenHFT et Redis [49] montre les résultats suivant :

	Redis	SharedHashMap
Single threaded	~10K updates/sec	~3M updates/sec
Multi-thread	~100K update/sec	~300M updates/sec

Pourquoi l'implémentation Java est-elle plus rapide ? Les auteurs proposent plusieurs réponses :

Le code a été conçu dés le départ pour les performances, le plus léger possible.
Elle fonctionne comme un base de données interne, sans nécessiter de communication entre processus. Il n'y a pas à payer pour des communications TCP ou d'envoi de message via le kernel.
Elle a été conçue pour être utilisé dans Java, avec moins de pauses, et en tenant compte du ramasse miette.
Elle a été écrite en Java pour Java.

Voici quelques collections de conteneurs lock-free :

High-Scale-Java [50] ;
LMAXCollection [51] ;
SnapTree [52] pour un arbre balancé sans verrous ;
Concurrency Freaks [53] avec différentes améliorations de ReadWriteLock.

Ces conteneurs proposent des alternatives à java.util.* ou java.util.concurrent.*, lorsque plusieurs sockets sont utilisés.

LMAX-Exchange propose également disruptor [54], un mécanisme de communication entre threads à l'aide d'un buffer circulaire. L'algorithme s'apparente à un BlockingQueue [55], mais avec la capacité de broadcaster les événements. Cela permet de déclencher plusieurs traitements en parallèle à partir des mêmes événements. Par exemple, persister l'événement, le répliquer et le traiter.

Il peut être lock-free. Deux implémentations permettent d'avoir un ou plusieurs consommateurs.

Pour éviter les impacts des allocations mémoires, tous les événements sont pré-alloués. Les modifications sont appliquées via des call-backs thread-safe. Les performances sont foudroyantes.

5. Des bases de données en RAM

Des dizaines [56] de bases de données en mémoires sont disponibles, en Open Source ou via des produits commerciaux.

Plusieurs modèles sont proposés :

Données orientés colonnes [57], comme SAP Hana [58]. Cela permet de réduire la consommation (compression) et d’optimiser l’accès à la RAM lors des analyses (spécialisation avantageuses). Les traitements peuvent s’exécuter en parallèles sur les différentes colonnes ;
Transaction en mémoires (OLTP [59]) pour permettre une consultation versionnée des données ;
Exploitation de la RAM et des disques SSD comme XAP MemoryXtend [60] ;
Avec ou sans distributions entre nodes ;
Des calculs distribués sur tous les cœurs ;
etc.

Ces approches permettent une meilleure exploitation des cores, évitent de matérialiser les agrégations sur les données car il est rapide de les recalculer. Cela permet de simplifier les modèles.

Les bases de données NoSql orientées colonnes bénéficient également d'une meilleure exploitation des caches lors des traitements batch. Parcourir une colonne sature les lignes de caches avec des valeurs utiles.

Depuis que le bus d’adressage mémoire est suffisamment grand pour permettre de monter toutes les données chaudes du SI en RAM, des solutions sont proposées. Elles exploitent les secrets révélés dans cette série d’articles.

6. Context event processing

Les processeurs d’événements [61] fonctionnent également en mémoire. Ils ne gardent que les événements nécessaires aux corrélations à calculer (fenêtre temporelle, nombre d’événements, etc.)

Pour éviter les accès concurrents, les structures internes utilisent souvent l’approche « Object immuable ».

C’est le cas de Esper [62], SAP Hana Smart Data Streaming [63], TIPCO CEP [64], etc.

Conclusion

À tous les niveaux, nous retrouvons ces algorithmes. Par exemple, les évolutions de Linux proposent une implémentation de futex [65] utilisant des stratégies différentes si le verrou est partagé par plusieurs threads du même processus ou par plusieurs processus. Les nouveautés [66] annoncées pour Java9 vont également dans le même sens. Le projet Valhalla [67], s’il aboutit, permettra de co-localiser les conteneurs de types primitifs. Cela réduira la fragmentation et améliorera l’exploitation des caches.

Les algorithmes lock-free ne sont pas toujours plus rapide que les algorithmes classiques. Il faut s'assurer que le verrou ou les caches sont bien la cause des mauvaises performances, avant de se lancer dans un code plus complexe. Bien entendu, votre code ne doit pas être hostile [68] au JIT. Il ne faut pas oublier que le GC a un impact sur les caches. Lors d'un arret-du-monde, tous les threads, sauf le thread du GC, sont interrompu.

Vous pouvez utiliser la classe ThreadMXBean [69] pour mesurer les cycles consommés par vos algorithmes. Attention à bien chauffer la JVM pour ne pas conclure trop vite. JMH [70] va vous aider. Overseer [71] est également votre ami.

Voici quelques recommandations :

Utilisez les verrous lorsque cela est possible. Ils sont faciles à utiliser correctement.
Évitez de verrouiller trop fréquemment, afin que le sur-coût reste négligeable.
Évitez de verrouiller trop longtemps
Utilisez des algorithmes lock-free lorsque cela est approprié, mais vérifiez que la complexité justifie le gain.
N'utilisez que des algorithmes standards ayant prouvés qu'ils étaient codés correctement.
Lorsque vous utilisez un algorithme lock-free, vérifiez d'utiliser des variables volatiles et des barrières d'accès à la mémoire si nécessaire.
Sélectionnez les algorithmes adaptés à votre usage.

Nous avons partagé des secrets bien gardé, permettant de revoir vos algorithmes profondément si le besoin se fait sentir. Vous n'aurez probablement jamais besoin d'en écrire. Une simple utilisation de conteneur lock-free est généralement suffisante.

Vous comprenez maintenant pourquoi il est préférable, dans un hyperviseur, d’allouer les cores d’un même socket à une VM et de ne pas surcharger les cores avec plusieurs vCpu... Cela a un impact certain sur les performances.

Dorénavant, pensez bien aux impacts de votre code sur les performances. Réfléchissez aux impacts sur les différents niveaux de caches. Parfois, quelques lignes de code de plus permettent des gains important.

Si vous travaillez pour des applications à haute fréquence (salles de marchés, flux d'informations, etc.) vous pouvez envisager d'appliquer ces techniques. Les blogs [72-76] pourront alors vous être utiles.