Java伪共享问题及最简单的解决方案

作者:一颗奔腾的心

2018-12-07 14:11:09

什么是伪共享

CPU缓存系统中是以缓存行(cache line)为单位存储的。目前主流的CPU Cache的Cache Line大小都是64Bytes。在多线程情况下,如果需要修改“共享同一个缓存行的变量”,就会无意中影响彼此的性能,这就是伪共享(False Sharing)。

CPU的三级缓存

由于CPU的速度远远大于内存速度,所以CPU设计者们就给CPU加上了缓存(CPU Cache)。 以免运算被内存速度拖累。(就像我们写代码把共享数据做Cache不想被DB存取速度拖累一样),CPU Cache分成了三个级别:L1,L2,L3。级别越小越接近CPU, 所以速度也更快, 同时也代表着容量越小。
CPU获取数据回依次从L1,L2,L3中查找,如果都找不到则会直接向内存查找。

缓存行

由于共享变量在CPU缓存中的存储是以缓存行为单位,一个缓存行可以存储多个变量(存满当前缓存行的字节数);而CPU对缓存的修改又是以缓存行为最小单位的,那么就会出现上诉的伪共享问题。

Cache Line可以简单的理解为CPU Cache中的最小缓存单位,今天的CPU不再是按字节访问内存,而是以64字节为单位的块(chunk)拿取,称为一个缓存行(cache line)。当你读一个特定的内存地址,整个缓存行将从主存换入缓存,并且访问同一个缓存行内的其它值的开销是很小的。
看如下代码示例:

  1. int[] arr = new int[64 * 1024 * 1024];
  2. long start = System.nanoTime();
  3. for (int i = 0; i < arr.length; i++) {
  4. arr[i] *= 3;
  5. }
  6. System.out.println(System.nanoTime() - start);
  7. long start2 = System.nanoTime();
  8. for (int i = 0; i < arr.length; i += 16) {
  9. arr[i] *= 3;
  10. }
  11. System.out.println(System.nanoTime() - start2);

表面上看,第二个循环工作量为第一个循环的1/16;但是执行时间是相差不大的,假设在内存规整的情况下,每16个int 占用4*16=64字节,正好一个缓存行,也就是说这两个循环访问内存的次数是一致的。导致耗时相差不大。

缓存关联性

目前常用的缓存设计是N路组关联(N-Way Set Associative Cache),他的原理是把一个缓存按照N个Cache Line作为一组(Set),缓存按组划为等分。每个内存块能够被映射到相对应的set中的任意一个缓存行中。比如一个16路缓存,16个Cache Line作为一个Set,每个内存块能够被映射到相对应的Set
中的16个CacheLine中的任意一个。一般地,具有一定相同低bit位地址的内存块将共享同一个Set。
下图为一个2-Way的Cache。由图中可以看到Main Memory中的Index0,2,4都映射在Way0的不同CacheLine中,Index1,3,5都映射在Way1的不同CacheLine中。
image.png

MESI协议

多核CPU都有自己的专有缓存(一般为L1,L2),以及同一个CPU插槽之间的核共享的缓存(一般为L3)。不同核心的CPU缓存中难免会加载同样的数据,那么如何保证数据的一致性呢,就是MESI协议了。
在MESI协议中,每个Cache line有4个状态,可用2个bit表示,它们分别是:
M(Modified):这行数据有效,数据被修改了,和内存中的数据不一致,数据只存在于本Cache中;
E(Exclusive):这行数据有效,数据和内存中的数据一致,数据只存在于本Cache中;
S(Shared):这行数据有效,数据和内存中的数据一致,数据存在于很多Cache中;
I(Invalid):这行数据无效。

那么,假设有一个变量i=3(应该是包括变量i的缓存块,块大小为缓存行大小);已经加载到多核(a,b,c)的缓存中,此时该缓存行的状态为S;此时其中的一个核a改变了变量i的值,那么在核a中的当前缓存行的状态将变为M,b,c核中的当前缓存行状态将变为I。如下图:
image.png

伪共享问题

那么为什么会出现伪共享问题呢?上诉的情况再扩展一下,假设在多线程情况下,x,y两个共享变量在同一个缓存行中,核a修改变量x,会导致核b,核c中的x变量和y变量同时失效。
此时对于在核a上运行的线程,仅仅只是修改了了变量x,却导致同一个缓存行中的所有变量都无效,需要重新刷缓存(并不一定代表每次都要从内存中重新载入,也有可能是从其他Cache中导入数据,具体的实现要看各个芯片厂商的实现了)。
假设此时在核b上运行的线程,正好想要修改变量Y,那么就会出现相互竞争,相互失效的情况,这就是伪共享啦。

有张 Disruptor 项目的经典示例图,如下:

image.png
上图中,一个运行在处理器 core1上的线程想要更新变量 X 的值,同时另外一个运行在处理器 core2 上的线程想要更新变量 Y 的值。但是,这两个频繁改动的变量都处于同一条缓存行。两个线程就会轮番发送 RFO 消息,占得此缓存行的拥有权。当 core1 取得了拥有权开始更新 X,则 core2 对应的缓存行需要设为 I 状态。当 core2 取得了拥有权开始更新 Y,则 core1 对应的缓存行需要设为 I 状态(失效态)。轮番夺取拥有权不但带来大量的 RFO 消息,而且如果某个线程需要读此行数据时,L1 和 L2 缓存上都是失效数据,只有 L3 缓存上是同步好的数据。从前一篇我们知道,读 L3 的数据非常影响性能。更坏的情况是跨槽读取,L3 都要 miss,只能从内存上加载。

表面上 X 和 Y 都是被独立线程操作的,而且两操作之间也没有任何关系。只不过它们共享了一个缓存行,但所有竞争冲突都是来源于共享。

遭遇伪共享

接下来我们就用 code 来进行实验和佐证。

  1. public class FalseShareTest implements Runnable {
  2. public static int NUM_THREADS = 4;
  3. public final static long ITERATIONS = 500L * 1000L * 1000L;
  4. private final int arrayIndex;
  5. private static VolatileLong[] longs;
  6. public static long SUM_TIME = 0l;
  7. public FalseShareTest(final int arrayIndex) {
  8. this.arrayIndex = arrayIndex;
  9. }
  10. public static void main(final String[] args) throws Exception {
  11. Thread.sleep(10000);
  12. for(int j=0; j<10; j++){
  13. System.out.println(j);
  14. if (args.length == 1) {
  15. NUM_THREADS = Integer.parseInt(args[0]);
  16. }
  17. longs = new VolatileLong[NUM_THREADS];
  18. for (int i = 0; i < longs.length; i++) {
  19. longs[i] = new VolatileLong();
  20. }
  21. final long start = System.nanoTime();
  22. runTest();
  23. final long end = System.nanoTime();
  24. SUM_TIME += end - start;
  25. }
  26. System.out.println("平均耗时:"+SUM_TIME/10);
  27. }
  28. private static void runTest() throws InterruptedException {
  29. Thread[] threads = new Thread[NUM_THREADS];
  30. for (int i = 0; i < threads.length; i++) {
  31. threads[i] = new Thread(new FalseShareTest(i));
  32. }
  33. for (Thread t : threads) {
  34. t.start();
  35. }
  36. for (Thread t : threads) {
  37. t.join();
  38. }
  39. }
  40. public void run() {
  41. long i = ITERATIONS + 1;
  42. while (0 != --i) {
  43. longs[arrayIndex].value = i;
  44. }
  45. }
  46. public final static class VolatileLong {
  47. public volatile long value = 0L;
  48. public long p1, p2, p3, p4, p5, p6; //屏蔽此行
  49. }
  50. }

上述代码的逻辑很简单,就是四个线程修改一数组不同元素的内容。元素的类型是 VolatileLong,只有一个长整型成员 value 和 6 个没用到的长整型成员。value 设为 volatile 是为了让 value 的修改对所有线程都可见。程序分两种情况执行,第一种情况为不屏蔽倒数第三行(见”屏蔽此行”字样),第二种情况为屏蔽倒数第三行。为了”保证”数据的相对可靠性,程序取 10 次执行的平均时间。执行情况如下(执行环境:32位 windows,四核,8GB 内存):
image.pngimage.png

两个逻辑一模一样的程序,前者的耗时大概是后者的 2.5 倍,这太不可思议了!那么这个时候,我们再用伪共享(False Sharing)的理论来分析一下。前者 longs 数组的 4 个元素,由于 VolatileLong 只有 1 个长整型成员,所以整个数组都将被加载至同一缓存行,但有4个线程同时操作这条缓存行,于是伪共享就悄悄地发生了。

基于此,我们有理由相信,在一定线程数量范围内(注意思考:为什么强调是一定线程数量范围内),随着线程数量的增加,伪共享发生的频率也越大,直观体现就是执行时间越长。为了证实这个观点,本人在同样的机器上分别用单线程、2、4、8个线程,对有填充和无填充两种情况进行测试。执行场景是取 10 次执行的平均时间,结果如下所示:
image.png

如何避免伪共享?

其中一个解决思路,就是让不同线程操作的对象处于不同的缓存行即可。

那么该如何做到呢?其实在我们注释的那行代码中就有答案,那就是缓存行填充(Padding) 。现在分析上面的例子,我们知道一条缓存行有 64 字节,而 Java 程序的对象头固定占 8 字节(32位系统)或 12 字节( 64 位系统默认开启压缩, 不开压缩为 16 字节),所以我们只需要填 6 个无用的长整型补上6*8=48字节,让不同的 VolatileLong 对象处于不同的缓存行,就避免了伪共享( 64 位系统超过缓存行的 64 字节也无所谓,只要保证不同线程不操作同一缓存行就可以)。

伪共享在多核编程中很容易发生,而且非常隐蔽。例如,在 JDK 的 LinkedBlockingQueue 中,存在指向队列头的引用 head 和指向队列尾的引用 tail 。而这种队列经常在异步编程中使有,这两个引用的值经常的被不同的线程修改,但它们却很可能在同一个缓存行,于是就产生了伪共享。线程越多,核越多,对性能产生的负面效果就越大。

由于某些 Java 编译器的优化策略,那些没有使用到的补齐数据可能会在编译期间被优化掉,我们可以在程序中加入一些代码防止被编译优化。如下:

  1. public static long preventFromOptimization(VolatileLong v) {
  2. return v.p1 + v.p2 + v.p3 + v.p4 + v.p5 + v.p6;
  3. }

另外一种技术是使用编译指示,来强制使每一个变量对齐。

下面的代码显式了编译器使用__declspec( align(n) ) 此处 n=64,按照 cache line 边界对齐。

  1. __declspec (align(64)) int thread1_global_variable;
  2. __declspec (align(64)) int thread2_global_variable;

当使用数组时,在 cache line 尾部填充 padding 来保证数据元素在 cache line 边界开始。如果不能够保证数组按照 cache line 边界对齐,填充数据结构【数组元素】使之是 cache line 大小的两倍。下面的代码显式了填充数据结构使之按照 cache line 对齐。并且通过 __declspec( align(n) ) 语句来保证数组也是对齐的。如果数组是动态分配的,你可以增加分配的大小,并调整指针来对其到 cache line 边界。

  1. struct ThreadParams
  2. {
  3. // For the following 4 variables: 4*4 = 16 bytes
  4. unsigned long thread_id;
  5. unsigned long v; // Frequent read/write access variable
  6. unsigned long start;
  7. unsigned long end;
  8. // expand to 64 bytes to avoid false-sharing
  9. // (4 unsigned long variables + 12 padding)*4 = 64
  10. int padding[12];
  11. };

Java8中的解决方案
Java8中已经提供了官方的解决方案,Java8中新增了一个注解:@sun.misc.Contended。加上这个注解的类会自动补齐缓存行,需要注意的是此注解默认是无效的,需要在jvm启动时设置-XX:-RestrictContended才会生效。

  1. @sun.misc.Contended
  2. public final static class VolatileLong {
  3. public volatile long value = 0L;
  4. //public long p1, p2, p3, p4, p5, p6;
  5. }

对于伪共享,我们在实际开发中该怎么做?

通过上面大篇幅的介绍,我们已经知道伪共享的对程序的影响。那么,在实际的生产开发过程中,我们一定要通过缓存行填充去解决掉潜在的伪共享问题吗?

其实并不一定。

首先就是多次强调的,伪共享是很隐蔽的,我们暂时无法从系统层面上通过工具来探测伪共享事件。其次,不同类型的计算机具有不同的微架构(如 32 位系统和 64 位系统的 java 对象所占自己数就不一样),如果设计到跨平台的设计,那就更难以把握了,一个确切的填充方案只适用于一个特定的操作系统。还有,缓存的资源是有限的,如果填充会浪费珍贵的 cache 资源,并不适合大范围应用。最后,目前主流的 Intel 微架构 CPU 的 L1 缓存,已能够达到 80% 以上的命中率。

综上所述,并不是每个系统都适合花大量精力去解决潜在的伪共享问题。

关注公众号,每天精彩内容,第一时间送达!

×
  • 用户登录
  • 注册新用户