1. CPU Cache 有多快？

问：为什么有了内存，还需要 CPU Cache？
根据摩尔定律，CPU的访问速度 每18个月就会翻一倍，相当于每年增长60%左右。虽然内存的速度 也在不断增长，但增长的速度 远小于CPU，平均每年增长7%左右。因此，CPU与内存的访问性能的差距 不断拉大，为了弥补 CPU与内存 之间的性能差距，所以在 CPU内部引入了CPU Cache，即⾼速缓存。）
在Linux系统中，可以使用下图的方式 来查看各级CPU Cache的大小：（比如这台服务器，离CPU核心最近的 L1 Cache 是 32KB，其次 L2 Cache 是 256KB，最大的 L3 Cache 是 3MB）

  • L1 Cache 通常会分为 数据缓存 和 指令缓存 ，这意味着数据和指令在 L1 Cache 这⼀层是分开缓存的，且的存储大小通常是⼀样的。
  • L3 Cache 比 L1 Cache 和 L2 Cache 大很多，这是因为 L1 Cache 和 L2 Cache 都是每个 CPU 核心独有的，而 L3 Cache 是多个 CPU 核心共享的。
程序执行时，会先将内存中的数据加载到 多个 CPU 核心共享的 L3 Cache 中，再加载到 每个核⼼独有的 L2 Cache，最后加载到 L1 Cache，之后才会被CPU读取。
越靠近CPU核心的缓存 其访问速度越快。


2. CPU Cache 的数据结构和读取过程是什么样的？

CPU Cache 的数据 是从内存中读取过来的，⼀小块⼀小块地读取数据。在 CPU Cache 中的，这样⼀小块⼀小块的数据，称为 Cache Line (缓存块)。
在Linux 系统中，可以用如下命令 来查看 CPU的Cache Line：（该服务器的 L1 Cache Line 的大小为 64字节，意味着 L1 Cache ⼀次载入数据的⼤小 是64字节）

举例说明：有⼀个 int array[100] 的数组，当载⼊array[0]时，由于该数组元素在内存中 只占4字节大小 (不足64字节)，CPU就会一次加载数组元素 array[0]~array[15] (顺序加载) 到CPU Cache中。当下次访问这些数组元素时，会直接从CPU Cache中读取，而不用再从内存中读取，从而大大提高了 CPU读取数据的性能。
事实上，CPU读取数据时，无论目标数据是否在Cache中，CPU都会 先访问Cache。只有当Cache中 找不到目标数据时，才会去访问内存，并将内存中的目标数据 读入到Cache中，之后CPU再从 CPU Cache 中读取目标数据。

这样的访问机制与 "使用内存作为硬盘的缓存" 的逻辑是⼀样的。（访问内存时，如果内存中 存有目标数据，则直接返回；否则，则需要去访问 速度很慢的硬盘）

直接映射 Cache：
接下来从最简单、基础的 直接映射Cache，来了解整个 CPU Cache 的数据结构和访问逻辑。
问题：CPU如何知道 要访问的内存数据 是否在Cache中？如果在的话，又如何找到 Cache中对应的数据？
前⾯已经提到， CPU访问内存数据时，是⼀小块⼀小块地读取数据，具体这"一小块数据"的⼤小 取决于coherency_line_size的值，⼀般为64字节。在内存中，这⼀小块的数据称为 内存块 (Block)。（读取内存时，首先需要知道 数据所在内存块的地址）
直接映射Cache 采用的策略，就是将 一个内存块的地址 固定映射到 一个CPU Line(缓存块) 的地址。映射关系的实现⽅式 则是使用 取模运算，取模运算的结果 就是内存块地址对应的 CPU Line(缓存块) 的地址。
举例说明：若内存共被划分为 32个内存块，CPU Cache 共有 8个CPU Line。假设CPU想要访问 第15号内存块，如果15号内存块中的数据 已经缓存在CPU Line中的话，则其⼀定映射在 7号CPU Line(缓存块)中，因为15%8=7。
但还存在一个小问题，使用取模方式映射后，会出现 "多个内存块对应同⼀个CPU Line(缓存块)" 的情况。（上⾯的例中，除了15号内存块 是映射在7号CPU Line中，另外 7号、23号、31号内存块 也都是映射到7号CPU Line中。

因此，为了区别不同的内存块，在对应的CPU Line中 存储了⼀个组标记。这个组标记会记录 当前CPU Line中存储的数据 对应的内存块，使用这个组标记 来区分不同的内存块。
除了组标记外，CPU Line还有两个信息：
  • 数据：从内存中加载过来的 实际存放的数据。
  • 有效位：⽤来标记对应的 CPU Line 中的数据是否是有效的，如果有效位是0，则无论CPU Line中是否有数据，CPU都会直接访问内存，重新加载数据。
CPU 在从 CPU Cache 读取数据的时候，并不是读取CPU Line中的 整个数据块，⽽是读取CPU所需要的 ⼀个数据片段，这样的⼀个数据片段 称为⼀个 字 (Word)。
那么如何在对应的 CPU Line中的数据块中 找到所需的字呢？答案是，需要⼀个 偏移量 (Offset)。
因此，⼀个"内存的访问地址"包含 组标记+CPU Line索引+偏移量 这三个信息。CPU通过这些信息，就能在CPU Cache中 找到缓存的数据。⽽CPU Cache中的数据结构，则是由 索引+有效位+组标记+数据块 这四个信息组成。

如果内存中的数据 已经在CPU Cahe中了，那CPU访问⼀个内存地址时，会经历如下4个步骤：
  1. 根据内存地址中的 索引信息，计算在CPU Cahe中的索引，找出对应的 CPU Line(缓存块) 的地址；
  2. 找到对应CPU Line(缓存块)后，判断CPU Line中的有效位，确认CPU Line中数据是否是有效的。如果数据无效，CPU就会直接访问内存，并重新加载数据；如果数据有效，则往下执⾏；
  3. 对比内存地址中的组标记 和CPU Line中的组标记，确认CPU Line中的数据 是否为要访问的内存数据。如果不是，CPU就会直接访问内存，并重新加载数据；如果是，则往下执⾏；
  4. 根据内存地址中的偏移量信息，从CPU Line(缓存块)中 读取对应的字；
除了直接映射Cache之外，还有其他通过内存地址 找到CPU Cache中的数据 的策略：⽐如 全相连Cache、组相连 Cache 等。

3. 如何写出让 CPU 跑得更快的代码？

CPU访问内存的速度 ⽐访问CPU Cache的速度 慢了100多倍，所以如果CPU所要操作的数据 "常在CPU Cache中"的话，这将会带来很⼤的性能提升。若访问的数据在CPU Cache中，则意味着缓存命中，缓存命中率越⾼的话，代码的性能就会越好，CPU也就跑的越快。
因此，"如何写出让 CPU 跑得更快的代码？" 这个问题，可以改成 "如何写出 CPU 缓存命中率⾼的代码？"。
前⾯提到， L1 Cache通常分为 数据缓存 和 指令缓存，这是因为CPU会 分别处理数据和指令。（例如 1+1=2 这个运算，+就是指令，会被放在指令缓存中；数字1是数据， 会被放在数据缓存中）
因此，我们要分开来看 数据缓存 和 指令缓存 的缓存命中率。

(1) 如何提升 数据缓存 的命中率？
问题：假设要遍历⼆维数组，有以下两种形式，虽然代码执行结果都是⼀样，但哪种形式的效率更⾼呢？为什么更高？

经过测试知，形式一中array[i][j]的执⾏时间 比形式⼆中的array[j][i] 快好几倍。之所以有这么大的差距，是因为二维数组array 所占用的内存 是连续的。
若长度 N 的值为 2，那么内存中的 数组元素的布局顺序 如下所示：

形式一中： array[i][j]访问数组元素的顺序 与内存中数组元素存放的顺序⼀致。当CPU访问array[0][0]时，由于该数据不在Cache 中，于是会顺序地 把array[0][0]与跟随其后的3个元素 从内存中加载到CPUCache中，因此当CPU访问 后⾯的3个数组元素时，就能在CPU Cache中 成功地找到数据。这意味着 缓存命中率很⾼，因为缓存命中的数据 不需要访问内存，从而大大提高了代码的性能。
形式二中：array[j][i]访问数组元素的顺序 如下所示 。

可以看到，array[j][i]的访问方式 是跳跃式的，而不是顺序的。如果N的数值很大，那么读取array[j][i]时，则无法将array[j+1][i] 也读入到CPU Cache中 (因为会先顺序读取 第j维的元素。若N很大时，一次读入就无法读到第j+1维的元素，因为可能第j维的元素 都不能够全读完)，既然array[j+1][i] 没有读入到CPU Cache中，那么就需要 从内存中读取该元素了。这种 不连续、跳跃式 访问数据元素的方式，很可能不能充分利用到 CPU Cache的特性，从而导致代码的性能不高。
访问array[0][0]元素时，CPU具体会⼀次从内存中 加载多少元素到CPU Cache中呢？前面提到过，这跟 CPU Cache Line(缓存块) 有关，它表示CPU Cache⼀次性 能加载数据的大小。
可以在Linux系统中 通过coherency_line_size配置 查看它的大小，通常是 64 个字节。

因此，当CPU访问内存数据时，如果数据不在CPU Cache中，则会⼀次性会连续加载 64字节大小的数据 到CPU Cache。那么当访问array[0][0]时，由于该元素不足64字节，于是就会往后继续 顺序读取array[0][0]~array[0][15] 到CPU Cache中。顺序访问的array[i][j] 利用了 CPU顺序读取 这⼀特点，所以比 跳跃式访问的array[j][i] 要快。
建议：遍历数组时，按照数组的内存布局 顺序访问，能够有效提高 CPU Cache的命中率，代码的性能 就会得到很大的提升。(提升 数据缓存的命中率 的方式就是：按照内存布局顺序访问)


(2) 如何提升 指令缓存 的命中率？
问题：有⼀个 元素为0到100之间的 由随机数组成的 ⼀维数组。对这个数组做两个操作，(1) 循环遍历数组，把小于在50的数组元素 置为0；(2) 将数组排序。是先遍历再排序 速度快，还是先排序再遍历 速度快呢？


在回答这个问题之前，先了解一下 CPU的分支预测器。对于 if 条件语句，意味着至少可以选择 跳转到两段不同的指令执行(if-else)。如果分支预测可以预测到 接下来要执行的指令，是if块中的指令，还是else块中指令，就可以"提前"将这些指令 放在指令缓存中，CPU就可以直接 从Cache中读取到指令，从而加快 程序的执行速度。
当数组中的元素是随机的，分⽀预测就⽆法有效⼯作，⽽当数组元素都是是顺序的，分支预测器会动态地根据 "历史命中的数据" 对未来进行预测，从而提高命中率。

如果可以肯定 代码中if条件为ture的概率 比较⾼，则可以使用显式分支预测工具。比如在C/C++语⾔中 编译器提供了 likely和unlikely 这两种宏，如果if条件为ture的概率⼤，则可以⽤ likely宏 把if中的表达式包裹起来，反之用unlikely宏。

建议：实际上，CPU自身的动态分⽀预测 是比较准的，所以只有当⾮常确信 CPU的预测不准 且知道实际的概率时，才建议使用这两种宏。

(3) 如何提升 多核CPU 的缓存命中率？
  • 在单核CPU中：虽然只能执⾏⼀个进程，但是操作系统给每个进程 分配了⼀个时间片。时间片用完后，就调度下⼀个进程，于是各个进程就按时间片 交替地使用CPU。从宏观上看，进程同时在执行；从微观上看，进程之间是串行的。
  • 在多核CPU中：进程可能在 不同CPU核心之间 来回切换执⾏，这对CPU Cache命中率是不利的的。虽然L3 Cache是多核心之间共享的，但是 L1和L2 Cache 都是每个核心独有的，如果⼀个进程 在不同CPU核心之间 来回切换，各个核心的缓存命中率 就会受到影响。相反，如果进程都在 同⼀个核心上执行，那么其数据的 L1和L2 Cache 的缓存命中率 都可以得到有效提高。（缓存命中率高意味着 CPU可以减少访问内存的频率）
当有多个同时执行的 "计算密集型" 的线程，为了防止出现 因为切换到不同的CPU核心 而导致缓存命中率下降 的问题，我们可以将线程绑定在 某一个CPU核心上，这样性能就可以得到 有效的提升。
Linux系统中，提供了sched_setaffinity方法，来实现 将线程绑定到某个CPU核心 这⼀功能。