泗门网站建设,非凡网站开发培训,金融 网站 模板,各种网站末班前言代码都是由 CPU 跑起来的#xff0c;我们代码写的好与坏就决定了 CPU 的执行效率#xff0c;特别是在编写计算密集型的程序#xff0c;更要注重 CPU 的执行效率#xff0c;否则将会大大影响系统性能。CPU 内部嵌入了 CPU Cache#xff08;高速缓存#xff09;#x… 前言代码都是由 CPU 跑起来的我们代码写的好与坏就决定了 CPU 的执行效率特别是在编写计算密集型的程序更要注重 CPU 的执行效率否则将会大大影响系统性能。CPU 内部嵌入了 CPU Cache高速缓存它的存储容量很小但是离 CPU 核心很近所以缓存的读写速度是极快的那么如果 CPU 运算时直接从 CPU Cache 读取数据而不是从内存的话运算速度就会很快。但是大多数人不知道 CPU Cache 的运行机制以至于不知道如何才能够写出能够配合 CPU Cache 工作机制的代码一旦你掌握了它你写代码的时候就有新的优化思路了。那么接下来我们就来看看CPU Cache 到底是什么样的是如何工作的呢又该写出让 CPU 执行更快的代码呢正文CPU Cache 有多快 你可能会好奇为什么有了内存还需要 CPU Cache根据摩尔定律CPU 的访问速度每 18 个月就会翻倍相当于每年增长 60% 左右内存的速度当然也会不断增长但是增长的速度远小于 CPU平均每年只增长 7% 左右。于是CPU 与内存的访问性能的差距不断拉大。到现在一次内存访问所需时间是 200~300 多个时钟周期这意味着 CPU 和内存的访问速度已经相差 200~300 多倍了。为了弥补 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 这一层是分开缓存的上图中的 index0 也就是数据缓存而 index1 则是指令缓存它两的大小通常是一样的。另外你也会注意到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 只需要 2~4 个时钟周期访问 L2 Cache 大约 10~20 个时钟周期访问 L3 Cache 大约 20~60 个时钟周期而访问内存速度大概在 200~300 个 时钟周期之间。如下表格所以CPU 从 L1 Cache 读取数据的速度相比从内存读取的速度会快 100 多倍。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[15]意味着 array[0]~array[15] 数组元素都会被缓存在 CPU Cache 中了因此当下次访问这些数组元素时会直接从 CPU Cache 读取而不用再从内存中读取大大提高了 CPU 读取数据的性能。事实上CPU 读取数据的时候无论数据是否存放到 Cache 中CPU 都是先访问 Cache只有当 Cache 中找不到数据时才会去访问内存并把内存中的数据读入到 Cache 中CPU 再从 CPU Cache 读取数据。这样的访问机制跟我们使用「内存作为硬盘的缓存」的逻辑是一样的如果内存有缓存的数据则直接返回否则要访问龟速一般的硬盘。那 CPU 怎么知道要访问的内存数据是否在 Cache 里如果在的话如何找到 Cache 对应的数据呢我们从最简单、基础的直接映射 CacheDirect Mapped Cache 说起来看看整个 CPU Cache 的数据结构和访问逻辑。前面我们提到 CPU 访问内存数据时是一小块一小块数据读取的具体这一小块数据的大小取决于 coherency_line_size 的值一般 64 字节。在内存中这一块的数据我们称为内存块Bock读取的时候我们要拿到数据所在内存块的地址。对于直接映射 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 中我们还会存储一个组标记Tag。这个组标记会记录当前 CPU Line 中存储的数据对应的内存块我们可以用这个组标记来区分不同的内存块。除了组标记信息外CPU Line 还有两个信息一个是从内存加载过来的实际存放数据Data。另一个是有效位Valid bit它是用来标记对应的 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 个步骤根据内存地址中索引信息计算在 CPU Cahe 中的索引也就是找出对应的 CPU Line 的地址找到对应 CPU Line 后判断 CPU Line 中的有效位确认 CPU Line 中数据是否是有效的如果是无效的CPU 就会直接访问内存并重新加载数据如果数据有效则往下执行对比内存地址中组标记和 CPU Line 中的组标记确认 CPU Line 中的数据是我们要访问的内存数据如果不是的话CPU 就会直接访问内存并重新加载数据如果是的话则往下执行根据内存地址中偏移量信息从 CPU Line 的数据块中读取对应的字。到这里相信你对直接映射 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 会别处理数据和指令比如 112 这个运算 就是指令会被放在「指令缓存」中而输入数字 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] 来访问则访问的顺序就是你可以看到访问的方式跳跃式的而不是顺序的那么如果 N 的数值很大那么操作 array[j][i] 时是没办法把 array[j1][i] 也读入到 CPU Cache 中的既然 array[j1][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] 因为利用了这一特点所以就会比跳跃式访问的 array[j][i] 要快。因此遇到这种遍历数组的情况时按照内存布局顺序访问将可以有效的利用 CPU Cache 带来的好处这样我们代码的性能就会得到很大的提升如何提升指令缓存的命中率提升数据的缓存命中率的方式是按照内存布局顺序访问那针对指令的缓存该如何提升呢我们以一个例子来看看有一个元素为 0 到 100 之间随机数字组成的一维数组接下来对这个数组做两个操作第一个操作循环遍历数组把小于 50 的数组元素置为 0第二个操作将数组排序那么问题来了你觉得先遍历再排序速度快还是先排序再遍历速度快呢在回答这个问题之前我们先了解 CPU 的分支预测器。对于 if 条件语句意味着此时至少可以选择跳转到两段不同的指令执行也就是 if 还是 else 中的指令。那么如果分支预测可以预测到接下来要执行 if 里的指令还是 else 指令的话就可以「提前」把这些指令放在指令缓存中这样 CPU 可以直接从 Cache 读取到指令于是执行速度就会很快。当数组中的元素是随机的分支预测就无法有效工作而当数组元素都是顺序的分支预测器会动态地根据历史命中数据对未来进行预测这样命中率就会很高。因此先排序再遍历速度会更快这是因为排序之后数字是从小到大的那么前几次循环命中 if 50 的次数会比较多于是分支预测就会缓存 if 里的 array[i] 0 指令到 Cache 中后续 CPU 执行该指令就只需要从 Cache 读取就好了。如果你肯定代码中的 if 中的表达式判断为 true 的概率比较高我们可以使用显示分支预测工具比如在 C/C 语言中编译器提供了 likely 和 unlikely 这两种宏如果 if 条件为 ture 的概率大则可以用 likely 宏把 if 里的表达式包裹起来反之用 unlikely 宏。实际上CPU 自身的动态分支预测已经是比较准的了所以只有当非常确信 CPU 预测的不准且能够知道实际的概率情况时才建议使用这两种宏。如果提升多核 CPU 的缓存命中率在单核 CPU虽然只能执行一个进程但是操作系统给每个进程分配了一个时间片时间片用完了就调度下一个进程于是各个进程就按时间片交替地占用 CPU从宏观上看起来各个进程同时在执行。而现代 CPU 都是多核心的进程可能在不同 CPU 核心来回切换执行这对 CPU Cache 不是有利的虽然 L3 Cache 是多核心之间共享的但是 L1 和 L2 Cache 都是每个核心独有的如果一个进程在不同核心来回切换各个核心的缓存命中率就会受到影响相反如果进程都在同一个核心上执行那么其数据的 L1 和 L2 Cache 的缓存命中率可以得到有效提高缓存命中率高就意味着 CPU 可以减少访问 内存的频率。当有多个同时执行「计算密集型」的线程为了防止因为切换到不同的核心而导致缓存命中率下降的问题我们可以把线程绑定在某一个 CPU 核心上这样性能可以得到非常可观的提升。在 Linux 上提供了 sched_setaffinity 方法来实现将线程绑定到某个 CPU 核心这一功能。总结 由于随着计算机技术的发展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 Cache 是根据 CPU Cache Line 批量操作数据的所以顺序地操作连续内存数据时性能能得到有效的提升对于指令缓存有规律的条件分支语句能够让 CPU 的分支预测器发挥作用进一步提高执行的效率另外对于多核 CPU 系统线程可能在不同 CPU 核心来回切换这样各个核心的缓存命中率就会受到影响于是要想提高进程的缓存命中率可以考虑把线程绑定 CPU 到某一个 CPU 核心。#推荐阅读 专辑|Linux文章汇总 专辑|程序人生 专辑|C语言嵌入式Linux微信扫描二维码关注我的公众号
