其他
如何写出让 CPU 跑得更快的代码?
The following article is from 小林coding Author 小林coding
来源 | 小林coding
前言
CPU Cache 有多快?
200~300
多个时钟周期,这意味着 CPU 和内存的访问速度已经相差 200~300
多倍了。index0
也就是数据缓存,而 index1
则是指令缓存,它两的大小通常是一样的。2~4
个时钟周期,访问 L2 Cache 大约 10~20
个时钟周期,访问 L3 Cache 大约 20~60
个时钟周期,而访问内存速度大概在 200~300
个 时钟周期之间。如下表格:int array[100]
的数组,当载入 array[0]
时,由于这个数组元素的大小在内存只占 4 字节,不足 64 字节,CPU 就会顺序加载
数组元素到 array[15]
,意味着 array[0]~array[15]
数组元素都会被缓存在 CPU Cache 中了,因此当下次访问这些数组元素时,会直接从 CPU Cache 读取,而不用再从内存中读取,大大提高了 CPU 读取数据的性能。coherency_line_size
的值,一般 64 字节。在内存中,这一块的数据我们称为内存块(Bock)
,读取的时候我们要拿到数据所在内存块的地址。15 % 8
的值是 7。一个是,从内存加载过来的实际存放数据(Data)。 另一个是,有效位(Valid bit),它是用来标记对应的 CPU Line 中的数据是否是有效的,如果有效位是 0,无论 CPU Line 中是否有数据,CPU 都会直接访问内存,重新加载数据。
根据内存地址中索引信息,计算在 CPU Cahe 中的索引,也就是找出对应的 CPU Line 的地址; 找到对应 CPU Line 后,判断 CPU Line 中的有效位,确认 CPU Line 中数据是否是有效的,如果是无效的,CPU 就会直接访问内存,并重新加载数据,如果数据有效,则往下执行; 对比内存地址中组标记和 CPU Line 中的组标记,确认 CPU Line 中的数据是我们要访问的内存数据,如果不是的话,CPU 就会直接访问内存,并重新加载数据,如果是的话,则往下执行; 根据内存地址中偏移量信息,从 CPU Line 的数据块中,读取对应的字。
如何写出让 CPU 跑得更快的代码?
1+1=2
这个运算,+
就是指令,会被放在「指令缓存」中,而输入数字 1
则会被放在「数据缓存」里。如何提升数据缓存的命中率?
array[i][j]
执行时间比形式二 array[j][i]
快好几倍。array
所占用的内存是连续的,比如长度 N
的指是 2
的话,那么内存中的数组元素的布局顺序是这样的:array[i][j]
访问数组元素的顺序,正是和内存中数组元素存放的顺序一致。当 CPU 访问 array[0][0]
时,由于该数据不在 Cache 中,于是会「顺序」把跟随其后的 3 个元素从内存中加载到 CPU Cache,这样当 CPU 访问后面的 3 个数组元素时,就能在 CPU Cache 中成功地找到数据,这意味着缓存命中率很高,缓存命中的数据不需要访问内存,这便大大提高了代码的性能。array[j][i]
来访问,则访问的顺序就是:array[j][i]
时,是没办法把 array[j+1][i]
也读入到 CPU Cache 中的,既然 array[j+1][i]
没有读取到 CPU Cache,那么就需要从内存读取该数据元素了。很明显,这种不连续性、跳跃式访问数据元素的方式,可能不能充分利用到了 CPU Cache 的特性,从而代码的性能不高。array[0][0]
元素时,CPU 具体会一次从内存中加载多少元素到 CPU Cache 呢?这个问题,在前面我们也提到过,这跟 CPU Cache Line 有关,它表示 CPU Cache 一次性能加载数据的大小,可以在 Linux 里通过 coherency_line_size
配置查看 它的大小,通常是 64 个字节。array[0][0]
时,由于该元素不足 64 字节,于是就会往后顺序读取 array[0][0]~array[0][15]
到 CPU Cache 中。顺序访问的 array[i][j]
因为利用了这一特点,所以就会比跳跃式访问的 array[j][i]
要快。如何提升指令缓存的命中率?
第一个操作,循环遍历数组,把小于 50 的数组元素置为 0; 第二个操作,将数组排序;
if < 50
的次数会比较多,于是分支预测就会缓存 if
里的 array[i] = 0
指令到 Cache 中,后续 CPU 执行该指令就只需要从 Cache 读取就好了。if
中的表达式判断为 true
的概率比较高,我们可以使用显示分支预测工具,比如在 C/C++ 语言中编译器提供了 likely
和 unlikely
这两种宏,如果 if
条件为 ture
的概率大,则可以用 likely
宏把 if
里的表达式包裹起来,反之用 unlikely
宏。如果提升多核 CPU 的缓存命中率?
sched_setaffinity
方法,来实现将线程绑定到某个 CPU 核心这一功能。对于数据缓存,我们在遍历数据的时候,应该按照内存布局的顺序操作,这是因为 CPU Cache 是根据 CPU Cache Line 批量操作数据的,所以顺序地操作连续内存数据时,性能能得到有效的提升; 对于指令缓存,有规律的条件分支语句能够让 CPU 的分支预测器发挥作用,进一步提高执行的效率;
end
雷军坚持了 10 年的东西
现在彻底凉了
推荐阅读: