04.缓存行与伪共享

缓存系统中是以缓存行（Cache Line）为单位存储的，缓存行是 2 的整数幂个连续字节，一般为 32-256 个字节，最常见的缓存行大小是 64 个字节；并且它有效地引用主内存中的一块儿地址。一个 Java 的 long 类型变量是 8 字节，因此在一个缓存行中可以存 8 个 long 类型的变量。CPU 每次从主存中拉取数据时，会把相邻的数据也存入同一个缓存行。在访问一个 long 数组的时候，如果数组中的一个值被加载到缓存中，它会自动加载另外 7 个。因此你能非常快的遍历这个数组。事实上，你可以非常快速的遍历在连续内存块中分配的任意数据结构。

当多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。

若两个变量放在同一个缓存行中，在多线程情况下，可能会相互影响彼此的性能。如上图所示，CPU1 上的线程更新了变量 X，则 CPU 上的缓存行会失效，同一行的 Y 即使没有更新也会失效，导致 Cache 无法命中。同样地，若 CPU2 上的线程更新了 Y，则导致 CPU1 上的缓存行又失效。如果 CPU 经常不能命中缓存，则系统的吞吐量则会下降。这就是伪共享问题。

下面的例子是测试利用缓存行的特性和不利用缓存行的特性的效果对比。

public class CacheLineEffect {
    //考虑一般缓存行大小是64字节，一个 long 类型占8字节
    static  long[][] arr;

    public static void main(String[] args) {
        arr = new long[1024 * 1024][];
        for (int i = 0; i < 1024 * 1024; i++) {
            arr[i] = new long[8];
            for (int j = 0; j < 8; j++) {
                arr[i][j] = 0L;
            }
        }
        long sum = 0L;

        // 按行读取
        long marked = System.currentTimeMillis();
        for (int i = 0; i < 1024 * 1024; i+=1) {
            for(int j =0; j< 8;j++){
                sum = arr[i][j];
            }
        }
        System.out.println("Loop times:" + (System.currentTimeMillis() - marked) + "ms");

        // 按列读取
        marked = System.currentTimeMillis();
        for (int i = 0; i < 8; i+=1) {
            for(int j =0; j< 1024 * 1024;j++){
                sum = arr[j][i];
            }
        }
        System.out.println("Loop times:" + (System.currentTimeMillis() - marked) + "ms");
    }
}

避免伪共享

解决伪共享问题，可以在变量的前后都占据一定的填充位置，尽量让变量占用一个完整的缓存行。如上图中，CPU1 上的线程更新了 X，则 CPU2 上的 Y 则不会失效。同样地，CPU2 上的线程更新了 Y，则 CPU1 的不会失效。参考 Java 内存布局可知，所有对象都有两个字长的对象头。第一个字是由 24 位哈希码和 8 位标志位(如锁的状态或作为锁对象)组成的 Mark Word。第二个字是对象所属类的引用。如果是数组对象还需要一个额外的字来存储数组的长度。每个对象的起始地址都对齐于 8 字节以提高性能。因此当封装对象的时候为了高效率，对象字段声明的顺序会被重排序成下列基于字节大小的顺序：

doubles (8) 和 longs (8)
ints (4) 和 floats (4)
shorts (2) 和 chars (2)
booleans (1) 和 bytes (1)
references (4/8)
<子类字段重复上述顺序>

一条缓存行有 64 字节, 而 Java 程序的对象头固定占 8 字节(32 位系统)或 12 字节(64 位系统默认开启压缩, 不开压缩为 16 字节)。我们只需要填 6 个无用的长整型补上 6*8=48 字节，让不同的 VolatileLong 对象处于不同的缓存行, 就可以避免伪共享了；64 位系统超过缓存行的 64 字节也无所谓，只要保证不同线程不要操作同一缓存行就可以。这个办法叫做补齐（Padding）：

public final static class VolatileLong
{
    public volatile long value = 0L;
    public long p1, p2, p3, p4, p5, p6; // 添加该行，错开缓存行，避免伪共享
}

某些 Java 编译器会将没有使用到的补齐数据, 即示例代码中的 6 个长整型在编译时优化掉, 可以在程序中加入一些代码防止被编译优化。

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

完整的示例如下：

public class FalseSharing implements Runnable{
        public final static long ITERATIONS = 500L * 1000L * 100L;
        private int arrayIndex = 0;

        private static ValuePadding[] longs;
        public FalseSharing(final int arrayIndex) {
            this.arrayIndex = arrayIndex;
        }

        public static void main(final String[] args) throws Exception {
            for(int i=1;i<10;i++){
                System.gc();
                final long start = System.currentTimeMillis();
                runTest(i);
                System.out.println("Thread num "+i+" duration = " + (System.currentTimeMillis() - start));
            }

        }

        private static void runTest(int NUM_THREADS) throws InterruptedException {
            Thread[] threads = new Thread[NUM_THREADS];
            longs = new ValuePadding[NUM_THREADS];
            for (int i = 0; i < longs.length; i++) {
                longs[i] = new ValuePadding();
            }
            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 = 0L;
            }
        }

        public final static class ValuePadding {
            protected long p1, p2, p3, p4, p5, p6, p7;
            protected volatile long value = 0L;
            protected long p9, p10, p11, p12, p13, p14;
            protected long p15;
        }
        public final static class ValueNoPadding {
            // protected long p1, p2, p3, p4, p5, p6, p7;
            protected volatile long value = 0L;
            // protected long p9, p10, p11, p12, p13, p14, p15;
        }
}

在 2G Hz，2 核，8G 内存, jdk 1.7.0_45 的运行环境下，使用了共享机制比没有使用共享机制，速度快了 4 倍左右。

最近更新于 0001-01-01

04.缓存行与伪共享

Cache Line & False Sharing | 缓存行与伪共享

避免伪共享