程序优化：CPU缓存基础知识

CPU缓存(CPU Cache)的目的是为了提高访问内存(RAM)的效率，这虽然已经涉及到硬件的领域，但它仍然与我们息息相关，了解了它的一些原理，能让我们写出更高效的程序，另外在多线程程序中，一些不可思议的问题也与缓存有关。

现代多核处理器，一个CPU由多个核组成，每个核又可以有多个硬件线程，比如我们说4核8线程，就是指有4个核，每个核2个线程，这在OS看来就像8个并行处理器一样。

CPU缓存有多级缓存，比如L1, L2, L3等：

• L1容量最小，速度最快，每个核都有L1缓存，L1又专门针对指令和数据分成L1d(数据缓存),L1i(指令缓存)。
• L2容量比L1大，速度比L1慢，每个核都有L2缓存。
• L3容量最大，速度最慢，多个核共享一个L3缓存。

有些CPU可能还有L4缓存，不过不常见；此外还有其他类型的缓存，比如TLB(translation lookaside buffer)，用于物理地址和虚拟地址转译，这不是我们关心的缓存。

下图展示了缓存和CPU的关系：

Linux用下面命令可以查看CPU缓存的信息：

$ getconf -a | grep CACHE
LEVEL1_ICACHE_SIZE                 32768
LEVEL1_ICACHE_ASSOC                8
LEVEL1_ICACHE_LINESIZE             64
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  262144
LEVEL2_CACHE_ASSOC                 8
LEVEL2_CACHE_LINESIZE              64
LEVEL3_CACHE_SIZE                  31457280
LEVEL3_CACHE_ASSOC                 20
LEVEL3_CACHE_LINESIZE              64
LEVEL4_CACHE_SIZE                  0
LEVEL4_CACHE_ASSOC                 0
LEVEL4_CACHE_LINESIZE              0

• 上面显示CPU只有3级缓存，L4都为0。
• L1的数据缓存和指令缓存分别是32KB；L2为256KB；L3为30MB。
• 在缓存和主存之间，数据是按固定大小的块传输的 该块称为缓存行(cache line)，这里显示每行的大小为64Bytes。
• ASSOC表示主存地址映射到缓存的策略，这里L1，L2是8路组相联，L3是20路组相联，等一会儿再说是什么意思。

一块CPU缓存可以看成是一个数组，数组元素是缓存项(cache entry)，一个缓存项的内容大概是这样的：

    +-------------------------------------------+   
    |  tag  |   data block(cache line) |  flag  |   
    +-------------------------------------------+

• data block就是从内存中拷贝过来的数据，也就是我们说的cache line，从上面信息可知大小是64字节。
• tag 保存了内存地址的一部分，是用来验证是否缓存命中的。
• flag 是一些标志位，比如缓存是否失效，写dirty等等。
• 实际上LEVEL1_ICACHE_SIZE这个数据，是用data block来算的，并不包括tag和flag占用的大小，比如64 x 512=32768，表示LEVEL1_ICACHE_SIZE可以缓存512个cache line。

缓存首先要解决的问题是：怎么映射内存地址和缓存地址？比如CPU要检查一个内存值是否已经缓存，那么它首先要能算出这个内存地址对应的缓存地址，然后才能检查。

为了解决这个问题，缓存将一个内存地址分成下面几个部分：

    +-------------------------------------------+   
    |  tag                | index    | offset   |   
    +-------------------------------------------+

• tag和缓存项中的tag对应，用来验证是否缓存命中的。
• index 缓存项数组中的索引。
• offset 缓存块(cache line)中的偏移，因为缓存块是64字节，而内存值可能只有4个字节，一个缓存块可以保存多个连续的内存值。这个offset实际上就是指明内存值在cache line中的位置。

现在我们举一个具体的例子，说明内存和缓存是如何映射的：

• 假如缓存的大小是32768B(32KB)，缓存块大小是64B，那么缓存项数组就有? 32768?/64=512 个。
• CPU要访问一个内存地址0x1CAABBDD?，它首先检查这个内存地址是否在缓存中，检查过程是这样的：
• 内存地址的二进制形式是(低位在前面)：

   |     tag                         |     index       | offset    |
    0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1

• 先计算内存在cache line中的偏移，因为缓存块是64字节，那么offset需要占6位(2^6=64)，即offset=011101=29。
• 接着要计算缓存项的索引，因为缓存项数组是512个，所以index需要占9位(2^9=512)，即index=011101111=239。
• 现在我们通过offset和index已经找到缓存块的具体位置了，但是因为内存要远比缓存大很多，所以多个内存块是可以映射到同一个位置的，怎么判断这个缓存块位置存的就是这个内存的值呢？答案就是tag：内存地址去掉index和offset的部分，剩下的就是tag=00011100101010101=0x3955。
• 通过index找到缓存项，比较缓存项中的tag是否与内存地址中的tag相同，如果相同表示命中，就直接取缓存块中的值；如果不同表示未命中，CPU需要将内存值拷贝到缓存(替换掉老的)。

这种映射方式就称为直接映射(Direct mapped)，它的缺点就是多个内存地址会映射到同一个缓存地址，拿上面的内存地址来看，只要offset和index相同的内存地址，就一定会映射到同一个地方，比如：

00011100101010100 011101111 011101
00011100101010110 011101111 011101
00011100101010111 011101111 011101

如果同时访问上面3个地址，就会一直替换缓存的值，也就是一直出现缓存冲突，这可能比没有缓存还要慢，因为除了访问内存外，还多一个拷贝内存值到缓存的操作。

为了解决上面的问题，我试着把缓存项数组分成2个数组(2路)，比如分成2个256的数组，如下图所示：

查找过程和上面其实一样的：

• 先通过index找到数组索引，只不过因为是2路，所以存在2个数组。
• 然后通过内存tag依次比较2个缓存顶的tag，如果其中一个tag相等，说明这个数组缓存命中；如果两个都不相等，说明缓存不命中，CPU会拷贝内存值到缓存中，但是现在有2个位置，要拷贝进哪个呢？我的理解CPU应该是随机选1路拷贝。
• offset这个其实无关紧要，因为它是cache line中的偏移。

那这个和直接映射相比，好在哪里呢，因为一个内存值会随机拷贝到2路中的1个，所以缓存冲突(多个内存地址映射到同一个缓存地址)的概率会降低一半；如果把缓存项数组分成4个数组，这就是4路组相联。

上面LEVEL1_ICACHE_ASSOC的值等于8，表明是8路组相联。分组越多，缓存冲突率越低，但是CPU要遍历的数组就越多，这是一个权衡的问题。

通过观察也可以发现，其实直接映射就是1路组相联。如果直接分成512个数组，那每个数组只有1项，这种就是全相联，CPU直接遍历512个数组，判断内存地址在哪1个。

• 当CPU从内存读数据时，如果该数据没有在缓存中(read miss)，CPU会把数据拷贝到缓存。
• 当CPU往内存写数据时：
• 有多种写策略：
• Write through 更新缓存的数据，同时更新内存的数据。
• Write back 只更新缓存的数据，同时在缓存项设置一个drity标志位，内存的数据只会在某个时刻更新(比如替换cache line时)。
• 如果在写的时候数据没有在缓存中(write miss)，也有两种策略：
• Write allocate 在写之前先把数据加载到缓存，然后再实施上面的写策略。
• No-write allocate 不加载缓存，直接把数据写到内存。数据只有在 read miss 时才会加载到缓存。

虽然上面两组策略可以任意搭配，但通常情况下是 No-write allocate 和 Write through 一起使用，而 Write allocate 则和 Write back 一起使用，下面是 wikipedia 的两张流程图。

• No-write allocate方式的 Write through Cache：

• Write allocate 方式的 Write back Cache：

从上面描述我们知道，当我们向一个内存写数据时，内存中的数据可能不马上被更新，这个新数据可能还在cache line呆着。因为每个核都有自己的缓存，如果CPU不做处理，可以想象一定会出问题的：比如核1改了数据，核2去读同一个数据，此时数据还在核1的缓存中，核2读到的就是老的数据。CPU为了处理多核间的缓存同步，有一套复杂的一致性协议。关于这个后面再来学习。

• CPU cache
• Cache (computing)