Un guide sur le faux partage et @Contended

1. Vue d'ensemble

Dans cet article, nous verrons comment parfois un faux partage peut retourner le multithreading contre nous.

Tout d'abord, nous allons commencer par un peu la théorie de la mise en cache et de la localité spatiale. Ensuite, nous réécrirons l'utilitaire simultané LongAdder et le comparerons à l' implémentation java.util.concurrent . Tout au long de l'article, nous utiliserons les résultats de référence à différents niveaux pour étudier l'effet du faux partage.

La partie Java de l'article dépend fortement de la disposition de la mémoire des objets. Étant donné que ces détails de mise en page ne font pas partie de la spécification JVM et sont laissés à la discrétion de l'implémenteur, nous nous concentrerons uniquement sur une implémentation JVM spécifique: la JVM HotSpot. Nous pouvons également utiliser les termes JVM et HotSpot JVM de manière interchangeable tout au long de l'article.

2. Ligne de cache et cohérence

Les processeurs utilisent différents niveaux de mise en cache - lorsqu'un processeur lit une valeur dans la mémoire principale, il peut mettre en cache cette valeur pour améliorer les performances.

En fait, la plupart des processeurs modernes mettent non seulement en cache la valeur demandée, mais également quelques valeurs supplémentaires à proximité . Cette optimisation est basée sur l'idée de localité spatiale et peut considérablement améliorer les performances globales des applications. En termes simples, les caches de processeur fonctionnent en termes de lignes de cache, au lieu de valeurs uniques pouvant être mises en cache.

Lorsque plusieurs processeurs fonctionnent sur les mêmes emplacements de mémoire ou à proximité, ils peuvent finir par partager la même ligne de cache . Dans de telles situations, il est essentiel de garder ces caches qui se chevauchent dans différents cœurs cohérents les uns avec les autres. L'action de maintenir une telle cohérence est appelée cohérence du cache.

Il existe de nombreux protocoles pour maintenir la cohérence du cache entre les cœurs de processeur. Dans cet article, nous allons parler du protocole MESI.

2.1. Le protocole MESI

Dans le protocole MESI, chaque ligne de cache peut être dans l'un de ces quatre états distincts: modifié, exclusif, partagé ou invalide. Le mot MESI est l'acronyme de ces états.

Pour mieux comprendre comment ce protocole fonctionne, parcourons un exemple. Supposons que deux cœurs vont lire à partir d'emplacements de mémoire à proximité:

Core A lit la valeur de a dans la mémoire principale. Comme indiqué ci-dessus, ce noyau récupère quelques valeurs supplémentaires de la mémoire et les stocke dans une ligne de cache. Ensuite, il marque cette ligne de cache comme exclusive puisque le noyau A est le seul noyau fonctionnant sur cette ligne de cache . À partir de maintenant, lorsque cela est possible, ce noyau évitera l'accès mémoire inefficace en lisant à la place à partir de la ligne de cache.

Après un certain temps, le noyau B décide également de lire la valeur de b depuis la mémoire principale:

Comme a et b sont si proches l'un de l'autre et résident dans la même ligne de cache, les deux cœurs marqueront leurs lignes de cache comme partagées .

Maintenant, supposons que le noyau A décide de changer la valeur de a :

Le noyau A stocke ce changement uniquement dans son tampon de stockage et marque sa ligne de cache comme modifiée . En outre, il communique ce changement au noyau B, et ce noyau marquera à son tour sa ligne de cache comme invalide .

C'est ainsi que différents processeurs s'assurent que leurs caches sont cohérents les uns avec les autres.

3. Faux partage

Voyons maintenant ce qui se passe lorsque le noyau B décide de relire la valeur de b . Comme cette valeur n'a pas changé récemment, nous pouvons nous attendre à une lecture rapide de la ligne de cache. Cependant, la nature de l'architecture multiprocesseur partagée invalide cette attente dans la réalité.

Comme mentionné précédemment, toute la ligne de cache était partagée entre les deux cœurs. Étant donné que la ligne de cache pour le noyau B n'est plus valide maintenant, il devrait lire à nouveau la valeur b de la mémoire principale :

Comme indiqué ci-dessus, la lecture de la même valeur b à partir de la mémoire principale n'est pas la seule inefficacité ici. Cet accès à la mémoire forcera le noyau A à vider son tampon de stockage, car le noyau B a besoin d'obtenir la dernière valeur . Après avoir vidé et récupéré les valeurs, les deux cœurs se retrouveront avec la dernière version de la ligne de cache étiquetée à nouveau dans l' état partagé :

So, this imposes a cache miss to one core and an early buffer flush to another one, even though the two cores weren't operating on the same memory location. This phenomenon, known as false sharing, can hurt the overall performance, especially when the rate of the cache misses is high. To be more specific, when this rate is high, processors will constantly reach out to the main memory instead of reading from their caches.

4. Example: Dynamic Striping

To demonstrate how false sharing can affect the throughput or latency of applications, we're going to cheat in this section. Let's define two empty classes:

abstract class Striped64 extends Number {} public class LongAdder extends Striped64 implements Serializable {}

Of course, empty classes aren't that useful, so let's copy-paste some logic into them.

For our Striped64 class, we can copy everything from the java.util.concurrent.atomic.Striped64 class and paste it into our class. Please make sure to copy the import statements, too. Also, if using Java 8, we should make sure to replace any call to sun.misc.Unsafe.getUnsafe() method to a custom one:

private static Unsafe getUnsafe() { try { Field field = Unsafe.class.getDeclaredField("theUnsafe"); field.setAccessible(true); return (Unsafe) field.get(null); } catch (Exception e) { throw new RuntimeException(e); } }

We can't call the sun.misc.Unsafe.getUnsafe() from our application classloader, so we have to cheat again with this static method. As of Java 9, however, the same logic is implemented using VarHandles, so we won't need to do anything special there, and just a simple copy-paste would suffice.

For the LongAdder class, let's copy everything from the java.util.concurrent.atomic.LongAdder class and paste it into ours. Again, we should copy the import statements, too.

Now, let's benchmark these two classes against each other: our custom LongAdder and java.util.concurrent.atomic.LongAdder.

4.1. Benchmark

To benchmark these classes against each other, let's write a simple JMH benchmark:

@State(Scope.Benchmark) public class FalseSharing { private java.util.concurrent.atomic.LongAdder builtin = new java.util.concurrent.atomic.LongAdder(); private LongAdder custom = new LongAdder(); @Benchmark public void builtin() { builtin.increment(); } @Benchmark public void custom() { custom.increment(); } }

If we run this benchmark with two forks and 16 threads in throughput benchmark mode (the equivalent of passing -bm thrpt -f 2 -t 16″ arguments), then JMH will print these stats:

Benchmark Mode Cnt Score Error Units FalseSharing.builtin thrpt 40 523964013.730 ± 10617539.010 ops/s FalseSharing.custom thrpt 40 112940117.197 ± 9921707.098 ops/s

The result doesn't make sense at all. The JDK built-in implementation dwarfs our copy-pasted solution by almost 360% more throughput.

Let's see the difference between latencies:

Benchmark Mode Cnt Score Error Units FalseSharing.builtin avgt 40 28.396 ± 0.357 ns/op FalseSharing.custom avgt 40 51.595 ± 0.663 ns/op

As shown above, the built-in solution also has better latency characteristics.

To better understand what's so different about these seemingly identical implementations, let's inspect some low-level performance monitoring counters.

5. Perf Events

To instrument low-level CPU events, such as cycles, stall cycles, instructions per cycle, cache loads/misses, or memory loads/stores, we can program special hardware registers on the processors.

As it turns out, tools like perf or eBPF are already using this approach to expose useful metrics. As of Linux 2.6.31, perf is the standard Linux profiler capable of exposing useful Performance Monitoring Counters or PMCs.

So, we can use perf events to see what’s going on at the CPU level when running each of these two benchmarks. For instance, if we run:

perf stat -d java -jar benchmarks.jar -f 2 -t 16 --bm thrpt custom

Perf will make JMH run the benchmarks against the copy-pasted solution and print the stats:

161657.133662 task-clock (msec) # 3.951 CPUs utilized 9321 context-switches # 0.058 K/sec 185 cpu-migrations # 0.001 K/sec 20514 page-faults # 0.127 K/sec 0 cycles # 0.000 GHz 219476182640 instructions 44787498110 branches # 277.052 M/sec 37831175 branch-misses # 0.08% of all branches 91534635176 L1-dcache-loads # 566.227 M/sec 1036004767 L1-dcache-load-misses # 1.13% of all L1-dcache hits

The L1-dcache-load-misses field represents the number of cache misses for the L1 data cache. As shown above, this solution has encountered around one billion cache misses (1,036,004,767 to be exact). If we gather the same stats for the built-in approach:

161742.243922 task-clock (msec) # 3.955 CPUs utilized 9041 context-switches # 0.056 K/sec 220 cpu-migrations # 0.001 K/sec 21678 page-faults # 0.134 K/sec 0 cycles # 0.000 GHz 692586696913 instructions 138097405127 branches # 853.812 M/sec 39010267 branch-misses # 0.03% of all branches 291832840178 L1-dcache-loads # 1804.308 M/sec 120239626 L1-dcache-load-misses # 0.04% of all L1-dcache hits

We would see that it encounters a lot fewer cache misses (120,239,626 ~ 120 million) compared to the custom approach. Therefore, the high number of cache misses might be the culprit for such a difference in performance.

Let's dig even deeper into the internal representation of LongAdder to find the actual culprit.

6. Dynamic Striping Revisited

The java.util.concurrent.atomic.LongAdder is an atomic counter implementation with high throughput. Instead of just using one counter, it's using an array of them to distribute the memory contention between them. This way, it will outperform the simple atomics such as AtomicLong in highly contended applications.

The Striped64 class is responsible for this distribution of memory contention, and this is how thisclass implements those array of counters:

@jdk.internal.vm.annotation.Contended static final class Cell { volatile long value; // omitted } transient volatile Cell[] cells;

Each Cell encapsulates the details for each counter. This implementation makes it possible for different threads to update different memory locations. Since we're using an array (that is, stripes) of states, this idea is called dynamic striping. Interestingly, Striped64 is named after this idea and the fact that it works on 64-bit data types.

Anyway, the JVM may allocate those counters near each other in the heap. That is, a few those counters will be in the same cache line. Therefore, updating one counter may invalidate the cache for nearby counters.

The key takeaway here is, the naive implementation of dynamic striping will suffer from false sharing. However, by adding enough padding around each counter, we can make sure that each of them resides on its cache line, thus preventing the false sharing:

As it turns out, the @jdk.internal.vm.annotation.Contended annotation is responsible for adding this padding.

The only question is, why didn't this annotation work in the copy-pasted implementation?

7. Meet @Contended

Java 8 introduced the sun.misc.Contended annotation (Java 9 repackaged it under the jdk.internal.vm.annotation package) to prevent false sharing.

Basically, when we annotate a field with this annotation, the HotSpot JVM will add some paddings around the annotated field. This way, it can make sure that the field resides on its own cache line. Moreover, if we annotate a whole class with this annotation, the HotSopt JVM will add the same padding before all the fields.

The @Contended annotation is meant to be used internally by the JDK itself. So by default, it doesn't affect the memory layout of non-internal objects. That's the reason why our copy-pasted adder doesn't perform as well as the built-in one.

To remove this internal-only restriction, we can use the -XX:-RestrictContended tuning flag when rerunning the benchmark:

Benchmark Mode Cnt Score Error Units FalseSharing.builtin thrpt 40 541148225.959 ± 18336783.899 ops/s FalseSharing.custom thrpt 40 546022431.969 ± 16406252.364 ops/s

As shown above, now the benchmark results are much closer, and the difference probably is just a bit of noise.

7.1. Padding Size

By default, the @Contended annotation adds 128 bytes of padding. That's mainly because the cache line size in many modern processors is around 64/128 bytes.

This value, however, is configurable through the -XX:ContendedPaddingWidth tuning flag. As of this writing, this flag only accepts values between 0 and 8192.

7.2. Disabling the @Contended

It's also possible to disable the @Contended effect via the -XX:-EnableContended tuning. This may prove to be useful when the memory is at a premium and we can afford to lose a bit (and sometimes a lot) of performance.

7.3. Use Cases

After its first release, the @Contended annotation has been used quite extensively to prevent false sharing in JDK's internal data structures. Here are a few notable examples of such implementations:

  • The Striped64 class to implement counters and accumulators with high throughput
  • The Thread class to facilitate the implementation of efficient random number generators
  • The ForkJoinPool work-stealing queue
  • The ConcurrentHashMap implementation
  • The dual data structure used in the Exchanger class

8. Conclusion

In this article, we saw how sometimes false sharing might cause counterproductive effects on the performance of multithreaded applications.

Pour rendre les choses plus concrètes, nous avons comparé l' implémentation de LongAdder en Java à sa copie et avons utilisé ses résultats comme point de départ pour nos enquêtes de performance.

De plus, nous avons utilisé l' outil perf pour recueillir des statistiques sur les métriques de performances d'une application en cours d'exécution sous Linux. Pour voir plus d'exemples de perf, il est fortement recommandé de lire le blog de Branden Greg. De plus, eBPF, disponible à partir de la version 4.4 du noyau Linux, peut également être utile dans de nombreux scénarios de traçage et de profilage.

Comme d'habitude, tous les exemples sont disponibles sur over sur GitHub.