如何写出让 CPU 跑得更快的代码?发表时间:2020-10-28 13:19 CPU Cache 有多快?你可能会好奇为什么有了内存,还需要 CPU Cache?根据摩尔定律,CPU 的访问速度每 18 个月就会翻倍,相当于每年增长 60% 左右,内存的速度当然也会不断增长,但是增长的速度远小于 CPU,平均每年只增长 7% 左右。于是,CPU 与内存的访问性能的差距不断拉大。 到现在,一次内存访问所需时间是 为了弥补 CPU 与内存两者之间的性能差异,就在 CPU 内部引入了 CPU Cache,也称高速缓存。 CPU Cache 通常分为大小不等的三级缓存,分别是 L1 Cache、L2 Cache 和 L3 Cache。 由于 CPU Cache 所使用的材料是 SRAM,价格比内存使用的 DRAM 高出很多,在当今每生产 1 MB 大小的 CPU Cache 需要 7 美金的成本,而内存只需要 0.015 美金的成本,成本方面相差了 466 倍,所以 CPU Cache 不像内存那样动辄以 GB 计算,它的大小是以 KB 或 MB 来计算的。 在 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 核心共享的。 程序执行时,会先将内存中的数据加载到共享的 L3 Cache 中,再加载到每个核心独有的 L2 Cache,最后进入到最快的 L1 Cache,之后才会被 CPU 读取。它们之间的层级关系,如下图: 越靠近 CPU 核心的缓存其访问速度越快,CPU 访问 L1 Cache 只需要 所以,CPU 从 L1 Cache 读取数据的速度,相比从内存读取的速度,会快 CPU Cache 的数据结构和读取过程是什么样的?CPU Cache 的数据是从内存中读取过来的,它是以一小块一小块读取数据的,而不是按照单个数组元素来读取数据的,在 CPU Cache 中的,这样一小块一小块的数据,称为 Cache Line(缓存块)。 你可以在你的 Linux 系统,用下面这种方式来查看 CPU 的 Cache Line,你可以看我服务器的 L1 Cache Line 大小是 64 字节,也就意味着 L1 Cache 一次载入数据的大小是 64 字节。 比如,有一个 事实上,CPU 读取数据的时候,无论数据是否存放到 Cache 中,CPU 都是先访问 Cache,只有当 Cache 中找不到数据时,才会去访问内存,并把内存中的数据读入到 Cache 中,CPU 再从 CPU Cache 读取数据。 这样的访问机制,跟我们使用「内存作为硬盘的缓存」的逻辑是一样的,如果内存有缓存的数据,则直接返回,否则要访问龟速一般的硬盘。 那 CPU 怎么知道要访问的内存数据,是否在 Cache 里?如果在的话,如何找到 Cache 对应的数据呢?我们从最简单、基础的直接映射 Cache(Direct Mapped Cache) 说起,来看看整个 CPU Cache 的数据结构和访问逻辑。 前面,我们提到 CPU 访问内存数据时,是一小块一小块数据读取的,具体这一小块数据的大小,取决于 对于直接映射 Cache 采用的策略,就是把内存块的地址始终「映射」在一个 CPU Line(缓存块) 的地址,至于映射关系实现方式,则是使用「取模运算」,取模运算的结果就是内存块地址对应的 CPU Line(缓存块) 的地址。 举个例子,内存共被划分为 32 个内存块,CPU Cache 共有 8 个 CPU Line,假设 CPU 想要访问第 15 号内存块,如果 15 号内存块中的数据已经缓存在 CPU Line 中的话,则是一定映射在 7 号 CPU Line 中,因为 机智的你肯定发现了,使用取模方式映射的话,就会出现多个内存块对应同一个 CPU Line,比如上面的例子,除了 15 号内存块是映射在 7 号 CPU Line 中,还有 7 号、23 号、31 号内存块都是映射到 7 号 CPU Line 中。 因此,为了区别不同的内存块,在对应的 CPU Line 中我们还会存储一个组标记(Tag)。这个组标记会记录当前 CPU Line 中存储的数据对应的内存块,我们可以用这个组标记来区分不同的内存块。 除了组标记信息外,CPU Line 还有两个信息:
CPU 在从 CPU Cache 读取数据的时候,并不是读取 CPU Line 中的整个数据块,而是读取 CPU 所需要的一个数据片段,这样的数据统称为一个字(Word)。那怎么在对应的 CPU Line 中数据块中找到所需的字呢?答案是,需要一个偏移量(Offset)。 因此,一个内存的访问地址,包括组标记、CPU Line 索引、偏移量这三种信息,于是 CPU 就能通过这些信息,在 CPU Cache 中找到缓存的数据。而对于 CPU Cache 里的数据结构,则是由索引 + 有效位 + 组标记 + 数据块组成。 如果内存中的数据已经在 CPU Cahe 中了,那 CPU 访问一个内存地址的时候,会经历这 4 个步骤:
到这里,相信你对直接映射 Cache 有了一定认识,但其实除了直接映射 Cache 之外,还有其他通过内存地址找到 CPU Cache 中的数据的策略,比如全相连 Cache (Fully Associative Cache)、组相连 Cache (Set Associative Cache)等,这几种策策略的数据结构都比较相似,我们理解流直接映射 Cache 的工作方式,其他的策略如果你有兴趣去看,相信很快就能理解的了。 如何写出让 CPU 跑得更快的代码?我们知道 CPU 访问内存的速度,比访问 CPU Cache 的速度慢了 100 多倍,所以如果 CPU 所要操作的数据在 CPU Cache 中的话,这样将会带来很大的性能提升。访问的数据在 CPU Cache 中的话,意味着缓存命中,缓存命中率越高的话,代码的性能就会越好,CPU 也就跑的越快。 于是,「如何写出让 CPU 跑得更快的代码?」这个问题,可以改成「如何写出 CPU 缓存命中率高的代码?」。 在前面我也提到, L1 Cache 通常分为「数据缓存」和「指令缓存」,这是因为 CPU 会别处理数据和指令,比如 因此,我们要分开来看「数据缓存」和「指令缓存」的缓存命中率。 如何提升数据缓存的命中率?假设要遍历二维数组,有以下两种形式,虽然代码执行结果是一样,但你觉得哪种形式效率最高呢?为什么高呢? 经过测试,形式一 之所以有这么大的差距,是因为二维数组 形式一用 而如果用形式二的 你可以看到,访问的方式跳跃式的,而不是顺序的,那么如果 N 的数值很大,那么操作 那访问 接下来,对这个数组做两个操作:
那么问题来了,你觉得先遍历再排序速度快,还是先排序再遍历速度快呢? 在回答这个问题之前,我们先了解 CPU 的分支预测器。对于 if 条件语句,意味着此时至少可以选择跳转到两段不同的指令执行,也就是 if 还是 else 中的指令。那么,如果分支预测可以预测到接下来要执行 if 里的指令,还是 else 指令的话,就可以「提前」把这些指令放在指令缓存中,这样 CPU 可以直接从 Cache 读取到指令,于是执行速度就会很快。 当数组中的元素是随机的,分支预测就无法有效工作,而当数组元素都是顺序的,分支预测器会动态地根据历史命中数据对未来进行预测,这样命中率就会很高。 因此,先排序再遍历速度会更快,这是因为排序之后,数字是从小到大的,那么前几次循环命中 如果你肯定代码中的 实际上,CPU 自身的动态分支预测已经是比较准的了,所以只有当非常确信 CPU 预测的不准,且能够知道实际的概率情况时,才建议使用这两种宏。 如果提升多核 CPU 的缓存命中率?在单核 CPU,虽然只能执行一个进程,但是操作系统给每个进程分配了一个时间片,时间片用完了,就调度下一个进程,于是各个进程就按时间片交替地占用 CPU,从宏观上看起来各个进程同时在执行。 而现代 CPU 都是多核心的,进程可能在不同 CPU 核心来回切换执行,这对 CPU Cache 不是有利的,虽然 L3 Cache 是多核心之间共享的,但是 L1 和 L2 Cache 都是每个核心独有的,如果一个进程在不同核心来回切换,各个核心的缓存命中率就会受到影响,相反如果进程都在同一个核心上执行,那么其数据的 L1 和 L2 Cache 的缓存命中率可以得到有效提高,缓存命中率高就意味着 CPU 可以减少访问 内存的频率。 当有多个同时执行「计算密集型」的线程,为了防止因为切换到不同的核心,而导致缓存命中率下降的问题,我们可以把线程绑定在某一个 CPU 核心上,这样性能可以得到非常可观的提升。 在 Linux 上提供了 总结由于随着计算机技术的发展,CPU 与 内存的访问速度相差越来越多,如今差距已经高达好几百倍了,所以 CPU 内部嵌入了 CPU Cache 组件,作为内存与 CPU 之间的缓存层,CPU Cache 由于离 CPU 核心很近,所以访问速度也是非常快的,但由于所需材料成本比较高,它不像内存动辄几个 GB 大小,而是仅有几十 KB 到 MB 大小。 当 CPU 访问数据的时候,先是访问 CPU Cache,如果缓存命中的话,则直接返回数据,就不用每次都从内存读取速度了。因此,缓存命中率越高,代码的性能越好。 但需要注意的是,当 CPU 访问数据时,如果 CPU Cache 没有缓存该数据,则会从内存读取数据,但是并不是只读一个数据,而是一次性读取一块一块的数据存放到 CPU Cache 中,之后才会被 CPU 读取。 内存地址映射到 CPU Cache 地址里的策略有很多种,其中比较简单是直接映射 Cache,它巧妙的把内存地址拆分成「索引 + 组标记 + 偏移量」的方式,使得我们可以将很大的内存地址,映射到很小的 CPU Cache 地址里。 要想写出让 CPU 跑得更快的代码,就需要写出缓存命中率高的代码,CPU L1 Cache 分为数据缓存和指令缓存,因而需要分别提高它们的缓存命中率:
另外,对于多核 CPU 系统,线程可能在不同 CPU 核心来回切换,这样各个核心的缓存命中率就会受到影响,于是要想提高进程的缓存命中率,可以考虑把线程绑定 CPU 到某一个 CPU 核心。 本文由乌鲁木齐笔记本电脑专卖店整理编辑 转载请注明出处! |