Una guida alla falsa condivisione e @Contended

1. Panoramica

In questo articolo vedremo come a volte la falsa condivisione può mettere il multithreading contro di noi.

Innanzitutto, inizieremo con un po 'di teoria sulla memorizzazione nella cache e sulla località spaziale. Quindi riscriveremo l' utilità simultanea LongAdder e la confronteremo con l' implementazione java.util.concurrent . In tutto l'articolo, utilizzeremo i risultati del benchmark a diversi livelli per indagare sugli effetti della falsa condivisione.

La parte dell'articolo relativa a Java dipende in gran parte dal layout di memoria degli oggetti. Poiché questi dettagli del layout non fanno parte della specifica JVM e sono lasciati alla discrezione dell'implementatore, ci concentreremo solo su un'implementazione JVM specifica: la JVM HotSpot. Possiamo anche utilizzare i termini JVM e HotSpot JVM in modo intercambiabile in tutto l'articolo.

2. Linea cache e coerenza

I processori utilizzano diversi livelli di memorizzazione nella cache: quando un processore legge un valore dalla memoria principale, può memorizzare nella cache tale valore per migliorare le prestazioni.

A quanto pare, la maggior parte dei processori moderni non solo memorizza nella cache il valore richiesto, ma memorizza anche alcuni valori vicini . Questa ottimizzazione si basa sull'idea di località spaziale e può migliorare significativamente le prestazioni complessive delle applicazioni. In poche parole, le cache del processore funzionano in termini di linee di cache, invece di singoli valori memorizzabili nella cache.

Quando più processori operano sulla stessa posizione di memoria o nelle vicinanze, potrebbero finire per condividere la stessa linea di cache . In tali situazioni, è essenziale mantenere quelle cache sovrapposte in core diversi coerenti tra loro. L'atto di mantenere tale coerenza è chiamato coerenza della cache.

Ci sono diversi protocolli per mantenere la coerenza della cache tra i core della CPU. In questo articolo parleremo del protocollo MESI.

2.1. Il protocollo MESI

Nel protocollo MESI, ogni riga della cache può trovarsi in uno di questi quattro stati distinti: Modificato, Esclusivo, Condiviso o Non valido. La parola MESI è l'acronimo di questi stati.

Per capire meglio come funziona questo protocollo, esaminiamo un esempio. Supponiamo che due core leggano da posizioni di memoria vicine:

Il core A legge il valore di a dalla memoria principale. Come mostrato sopra, questo core recupera alcuni valori in più dalla memoria e li memorizza in una riga della cache. Quindi contrassegna quella linea di cache come esclusiva poiché il core A è l'unico core che opera su questa linea di cache . D'ora in poi, quando possibile, questo core eviterà l'accesso inefficiente alla memoria leggendo invece dalla riga della cache.

Dopo un po ', anche il core B decide di leggere il valore di b dalla memoria principale:

Poiché un e b sono così vicini l'uno all'altro e risiedono nella stessa linea di cache, entrambi i core taggherà loro linee cache come comune .

Supponiamo ora che il core A decida di modificare il valore di a :

Il core A memorizza questa modifica solo nel suo buffer di archiviazione e contrassegna la sua linea di cache come modificata . Inoltre, comunica questa modifica al core B e questo core, a sua volta, segnerà la sua linea di cache come non valida .

È così che processori diversi si assicurano che le loro cache siano coerenti tra loro.

3. Falsa condivisione

Vediamo ora cosa succede quando il core B decide di rileggere il valore di b . Poiché questo valore non è cambiato di recente, potremmo aspettarci una lettura veloce dalla riga della cache. Tuttavia, la natura dell'architettura multiprocessore condivisa invalida questa aspettativa nella realtà.

Come accennato in precedenza, l'intera linea della cache era condivisa tra i due core. Poiché la riga della cache per il core B ora non è valida , dovrebbe leggere di nuovo il valore b dalla memoria principale :

Come mostrato sopra, leggere lo stesso valore b dalla memoria principale non è l'unica inefficienza qui. Questo accesso alla memoria costringerà il core A a svuotare il buffer di archiviazione, poiché il core B deve ottenere il valore più recente . Dopo aver scaricato e recuperato i valori, entrambi i core finiranno con l'ultima versione della linea di cache contrassegnata di nuovo nello stato condiviso :

Quindi, questo impone una mancanza di cache su un core e un primo svuotamento del buffer su un altro, anche se i due core non funzionavano nella stessa posizione di memoria . Questo fenomeno, noto come falsa condivisione, può compromettere le prestazioni complessive, soprattutto quando la percentuale di errori nella cache è elevata. Per essere più precisi, quando questa velocità è alta, i processori raggiungeranno costantemente la memoria principale invece di leggere dalle loro cache.

4. Esempio: striping dinamico

Per dimostrare come la falsa condivisione può influenzare il throughput o la latenza delle applicazioni, trucceremo in questa sezione. Definiamo due classi vuote:

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

Ovviamente, le classi vuote non sono così utili, quindi copia e incolla un po 'di logica in esse.

Per la nostra classe Striped64 , possiamo copiare tutto dalla classe java.util.concurrent.atomic.Striped64 e incollarlo nella nostra classe. Assicurati di copiare anche le istruzioni di importazione . Inoltre, se si utilizza Java 8, è necessario assicurarsi di sostituire qualsiasi chiamata al metodo sun.misc.Unsafe.getUnsafe () con una personalizzata:

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

Non possiamo chiamare sun.misc.Unsafe.getUnsafe () dal nostro programma di caricamento classi dell'applicazione, quindi dobbiamo imbrogliare di nuovo con questo metodo statico. A partire da Java 9, tuttavia, la stessa logica è implementata utilizzando VarHandles , quindi non avremo bisogno di fare nulla di speciale lì, e sarebbe sufficiente un semplice copia-incolla.

Per la classe LongAdder , copia tutto dalla classe java.util.concurrent.atomic.LongAdder e incollalo nella nostra. Di nuovo, dovremmo copiare anche le istruzioni di importazione .

Ora confrontiamo queste due classi l'una con l'altra: il nostro LongAdder personalizzato e java.util.concurrent.atomic.LongAdder.

4.1. Prova delle prestazioni

Per confrontare queste classi l'una con l'altra, scriviamo un semplice benchmark JMH:

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

Se eseguiamo questo benchmark con due fork e 16 thread in modalità benchmark throughput (l'equivalente del passaggio di argomenti " - -bm thrpt -f 2 -t 16" ), JMH stamperà queste statistiche:

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.

Per rendere le cose più concrete, abbiamo confrontato l' implementazione di LongAdder in Java con la sua copia e utilizzato i suoi risultati come punto di partenza per le nostre indagini sulle prestazioni.

Inoltre, abbiamo utilizzato lo strumento perf per raccogliere alcune statistiche sulle metriche delle prestazioni di un'applicazione in esecuzione su Linux. Per vedere altri esempi di perf, si consiglia vivamente di leggere il blog di Branden Greg. Inoltre, eBPF, disponibile a partire dalla versione 4.4 del kernel Linux, può anche essere utile in molti scenari di tracciamento e profilazione.

Come al solito, tutti gli esempi sono disponibili su GitHub.