Cpu-Cache和伪共享

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
本文字数： 33k | 阅读时长 ≈ 30 分钟

Cpu-Cache和伪共享

下图是计算机的基本结构。L1、L2、L3分别表示一级缓存、二级缓存、三级缓存，越靠近CPU的缓存，速度越快，容量也越小。所以L1缓存很小但很快，并且紧靠着在使用它的CPU内核；L2大一些，也慢一些，并且仍然只能被一个单独的CPU核使用；L3更大、更慢，并且被单个插槽上的所有CPU核共享；最后是主存，由全部插槽上的所有CPU核共享。

computer

当CPU执行运算的时候，它先去L1查找所需的数据、再去L2、然后是L3，如果最后这些缓存中都没有，所需的数据就要去主内存拿。走得越远，运算耗费的时间就越长。所以如果你在做一些很频繁的事，你要尽量确保数据在L1缓存中。

下面是从CPU访问不同层级数据的时间概念:

从CPU到 大约需要的CPU周期 大约需要的时间
主存 约60-80ns
QPI 总线传输(between sockets, not drawn) 约20ns
L3 cache 约40-45 cycles 约15ns
L2 cache 约10 cycles 约3ns
L1 cache 约3-4 cycles 约1ns
寄存器 1 cycle

可见CPU读取主存中的数据会比从L1中读取慢了近2个数量级。

Cache Line 缓存行

缓存系统中是以缓存行（cache line）为单位存储的。缓存行是2的整数幂个连续字节，一般为32-256个字节。最常见的缓存行大小是64个字节。CPU每次从主存中拉取数据时，会把相邻的数据也存入同一个cache line。

一个Java的long类型变量是8字节，因此在一个缓存行中可以存8个long类型的变量。在访问一个long数组的时候，如果数组中的一个值被加载到缓存中，它会自动加载另外7个。因此你能非常快的遍历这个数组。事实上，你可以非常快速的遍历在连续内存块中分配的任意数据结构。

Cache 映射

cache的容量要远远小于主存，主存和cache肯定不是一一映射的，那么它们的映射关系是怎样的？

Cache分为3类：Fully Associative、Direct Mapped、N-Way Set Associative。

Fully Associative是全关联的意思，每个内存块能够被映射到任意一个缓存槽。操作效果上相当于一个散列表。如果在一个Cache集内，任何一个地址的数据都可以缓存在任何一个Cache Line里，那么我们称这个Cache是Fully Associative。给一个内存地址，要知道他是否存在于Cache中，就需要遍历所有Cache Line并比较缓存内容的地址。而Cache的本意就是为了在尽可能少得CPU Cycle内取到数据。那么想要设计一个快速的Fully Associative的Cache几乎是不可能的。

Direct Mapped给定一个内存地址，就唯一确定了一条Cache Line，每个内存块只能映射到一个特定的缓存槽。以4GB内存空间，128KB L2 Cache，64B Cache Line，那么4GB/(128KB/64B)=2MB共用一条Cache Line，这种模式下每条Cache Line的使用率如果要做到接近100%，就需要操作系统对于内存的分配和访问在地址上也是近乎平均的。而与我们的意愿相反，为了减少内存碎片和实现便捷，操作系统更多的是连续集中的使用内存。这样会出现的情况就是0-1000号这样的低编号Cache Line由于内存经常被分配并使用，而16000号以上的Cache Line由于内存鲜有进程访问，几乎一直处于空闲状态。这种情况下，本来就宝贵的二级CPU缓存，使用率也许50%都无法达到。

N-Way Set Associative缓存的原理是把一个缓存按照N个Cache Line作为一组（set），缓存按组划为等分，每个内存块能够被映射到N路特定缓存槽中的任意一路。这样一个64位系统的内存地址在4MB二级缓存中就划成了三个部分，低位6个bit表示在Cache Line中的偏移量，中间12bit表示Cache组号（set index），剩余的高位46bit就是内存地址的唯一id。2^18(256K)*16(way)=4M这样的设计相较前两种设计有以下两点好处：

  • 给定一个内存地址可以唯一对应一个set，对于set中只需遍历16个元素就可以确定对象是否在缓存中。
  • 每2^18(256K)*16(way)=4M的连续热点数据才会导致一个set内的conflict（Direct Mapped中512K的连续热点数据就会出现conflict）。

cpu_cache_direct_mapping

为什么N-Way Set Associative的Set段是从低位而不是高位开始的？

由于内存的访问通常是大片连续的，或者是因为在同一程序中而导致地址接近的（即这些内存地址的高位都是一样的）。所以如果把内存地址的高位作为set index的话，那么短时间的大量内存访问都会因为set index相同而落在同一个set index中，从而导致cache conflicts使得L2, L3 Cache的命中率低下，影响程序的整体执行效率。

直接映射缓存会引发冲突——当多个值竞争同一个缓存槽，它们将相互驱逐对方，导致命中率暴跌。另一方面，完全关联缓存过于复杂，并且硬件实现上昂贵。N路组关联是处理器缓存的典型方案，它在电路实现简化和高命中率之间取得了良好的折中。

cache 结构

假设内存容量为M，内存地址为m位：那么寻址范围为000…00~FFF…F(m位)

倘若把内存地址分为以下三个区间：

memory

Cache的逻辑结构:

cache_struct

1
2
B = 2^b
S = 2^s

一个cache被分为S个组，每个组有E个cacheline，而一个cacheline中，有B个存储单元，现代处理器中，这个存储单元一般是以字节(通常8个位)为单位的，也是最小的寻址单元。因此，在一个内存地址中，中间的s位决定了该单元被映射到哪一组，而最低的b位决定了该单元在cacheline中的偏移量。valid通常是一位，代表该cacheline是否是有效的(当该cacheline不存在内存映射时，当然是无效的)。tag就是内存地址的高t位，因为可能会有多个内存地址映射到同一个cacheline中，所以该位是用来校验该cacheline是否是CPU要访问的内存单元。

当tag和valid校验成功是，我们称为cache命中，这时只要将cache中的单元取出，放入CPU寄存器中即可。

当tag或valid校验失败的时候，就说明要访问的内存单元(也可能是连续的一些单元，如int占4个字节，double占8个字节)并不在cache中，这时就需要去内存中取了，这就是cache不命中的情况(cache miss)。当不命中的情况发生时，系统就会从内存中取得该单元，将其装入cache中，与此同时也放入CPU寄存器中，等待下一步处理。注意，以下这一点对理解linux cache机制非常重要：

当从内存中取单元到cache中时，会一次取一个cacheline大小的内存区域到cache中，然后存进相应的cacheline中。

  • 当E=1时， 每组只有一个cacheline。那么相隔2^(s+b)个单元的2个内存单元，会被映射到同一个cacheline中。

  • 当1<E<C/B时，每组有E个cacheline，不同的地址，只要中间s位相同，那么就会被映射到同一组中，同一组中被映射到哪个cacheline中是依赖于替换算法的。

  • 当E=C/B，此时S=1，每个内存单元都能映射到任意的cacheline。带有这样cache的处理器几乎没有，因为这种映射机制需要昂贵复杂的硬件来支持。

测试Cache Miss

下面的代码引用自http://coderplay.iteye.com/blog/1485760

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class L1CacheMiss {
    private static final int RUNS = 10;
    private static final int DIMENSION_1 = 1024 * 1024;
    private static final int DIMENSION_2 = 62;
    private static long[][] longs;
    public static void main(String[] args) throws Exception {
        longs = new long[DIMENSION_1][];
        for (int i = 0; i < DIMENSION_1; i++) {
            longs[i] = new long[DIMENSION_2];
        }
        System.out.println("starting....");
        final long start = System.nanoTime();
        long sum = 0L;
        for (int r = 0; r < RUNS; r++) {
            // 1. slow
            for (int j = 0; j < DIMENSION_2; j++) {
                for (int i = 0; i < DIMENSION_1; i++) {
                    sum += longs[i][j];
                }
            }

            // 2. fast
//            for (int i = 0; i < DIMENSION_1; i++) {
//                for (int j = 0; j < DIMENSION_2; j++) {
//                    sum += longs[i][j];
//                }
//            }
        }
        System.out.println("duration = " + (System.nanoTime() - start));
    }
}
// slow
// starting....
// duration = 11883939677

// fast
// starting....
// duration = 888085368

这里定义了一个二维数组，第一维长度是1024*1024，第二维长度是62，这里遍历二维数组。由于二维数组中每一个数组对象的长度是62，那么可以知道，long类型的数组对象头的大小是16字节（这里默认开启了指针压缩），每个long类型的数据大小是8字节，那么一个long类型的数组大小为16+8*62=512字节。

第一种情况，因为二维数组中的每一个数组对象占用的内存大小是512字节，而缓存行的大小是64字节，那么使用第一种遍历方式，假设当前遍历的数据是longs[i][j]，那么下一个遍历的数据是longs[i+1][j]，也就是说遍历的不是同一个数组对象，那么这两次遍历的数据肯定不在同一个缓存行内，也就是产生了Cache Miss；

在第二种情况中，假设当前遍历的数据是longs[i][j]，那么下一个遍历的数据是longs[i][j+1]，遍历的是同一个数组对象，所以当前的数据和下一个要遍历的数据可能都是在同一个缓存行中，这样发生Cache Miss的情况就大大减少了。

MESI协议及RFO请求

典型的CPU微架构有3级缓存, 每个核都有自己私有的L1, L2缓存. 那么多线程编程时, 另外一个核的线程想要访问当前核内L1, L2 缓存行的数据, 该怎么办呢? 如果第2个核需要这份数据, 由第1个核直接把数据内容发过去, 数据只需要传一次. 但是前者怎么判断后者的缓存行已经被弄脏(写)了呢?

MESI协议

MESI

M,E,S和I代表使用MESI协议时缓存行所处的四个状态:

  • M(修改, Modified): 本地处理器已经修改缓存行, 即是脏行, 它的内容与内存中的内容不一样. 并且此cache只有本地一个拷贝(专有).
  • E(专有, Exclusive): 缓存行内容和内存中的一样, 而且其它处理器都没有这行数据
  • S(共享, Shared): 缓存行内容和内存中的一样, 有可能其它处理器也存在此缓存行的拷贝
  • I(无效, Invalid): 缓存行失效, 不能使用

状态迁移说明

初始时, 缓存行没有加载任何数据, 所以它处于I状态.

本地写(Local Write)

  • 如果本地处理器写数据至处于I状态的缓存行, 则缓存行的状态变成M.

本地读(Local Read)

  • 如果本地处理器读取处于I状态的缓存行, 很明显此缓存没有数据给它. 此时分两种情况:
    • 其它处理器的缓存里也没有此行数据, 则从内存加载数据到此缓存行后, 再将它设成E状态, 表示只有我一家有这条数据, 其它处理器都没有
    • 其它处理器的缓存有此行数据, 则将此缓存行的状态设为S状态.
  • 如果处于M状态的缓存行, 再由本地处理器写入/读出, 状态是不会改变的.

远程读(Remote Read)

  • 假设我们有两个处理器c1和c2. 如果c2需要读另外一个处理器c1的缓存行内容, c1需要把它缓存行的内容通过内存控制器(Memory Controller)发送给c2, c2接到后将相应的缓存行状态设为S. 在设置之前, 内存也得从总线上得到这份数据并保存.

远程写(Remote Write)

  • 其实确切地说不是远程写, 而是c2得到c1的数据后, 不是为了读, 而是为了写. 也算是本地写, 只是c1也拥有这份数据的拷贝, 这该怎么办呢? c2将发出一个RFO(Request For Owner)请求, 它需要拥有这行数据的权限, 其它处理器的相应缓存行设为I, 除了它自已, 谁不能动这行数据. 这保证了数据的安全, 同时处理RFO请求以及设置I的过程将给写操作带来很大的性能消耗.

MSEI状态迁移

伪共享

我们从上节知道, 写操作的代价很高, 特别当需要发送RFO消息时. 我们编写程序时, 什么时候会发生RFO请求呢? 有以下两种:

  1. 线程的工作从一个处理器移到另一个处理器, 它操作的所有缓存行都需要移到新的处理器上. 此后如果再写缓存行, 则此缓存行在不同核上有多个拷贝, 需要发送RFO请求了.
  2. 两个不同的处理器确实都需要操作相同的缓存行

在Java程序中,数组的成员在缓存中也是连续的. 其实从Java对象的相邻成员变量也会加载到同一缓存行中. 如果多个线程操作不同的成员变量, 但是相同的缓存行, 伪共享(False Sharing)问题就发生了.

FalseSharing

在核心1上运行的线程想更新变量X，同时核心2上的线程想要更新变量Y。不幸的是，这两个变量在同一个缓存行中。每个线程都要去 竞争缓存行的所有权来更新变量。如果核心1获得了所有权，缓存子系统将会使核心2中对应的缓存行失效。当核心2获得了所有权然后执行更新操作，核心1就要 使自己对应的缓存行失效。这会来来回回的经过L3缓存，大大影响了性能。如果互相竞争的核心位于不同的插槽，就要额外横跨插槽连接，问题可能更加严重。

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

如何避免伪共享

假设有一个类中，只有一个long类型的变量：

1
2
3
public final static class VolatileLong {
    public volatile long value = 0L;
}

这时定义一个VolatileLong类型的数组，然后让多个线程同时并发访问这个数组，这时可以想到，在多个线程同时处理数据时，数组中的多个VolatileLong对象可能存在同一个缓存行中，通过上文可知，这种情况就是伪共享。

怎么样避免呢？在Java 7之前，可以在属性的前后进行padding，例如：

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

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

这里有一个问题：在马丁的博客有提到中Java7优化了无用字段，会使这种形式的补位无效，需要采用暴露补位属性的方法来避免优化，但在我的测试里，这种形式是有效的。

而在Java 8中，提供了@sun.misc.Contended注解来避免伪共享，原理是在使用此注解的对象或字段的前后各增加128字节大小的padding，使用2倍于大多数硬件缓存行的大小来避免相邻扇区预取导致的伪共享冲突。

  • 会议ppt
  • 官方邮件

注意，执行时，必须加上虚拟机参数-XX:-RestrictContended，@Contended注释才会生效。

下面看下测试代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.concurrent.atomic.AtomicLong;

public class FalseSharing implements Runnable {
    public final static int NUM_THREADS = 4; // change
    public final static long ITERATIONS = 500L * 1000L * 1000L;
    private final int arrayIndex;
    private static VolatileLong1[] longs = new VolatileLong1[NUM_THREADS];
    // private static VolatileLong2[] longs = new VolatileLong2[NUM_THREADS];
    // private static VolatileLong3[] longs = new VolatileLong3[NUM_THREADS];
    static {
        for (int i = 0; i < longs.length; i++) {
            longs[i] = new VolatileLong1();
        }
    }
    public FalseSharing(final int arrayIndex) {
        this.arrayIndex = arrayIndex;
    }
    public static void main(final String[] args) throws Exception {
        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].set(i);
        }
    }
    public final static class VolatileLong1 extends AtomicLong{
    }

    public static class VolatileLong2 extends AtomicLong
    {
        long p1, p2, p3, p4, p5, p6, p7 = 7L; 
        //此处 7*8+ AtomicLong的内部Long可以避免cache line同一行
    }
    @sun.misc.Contended
    public final static class VolatileLong3 extends AtomicLong{

    }
}
// class 1 duration = 35049006509
// class 2 duration = 20071760315
// class 3 duration = 18051448813
// 使用了原子类，所以性能的差距没有特别大的体现。

@sun.misc.Contended注解

上文中将@sun.misc.Contended注解用在了对象上，@sun.misc.Contended注解还可以指定某个字段，并且可以为字段进行分组，下面通过代码来看下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * VM Options:
 * -javaagent:classmexer.jar
 * -XX:-RestrictContended
 */
public class ContendedTest {
    byte a;
    @sun.misc.Contended("first")
    long b;
    @sun.misc.Contended("first")
    long c;
    int d;
    private static Unsafe UNSAFE;
    static {
        try {
            Field f = Unsafe.class.getDeclaredField("theUnsafe");
            f.setAccessible(true);
            UNSAFE = (Unsafe) f.get(null);
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        }
    }
    public static void main(String[] args) throws NoSuchFieldException {
        System.out.println("offset-a: " + UNSAFE.objectFieldOffset(ContendedTest.class.getDeclaredField("a")));
        System.out.println("offset-b: " + UNSAFE.objectFieldOffset(ContendedTest.class.getDeclaredField("b")));
        System.out.println("offset-c: " + UNSAFE.objectFieldOffset(ContendedTest.class.getDeclaredField("c")));
        System.out.println("offset-d: " + UNSAFE.objectFieldOffset(ContendedTest.class.getDeclaredField("d")));
        ContendedTest contendedTest = new ContendedTest();
        // 打印对象的shallow size
        System.out.println("Shallow Size: " + MemoryUtil.memoryUsageOf(contendedTest) + " bytes");
        // 打印对象的 retained size
        System.out.println("Retained Size: " + MemoryUtil.deepMemoryUsageOf(contendedTest) + " bytes");
    }
}

这里在变量b和c中使用了@sun.misc.Contended注解，并将这两个变量分为1组，执行结果如下：

1
2
3
4
5
6
offset-a: 16
offset-b: 152
offset-c: 160
offset-d: 12
Shallow Size: 296 bytes
Retained Size: 296 bytes

可见int类型的变量的偏移地址是12，也就是在对象头后面，因为它正好是4个字节，然后是变量a。@sun.misc.Contended注解的变量会加到对象的最后面，这里就是b和c了，那么b的偏移地址是152，之前说过@sun.misc.Contended注解会在变量前后各加128字节，而byte类型的变量a分配完内存后这时起始地址应该是从17开始，因为byte类型占1字节，那么应该补齐到24，所以b的起始地址是24+128=152，而c的前面并不用加128字节，因为b和c被分为了同一组。

我们算一下c分配完内存后，这时的地址应该到了168，然后再加128字节，最后大小就是296。内存结构如下：

| d:12~16 | — | a:16~17 | — | 17~24 | — | 24~152 | — | b:152~160 | — | c:160~168 | — | 168~296 |

如果b,c 不分为一组，那么b和c中增加了128字节的padding。

| d:12~16 | — | a:16~17 | — | 17~24 | — | 24~152 | — | b:152~160 | — | 160~288 | — | c:288~296 | — | 296~424 |

参考资料：

  • http://igoro.com/archive/gallery-of-processor-cache-effects/
-------------本文结束感谢您的阅读-------------
坚持分享，您的支持将鼓励我继续创作！
0%