Ein Leitfaden für False Sharing und @Contended

1. Übersicht

In diesem Artikel werden wir sehen, wie manchmal falsches Teilen Multithreading gegen uns wenden kann.

Zunächst beginnen wir mit der Theorie des Caching und der räumlichen Lokalität. Anschließend schreiben wir das gleichzeitige Dienstprogramm LongAdder neu und vergleichen es mit der Implementierung von java.util.concurrent . Im gesamten Artikel werden wir die Benchmark-Ergebnisse auf verschiedenen Ebenen verwenden, um die Auswirkungen von falschem Teilen zu untersuchen.

Der Java-bezogene Teil des Artikels hängt stark vom Speicherlayout der Objekte ab. Da diese Layoutdetails nicht Teil der JVM-Spezifikation sind und im Ermessen des Implementierers liegen, konzentrieren wir uns nur auf eine bestimmte JVM-Implementierung: die HotSpot-JVM. Wir können auch die JVM- und HotSpot-JVM-Begriffe im gesamten Artikel austauschbar verwenden.

2. Cache-Zeile und Kohärenz

Prozessoren verwenden unterschiedliche Caching-Ebenen. Wenn ein Prozessor einen Wert aus dem Hauptspeicher liest, kann er diesen Wert zwischenspeichern, um die Leistung zu verbessern.

Wie sich herausstellt, zwischenspeichern die meisten modernen Prozessoren nicht nur den angeforderten Wert, sondern auch einige weitere Werte in der Nähe . Diese Optimierung basiert auf der Idee der räumlichen Lokalität und kann die Gesamtleistung von Anwendungen erheblich verbessern. Einfach ausgedrückt, arbeiten Prozessor-Caches in Form von Cache-Zeilen anstelle einzelner zwischenspeicherbarer Werte.

Wenn mehrere Prozessoren an denselben oder in der Nähe befindlichen Speicherorten arbeiten, teilen sie sich möglicherweise dieselbe Cache-Zeile . In solchen Situationen ist es wichtig, diese überlappenden Caches in verschiedenen Kernen konsistent zu halten. Das Aufrechterhalten einer solchen Konsistenz wird als Cache-Kohärenz bezeichnet.

Es gibt einige Protokolle, um die Cache-Kohärenz zwischen CPU-Kernen aufrechtzuerhalten. In diesem Artikel werden wir über das MESI-Protokoll sprechen.

2.1. Das MESI-Protokoll

Im MESI-Protokoll kann sich jede Cache-Zeile in einem dieser vier unterschiedlichen Zustände befinden: Geändert, Exklusiv, Freigegeben oder Ungültig. Das Wort MESI ist das Akronym dieser Staaten.

Um besser zu verstehen, wie dieses Protokoll funktioniert, gehen wir ein Beispiel durch. Angenommen, zwei Kerne werden aus nahe gelegenen Speicherorten lesen:

Kern A liest den Wert von a aus dem Hauptspeicher. Wie oben gezeigt, ruft dieser Kern einige weitere Werte aus dem Speicher ab und speichert sie in einer Cache-Zeile. Dann markiert es diese Cache-Zeile als exklusiv, da Kern A der einzige Kern ist, der auf dieser Cache-Zeile arbeitet . Wenn möglich, vermeidet dieser Kern von nun an den ineffizienten Speicherzugriff, indem er stattdessen aus der Cache-Zeile liest.

Nach einer Weile beschließt Kern B auch, den Wert von b aus dem Hauptspeicher zu lesen :

Da a und b so nahe beieinander liegen und sich in derselben Cache-Zeile befinden, kennzeichnen beide Kerne ihre Cache-Zeilen als gemeinsam genutzt .

Nehmen wir nun an, dass Kern A beschließt, den Wert von a zu ändern :

Der Kern A speichert diese Änderung nur in seinem Speicherpuffer und markiert seine Cache-Zeile als geändert . Außerdem teilt es diese Änderung dem Kern B mit, und dieser Kern markiert seinerseits seine Cache-Zeile als ungültig .

Auf diese Weise stellen verschiedene Prozessoren sicher, dass ihre Caches miteinander kohärent sind.

3. Falsches Teilen

Nun wollen wir sehen, was passiert, wenn Kern B beschließt, den Wert von b erneut zu lesen . Da sich dieser Wert in letzter Zeit nicht geändert hat, können wir ein schnelles Lesen aus der Cache-Zeile erwarten. Die Natur der gemeinsam genutzten Multiprozessor-Architektur macht diese Erwartung in der Realität jedoch ungültig.

Wie bereits erwähnt, wurde die gesamte Cache-Zeile zwischen den beiden Kernen geteilt. Da die Cache - Zeile für den Kern B ist ungültig jetzt, sollte es den Wert lesen b aus dem Hauptspeicher wieder :

Wie oben gezeigt, ist das Lesen des gleichen b- Werts aus dem Hauptspeicher hier nicht die einzige Ineffizienz. Dieser Speicherzugriff zwingt den Kern A , seinen Speicherpuffer zu leeren, da der Kern B den neuesten Wert erhalten muss . Nach dem Löschen und Abrufen der Werte wird auf beiden Kernen die neueste Cache-Zeilenversion angezeigt, die erneut im freigegebenen Status markiert ist :

Dies führt also zu einem Cache-Miss für einen Kern und einem frühen Puffer-Flush für einen anderen, obwohl die beiden Kerne nicht am selben Speicherort betrieben wurden . Dieses als falsches Teilen bekannte Phänomen kann die Gesamtleistung beeinträchtigen, insbesondere wenn die Rate der Cache-Fehlschläge hoch ist. Genauer gesagt, wenn diese Rate hoch ist, greifen Prozessoren ständig auf den Hauptspeicher zu, anstatt aus ihren Caches zu lesen.

4. Beispiel: Dynamisches Striping

Um zu demonstrieren, wie sich falsches Teilen auf den Durchsatz oder die Latenz von Anwendungen auswirken kann, werden wir in diesem Abschnitt schummeln. Definieren wir zwei leere Klassen:

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

Leere Klassen sind natürlich nicht so nützlich, also lasst uns eine Logik kopieren und in sie einfügen.

Für unsere Striped64- Klasse können wir alles aus der Klasse java.util.concurrent.atomic.Striped64 kopieren und in unsere Klasse einfügen. Bitte kopieren Sie auch die Importanweisungen . Wenn Sie Java 8 verwenden, sollten Sie außerdem sicherstellen, dass jeder Aufruf der sun.misc.Unsafe.getUnsafe () -Methode durch eine benutzerdefinierte Methode ersetzt wird:

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); } }

Wir können sun.misc.Unsafe.getUnsafe () nicht von unserem Application Classloader aus aufrufen , daher müssen wir mit dieser statischen Methode erneut schummeln. Ab Java 9 wird jedoch dieselbe Logik mit VarHandles implementiert , sodass wir dort nichts Besonderes tun müssen und nur ein einfaches Kopieren und Einfügen ausreichen würde.

Kopieren Sie für die LongAdder- Klasse alles aus der java.util.concurrent.atomic.LongAdder- Klasse und fügen Sie es in unsere ein. Auch hier sollten wir die Importanweisungen kopieren .

Vergleichen wir nun diese beiden Klassen miteinander: unseren benutzerdefinierten LongAdder und java.util.concurrent.atomic.LongAdder.

4.1. Benchmark

Um diese Klassen miteinander zu vergleichen, schreiben wir einen einfachen 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(); } }

Wenn wir diesen Benchmark mit zwei Gabeln und 16 Threads im Durchsatz-Benchmark-Modus ausführen (das Äquivalent zum Übergeben von " - -bm thrpt -f 2 -t 16" -Argumenten), druckt JMH diese Statistiken:

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.

Um die Sache konkreter zu machen, haben wir die LongAdder- Implementierung in Java mit ihrer Kopie verglichen und ihre Ergebnisse als Ausgangspunkt für unsere Leistungsuntersuchungen verwendet.

Außerdem haben wir das Perf- Tool verwendet, um einige Statistiken zu den Leistungsmetriken einer laufenden Anwendung unter Linux zu sammeln. Um weitere Beispiele für Perf zu sehen, wird dringend empfohlen, den Blog von Branden Greg zu lesen. Darüber hinaus kann eBPF, das ab Linux Kernel Version 4.4 verfügbar ist, auch in vielen Tracing- und Profiling-Szenarien hilfreich sein.

Wie üblich sind alle Beispiele auf GitHub verfügbar.