Java中的伪共享以及应对方案

什么是伪共享

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)。当你读一个特定的内存地址，整个缓存行将从主存换入缓存，并且访问同一个缓存行内的其它值的开销是很小的。
看如下代码示例：

    int[] arr = new int[64 * 1024 * 1024];
    long start = System.nanoTime();
    for (int i = 0; i < arr.length; i++) {
        arr[i] *= 3;
    }
    System.out.println(System.nanoTime() - start);

    long start2 = System.nanoTime();
    for (int i = 0; i < arr.length; i += 16) {
        arr[i] *= 3;
    }
    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中。

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。如下图：

伪共享问题

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

Java对于伪共享的传统解决方案

package com.alibaba;

/**
 * Created by Administrator on 2016/10/13 0013.
 */
public final class FalseSharing implements Runnable {
    private final static int NUM_THREADS = 4; // change
    private final static long ITERATIONS = 500L * 1000L * 1000L;
    private final int arrayIndex;
    private static VolatileLong[] longs = new VolatileLong[NUM_THREADS];

    static {
        for (int i = 0; i < longs.length; i++) {
            longs[i] = new VolatileLong();
        }
    }

    public FalseSharing(final int arrayIndex) {
        this.arrayIndex = arrayIndex;
    }

    public static void main(final String[] args) throws Exception {
        final long start = System.nanoTime();
        runTest();
        System.out.println("duration = " + (System.nanoTime() - start));
    }

    private static void runTest() throws InterruptedException {
        Thread[] threads = new Thread[NUM_THREADS];

        for (int i = 0; i < threads.length; i++) {
            threads[i] = new Thread(new FalseSharing(i));
        }
        for (Thread t : threads) {
            t.start();
        }
        for (Thread t : threads) {
            t.join();
        }
    }

    public void run() {
        long i = ITERATIONS + 1;
        while (0 != --i) {
            longs[arrayIndex].value = i;
        }
    }

    public final static class VolatileLong {
        public volatile long value = 0L;
        public long p1, p2, p3, p4, p5, p6;
    }
}

执行结果：

duration = 9465942893

现在，我们将VolatileLong中不使用的6个long变量注释掉，再次执行：

   public final static class VolatileLong {
        public volatile long value = 0L;
        //public long p1, p2, p3, p4, p5, p6; 
    }

duration = 20362748888

可以看到，两个程序逻辑完全一致，只是注释掉了几个没有使用到的变量，却导致性能相差很大。 我们知道一条缓存行有64字节, 而Java程序的对象头固定占8字节(32位系统)或12字节(64位系统默认开启压缩, 不开压缩为16字节). 我们只需要填6个无用的长整型补上6*8=48字节, 让不同的VolatileLong对象处于不同的缓存行, 就可以避免伪共享了(64位系统超过缓存行的64字节也无所谓,只要保证不同线程不要操作同一缓存行就可以)。这个办法叫做补齐(Padding)。

Java8中的解决方案

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

运行结果：

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

duration = 8987991013

参考文献：

1：http://igoro.com/archive/gallery-of-processor-cache-effects/
2：http://ifeve.com/false-sharing/
3：http://blog.csdn.net/muxiqingyang/article/details/6615199