不同物理器件的访问速度不一：速度快的代价高、容量小；代价低且容量大，速度较慢。
为充分发挥各种器件优点，计算机存储数据的物理器件不会只选择一种，而是以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位很好理解，它是缓存块的内部偏移（
为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查看缓存信息：
代码语言：javascript复制# 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 4
LEVEL2_CACHE_LINESIZE 64
LEVEL3_CACHE_SIZE 3145728
LEVEL3_CACHE_ASSOC 12
LEVEL3_CACHE_LINESIZE 64
LEVEL4_CACHE_SIZE 0
LEVEL4_CACHE_ASSOC 0
LEVEL4_CACHE_LINESIZE 0这缓存信息中，L1Cache（LEVEL1_ICACHE和LEVEL1_DCACHE分别表示指令缓存、数据缓存）的cache line 大小为64字节，路数为8路，32K，可计算出缓存组数为64组（
）。
第二步，我们使用一个程序来测试缓存的影响：
代码语言：javascript复制// cache.c
#include
#include
#define M 64
#define N 10000000
int 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;
}
运行结果：
代码语言：javascript复制# gcc cache.c
# time ./a.out
8
real 0m2.670s
user 0m2.671s
sys 0m0.001s第三步，第二层循环的迭代次数扩大一倍：
代码语言：javascript复制# gcc cache.c
# time ./a.out
8
real 0m16.693s
user 0m16.700s
sys 0m0.001s虽然运算量增加了一倍，但运行时间增加6倍，性能劣化三倍。劣化根本原因，当i > 4096，即访问4096后的元素，同组的cache line已全部使用，须替换，且之后的每次访问都会冲突，导致缓存块频繁替换，性能劣化严重。
6 程序局部性
分为：
- 时间局部性 被访问过一次的内存位置，很可能不远将来会被再次访问
- 空间局部性 如果一个内存位置被引用过，那么它邻近位置在不远的将来也有很大概率会被访问。
若程序有很好的局部性，那么在程序运行期间，缓存缺失就很少发生。
利用局部性原理，设计了缓存，把可能会被访问到的少量数据放在缓存中，大大加速CPU访存速度。
虚拟内存的页缓存也同理，未来最有可能会被访问到的页面会被保留在物理内存。所以多级存储结构里，当访问者和被访问者之间的速度不匹配，就是缓存能够发挥作用的场景。同理还有CDN。
修改案例，验证程序局部性对缓存命中率的影响。
代码语言：javascript复制#include
#include
#define M 10000
#define N 10000
int 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;
}- 修改迭代次数，方便测试
- 将之前间隔访问数组中的部分元素修改为顺序访问整个数组，访问方式按二维数组的行逐次访问
测试结果：
代码语言：javascript复制# gcc -O0 cache.c
# time ./a.out
8
real 0m1.245s
user 0m0.797s
sys 0m0.449s按列访问时，即将内层循环条件提到外：
代码语言：javascript复制for(int j = 0; j < N; j ) {
for(int i = 0; i < M; i ) {
a[i][j] ;
}
}运行结果：
代码语言：javascript复制# gcc -O0 cache.c
# time ./a.out
8
real 0m2.527s
user 0m1.980s
sys 0m0.548s性能也2倍劣化，主因当按行访问时地址连续，下次访问的元素和当前大概率在同一cache line（一个元素8字节，而一个cache line容纳8个元素），但按列访问时，由于地址跨度大，下次访问的元素基本不可能还在同一cache line，增加cache line被替换的次数，导致性能劣化。
这次编译项都添加-O0选项，告诉编译器不要进行优化，因为编译器聪明，能识别出这种循环外提的优化，所以要先关掉优化。
因缓存使用不当而引起的性能下降的问题：
7 伪共享
伪共享（false-sharing），当两个线程同时各自修改两个相邻的变量，由于缓存是按缓存块来组织，当一个线程对一个缓存块执行写操作，须使其他线程含有对应数据的缓存块无效。
这样两个线程都会同时使对方的缓存块无效，导致性能下降。
7.1 案例
代码语言：javascript复制#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 = %lldn", s.a, s.b);
return 0;
}创建两个线程，分别修改结构体S中的a 、b 变量。a 、b均为long long 类型，都占8字节，所以a 、b 在同一个cache line中，因此会发生为伪共享。
运行结果：
代码语言：javascript复制# gcc -Wall false_sharing.c -lpthread
# time ./a.out
a = 100000000, b = 100000000
real 0m0.790s
user 0m1.481s
sys 0m0.008s7.2 解决伪共享
a 、b不要放在同一个cache line，这样两个线程分别操作不同cache line，不会相互影响。
对结构体S修改：
代码语言：javascript复制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肯定会被映射到不同缓存块，程序执行结果：
代码语言：javascript复制# gcc -Wall false_sharing.c -lpthread
# time ./a.out
a = 100000000, b = 100000000
real 0m0.347s
user 0m0.693s
sys 0m0.001s性能有一倍的提升。
伪共享是一种缓存缺失问题，并发场景中常见。Java并发库里经常会看到为了解决伪共享而进行的数据填充。
8 总结
缓存是整个存储体系结构的灵魂，它让内存访问的速度接近于寄存器的访问速度。缓存对程序员是透明的，程序员不必使用特定的API接口来操作缓存工作，它是自动工作的。但如果我们的代码写得不好的话，我们就会感受到缓存不能起作用时的性能下降了。
缓存的映射方式包括了直接相连、全相连、组组相连三种。直接相连映射会导致缓存块被频繁替换；而全相连映射可以很大程度上避免冲突，但查询效率低；组组相连映射，与直接相连映射相比，产生冲突的可能性更小，与全相连映射相比，查询效率更高，实现也更简单。
如果要访问的数据不在缓存中，这就是缓存缺失。当发生缓存缺失时，就需要往缓存中加载目标地址的数据。如果缓存空间不足了，就需要对缓存块进行替换，替换的策略多采用LRU策略。
缓存缺失对性能影响非常大。缓存缺失主要包括强制缺失，冲突缺失和容量缺失。为了避免缓存缺失我们一定要注意程序的局部性，虽然编译器会帮我们做很多事情，但编译器还是有很多情况是无法优化的。
伪共享是一类非常典型的缓存缺失问题。它是由于多个线程都反复使对方的缓存块无效，带来的性能下降。为了解决这一类问题，我们可以考虑让多个线程所共同访问的对象，在物理上隔离开，保证它们不会落在同一个缓存块里。
