不同物理器件的访问速度不一:速度快的代价高、容量小;代价低且容量大,速度较慢。

为充分发挥各种器件优点,计算机存储数据的物理器件不会只选择一种,而是以CPU为核心,由内而外地组建一整套存储体系结构。它将各种不同的器件组合成一个体系,让各种器件扬长避短,从而形成一种快速、大容量、低成本的内存系统。

写高性能程序,须理解存储体系结构并运用好。

1 存储体系结构的核心

成本角度,计算机的存储结构被设计成分层,包括寄存器、缓存、内存、磁盘等。

缓存让内存访问速度接近于寄存器访问速度。

过去几十年,处理器速度增长远超内存速度增长。尤其是在2001~2005年间,处理器的时钟频率在以55%的速度增长,而同期内存速度的增长仅为7%。为了缩小处理器和内存之间的速度差距,缓存被设计了。

距离处理器越近,访问速度越快,造价越高,容量就更小。缓存是处理器、内存间的桥梁,分为多层,包括L1、L2、L3层等。缓存速度介于处理器、内存间:

  • 访问处理器内部寄存器的速度在1ns内(一个时钟周期)
  • 访问内存速度通常在50~100ns(上百个时钟周期)
  • 缓存
    • 靠近处理器最近的L1层缓存的访问速度在1ns~2ns(3个时钟周期)
    • 外层L2和L3层的访问速度在10ns~20ns(几十个时钟周期)

根据空间局部性、时间局部性原理,一个处理得当程序,缓存命中率要想达到70~90%不难。因此,存储系统加入缓存,可让整个存储系统的性能接近寄存器,且每字节的成本都接近内存,甚至磁盘。

可见缓存结合寄存器速度快、内存造价低,是整个存储体系的灵魂。

2 缓存的物理架构

缓存由SRAM(静态随机存储)组成,本质是一种时序逻辑电路,具体的每个单元(比特)由一个个锁存器构成,锁存器就是让电路具有记忆功能。

SRAM单位造价较高,远高于内存的组成结构“DRAM(动态随机存储)”。因为:

  • 实现一个锁存器需六个晶体管
  • 实现一个DRAM仅需一个晶体管和一个电容

但DRAM因为结构简单,单位面积可以存放更多数据,所以更适合做内存。为了兼顾这两者的优缺点,于是它们中间需要加入缓存。

DRAM因有电容,不是单纯逻辑电路,所以不能用CMOS工艺,而SRAM可以。所以缓存能集成到芯片内部,而内存和芯片分开制造。

缓存怎样集成到芯片

过去单核时代,处理器和各级缓存都只有一个,因此缓存集成方式单一,即把处理器和缓存直连。2004年,Intel取消4GHz奔腾处理器研发,即处理器以提升主频榨取性能时代结束,多核处理器成为主流。

多核芯片,缓存集成方式:

  • 集中式缓存:一个缓存和所有处理器直接相连,多核共享这个缓存
  • 分布式缓存:一个处理器仅和一个缓存相连,一个处理器对应一个缓存
  • 混合式缓存:在L3采用集中式缓存,在L1和L2采用分布式缓存

多核处理器大多采用混合式:

  • L3,所有处理器核共享
  • L1、L2,每个处理器核特有

3 缓存的工作原理

3.1 cache line

缓存进行管理的一个最小存储单元,也叫缓存块。从内存向缓存加载数据也是按缓存块进行加载的,一个缓存块和一个内存中相同容量的数据块(下称内存块)对应。

管理缓存块的角度看缓存块的组织形式:

小方框代表一个缓存块。整个缓存由组(set)构成,每组由路(way)构成。所以

整个缓存容量 = 组数 * 路数 * 缓存块大小

为简化寻址方式,内存地址确定的数据块总被放在一个固定组,但可放在组内任意路,即对特定地址数据的访问,它若要载入缓存,则它放在上图中的行数固定,但具体放到哪列不固定。

根据组、路数不同:

缓存映射方式分类

  • 直接相连映射:缓存只有一个路,一个内存块只能放置在特定的组上

    当多个内存块映射到同一组,会冲突,因为只有一列,就需将旧缓存块换出,新缓存块放入,这会导致缓存块被频繁替换

  • 全相连映射:缓存只有一个组,所有的内存块都放在这一个组的不同路上

    大程度避免冲突,不过,当查询某缓存块时,需逐个遍历每路,且电路实现较难。折中办法就是,采用组组相连映射

  • 组组相连映射:缓存同时由多个组和多个路

    与直接相连映射相比,产生冲突可能性更小,与全相连映射相比,查询效率更高,实现更简单

缓存组数一直是2n。虽这样利于查询和定位,但若一个程序刚好以2{n}间隔寻址,就会导致地址更多的被映射到同组,而另外一些组就会被映射很少。因此,也有些缓存的组数设计成一个质数,这样即便程序以2^{n}间隔寻址,落到同组可能性大大减小,缓存各组的利用率相对均衡。

一个内存块怎样映射到一个缓存块?

缓存块的内部结构

  • V(valid),这缓存块是否有效或是否正在被使用
  • M(modified),这缓存块是否被写,即“脏”位
  • B,缓存块的bit个数

假设要寻址一个32位地址,缓存块64字节,缓存组织方式4路组相连,缓存8K。

缓存共32组(8 * 1024 / 64 / 4=32)。则对任一32位地址Addr ,它映射到缓存的组号(set index)为 Addr对组数32取模,组号同时也等于Addr的第6~10位( (Addr >> 6) & 0x1F ),Addr低6位很好理解,它是缓存块的内部偏移( 2 6 2^{6} 26为64字节)。

确定需要被映射到哪组后,需在该组的路中查询。查询方式也简单,直接将每个缓存块tag的bit位和地址Addr的高21位逐一匹配:

  • 相等,说明该内存块已载入缓存
  • 若无匹配的tag,说明缓存缺失,需将内存块放到该组的一个空闲缓存块上
  • 若所有路的缓存块都正被使用,就需要选择一个缓存块,将其移出缓存,把新的内存块载入

上面这个过程涉及到缓存块状态转换,而状态转换又涉及到有效位V、脏位M、标签tag。

缓存状态转换:

当同组的缓存块都被用完,需选择一个缓存块被换出,那选谁换出呢?和缓存块替换策略有关。

4 缓存块替换策略

目标:被替换出的数据块应该是将来最晚会被访问的块。但对将来事情无法预测,因为处理器不知程序将来访问哪个地址。因此,现在的缓存替换策略都采用最近最少使用算法(Least Recently Used ,LRU)或类LRU算法。

如程序要顺序访问 B1 、B2、B3、B4、B5地址块,这几个缓存块都映射到缓存的同一组,同时假设缓存采用4路组组相连映射,则当访问B5时,B1就需被替换出来。最简单的利用位矩阵实现。

先定义一个行、列都与缓存路数相同的矩阵。当访问某路对应缓存块,先将该路对应的所有行置为1,然后再将该路对应的所有列置为0。最终结果体现为,缓存块访问时间的先后顺序,由矩阵行中1的个数决定,最近最常访问缓存块对应行1的个数最多。

假设现在一个四路相连的缓存组包含数据块 B1、B2、B3、B4, 数据块的访问顺序为 B2、B3、B1、B4,则LRU矩阵在每次访问后的变化:

最终B2对应行的1的个数最少,所以B2将会被优先替换。

5 缓存对程序性能的影响

CPU将未来最可能被用到的内存数据加载进缓存。若下次访问内存时:

  • 数据已在缓存中,即缓存命中,它获取目标数据的速度很快
  • 若数据不在缓存,即缓存缺失,此时要启动内存数据传输,而内存访问速度相比缓存差很多。所以要避免这种情况

哪些情况易缓存缺失及程序性能影响。

5.1 缓存缺失

缓存性能主要取决于缓存命中率,缓存缺失(cache miss)越少,缓存性能越好。

引起缓存缺失的类型:

① 强制缺失

第一次将数据块读入缓存所产生缺失,也称冷缺失(cold miss),因为当发生缓存缺失时,缓存是空的(冷的)。

因为第一次将数据读入缓存时,缓存不会有数据,这种缺失无法避免。

② 冲突缺失

由于缓存的相连度有限导致的缺失。

③ 容量缺失

由于缓存大小有限导致的缺失。可认为是除了强制缺失、冲突缺失外的缺失。当程序运行的某段时间内,访问地址范围超过缓存大小过多,这样缓存容量就会成为缓存性能瓶颈。

注意和冲突缺失区别:

  • 冲突缺失指同组内的缺失
  • 容量缺失描述范围是整个缓存

第②类冲突缺失因为相连度有限。第一步可通过getconf查看缓存信息:

# getconf -a |grep CACHELEVEL1_ICACHE_SIZE                 32768LEVEL1_ICACHE_ASSOC                8LEVEL1_ICACHE_LINESIZE             64LEVEL1_DCACHE_SIZE                 32768LEVEL1_DCACHE_ASSOC                8LEVEL1_DCACHE_LINESIZE             64LEVEL2_CACHE_SIZE                  262144LEVEL2_CACHE_ASSOC                 4LEVEL2_CACHE_LINESIZE              64LEVEL3_CACHE_SIZE                  3145728LEVEL3_CACHE_ASSOC                 12LEVEL3_CACHE_LINESIZE              64LEVEL4_CACHE_SIZE                  0LEVEL4_CACHE_ASSOC                 0LEVEL4_CACHE_LINESIZE              0

这缓存信息中,L1Cache(LEVEL1_ICACHE和LEVEL1_DCACHE分别表示指令缓存、数据缓存)的cache line 大小为64字节,路数为8路,32K,可计算出缓存组数为64组( 32 K ÷ 8 ÷ 64 = 64 32K\div8\div64=64 32K÷8÷64=64)。

第二步,我们使用一个程序来测试缓存的影响:

// cache.c#include #include  #define M  64#define N  10000000int main( ){   printf("%ld",sizeof(long long));   long long (*a)[N] = (long long(*)[N])calloc(M * N, sizeof(long long));    for(int i = 0; i < 100000000; i++) {       for(int j = 0; j < 4096; j+=512) {           a[5][j]++;       }   }   return 0;}

上面代码中定义了一个二维数组,数组中元素的类型为long long ,元素大小为8字节。所以一个cache line 可以存放 64 ÷ 8 64\div8 64÷8= 8 8 8个元素。一组是8路,所以一组可以存放 8 × 8 8\times8 8×8= 64 64 64个元素。一路包含64个cache line,因为前面计算出缓存的组数为64,所以一路可以存放 8 × 64 8\times64 8×64= 512 512 512个元素。

代码中:

  • 第一层循环,执行次数
  • 第二层循环,以512 为间隔访问元素,即每次访问都会落在同一个组内的不同cache line ,因为一组有8路,所以我们迭代到 512 × 8 512\times8 512×8= 4096 4096 4096的位置。这样可以使同一组刚好可以容纳二层循环需要的地址空间。

运行结果:

# gcc cache.c# time ./a.out8real 0m2.670suser 0m2.671ssys 0m0.001s

第三步,第二层循环的迭代次数扩大一倍:

# gcc cache.c# time ./a.out8real 0m16.693suser 0m16.700ssys 0m0.001s

虽然运算量增加了一倍,但运行时间增加6倍,性能劣化三倍。劣化根本原因,当i > 4096,即访问4096后的元素,同组的cache line已全部使用,须替换,且之后的每次访问都会冲突,导致缓存块频繁替换,性能劣化严重。

6 程序局部性

分为:

  • 时间局部性

    被访问过一次的内存位置,很可能不远将来会被再次访问

  • 空间局部性

    如果一个内存位置被引用过,那么它邻近位置在不远的将来也有很大概率会被访问。

若程序有很好的局部性,那么在程序运行期间,缓存缺失就很少发生。

利用局部性原理,设计了缓存,把可能会被访问到的少量数据放在缓存中,大大加速CPU访存速度。

虚拟内存的页缓存也同理,未来最有可能会被访问到的页面会被保留在物理内存。所以多级存储结构里,当访问者和被访问者之间的速度不匹配,就是缓存能够发挥作用的场景。同理还有CDN。

修改案例,验证程序局部性对缓存命中率的影响。

#include #include  #define M  10000#define N  10000int main( ){   printf("%ld",sizeof(long long));   long long (*a)[N] = (long long(*)[N])calloc(M * N, sizeof(long long));      for(int i = 0; i < M; i++) {       for(int j = 0; j < N; j++) {           a[i][j]++;       }   }   return 0;}
  • 修改迭代次数,方便测试
  • 将之前间隔访问数组中的部分元素修改为顺序访问整个数组,访问方式按二维数组的行逐次访问

测试结果:

# gcc -O0 cache.c# time ./a.out8real 0m1.245suser 0m0.797ssys 0m0.449s

按列访问时,即将内层循环条件提到外:

for(int j = 0; j < N; j++) {    for(int i = 0; i < M; i++) {        a[i][j]++;    }}

运行结果:

# gcc -O0 cache.c# time ./a.out8real 0m2.527suser 0m1.980ssys 0m0.548s

性能也2倍劣化,主因当按行访问时地址连续,下次访问的元素和当前大概率在同一cache line(一个元素8字节,而一个cache line容纳8个元素),但按列访问时,由于地址跨度大,下次访问的元素基本不可能还在同一cache line,增加cache line被替换的次数,导致性能劣化。

这次编译项都添加-O0选项,告诉编译器不要进行优化,因为编译器聪明,能识别出这种循环外提的优化,所以要先关掉优化。

因缓存使用不当而引起的性能下降的问题:

7 伪共享

伪共享(false-sharing),当两个线程同时各自修改两个相邻的变量,由于缓存是按缓存块来组织,当一个线程对一个缓存块执行写操作,须使其他线程含有对应数据的缓存块无效。

这样两个线程都会同时使对方的缓存块无效,导致性能下降。

7.1 案例

#include #include  struct S{   long long a;   long long b;} s; void *thread1(void *args){    for(int i = 0;i < 100000000; i++){        s.a++;    }    return NULL;} void *thread2(void *args){    for(int i = 0;i < 100000000; i++){        s.b++;    }    return NULL;} int main(int argc, char *argv[]) {    pthread_t t1, t2;    s.a = 0;    s.b = 0;    pthread_create(&t1, NULL, thread1, NULL);    pthread_create(&t2, NULL, thread2, NULL);    pthread_join(t1, NULL);    pthread_join(t2, NULL);    printf("a = %lld, b = %lld\n", s.a, s.b);    return 0;}

创建两个线程,分别修改结构体S中的a 、b 变量。a 、b均为long long 类型,都占8字节,所以a 、b 在同一个cache line中,因此会发生为伪共享。

运行结果:

# gcc -Wall false_sharing.c -lpthread# time ./a.outa = 100000000, b = 100000000 real 0m0.790suser 0m1.481ssys 0m0.008s

7.2 解决伪共享

a 、b不要放在同一个cache line,这样两个线程分别操作不同cache line,不会相互影响。

对结构体S修改:

struct S{   long long a;   long long nop_0;   long long nop_1;   long long nop_2;   long long nop_3;   long long nop_4;   long long nop_5;   long long nop_6;   long long nop_7;   long long b;} s;

因为a、b中间插入8个long long变量,中间隔64字节,所以a、b肯定会被映射到不同缓存块,程序执行结果:

# gcc -Wall false_sharing.c -lpthread# time ./a.outa = 100000000, b = 100000000 real 0m0.347suser 0m0.693ssys 0m0.001s

性能有一倍的提升。

伪共享是一种缓存缺失问题,并发场景中常见。Java并发库里经常会看到为了解决伪共享而进行的数据填充。

8 总结

缓存是整个存储体系结构的灵魂,它让内存访问的速度接近于寄存器的访问速度。缓存对程序员是透明的,程序员不必使用特定的API接口来操作缓存工作,它是自动工作的。但如果我们的代码写得不好的话,我们就会感受到缓存不能起作用时的性能下降了。

缓存的映射方式包括了直接相连、全相连、组组相连三种。直接相连映射会导致缓存块被频繁替换;而全相连映射可以很大程度上避免冲突,但查询效率低;组组相连映射,与直接相连映射相比,产生冲突的可能性更小,与全相连映射相比,查询效率更高,实现也更简单。

如果要访问的数据不在缓存中,这就是缓存缺失。当发生缓存缺失时,就需要往缓存中加载目标地址的数据。如果缓存空间不足了,就需要对缓存块进行替换,替换的策略多采用LRU策略。

缓存缺失对性能影响非常大。缓存缺失主要包括强制缺失,冲突缺失和容量缺失。为了避免缓存缺失我们一定要注意程序的局部性,虽然编译器会帮我们做很多事情,但编译器还是有很多情况是无法优化的。

伪共享是一类非常典型的缓存缺失问题。它是由于多个线程都反复使对方的缓存块无效,带来的性能下降。为了解决这一类问题,我们可以考虑让多个线程所共同访问的对象,在物理上隔离开,保证它们不会落在同一个缓存块里。