高效编码与 CPU 缓存
众所周知，计算机通过 CPU 执行机器指令，无论是像 Java 这样的高级语言，还是如汇编这样的偏底层语言，最后都会被翻译成机器码由 CPU 进行。通常，使用 CPU 是操作系统内核的工作。当程序在计算机上运行时，CPU、内存都是程序可以利用的系统资源，合理得利用好，利用充分系统允许分配的资源，能够让我们的代码运行效率提升很多。
每个程序并不是能够利用计算机上的全部系统资源，在 Linux 中的内核组件 cgroup(control group) 就可以限制一个进程可以使用的 CPU 使用率、内存使用。
计算密集型与IO密集型
针对 CPU 的使用情况，应用程序可以分为计算密集型和IO密集型程序。计算密集型对应着那些程序运行的主要时间都在占用着 CPU 执行指令，例如图片处理程序。而 IO 密集型程序对应着那些程序运行的主要时间都在等待 IO 响应的程序，通常这些程序占用的 CPU 微乎其微。两类程序的 CPU 使用率差别可能很大，甚至可能一个 100%，一个 0.1%。
所以，当我们编写计算密集型的程序时，CPU的执行效率就开始变得至关重要。由于 CPU 缓存由更快的 SRAM 构成（内存是由 DRAM 构成的），而且离 CPU 核心更近，如果运算时需要的输入数据是从 CPU 缓存，而不是内存中读取时，运算速度就会快很多。所以，了解 CPU 缓存对性能的影响，便能够更有效地编写我们的代码，优化程序性能。
计算机内存层次图如下：
[图片上传失败...(image-d2fd25-1631958287193)]
CPU缓存结构图如下：
[图片上传失败...(image-c309fd-1631958287194)]
CPU 缓存离 CPU 核心更近，由于电子信号传输是需要时间的，所以离 CPU 核心越近，缓存的读写速度就越快。但 CPU 的空间很狭小，离 CPU 越近缓存大小受到的限制也越大。
拿某个Linux系统举例，离 CPU 最近的一级缓存是 32KB，二级缓存是 256KB，最大的三级缓存则是 20MB。三级缓存比一、二级缓存大数十倍的原因是因为当下的 CPU 都是多核心的，每个核心都有自己的一、二级缓存，但三级缓存却是一颗 CPU 上所有核心共享的。程序执行时，会先将内存中的数据载入到共享的三级缓存中，再进入每颗核心独有的二级缓存，最后进入最快的一级缓存，之后才会被 CPU 使用。缓存要比内存快很多。CPU 访问一次内存通常需要 100 个时钟周期以上，而访问一级缓存只需要 4~5 个时钟周期，二级缓存大约 12 个时钟周期，三级缓存大约 30 个时钟周期。
缓存命中
如果 CPU 所要操作的数据在缓存中，则直接读取，这称为缓存命中。命中缓存会带来很大的性能提升，因此，我们的代码优化目标是提升 CPU 缓存的命中率。
CPU 会区别对待指令与数据。比如，“1+1=2”这个运算，“+”就是指令，会放在一级指令缓存中，而“1”这个输入数字，则放在一级数据缓存中。虽然在冯诺依曼计算机体系结构中，代码指令与数据是放在一起的，但执行时却是分开进入指令缓存与数据缓存的，因此我们要分开来看二者的缓存命中率。
数据缓存的命中
先从一个实际的例子看看
#include<stdio.h>
#include<time.h>
int main(){
clock_t start,end;
char a[2048][2048] = {0};
int i = 0;
int j = 0;
start = clock();
for(i=0; i<2048;i++){
for(j=0; j<2048;j++){
a[i][j] = 0; // 注意：a[i][j]
}
}
end = clock();
printf("a[i][j] 的耗时 %lu ms", end - start);
start = clock();
for(i=0; i<2048;i++){
for(j=0; j<2048;j++){
a[j][i] = 0; // 注意：a[j][i]
}
}
end = clock();
printf("a[j][i] 的耗时 %lu ms", end - start);
}
# a[i][j] 的耗时 7385 msa[j][i] 的耗时 33024 ms
这个程序有两部分，每个部分通过获取 clock 获取时间戳，两个 printf 打印了两段代码的耗时，两段代码唯一的区别就是在双层循环里，访问对数组进行赋值的二维下标一个是 a[i][j], 一个是 a[j][i]，从结果上看，二者的运行耗时相差进5倍。为什么会出现如此大的差异呢？
程序运行时间主要由以下两部分组成：
CPU 执行代码的行数。这里对于二者，循环的次数是相同的，故此部分可以视为相同
每行代码执行的次数。i 和 j都函数栈中，在 gcc 编译的时候已经编译成字节码了，数组 a 指向内存中的一片区域，难道
a[i][j]和a[j][i]，访问的时间不同吗？
再次观察 a[i][j] 和 a[j][i]，前者可以理解成先访问行，再访问列，后者则相反。从内存的角度，单次从同一类内存中读取一个字节地址的时间是相同的。造成上述时间差异的唯一可能就是：第一种每次访问的字节并不是都从同一类存储介质中读取的。
回到计算机的内存层次图：
[图片上传失败...(image-78c210-1631958287194)]
从上至下，访问速度呈急速下降趋势。会不会是从底层的存储介质中，一次读取了一片区域的内容，然后将之存储到了上一层的存储介质中呢？
空间局部性原理
局部性分为：时间局部性和空间局部性。如果一个内存位置被重复的引用，那就是有了时间局部性，如果一个内存位置被引用了，很快这个位置的附近位置也被引用了，这就有了空间局部性。
程序往往有访问一个聚集空间的数据块的倾向。当我们访问数组中的某个元素时，CPU 会将该元素按照数组在内存布局中的相邻元素一起读入缓存中。
由于缓存中的数据是一个个数据块，每个数据块包含几十到几千字节不等，如果某个程序要访问数组a，第一次缓存没命中，cpu会从主存中取出包含数组a的一个数据块，复制到缓存中来，下次访问a[1],a[2],a[3]的数据时每次都缓存命中，极大的提高了效率，实现了空间的局部性。
[图片上传失败...(image-41ce8f-1631958287194)]
为什么要如此设计？
主存容量远远比缓存大，CPU执行程序的时候需要使用内存块，如果该内存块在缓存上，那么处理器直接从缓存上取值就行了，因为缓存的数据传输的速率比内存快的多。因为主存容量大，为了更快速的访问，就要把这个内存块移到缓存上。
重新审视上方的 C 代码，可以断定：a[i][j] 和 a[j][i]，两种在 for 循环中的访问方式，一定是花费时间少的前者有更多次的 数据缓存的命中。而后者是跳跃访问内存的，缓存命中的几率会大大降低。
载入上述数组时，会携带多少个邻近元素呢？
CPU Cache Line，它定义了缓存一次载入数据的大小，Linux 上通常是 64 字节。因此，对于一台 64字节 CCL 的机器，当载入 a[0][0]时，若它们占用的内存不足 64 字节，CPU 就会顺序地补足后续元素。顺序访问的 a[i][j]因为利用了这一特点，所以就会比 a[j][i]要快。当元素类型是 4 个字节的整数时，性能就会比 8 个字节的高精度浮点数时速度更快，因为缓存一次载入的元素会更多(缓存命中的概率更高)。
定义对象时，可以补齐64字节来避免访问一个对象时需要多次读取内存
遇到这种遍历访问数组的情况时，按照内存布局顺序访问将会带来很大的性能提升。
指令缓存的命中
还是从一个例子入手：
#include "stdio.h"
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <unistd.h>
#define TESTN 128 * 1024 * 1024L
using namespace std;
int main()
{
clock_t start, end;
unsigned char *arr = new unsigned char[TESTN];
for (long i = 0; i < TESTN; i++)
arr[i] = rand() % 256;
start = clock();
for (long i = 0; i < TESTN; i++)
{
if (arr[i] < 128)
arr[i] = 0;
}
end = clock();
printf("直接比较 %f ms\n", ((double)end - start) / CLOCKS_PER_SEC * 1000);
unsigned char *arr2 = new unsigned char[TESTN];
for (long i = 0; i < TESTN; i++)
arr2[i] = rand() % 256;
sort(arr2, arr2 + TESTN);
start = clock();
for (long i = 0; i < TESTN; i++)
{
if (arr2[i] < 128)
// 分支预测
arr2[i] = 0;
}
end = clock();
printf("先排序后比较 %f ms\n", ((double)end - start) / CLOCKS_PER_SEC * 1000);
}
编译运行，输出结果如下：
直接比较 649.587000 ms
先排序后比较 255.769000 ms
上述的示例代码很简单，通过随机函数生成一个TESTN长度的数组，分别考察直接比较与排序后比较的耗时。两者的时间相差3倍。
CPU 分支预测
当代码中出现 if、switch 等语句时，意味着此时至少可以选择跳转到两段不同的指令去执行。如果分支预测器可以预测接下来要在哪段代码执行（比如 if 还是 else 中的指令），就可以提前把这些指令放在缓存中，CPU 执行时就会很快。当数组中的元素完全随机时，分支预测器无法有效工作，而当 array 数组有序时，分支预测器会动态地根据历史命中数据对未来进行预测，命中率就会非常高。
分支预测本身的原理非常复杂(分为静态预测和动态预测)。平时写代码的时候可以通过分支预测极大的提高此类场景的执行效率。
多CPU提升缓存命中率
前面我们都是面向一个 CPU 核心谈数据及指令缓存的，然而现代 CPU 几乎都是多核的。虽然三级缓存面向所有核心，但一、二级缓存是每颗核心独享的。我们知道，即使只有一个 CPU 核心，现代分时操作系统都支持许多进程同时运行。这是因为操作系统把时间切成了许多片，微观上各进程按时间片交替地占用 CPU，这造成宏观上看起来各程序同时在执行。
若进程 A 在时间片 1 里使用 CPU 核心 1，自然也填满了核心 1 的一、二级缓存，当时间片 1 结束后，操作系统会让进程 A 让出 CPU，基于效率并兼顾公平的策略重新调度 CPU 核心 1，以防止某些进程饿死。如果此时 CPU 核心 1 繁忙，而 CPU 核心 2 空闲，则进程 A 很可能会被调度到 CPU 核心 2 上运行，这样，即使我们对代码优化得再好，也只能在一个时间片内高效地使用 CPU 一、二级缓存了，下一个时间片便面临着缓存效率的问题。
因此，操作系统提供了将进程或者线程绑定到某一颗 CPU 上运行的能力。当多线程同时执行密集计算，且 CPU 缓存命中率很高时，如果将每个线程分别绑定在不同的 CPU 核心上，性能便会获得非常可观的提升。
import os
import time
from multiprocessing import Process
import numpy as np
def func1(name):
affinity_mask = {3}
os.sched_setaffinity(0, affinity_mask) # 绑定 cpu4
print(f"我是{os.getpid()}下的{name}开始, CPU {os.sched_getaffinity(os.getpid())}")
a = np.random.rand(1024 * 16)
sum = 0
start = time.time()
for i in range(1024 * 16):
for one in a:
sum += one
end = time.time()
print(f"我是{os.getpid()}下的{name}, 和为{sum}结束, time为{(end- start)}")
def func2(name):
affinity_mask = {6}
os.sched_setaffinity(0, affinity_mask) # 绑定 cpu7
print(f"我是{os.getpid()}下的{name}开始, CPU {os.sched_getaffinity(os.getpid())}")
a = np.random.rand(1024 * 16)
sum = 0
start = time.time()
for i in range(1024 * 16):
for one in a:
sum += one
end = time.time()
print(f"我是{os.getpid()}下的{name}, 和为{sum}结束, time为{(end- start)}")
if __name__ == '__main__':
print(os.sched_getaffinity(0))
p1 = Process(target=func1, args=("进程1",))
p2 = Process(target=func2, args=("进程2",))
p2.start()
p1.start()
p1.join()
p2.join()
总结
CPU 缓存命中、分支预测等虽然是偏底层的原理，但是一旦理解启动的道理和使用方法，可以在写代码时仿佛洞悉程序的运行机制，对于写出高效，运行快速，顺应 CPU的程序有着极大的作用。
