References
gallery-of-processor-cache-effects
程序局部性原理
程序局部性原理是CPU Cache的理论基础。
时间局部性
时间局部性是指被CPU访问的数据，短期内还要被继续访问，比如循环、递归、方法的反复调用等。
空间局部性
空间局部性是指被CPU访问的数据的相邻数据，CPU短期内还要被继续访问，比如顺序执行的代码、连续创建的两个对象、数组等。
一致性原理
写入策略
直写模式(WriteThrough)
在数据更新时，将数据同时写入内存和Cache，该策略操作简单，但是因为每次都要写入内存，速度较慢。
回写模式(WriteBack)
在数据更新时，只将数据写入到Cache中，只有在数据被替换出Cache时，被修改的数据才会被写入到内存中，该策略因为不需要写入到内存中，所以速度较快。但数据仅写在了Cache中，Cache数据和内存数据不一致，此时如果有其它CPU访问数据，就会读到脏数据，出现bug，所以这里需要用到Cache的一致性协议来保证CPU读到的是最新的数据。
一致性
多个CPU对某块内存同时读写，就会引起冲突的问题，被称为Cache一致性问题。通过MESI协议解决，当一个CPU1修改了Cache中的某字节数据时，那么其它的所有CPU都会收到通知，它们的相应Cache就会被置为无效状态，当其他的CPU需要访问此字节的数据时，发现自己的Cache相关数据已失效，这时CPU1会立刻把数据写到内存中，其它的CPU就会立刻从内存中读取该数据。
MESI是通过四种状态的控制来解决Cache一致性问题的，四种状态分别是：
- M(Modified，已修改)
- E(Exclusive，独占)
- S(Shared，共享)
- I(Invalidated，已失效)
主存与Cache的映射关系
直接映射
每个主存块只能映射Cache的一个特定块。直接映射是最简单的地址映射方式，它的硬件简单，成本低，地址转换速度快，但是这种方式不太灵活，Cache的存储空间得不到充分利用，每个主存块在Cache中只有一个固定位置可存放，容易产生冲突，使Cache效率下降，因此只适合大容量Cache采用。
例如，如果一个程序需要重复引用主存中第0块与第16块，最好将主存第0块与第16块同时复制到Cache中，但由于它们都只能复制到Cache的第0块中去，即使Cache中别的存储空间空着也不能占用，因此这两个块会不断地交替装入Cache中，导致命中率降低。
全相连映射
主存中任何一块都可以映射到Cache中的任何一块位置上，但设计困难。
组相连映射
组相联映射实际上是直接映射和全相联映射的折中方案，主存和Cache都分组，主存中一个组内的块数与Cache中的分组数相同，组间采用直接映射，组内采用全相联映射。也就是说，将Cache分成u组，每组v块，主存块存放到哪个组是固定的，至于存到该组哪一块则是灵活的。例如，主存分为256组，每组8块，Cache分为8组，每组2块。
Cache的替换策略
LRU(Least Recently Use)策略，即最近最少使用。
代码分析
通过不停改变测试矩阵的大小，还能大致得出你电脑的CPU Cache的大小(搞懂矩阵在内存中的分布)，具体参考此链接，大致结果后文有展示。
/**
* author: CofCai
* datatime: 2020-11-10 15:37:50
* file description:
* 该文件用于验证CPU Cache的作用，主要是看到了一篇微信公众号
* 的推送，然后读完这篇文章，发现我们的通信软件基础课上讲过类似
* 的问题，所以在此记录一下。
* 原文文章《利用CPU Cache写出高性能代码》：
* https://mp.weixin.qq.com/s/_hZtklfMINCqYTlBwmz7pA
* 另附：http://igoro.com/archive/gallery-of-processor-cache-effects/
* 一致性原理：cache中和内存中的数据可能不一样（不同步），直写模式和回写模式
* 程序局部性原理（cache的理论基础）：时间局部性、空间局部性
* 通过不停改变矩阵的大小，还能大致得出你电脑的CPU Cache的大小(搞懂矩阵在内存中的分布)。
*/
#include <stdio.h>
#include <time.h>
#define row 5120
#define col 5120
#define count 20 //调用traverse_by_row/col函数一次：遍历matrix矩阵count次
int matrix[row][col] = {0}; //测试矩阵
void traverse_by_row();
void traverse_by_col();
double test(); /* 调用traverse_by_row/col函数一次 */
int main(int argc, char const *argv[])
{
printf("test matrix is %d rows, %d cols!\n", row, col);
int t, times = 5;
double res[20] = {0};
FILE *pFile=fopen("./cache.csv","wt+");
if(pFile==NULL)
{
printf("cache.csv opened failed");
return -1;
}
for (t = 0; t < times; t++)
{
res[t] = test();
fprintf(pFile,"%f,",res[t]);
printf("\n");
}
printf("test over\n");
return 0;
}
void traverse_by_row()
{
int sum_row = 0;
for (int r = 0; r < row; ++r)
{
for (int c = 0; c < col; ++c)
{
sum_row += matrix[r][c];
}
}
}
void traverse_by_col()
{
int sum_col = 0;
for (int c = 0; c < col; ++c)
{
for (int r = 0; r < row; ++r)
{
sum_col += matrix[r][c];
}
}
}
double test()
{
clock_t start, finish;
double tot_time1, tot_time2;
/** 按行遍历，会快一些 */
start = clock();
for (int i = 0; i < count; ++i)
{
traverse_by_row();
}
finish = clock();
tot_time1 = (double)(finish - start) / CLK_TCK;
printf("traverse by row %d times, totally spend %.5f(s)\n", count, tot_time1);
/** 按列遍历，会慢一些 */
start = clock();
for (int i = 0; i < count; ++i)
{
traverse_by_col();
}
finish = clock();
tot_time2 = (double)(finish - start) / CLK_TCK;
printf("traverse by col %d times, totally spend %.5f(s)\n", count, tot_time2);
return (tot_time2 - tot_time1);
}
测试结果
仅测试了5次，虽然每一次都有细微差别，但整体上来说，按行访问比按列访问都要快，而且快不少。
调整测试矩阵的大小可以大致得出电脑的cache大小，具体怎么做？请思考前文的空间局部性原理。
- 减小测试矩阵大小，如512x512，结果如下图，可以发现有些时候按列访问甚至比按行访问更快，至少说明此时矩阵第二行之前的元素都被放到cache中了，即cache至少比512*sizeof(int)B大。
- 继续增大测试矩阵大小到1024x1024，结果如下图，发现按行访问和按列访问大致一样，可认为此时是cache的一个临界大小，即cache大小大约为1024*sizeof(int)B。
- 继续增大测试矩阵大小到2048x2048，结果如下图，发现按行访问均快于按列访问，说明此时cache中没有矩阵第二行之后的元素，也就说明cache的大小小于2048*sizeof(int)B。
注：上面的比较均为感性，测试结果受多因素影响（毕竟测试的时候有其它软件也在运行，也会占用cache），但原理是没问题的。另外，现在的CPU有多级缓存，可以逐渐增大测试矩阵大小并记录相应的时间消耗，画出相应曲线图（横轴为测试矩阵大小，纵轴为按行/按列访问的时间消耗以及差值），从差值的几个突变区域可以大致推出每级cache的大小。
