如何利用缓存让CPU更有效率地执行代码？
数组遍历方式我们先来看一个很经典的例子(例子是c语言写的，其他语言实现也都是差不多的)：
#include #include #include int main(){ clock_t begin, end; double cost; begin = clock(); int count = 10000; int* array = (int*)malloc(sizeof(int) * count * count);//2维数组 //代码1 按行遍历 //for (int i = 0;i < count;i++) { // for (int j = 0; j < count; j++) { // array[i * count + j] = 0; // } //} //代码2 按列遍历 for (int i = 0;i < count;i++) { for (int j = 0; j < count; j++) { array[j * count + i] = 0; } } end = clock(); cost = (double)(end - begin) / clocks_per_sec; printf(constant clocks_per_sec is: %ld, time cost is: %lf, clocks_per_sec, cost); return 0;}运行结果：
#代码1 constant clocks_per_sec is: 1000, time cost is: 0.126000 #代码2constant clocks_per_sec is: 1000, time cost is: 0.301000clocks_per_sec=1000，表示当前电脑1秒是被分成了1000个时间片，也就是说时间测量最小单位为1ms
所以上述代码1，在笔者的电脑运行耗时大约0.126ms；而代码2，运行耗时却高达0.301ms
这2段代码块 基本一致，唯独遍历方式不同 ，代码1是按行遍历，而代码2是按列遍历
无非是遍历方式不一样，但为啥运行效率会差这么多呢？
我们知道在内存中，数组一般是按行存储的，如array[0][0],array[0][1],...,array[2][0],array[2][1],...
上述代码块1是按行遍历，而代码块2是按列遍历，按行遍历时可以由指向数组第一个数的指针一直往下走，就可以遍历完整个数组，而按列遍历则要获得指向每一列的第一行的元素的指针，然后每次将指针指下一行，但是指针的寻址很快，所以在内存中这2种数组遍历方式的效率，不会有明显的区别
那为啥运行效率会差这么多呢
其实这个背后其实是cpu cache起作用！笔者吐血画了张图帮助大家更直观地了解原理
：
上图，左边是数组按列遍历的情况，右边是按行遍历的情况，笔者把他们合到了一张图上，这样对比度更强
我们知道cpu cahce利用了空间局部性的原理来提高性能，如果一个内存的位置被引用，那么将来它附近的位置也会被引用
也就是说当数组按行遍历时，当访问第一个数组元素array[0][0]，cpu会在缓存中，寻找这个内存地址对应的cache line，这时候肯定找不到啊，发生缓存缺失cache miss，会触发cpu把array[0][0]地址处以及后面连续的一段内存都load到cache line中，这个时候访问数组中第2~8个元素，会直接在cpu cache中找到对应的数据，即缓存命中cache hit，这样就不需要访问内存了；直到访问第9个数组元素，再次发生cache miss，周而复始直到程序结束
cpu每次能加载多少内存到cache line中，主要取决于cache line的容量，上图只是举个例子，一般主流的 cpu 的 cache line 大小是64 byte，过大或者过小都会影响性能
我们可以发现按行遍历时， 访问数组元素的顺序，是与内存中数组元素存放的顺序一致 ，每次发生cache miss，都加载一堆内存区域的数据，数组后续元素都能在缓存中找到对应的数据，这样缓存命中率较高，从而减少缓存缺失导致的开销
而按列遍历时， 访问数组元素的顺序，是和内存中数组元素存放的顺序不一致，跳跃式访问 ，每次发生cache miss，哪怕都加载一堆内存区域的数据，像上图一样每次缓存只能命中1次，会导致频繁发生cache miss，因此缓存命中率特别低
而 缓存读写速度要远远快于内存的读写速度 ，这里笔者再次拿出经典的储存器金字塔图，在冯诺依曼架构下，计算机存储器是分层次的，存储器的层次结构如下图所示，是一个金字塔形状的东西。从上到下依次是寄存器、缓存、主存(内存)、硬盘等等
离cpu越近的存储器，访问速度越来越快，容量越来越小，每字节的成本也越来越昂贵
比如一个主频为3.0ghz的cpu，寄存器的速度最快，可以在1个时钟周期内访问，一个时钟周期(cpu中基本时间单位)大约是0.3纳秒，内存访问大约需要120纳秒，固态硬盘访问大约需要50-150微秒，机械硬盘访问大约需要1-10毫秒，最后网络访问最慢，得几十毫秒左右。
这个大家可能对时间不怎么敏感，那如果我们把 一个时钟周期如果按1秒算的话，那寄存器访问大约是1s，内存访问大约就是6分钟 ，固态硬盘大约是2-6天 ，传统硬盘大约是1-12个月，网络访问就得几年了 ！我们可以发现cpu的速度和内存等存储器的速度，完全不是一个量级上的。
所以尽可能地让代码只访问缓存，避免频繁访问内存，能极大地提高代码性能，所以数组按行遍历要远远快于是按列遍历，当然前提条件数组在内存中是按行储存的
循环的步长我们这里还是举一个经典例子:
#include #include #include int main(){ clock_t begin, end; double cost; begin = clock(); const int len = 64 * 1024 * 1024; int* arr = (int*)malloc(sizeof(int) * len); //代码1 //for (int i = 0; i < len; i += 2) arr[i] *= 3; //代码2 for (int i = 0; i < len; i += 8) arr[i] *= 3; end = clock(); cost = (double)(end - begin) / clocks_per_sec; printf(constant clocks_per_sec is: %ld, time cost is: %lf, clocks_per_sec, cost); return 0;}代码1这个循环功能是将数组的每2个值乘3，代码2循环则将每8个值乘3，也就是代码1应该比代码少4倍的计算量，那有人可能会认为，时间也会节约4分之三
但真的是这样吗？
我们直接来看运行结果:
#代码1 constant clocks_per_sec is: 1000, time cost is: 0.068000#代码2constant clocks_per_sec is: 1000, time cost is: 0.058000我们发现在笔者的电脑跑下来，时间分别是：0.068ms,0.058ms;它们的耗时其实差不多，远远没有4倍差距那么大
其实 循环执行时间长短由数组的内存访问次数决定的，而非整型数的乘法运算次数 ；因为这个时候缓存已经起作用了，当缓存丢失时，cpu这个时候会将一段内存加载到缓存中，以cache line为单位，一般是64byte
而上述代码中无论步长是2还是8，都是在一个cache line中，cpu访问同一个缓存行内其它值的开销是很小的；另一方面这两个循环的主存访问次数其实是一样的。所以这2个循环耗时相差不大
但这并不意味这步长无论多大都是这样的，是有一个临界点的；在c语言中，一个整型=4个字节，所以16个整型数占用64字节(byte)=一个cache line(64byte)
因此当cache line大小为64byte时，步长在1~16范围内，循环运行时间相差不大。但从16往后，每次步长加倍，运行时间减半
上图来源于gallery of processor cache effects
伪共享和缓存行对齐我们再来看一个多线程的例子：
#include #include #include #include struct s { long long a; //long long noop[8]; long long b;} s;void* threada(void* p) { for (int i = 0; i < 100000000; i++) { s.a++; } return null;}void* threadb(void* p){ for (int i = 0; i < 100000000; i++) { s.b++; } return null;}int main(){ clock_t begin, end; double cost; begin = clock(); pthread_t thread1, thread2; pthread_create(&thread1, null, threada, null); pthread_create(&thread2, null, threadb, null); pthread_join(thread1, null); pthread_join(thread2, null); end = clock(); cost = (double)(end - begin) / clocks_per_sec; printf(constant clocks_per_sec is: %ld, time cost is: %lf, clocks_per_sec, cost); return 0;}运行结果：
constant clocks_per_sec is: 1000, time cost is: 0.194000上述例子，表示2个线程同时修改两个相邻的变量（在一个结构体内），而在c语言中，long类型占8个字节，所以这2个变量a、b都在同一个cache line中；另外在如今多核cpu的时代，2个线程可能由不同核心分别执行，那么缓存一致性的问题不可避免。
我们知道， 缓存的加载更新不是以字节为单位，而是以cache line为单位 ，在基于mesi协议下，当2个线程同时修改两个相邻的变量，整个cache line都会被整个刷新
这会出现一个伪共享现象：当线程a读取变量a，并修改a，线程a在未写回缓存之前，同时另一个线程b读取了b，读取这个b所在的缓存，由于缓存一致性协议，其实该缓存行处于无效状态，需要重新加载缓存。这就是 缓存伪共享false-sharing 。使用缓存的本意是为了提高性能，但是现在场景下，多个线程在不同的cpu核心上高频反复访问这种cachelin伪共享的变量，会严重牺牲性能
所以我们写代码的时候需要注意伪共享问题，那如何解决呢？
其实也很简单，我们只要保证多线程需要同时操作的变量不在同一个cache line中即可，我们这里cache line的大小为64字节，最简单的方法我们只需在这个例子的结构体中，再加一行代码
struct s { long long a; long long noop[8]; long long b;} s;long long noop[8];占用8*8=64字节，也就是一个cache line的大小，这样就能保证变量a、b不在同一个cache line中，这样就不会再出现伪共享现象
最后我们校验一下，从最终执行结果来看，时间确实节约了不少：
constant clocks_per_sec is: 1000, time cost is: 0.148000当然还有其他优化方式，比如编译器直接优化，如果我们对伪共享现象 反向思考 ，当有多个小变量并不涉及到很复杂的读写依赖，那么我们应该尽可能将这些小变量放在同一个缓存行cache line上，这个也叫做缓存行对齐
因为这些小变量可能散落在内存的各个地方，降低缓存命中率，就得多次加载到缓存，那如果能一起加载到同一个缓存行上，缓存命中率就能大大提高，从而提升代码的性能
在c语言中，为了避免伪共享，编译器会自动将结构体，字节补全以及 内存对齐 (内存对齐就不展开讲了，感兴趣地自行去了解一下);另外对齐的大小最好是缓存行的长度，这样缓存只要load一次即可
#define cache_line 64 //缓存行长度struct s1 {int a, b, c, d;} __attribute__ ((aligned(cache_line)));//__align用于显式对齐，这种方式使得结构体字节对齐的大小为缓存行的大小最后再补充一个，linux提供一个函数，sched_setaffinity可以在多核cpu系统中，设置线程的cpu亲和力，使线程绑定在某一个或几个cpu核心上运行，避免在多个核心之间来回切换，因为l3 cache 是多核心之间共享的，但l1 和 l2 cache都是每个核心独有的，如果线程都在同一个核心上执行，能够减少保证缓存一致性的操作，从而减少访问内存的频率，提升程序性能。
2019年的服务机器人发展的趋势是什么样
激光位移传感器的激光三角测量法原理与激光回波分析原理解析
ADC时序和数字接口时序的时序因素和解决方案
专打雷达的中国无人机首次露面
监控系统在智能家居上有什么可以应用的
如何利用缓存让CPU更有效率地执行代码？
基于STM32单片机的私家车安全检测系统设计
拥有四个翅膀的像蜜蜂的微型机器人
联发科天玑1000L性能到底怎么样
紫光卓远入主在即 昆明机床将并入＂清华系＂
浪涌抑制器简化了MIL-STD-1275D合规性
简谈基于fpga设计9/7小波变换原理
港行Lumia920价格曝光 11月份上市
谷歌收购 Fitbit反垄断方案未获澳大利亚监管认可
物联网碎片化使得开发FPGA芯片成本高
利亚德披露有关Micro LED业务的最新消息
iPhone12下月发布 苹果A系列芯片三年AI进化 为何要大规模升级AI算力
华强收购策略，助力芯斐电子
自有处理器遇冷？小米5C发布不到四个月就开始降价了
差分运放和仪表放大器应用科普
#include #include #include int main(){ clock_t begin, end; double cost; begin = clock(); int count = 10000; int* array = (int*)malloc(sizeof(int) * count * count);//2维数组 //代码1 按行遍历 //for (int i = 0;i < count;i++) { // for (int j = 0; j < count; j++) { // array[i * count + j] = 0; // } //} //代码2 按列遍历 for (int i = 0;i < count;i++) { for (int j = 0; j < count; j++) { array[j * count + i] = 0; } } end = clock(); cost = (double)(end - begin) / clocks_per_sec; printf(constant clocks_per_sec is: %ld, time cost is: %lf, clocks_per_sec, cost); return 0;}运行结果：
#代码1 constant clocks_per_sec is: 1000, time cost is: 0.126000 #代码2constant clocks_per_sec is: 1000, time cost is: 0.301000clocks_per_sec=1000，表示当前电脑1秒是被分成了1000个时间片，也就是说时间测量最小单位为1ms
所以上述代码1，在笔者的电脑运行耗时大约0.126ms；而代码2，运行耗时却高达0.301ms
这2段代码块 基本一致，唯独遍历方式不同 ，代码1是按行遍历，而代码2是按列遍历
无非是遍历方式不一样，但为啥运行效率会差这么多呢？
我们知道在内存中，数组一般是按行存储的，如array[0][0],array[0][1],...,array[2][0],array[2][1],...
上述代码块1是按行遍历，而代码块2是按列遍历，按行遍历时可以由指向数组第一个数的指针一直往下走，就可以遍历完整个数组，而按列遍历则要获得指向每一列的第一行的元素的指针，然后每次将指针指下一行，但是指针的寻址很快，所以在内存中这2种数组遍历方式的效率，不会有明显的区别
那为啥运行效率会差这么多呢
其实这个背后其实是cpu cache起作用！笔者吐血画了张图帮助大家更直观地了解原理
：
上图，左边是数组按列遍历的情况，右边是按行遍历的情况，笔者把他们合到了一张图上，这样对比度更强
我们知道cpu cahce利用了空间局部性的原理来提高性能，如果一个内存的位置被引用，那么将来它附近的位置也会被引用
也就是说当数组按行遍历时，当访问第一个数组元素array[0][0]，cpu会在缓存中，寻找这个内存地址对应的cache line，这时候肯定找不到啊，发生缓存缺失cache miss，会触发cpu把array[0][0]地址处以及后面连续的一段内存都load到cache line中，这个时候访问数组中第2~8个元素，会直接在cpu cache中找到对应的数据，即缓存命中cache hit，这样就不需要访问内存了；直到访问第9个数组元素，再次发生cache miss，周而复始直到程序结束
cpu每次能加载多少内存到cache line中，主要取决于cache line的容量，上图只是举个例子，一般主流的 cpu 的 cache line 大小是64 byte，过大或者过小都会影响性能
我们可以发现按行遍历时， 访问数组元素的顺序，是与内存中数组元素存放的顺序一致 ，每次发生cache miss，都加载一堆内存区域的数据，数组后续元素都能在缓存中找到对应的数据，这样缓存命中率较高，从而减少缓存缺失导致的开销
而按列遍历时， 访问数组元素的顺序，是和内存中数组元素存放的顺序不一致，跳跃式访问 ，每次发生cache miss，哪怕都加载一堆内存区域的数据，像上图一样每次缓存只能命中1次，会导致频繁发生cache miss，因此缓存命中率特别低
而 缓存读写速度要远远快于内存的读写速度 ，这里笔者再次拿出经典的储存器金字塔图，在冯诺依曼架构下，计算机存储器是分层次的，存储器的层次结构如下图所示，是一个金字塔形状的东西。从上到下依次是寄存器、缓存、主存(内存)、硬盘等等
离cpu越近的存储器，访问速度越来越快，容量越来越小，每字节的成本也越来越昂贵
比如一个主频为3.0ghz的cpu，寄存器的速度最快，可以在1个时钟周期内访问，一个时钟周期(cpu中基本时间单位)大约是0.3纳秒，内存访问大约需要120纳秒，固态硬盘访问大约需要50-150微秒，机械硬盘访问大约需要1-10毫秒，最后网络访问最慢，得几十毫秒左右。
这个大家可能对时间不怎么敏感，那如果我们把 一个时钟周期如果按1秒算的话，那寄存器访问大约是1s，内存访问大约就是6分钟 ，固态硬盘大约是2-6天 ，传统硬盘大约是1-12个月，网络访问就得几年了 ！我们可以发现cpu的速度和内存等存储器的速度，完全不是一个量级上的。
所以尽可能地让代码只访问缓存，避免频繁访问内存，能极大地提高代码性能，所以数组按行遍历要远远快于是按列遍历，当然前提条件数组在内存中是按行储存的
循环的步长我们这里还是举一个经典例子:
#include #include #include int main(){ clock_t begin, end; double cost; begin = clock(); const int len = 64 * 1024 * 1024; int* arr = (int*)malloc(sizeof(int) * len); //代码1 //for (int i = 0; i < len; i += 2) arr[i] *= 3; //代码2 for (int i = 0; i < len; i += 8) arr[i] *= 3; end = clock(); cost = (double)(end - begin) / clocks_per_sec; printf(constant clocks_per_sec is: %ld, time cost is: %lf, clocks_per_sec, cost); return 0;}代码1这个循环功能是将数组的每2个值乘3，代码2循环则将每8个值乘3，也就是代码1应该比代码少4倍的计算量，那有人可能会认为，时间也会节约4分之三
但真的是这样吗？
我们直接来看运行结果:
#代码1 constant clocks_per_sec is: 1000, time cost is: 0.068000#代码2constant clocks_per_sec is: 1000, time cost is: 0.058000我们发现在笔者的电脑跑下来，时间分别是：0.068ms,0.058ms;它们的耗时其实差不多，远远没有4倍差距那么大
其实 循环执行时间长短由数组的内存访问次数决定的，而非整型数的乘法运算次数 ；因为这个时候缓存已经起作用了，当缓存丢失时，cpu这个时候会将一段内存加载到缓存中，以cache line为单位，一般是64byte
而上述代码中无论步长是2还是8，都是在一个cache line中，cpu访问同一个缓存行内其它值的开销是很小的；另一方面这两个循环的主存访问次数其实是一样的。所以这2个循环耗时相差不大
但这并不意味这步长无论多大都是这样的，是有一个临界点的；在c语言中，一个整型=4个字节，所以16个整型数占用64字节(byte)=一个cache line(64byte)
因此当cache line大小为64byte时，步长在1~16范围内，循环运行时间相差不大。但从16往后，每次步长加倍，运行时间减半
上图来源于gallery of processor cache effects
伪共享和缓存行对齐我们再来看一个多线程的例子：
#include #include #include #include struct s { long long a; //long long noop[8]; long long b;} s;void* threada(void* p) { for (int i = 0; i < 100000000; i++) { s.a++; } return null;}void* threadb(void* p){ for (int i = 0; i < 100000000; i++) { s.b++; } return null;}int main(){ clock_t begin, end; double cost; begin = clock(); pthread_t thread1, thread2; pthread_create(&thread1, null, threada, null); pthread_create(&thread2, null, threadb, null); pthread_join(thread1, null); pthread_join(thread2, null); end = clock(); cost = (double)(end - begin) / clocks_per_sec; printf(constant clocks_per_sec is: %ld, time cost is: %lf, clocks_per_sec, cost); return 0;}运行结果：
constant clocks_per_sec is: 1000, time cost is: 0.194000上述例子，表示2个线程同时修改两个相邻的变量（在一个结构体内），而在c语言中，long类型占8个字节，所以这2个变量a、b都在同一个cache line中；另外在如今多核cpu的时代，2个线程可能由不同核心分别执行，那么缓存一致性的问题不可避免。
我们知道， 缓存的加载更新不是以字节为单位，而是以cache line为单位 ，在基于mesi协议下，当2个线程同时修改两个相邻的变量，整个cache line都会被整个刷新
这会出现一个伪共享现象：当线程a读取变量a，并修改a，线程a在未写回缓存之前，同时另一个线程b读取了b，读取这个b所在的缓存，由于缓存一致性协议，其实该缓存行处于无效状态，需要重新加载缓存。这就是 缓存伪共享false-sharing 。使用缓存的本意是为了提高性能，但是现在场景下，多个线程在不同的cpu核心上高频反复访问这种cachelin伪共享的变量，会严重牺牲性能
所以我们写代码的时候需要注意伪共享问题，那如何解决呢？
其实也很简单，我们只要保证多线程需要同时操作的变量不在同一个cache line中即可，我们这里cache line的大小为64字节，最简单的方法我们只需在这个例子的结构体中，再加一行代码
struct s { long long a; long long noop[8]; long long b;} s;long long noop[8];占用8*8=64字节，也就是一个cache line的大小，这样就能保证变量a、b不在同一个cache line中，这样就不会再出现伪共享现象
最后我们校验一下，从最终执行结果来看，时间确实节约了不少：
constant clocks_per_sec is: 1000, time cost is: 0.148000当然还有其他优化方式，比如编译器直接优化，如果我们对伪共享现象 反向思考 ，当有多个小变量并不涉及到很复杂的读写依赖，那么我们应该尽可能将这些小变量放在同一个缓存行cache line上，这个也叫做缓存行对齐
因为这些小变量可能散落在内存的各个地方，降低缓存命中率，就得多次加载到缓存，那如果能一起加载到同一个缓存行上，缓存命中率就能大大提高，从而提升代码的性能
在c语言中，为了避免伪共享，编译器会自动将结构体，字节补全以及 内存对齐 (内存对齐就不展开讲了，感兴趣地自行去了解一下);另外对齐的大小最好是缓存行的长度，这样缓存只要load一次即可
#define cache_line 64 //缓存行长度struct s1 {int a, b, c, d;} __attribute__ ((aligned(cache_line)));//__align用于显式对齐，这种方式使得结构体字节对齐的大小为缓存行的大小最后再补充一个，linux提供一个函数，sched_setaffinity可以在多核cpu系统中，设置线程的cpu亲和力，使线程绑定在某一个或几个cpu核心上运行，避免在多个核心之间来回切换，因为l3 cache 是多核心之间共享的，但l1 和 l2 cache都是每个核心独有的，如果线程都在同一个核心上执行，能够减少保证缓存一致性的操作，从而减少访问内存的频率，提升程序性能。
2019年的服务机器人发展的趋势是什么样
激光位移传感器的激光三角测量法原理与激光回波分析原理解析
ADC时序和数字接口时序的时序因素和解决方案
专打雷达的中国无人机首次露面
监控系统在智能家居上有什么可以应用的
如何利用缓存让CPU更有效率地执行代码？
基于STM32单片机的私家车安全检测系统设计
拥有四个翅膀的像蜜蜂的微型机器人
联发科天玑1000L性能到底怎么样
紫光卓远入主在即 昆明机床将并入＂清华系＂
浪涌抑制器简化了MIL-STD-1275D合规性
简谈基于fpga设计9/7小波变换原理
港行Lumia920价格曝光 11月份上市
谷歌收购 Fitbit反垄断方案未获澳大利亚监管认可
物联网碎片化使得开发FPGA芯片成本高
利亚德披露有关Micro LED业务的最新消息
iPhone12下月发布 苹果A系列芯片三年AI进化 为何要大规模升级AI算力
华强收购策略，助力芯斐电子
自有处理器遇冷？小米5C发布不到四个月就开始降价了
差分运放和仪表放大器应用科普