当前位置：首页 > news >正文

cache miss问题C++示例

news 来源：原创 2024/9/21 11:13:13

原题是：

const int LEN = 64*1024*1024;
int *arr = new int[LEN];
for (int i = 0; i < LEN; i += 2) arr[i] *= i; // 循环1
for (int i = 0; i < LEN; i += 8) arr[i] *= i; // 循环2

第二个循环比第一个循环少了四倍的计算量，理论上应该要快4倍，但是实际跑起来的数据，我自己的机器跑出来的数据：

循环1执行时间：339.960 ms循环2执行时间：325.230 ms

两个循环的执行时延相差无几。和我们的想象很不一样，why?

写个小程序验证：

#include <iostream>
#include <ctime>
#include <array> 
using namespace std;
int main()
{const int LEN = 64 * 1024 * 1024;int *a = new int [LEN];cout << "a的长度是" << sizeof(a) << endl;cout << "*a的长度是" << sizeof(*a) << endl;cout << "int 的长度是" << sizeof(int) << endl;for (int i = 0; i < LEN; i += 2){a [i] = i * 3;}clock_t endTime = clock();cout << "程序执行时间为" << (double)endTime / CLOCKS_PER_SEC * 1e3 << "ms" << endl;const int LEN_1 = 64 * 1024;array<int, LEN_1> b;cout << "b的长度 " << b.size() << endl;
}

输出结果是：

a的长度是8
*a的长度是4
int 的长度是4
程序执行时间为270.029ms
b的长度 65536

注意程序执行时间有一定的随机性，大致在270ms附近浮动，此时循环的步长是2。

而将步长改为8后，程序执行时间如下：

a的长度是8
*a的长度是4
int 的长度是4
程序执行时间为217.026ms
b的长度 65536

可以看到，步进是2和8的执行时间的确相差不大。
为此我们测试了以下几组数据，绘制表格大致如下：
在这里插入图片描述

感觉还是不太对，步长到16之后，时间并未出现减半式的下跌。不知道问题出在哪。
原题在以下链接中：
http://igoro.com/archive/gallery-of-processor-cache-effects/

第2天：
原题的答案是和计算机硬件结构直接相关的，《现代操作系统》的第1.3.2节存储器，书中所讲与本题的官方答案基本一致。带着题目看书的过程中，也加深了我对计算机存储结构的理解。所以在这里用自己的话总结一下。
计算机中的典型的存储结构如下图所示：
在这里插入图片描述
计算机的典型存储单元包括寄存器、高速缓存、主存、磁盘。自上而下看，越往下的存储器，从架构上说，其离CPU越远，运行速度越慢，但容量也更大。

第一层的寄存器是最接近CPU的存储器，其材质和CPU一样，所以有着和CPU同样的存取速度。其实也很好理解，因为它要保证CPU指令的正常执行，所以他们一样快就行了。但是其造价昂贵，所以其大小一般就是32 * 32bit = 128B（32位操作系统）或64 * 64bit = 512B（64位操作系统），很明显连1KB都不到。

第二层是高速缓存，或者简称为缓存，它本来是属于主存的一部分，但是它在架构上离CPU更近一些，其每行有64字节数据，称为“高速缓存行”。假设其大小为4MB，则其一共有64 000个高速缓存行。当CPU运行指令所需的数据在高速缓存行中时，称为“命中”。当没有命中时，高速缓存行就需要向总线申请向主存中调取数据。正是因为缓存速度快，所以工程师们又将其分为L1级缓存和L2级缓存。其中L1级缓存没有时延，就类似于寄存器，而L2级缓存会有1-2个时钟周期的时延，但也非常短了。

第三层是主存（内存），也称为RAM(random access memory，随机访问存储器）。我的云桌面的主存就是12G的（本书是2017年及以前更新和编写的，那时的容量可能就只有1-8G），主存里存的东西都是暂时的，当电脑关机后，就丢失了。

第四层是磁盘，这里讲的是盘面会旋转的，带有磁头的机械硬盘，类似于留声机。其实这个也快淘汰了，因为我的Mac电脑里就没有机械硬盘了，取而代之的是固态硬盘（solid state disk，SSD），机械硬盘的读写速度可能只有10M/s，而固态硬盘能达到500M/s。但是它的速度和主存仍然不是一个数量级的。

对于这个题目，程序在运行到声明数组时，是要给他申请内存的，也就是说数组里的数全存在主存里。当CPU运行的乘法指令时，乘法本身很快，因为CPU里有乘法器硬件。但是高速缓存行里没有数组的各个数字。所以此时需要去内存中取，而这个过程叫cache存取。

高速缓存行的长度是64字节，而一个int整型的长度是4个字节，高速缓存行去取数字时，不是每个字节依次取，而是一次性取满整行。所以一个高速缓存行一次可以取16个int整型。

高速缓存行一旦无法命中，则要重新来主存取数。甭管循环步长是1-16之间的任何数字，高速缓存行都得挨个将所有主存的的64M数据都取走，但一旦步长是32时，情况发生了变化，高速缓存行每隔16个int取一次，所以时间缩短了一半。

指令执行的时间很快，而高速缓存行申请内存的过程很耗时间，这就是本题的关键。

通过假设也可以看出来，假设电脑的主频是2G，即在单核单线程单发射的结构的情况下，CPU每秒能运行2G条指令。64M个int字中，假设循环步长是2，则共有32M条指令需要运行，耗费时间是：
在这里插入图片描述
当步长是16时，共有4M就算运行这些指令不需要花时间，那也才比步长为2的快了16ms，但是程序的整体运行时间是300ms+，由此说明，存取数据的时间比指令运行时间长得多，二者不是一个数量级的。