Panduan untuk Perkongsian Palsu dan @Contended

Pengaturcaraan

1. Gambaran keseluruhan

Dalam artikel ini, kita akan melihat bagaimana kadangkala perkongsian palsu dapat mengubah multithreading terhadap kita.

Pertama, kita akan memulakan dengan sedikit teori mengenai cache dan lokaliti ruang. Kemudian kita akan menulis semula utiliti serentak LongAdder dan menanda arasnya terhadap pelaksanaan java.util.concurrent . Sepanjang artikel, kami akan menggunakan hasil penanda aras pada tahap yang berbeza untuk menyiasat kesan perkongsian palsu.

Bahagian artikel yang berkaitan dengan Java sangat bergantung pada susunan memori objek. Oleh kerana perincian susun atur ini bukan sebahagian dari spesifikasi JVM dan diserahkan kepada budi bicara pelaksana, kami hanya akan memfokuskan pada satu pelaksanaan JVM tertentu: HotSpot JVM. Kami juga boleh menggunakan istilah JVM dan HotSpot JVM secara bergantian sepanjang artikel.

2. Garis Cache dan Koherensi

Pemproses menggunakan tahap cache yang berbeza - apabila pemproses membaca nilai dari memori utama, prosesor mungkin menyimpan nilai tersebut untuk meningkatkan prestasi.

Ternyata, kebanyakan pemproses moden tidak hanya menyimpan nilai yang diminta tetapi juga menyimpan beberapa nilai berdekatan . Pengoptimuman ini berdasarkan idea lokaliti ruang dan dapat meningkatkan prestasi keseluruhan aplikasi secara signifikan. Ringkasnya, cache pemproses berfungsi dari segi garis cache, dan bukannya nilai cache tunggal.

Apabila beberapa pemproses beroperasi di lokasi memori yang sama atau berdekatan, mereka mungkin akan berkongsi baris cache yang sama . Dalam situasi seperti itu, adalah mustahak untuk memastikan cache yang bertindih dalam inti yang berlainan tetap sama. Tindakan mengekalkan konsistensi tersebut disebut koherensi cache.

Ada beberapa protokol untuk mengekalkan koherensi cache antara core CPU. Dalam artikel ini, kita akan membincangkan protokol MESI.

2.1. Protokol MESI

Dalam protokol MESI, setiap baris cache dapat berada di salah satu dari empat keadaan yang berbeza: Diubah, Eksklusif, Dikongsi, atau Tidak Sah. Perkataan MESI adalah singkatan dari keadaan ini.

Untuk lebih memahami bagaimana protokol ini berfungsi, mari kita teliti contohnya. Katakan dua inti akan dibaca dari lokasi memori yang berdekatan:

Inti A membaca nilai a dari memori utama. Seperti yang ditunjukkan di atas, inti ini memperoleh beberapa nilai lagi dari memori dan menyimpannya ke garis cache. Kemudian ia menandakan bahawa baris cache eksklusif kerana inti A adalah satu-satunya teras yang beroperasi pada baris cache ini . Mulai sekarang, jika boleh, teras ini akan mengelakkan akses memori yang tidak cekap dengan membaca dari baris cache.

Selepas beberapa ketika, teras B juga memutuskan untuk membaca nilai b dari memori utama:

Oleh kerana a dan b sangat dekat satu sama lain dan berada di baris cache yang sama, kedua-dua teras akan menandai baris cache mereka sebagai bersama .

Sekarang, mari kita andaikan bahawa teras A memutuskan untuk menukar nilai yang :

Inti A menyimpan perubahan ini hanya dalam buffer stornya dan menandakan garis cache sebagai diubah . Juga, ia menyampaikan perubahan ini kepada inti B, dan inti ini, pada gilirannya, akan menandakan garis cache sebagai tidak sah .

Itulah bagaimana pemproses yang berbeza memastikan bahawa cache mereka saling berkaitan antara satu sama lain.

3. Perkongsian Palsu

Sekarang, mari kita lihat apa yang berlaku apabila inti B memutuskan untuk membaca semula nilai b . Oleh kerana nilai ini tidak berubah baru-baru ini, kami mungkin mengharapkan pembacaan cepat dari baris cache. Walau bagaimanapun, sifat seni bina multiprosesor bersama membatalkan harapan ini dalam kenyataan.

Seperti yang telah disebutkan sebelumnya, keseluruhan baris cache dibagi antara kedua-dua teras. Sejak talian cache untuk teras B adalah tidak sah sekarang, ia perlu membaca nilai b dari memori utama lagi :

Seperti yang ditunjukkan di atas, membaca nilai b yang sama dari memori utama bukan satu-satunya ketidakcekapan di sini. Akses memori ini akan memaksa inti A untuk membuang buffer stornya, kerana inti B perlu mendapatkan nilai terkini . Setelah memerah dan mengambil nilai, kedua-dua teras akan berakhir dengan versi baris cache terbaru yang ditandai dalam keadaan bersama sekali lagi:

Jadi, ini memaksakan ketinggalan cache ke satu inti dan penyangga awal ke arah yang lain, walaupun kedua-dua teras tidak beroperasi di lokasi memori yang sama . Fenomena ini, yang dikenali sebagai perkongsian palsu, boleh menjejaskan prestasi keseluruhan, terutamanya apabila kadar kehilangan cache tinggi. Untuk lebih spesifik, apabila kadar ini tinggi, pemproses akan terus mencapai memori utama dan bukannya membaca dari cache mereka.

4. Contoh: Jalur Dinamik

Untuk menunjukkan bagaimana perkongsian palsu dapat mempengaruhi throughput atau kependaman aplikasi, kita akan menipu di bahagian ini. Mari tentukan dua kelas kosong:

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

Sudah tentu, kelas kosong tidak begitu berguna, jadi mari kita salin-tempel beberapa logik ke dalamnya.

Untuk kelas Striped64 kami , kami dapat menyalin semuanya dari kelas java.util.concurrent.atomic.Striped64 dan menampalnya ke kelas kami. Pastikan juga menyalin penyataan import . Juga, jika menggunakan Java 8, kita harus memastikan untuk mengganti kaedah panggilan ke sun.misc.Unsafe.getUnsafe () ke kaedah khusus:

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

Kami tidak dapat memanggil sun.misc.Unsafe.getUnsafe () dari pemuat kelas aplikasi kami, jadi kami harus menipu lagi dengan kaedah statik ini. Namun, pada Java 9, logik yang sama diimplementasikan menggunakan VarHandles , jadi kami tidak perlu melakukan sesuatu yang istimewa di sana, dan hanya sekadar copy-paste yang cukup.

Untuk kelas LongAdder , mari salin semuanya dari kelas java.util.concurrent.atomic.LongAdder dan tampalkannya ke kelas kami. Sekali lagi, kita juga harus menyalin penyataan import .

Sekarang, mari kita aras dua kelas ini antara satu sama lain: LongAdder dan java.util.concurrent.atomic.LongAdder khas kami .

4.1. Tanda aras

Untuk menanda aras kelas ini antara satu sama lain, mari tulis penanda aras JMH yang mudah:

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

Sekiranya kita menjalankan penanda aras ini dengan dua garpu dan 16 utas dalam mod penanda aras throughput (setara dengan melewati argumen “ - -bm thrpt -f 2 -t 16 )), maka JMH akan mencetak statistik ini:

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.

Untuk membuat perkara lebih konkrit, kami membuat penanda aras pelaksanaan LongAdder di Java berbanding salinannya dan menggunakan hasilnya sebagai titik permulaan penyelidikan prestasi kami.

Juga, kami menggunakan alat perf untuk mengumpulkan beberapa statistik mengenai metrik prestasi aplikasi yang sedang berjalan di Linux. Untuk melihat lebih banyak contoh perf, sangat disarankan untuk membaca blog Branden Greg. Lebih-lebih lagi, eBPF, tersedia dari Linux Kernel versi 4.4, juga dapat berguna dalam banyak senario penelusuran dan profil.

Seperti biasa, semua contoh boleh didapati di GitHub.