CPU Cache 如何影响程序性能

CPU Cache 是CPU 中用于减少平均访问内存时间的高速存储器件。较内存使用的DRAM ，cache 使用的SRAM 速度更快、价格也更高，所以cache 容量一般较小。与cache 相关的概念有：cache line，associativity（相连性），L1 cache，L2 cache ，cache 命中，cache 失效等。

cache 按层次分为L1、L2 甚至L3级cache，速度依次递减，容量依次增大。CPU 直接能够读取的只有L1 cache。在大多数处理器包括Intel CPU 中，cache按照缓存的指令或者数据分为数据缓存和指令缓存（如L1d 和L1i）。在多核的CPU 中，每个核心具有独立的L1 级cache，往往公用L2 级cache。公用cache 可能存在多线程缓存污染等问题。

cache 和内存传输的最小单位是cache line，一般大小为64 bytes。cache 每次从内存读取或者写入cache line 大小的数据，而不是我们在程序中定义的数据结构的大小。cache lines 之间的替换常用的是LRU 算法。如果CPU 读取的数据在cache 中，则cache 命中（cache hit），否则cache 失效（cache miss）。每一级的cache 失效将到下一级cache 中寻找数据，直至内存。cache miss 是有开销的，小于访存时间，大于cache hit 时间。每次cache 失效，CPU 就会处于停滞（stall）状态，直至缓存读取到所需要的数据。

因为cache 容量远小于内存（有种说法是1:1000），内存和cache 之间存在映射关系（associativity）。按照映射关系不同，分为：全相连映射（fully associative），多路组相连映射（N-way set associative）和直接映射（directly mapped）。全相连映射缓存和内存是全映射关系，内存中任何一块数据都可以没有限制地放的任何一个cache line 中，缓存利用率高，但设计复杂未被采用；直接映射将一块内存地址映射到一个cache line（the number of cache line = memory address%number of cache lines，其中内存地址以cache line 大小为单位），直接映射设计起来简单，但利用率低；多路组相连映射缓存更为常见，是设计复杂度和性能的权衡。它将一块内存映射到不同路上的cache lines 中，如果是8-路组相连，则一块内存映射到8-路上的cache lines 上（the number of cache line = memory address%(number of cache lines/number of ways)。不同路上的负责缓存相同内存的缓存构成一个集合set，不同set 缓存不同内存地址的数据。number of set = cache size/(ways of associativity * size of cache line)。

下图是两路组相连映射（Two-way set associative）的一个例子：

将给出几个缓存相关的程序用例，实验用例的环境如下：

环境

CPU : Intel(R) Xeon(R) CPU E5620 @ 2.40GHz 32KB L1 cache，12MB L2 cache

OS : 2.6.35-22-generic #33-Ubuntu

GCC Version : 4.4.5

compiler flags : -O3 -msse4 -DINTEL_SSE4 -Wall -std=c99

Example 1 : Cache Line

Cache line 的大小一般是64 Bytes，如果程序连续访问的数据在同一个cache line 中将减少cache miss 的次数。下面的程序以step 步为间隔访问64MB 数据：

    unsigned int *pbuff;
    unsigned long long buff_size = 64*1024*1024;
    gettimeofday(&start, NULL);
    for(unsigned long long i = 0; i < buff_size; i=i+step){
        pbuff[i] += 3;
    }
    gettimeofday(&end, NULL);

结果如下图：

图中步长在16 时出现拐点。在step < 16 时，并没有随着步长增加而减少运行时间，这是因为：unsigned int 类型大小为 4 Bytes，程序中如果步长小于16（16*4Bytes = 64Bytes）的话，步长较少只会增加cache 的命中，而cache 命中时间相对于从内存读取数据可忽略不计。而只有step>16 时，才能够减少因为从内存读取到缓存的数据量，从而减少运行时间。

Example 2 : Cache Size

cache 的大小对性能的影响巨大，下面的代码针对不同的buff_size 测试读写速度：

unsigned char *pbuff;
for(int j = 0 ; j < iters; ++j){
    for(unsigned long long i = 0; i < buff_size; i=i+64){
            (*(pbuff+i))++;
       }
}

程序迭代访问一段buff ，计算访问速度，步长为64Bytes（size of cache line）。

在L1 cache 大小之前，速度都在50GB/s 速度以上。L2 cache 大小在12MB ，虽然在12MB 有下降沿，但不是很明显，这和编译器有关。但在32MB 以后速度基本上维持在3 GB/s 左右，大致为访存速度。

Example 3 : Cache Association

cache 的关联性也会影响到程序的性能，因为不同set 的cache 是负责不同内存块的。如果频繁访问某些内存块会导致某些sets of cache 经常被替换，而其余sets 没有被利用。下面的程序按照不同步长循环访问固定大小的buff，循环的次数iters 固定，因此cache miss 影响了系统运行时间

unsigned char *pbuff;
 
for(unsigned long long i = 0; i < iters; ++i){
    tmp = p+step;
    (*(pbuff+p))++;
    if(tmp>buff_size){p=0;}else{p=tmp;}
}

下面测试时buff 大小为32MB，循环运行2²⁹ 得到的结果，L2 cache miss 对运行时间的影响非常明显，在512、1024、1536、2048 等步长都出现了尖锐的峰值（原因在下面一个例子中分析）。

下图是buff 大小为33KB（大于L1 cache 32KB），循环运行2²⁹ 的运行时间，在步长128，256，512 都出现了尖锐的峰值。我们的cache 是32KB，8路组相连，64 个cache sets，每个set 大小为512B（8 条cache line），那么相同set 映射的内存间隔为32KB/8 = 64×64B= 4KB。所以步长为4KB 的访问实际上访问的是位于同一个cache set 中的数据，访问集中在一个set 中导致大量的cache miss。同理步长为4KB的约数大小（如1KB，512B）时，访问会集中在2/4/8/.. 等cache sets 中，同样会因为LRU 导致大量cache miss 使得运行时间变长。这种内存间隔长度在Agner Fog 的 Optimizing software in C++ 中有提到：

critical_stride = cache_size/number_of_ways = number_of_sets * line_size

Example 4 : Matrix Inversion

下面是一个更实际的例子，转置一个正方矩阵：

#include<stdio.h>
#include<stdlib.h>

invert_matrix(unsigned int *pm, unsigned int size_m){
    unsigned int tmp;
    for(int i = 0; i < size_m; ++i){
        for(int j = 0; j < size_m; ++j){
            tmp = *(pm+i*size_m+j); 
            *(pm+i*size_m+j) = *(pm+j*size_m+i);
            *(pm+j*size_m+i) = tmp;
        }
    }
}

int main(int argc, char*argv[]){
    unsigned int size_m = atoi(argv[1]);
    unsigned int *pmatrix;
    
    pmatrix = (unsigned int *)malloc(size_m*size_m*(sizeof(unsigned int)));
    memset(pmatrix, 255, size_m*size_m);
  invert_matrix(pmatrix, size_m);
    free(pmatrix);
}

下图则给出了转置一个矩阵随着矩阵大小增大所需要的时间：

随着正方矩阵的增加，所需要的时间不断增加毋庸置疑，但“奇怪”的是512×512 大小的正方矩阵处出现了一个峰值。仔细分析下就知道还是critical_stride 惹的祸。代码中inverse_matrix 中的循环执行的是置换matrix[i][j] 和matrix[j][i] 的值，其中matrix[i][j] 是按照内存顺序访问第i 行的元素，而matrix[j][i] 每次访问第i 列的所有元素。这些元素单独占据一个cache line，而且间隔为512*4Bytes = 2KB。也就是说同列上相间隔的一个元素差距为半个critical_stride ，同列上所有元素在内存上只映射到两个sets 16 个cache line，而一列中有512 个元素，这样就导致了在访问列上的元素时导致大量cache miss。使得行上的顺序访问无法利用到列上已经访问缓存在cache 上的元素。同理在256×256 和128×128 处也有两个峰值：

126    24.792000 us                              254    110.082000 us
127    25.243000 us                              255    110.596000 us
128    43.110000 us                              256    225.817000 us
129    25.892000 us                              257    104.745000 us
130    26.431000 us                              258    107.871000 us

不用奇怪在1024×1024 处为啥没有也出现峰值，因为当矩阵增大到一定程度时，没有足够的L1 cache 缓存单列上的元素，从而导致matrix[i][j] 是按照内存顺序访问第i 行的元素也无法利用到列上元素的缓存，这是由于L1 cache 大小决定的，而不是因为列上元素只映射到少量的sets 中导致的，因此矩阵足够大时不会再有峰值。

参考：

【1】 CPU Cache WIKI

【2】 gallery-of-processor-cache-effects

【3】 Functional Principles of Cache Memory

【4】 Why speed of memcpy() drops dramatically every 4KB?

【5】 Speed of memcpy() greatly influenced by different ways of malloc()

【6】 Why is transposing a matrix of 512×512 much slower than transposing a matrix of 513×513?