防止断更 请务必加首发微信：1716 143665
关闭
讲堂
部落
Python 进阶训练营
算法训练营
架构师训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
01 | CPU缓存：怎样写代码能够让CPU执行得更快？
2020-04-27 陶辉
系统性能调优必知必会
进入课程
讲述：陶辉
时长13:48大小11.07M
你好，我是陶辉。
这是课程的第一讲，我们先从主机最重要的部件 CPU 开始，聊聊如何通过提升 CPU 缓存的命中率来优化程序的性能。
任何代码的执行都依赖 CPU，通常，使用好 CPU 是操作系统内核的工作。然而，当我们编写计算密集型的程序时，CPU 的执行效率就开始变得至关重要。由于 CPU 缓存由更快的 SRAM 构成（内存是由 DRAM 构成的），而且离 CPU 核心更近，如果运算时需要的输入数据是从 CPU 缓存，而不是内存中读取时，运算速度就会快很多。所以，了解 CPU 缓存对性能的影响，便能够更有效地编写我们的代码，优化程序性能。
然而，很多同学并不清楚 CPU 缓存的运行规则，不知道如何写代码才能够配合 CPU 缓存的工作方式，这样，便放弃了可以大幅提升核心计算代码执行速度的机会。而且，越是底层的优化，适用范围越广，CPU 缓存便是如此，它的运行规则对分布式集群里各种操作系统、编程语言都有效。所以，一旦你能掌握它，集群中巨大的主机数量便能够放大优化效果。
接下来，我们就看看，CPU 缓存结构到底是什么样的，又该如何优化它？
CPU 的多级缓存
刚刚我们提到，CPU 缓存离 CPU 核心更近，由于电子信号传输是需要时间的，所以离 CPU 核心越近，缓存的读写速度就越快。但 CPU 的空间很狭小，离 CPU 越近缓存大小受到的限制也越大。所以，综合硬件布局、性能等因素，CPU 缓存通常分为大小不等的三级缓存。
CPU 缓存的材质 SRAM 比内存使用的 DRAM 贵许多，所以不同于内存动辄以 GB 计算，它的大小是以 MB 来计算的。比如，在我的 Linux 系统上，离 CPU 最近的一级缓存是 32KB，二级缓存是 256KB，最大的三级缓存则是 20MB（Windows 系统查看缓存大小可以用 wmic cpu 指令，或者用CPU-Z这个工具）。
你可能注意到，三级缓存要比一、二级缓存大许多倍，这是因为当下的 CPU 都是多核心的，每个核心都有自己的一、二级缓存，但三级缓存却是一颗 CPU 上所有核心共享的。
程序执行时，会先将内存中的数据载入到共享的三级缓存中，再进入每颗核心独有的二级缓存，最后进入最快的一级缓存，之后才会被 CPU 使用，就像下面这张图。
缓存要比内存快很多。CPU 访问一次内存通常需要 100 个时钟周期以上，而访问一级缓存只需要 4~5 个时钟周期，二级缓存大约 12 个时钟周期，三级缓存大约 30 个时钟周期（对于 2GHZ 主频的 CPU 来说，一个时钟周期是 0.5 纳秒。你可以在 LZMA 的Benchmark中找到几种典型 CPU 缓存的访问速度）。
如果 CPU 所要操作的数据在缓存中，则直接读取，这称为缓存命中。命中缓存会带来很大的性能提升，因此，我们的代码优化目标是提升 CPU 缓存的命中率。
当然，缓存命中率是很笼统的，具体优化时还得一分为二。比如，你在查看 CPU 缓存时会发现有 2 个一级缓存（比如 Linux 上就是上图中的 index0 和 index1），这是因为，CPU 会区别对待指令与数据。比如，“1+1=2”这个运算，“+”就是指令，会放在一级指令缓存中，而“1”这个输入数字，则放在一级数据缓存中。虽然在冯诺依曼计算机体系结构中，代码指令与数据是放在一起的，但执行时却是分开进入指令缓存与数据缓存的，因此我们要分开来看二者的缓存命中率。
提升数据缓存的命中率
我们先来看数据的访问顺序是如何影响缓存命中率的。
int array[N][N];
你可以思考一下，用 array[j][i]和 array[i][j]访问数组元素，哪一种性能更快？
for(i = 0; i < N; i+=1) {
for(j = 0; j < N; j+=1) {
array[i][j] = 0;
}
}
在我给出的 GitHub 地址上的 C++ 代码实现中，前者 array[j][i]执行的时间是后者 array[i][j]的 8 倍之多（请参考traverse_2d_array.cpp，如果使用 Python 代码，traverse_2d_array.py 由于数组容器的差异，性能差距不会那么大）。
为什么会有这么大的差距呢？这是因为二维数组 array 所占用的内存是连续的，比如若长度 N 的值为 2，那么内存中从前至后各元素的顺序是：
array[0][0]，array[0][1]，array[1][0]，array[1][1]。
如果用 array[i][j]访问数组元素，则完全与上述内存中元素顺序一致，因此访问 array[0][0]时，缓存已经把紧随其后的 3 个元素也载入了，CPU 通过快速的缓存来读取后续 3 个元素就可以。如果用 array[j][i]来访问，访问的顺序就是：
array[0][0]，array[1][0]，array[0][1]，array[1][1]
此时内存是跳跃访问的，如果 N 的数值很大，那么操作 array[j][i]时，是没有办法把 array[j+1][i]也读入缓存的。
到这里我们还有 2 个问题没有搞明白：
为什么两者的执行时间有约 7、8 倍的差距呢？
载入 array[0][0]元素时，缓存一次性会载入多少元素呢？
其实这两个问题的答案都与 CPU Cache Line 相关，它定义了缓存一次载入数据的大小，Linux 上你可以通过 coherency_line_size 配置查看它，通常是 64 字节。
因此，我测试的服务器一次会载入 64 字节至缓存中。当载入 array[0][0]时，若它们占用的内存不足 64 字节，CPU 就会顺序地补足后续元素。顺序访问的 array[i][j]因为利用了这一特点，所以就会比 array[j][i]要快。也正因为这样，当元素类型是 4 个字节的整数时，性能就会比 8 个字节的高精度浮点数时速度更快，因为缓存一次载入的元素会更多。
因此，遇到这种遍历访问数组的情况时，按照内存布局顺序访问将会带来很大的性能提升。
再来看为什么执行时间相差 8 倍。在二维数组中，其实第一维元素存放的是地址，第二维存放的才是目标元素。由于 64 位操作系统的地址占用 8 个字节（32 位操作系统是 4 个字节），因此，每批 Cache Line 最多也就能载入不到 8 个二维数组元素，所以性能差距大约接近 8 倍。（用不同的步长访问数组，也能验证 CPU Cache Line 对性能的影响，可参考我给你准备的Github上的测试代码）。
关于 CPU Cache Line 的应用其实非常广泛，如果你用过 Nginx，会发现它是用哈希表来存放域名、HTTP 头部等数据的，这样访问速度非常快，而哈希表里桶的大小如 server_names_hash_bucket_size，它默认就等于 CPU Cache Line 的值。由于所存放的字符串长度不能大于桶的大小，所以当需要存放更长的字符串时，就需要修改桶大小，但 Nginx 官网上明确建议它应该是 CPU Cache Line 的整数倍。
为什么要做这样的要求呢？就是因为缓存是按照 64 字节的整数倍来访问内存的，哈希表的桶按此大小排列布局，就可以尽量减少访问内存的次数。比如，若桶大小为 64 字节，那么根据地址获取字符串时只需要访问一次内存，而桶大小为 50 字节，会导致最坏 2 次访问内存，而 70 字节最坏会有 3 次访问内存。
如果你在用 Linux 操作系统，可以通过一个名叫 Perf 的工具直观地验证缓存命中的情况（可以用 yum install perf 或者 apt-get install perf 安装这个工具，这个网址中有大量案例可供参考）。
执行 perf stat 可以统计出进程运行时的系统信息（通过 -e 选项指定要统计的事件，如果要查看三级缓存总的命中率，可以指定缓存未命中 cache-misses 事件，以及读取缓存次数 cache-references 事件，两者相除就是缓存的未命中率，用 1 相减就是命中率。类似的，通过 L1-dcache-load-misses 和 L1-dcache-loads 可以得到 L1 缓存的命中率），此时你会发现 array[i][j]的缓存命中率远高于 array[j][i]。
当然，perf stat 还可以通过指令执行速度反映出两种访问方式的优劣，如下图所示（instructions 事件指明了进程执行的总指令数，而 cycles 事件指明了运行的时钟周期，二者相除就可以得到每时钟周期所执行的指令数，缩写为 IPC。如果缓存未命中，则 CPU 要等待内存的慢速读取，因此 IPC 就会很低。array[i][j]的 IPC 值也比 array[j][i]要高得多）：
提升指令缓存的命中率
说完数据的缓存命中率，再来看指令的缓存命中率该如何提升。
我们还是用一个例子来看一下。比如，有一个元素为 0 到 255 之间随机数字组成的数组：
int array[N];
for (i = 0; i < TESTN; i++) array[i] = rand() % 256;
接下来要对它做两个操作：一是循环遍历数组，判断每个数字是否小于 128，如果小于则把元素的值置为 0；二是将数组排序。那么，先排序再遍历速度快，还是先遍历再排序速度快呢？
for(i = 0; i < N; i++) {
if (array [i] < 128) array[i] = 0;
}
sort(array, array +N);
我先给出答案：先排序的遍历时间只有后排序的三分之一（参考 GitHub 中的branch_predict.cpp 代码）。为什么会这样呢？这是因为循环中有大量的 if 条件分支，而 CPU含有分支预测器。
当代码中出现 if、switch 等语句时，意味着此时至少可以选择跳转到两段不同的指令去执行。如果分支预测器可以预测接下来要在哪段代码执行（比如 if 还是 else 中的指令），就可以提前把这些指令放在缓存中，CPU 执行时就会很快。当数组中的元素完全随机时，分支预测器无法有效工作，而当 array 数组有序时，分支预测器会动态地根据历史命中数据对未来进行预测，命中率就会非常高。
究竟有多高呢？我们还是用 Linux 上的 perf 来做个验证。使用 -e 选项指明 branch-loads 事件和 branch-load-misses 事件，它们分别表示分支预测的次数，以及预测失败的次数。通过 L1-icache-load-misses 也能查看到一级缓存中指令的未命中情况。
C/C++ 语言中编译器还给应用程序员提供了显式预测分支概率的工具，如果 if 中的条件表达式判断为“真”的概率非常高，我们可以用 likely 宏把它括在里面，反之则可以用 unlikely 宏。当然，CPU 自身的条件预测已经非常准了，仅当我们确信 CPU 条件预测不会准，且我们能够知晓实际概率时，才需要加入这两个宏。
if (likely(a == 1)) …
提升多核 CPU 下的缓存命中率
前面我们都是面向一个 CPU 核心谈数据及指令缓存的，然而现代 CPU 几乎都是多核的。虽然三级缓存面向所有核心，但一、二级缓存是每颗核心独享的。我们知道，即使只有一个 CPU 核心，现代分时操作系统都支持许多进程同时运行。这是因为操作系统把时间切成了许多片，微观上各进程按时间片交替地占用 CPU，这造成宏观上看起来各程序同时在执行。
因此，若进程 A 在时间片 1 里使用 CPU 核心 1，自然也填满了核心 1 的一、二级缓存，当时间片 1 结束后，操作系统会让进程 A 让出 CPU，基于效率并兼顾公平的策略重新调度 CPU 核心 1，以防止某些进程饿死。如果此时 CPU 核心 1 繁忙，而 CPU 核心 2 空闲，则进程 A 很可能会被调度到 CPU 核心 2 上运行，这样，即使我们对代码优化得再好，也只能在一个时间片内高效地使用 CPU 一、二级缓存了，下一个时间片便面临着缓存效率的问题。
因此，操作系统提供了将进程或者线程绑定到某一颗 CPU 上运行的能力。如 Linux 上提供了 sched_setaffinity 方法实现这一功能，其他操作系统也有类似功能的 API 可用。我在 GitHub 上提供了一个示例程序（代码见这里），你可以看到，当多线程同时执行密集计算，且 CPU 缓存命中率很高时，如果将每个线程分别绑定在不同的 CPU 核心上，性能便会获得非常可观的提升。Perf 工具也提供了 cpu-migrations 事件，它可以显示进程从不同的 CPU 核心上迁移的次数。
小结
今天我给你介绍了 CPU 缓存对程序性能的影响。这是很底层的性能优化，它对各种编程语言做密集计算时都有效。
CPU 缓存分为数据缓存与指令缓存，对于数据缓存，我们应在循环体中尽量操作同一块内存上的数据，由于缓存是根据 CPU Cache Line 批量操作数据的，所以顺序地操作连续内存数据时也有性能提升。
对于指令缓存，有规律的条件分支能够让 CPU 的分支预测发挥作用，进一步提升执行效率。对于多核系统，如果进程的缓存命中率非常高，则可以考虑绑定 CPU 来提升缓存命中率。
思考题
最后请你思考下，多线程并行访问不同的变量，这些变量在内存布局是相邻的（比如类中的多个变量），此时 CPU 缓存就会失效，为什么？又该如何解决呢？欢迎你在留言区与大家一起探讨。
感谢阅读，如果你觉得这篇文章对你有一些启发，也欢迎把它分享给你的朋友。
© 加微信：642945106 发送“赠送”领取赠送精品课程 发数字“2”获取众筹列表。
上一篇
开篇词 | 万变不离其宗，性能优化也有章可循
下一篇
02 | 内存池：如何提升内存分配的效率？
写留言
1716143665 拼课微信(31)
2020-04-27因为在多核CPU时代，CPU有“缓存一致性”原则，也就是说每个处理器（核）都会通过嗅探在总线上传播的数据来检查自己的缓存值是不是过期了。如果过期了，则失效。比如声明volitate，当变量被修改，则会立即要求写入系统内存。展开作者回复: 讲得非常好！忆水寒同学对底层知识理解地很透彻！
14
2020-04-27一片连续的内存被加载到不同cpu核心中（就是同一个cache line在不同的cpu核心），其中一个cpu核心中修改cache line,其它核心都失效，加锁也是加在cache line上，其它核心线程也被锁住，降低了性能。解决办法是填充无用字节数，使分开展开作者回复: 完全正确！二星球同学用过填充法写代码么？或者看到过这样的开源代码？
3 7
2020-04-27思考题：
数据从内存加载到高速缓存中，以块为基本单元（一个块64字节），相邻的两个变量很可能在同一块中，当这个数据块分别加载到两颗cpu的高速缓存中时，只要一个cpu对该块（高速缓存中缓存的块）进行写操作，那么另一cpu缓存的该块将失效。
可以通过将两个变量放到不同的缓存块中，来解决这个问题展开 3 5
2020-04-27第一篇就进入知识盲区了展开作者回复: 你好海罗，这门课虽然只有30讲，但会涵盖绝大部分性能优化点，所以每篇文章都会涉及不同的知识。这一篇我希望你能明白CPU缓存的用途，这是成为高手必须了解的知识。
比如，我在protobuf那一讲中，还会讲到protobuf是怎么利用缓存的。所以，你可以先有这么一个概念，在后续用到的时候，再回过头来看，就更容易理解了。 4- 2020-04-28此时内存是跳跃访问的，如果 N 的数值很大，那么操作 array[j][i]时，是没有办法把 array[j][i+1]也读入缓存的。
---------------------------------------------------------------------------------------------
老师是不是写错了，应该是”那么操作 array[j][i]时，是没有办法把 array[j+1][i]（而不是array[j][i+1]）也读入缓存的。”展开作者回复: 你好赖阿甘，你读得很仔细，完全正确，我笔误啦，非常感谢你的提醒，稍候我会联系编辑小姐姐更正的。
1 3 - 2020-04-27这个文章其实讲解的很细致，来龙去脉都说清楚了。不错！
其实每篇文章能讲到这个地步，作为读者（也可以称为学生）每篇能够学到一个哪怕很小的知识点，那也是值得的。展开作者回复: 最初这篇文章有6千字，想在一篇文章中讲清楚CPU缓存太难啦，后来编辑小姐姐协助我一点点删下来，还是担心读者看不懂，找不到重点。
忆水寒同学的知识很扎实，你点赞我就放心啦^_^。 1 2 
2020-04-27陶老师我们集群有一个问题，某一台物理机的CPU会被Hadoop yarn的查询任务打满，并且占用最多的pid在不停的变化，我查看了TIME_WAIT的个数好像也不是很多，在顶峰的时候还没达到一万，能够持续一两个小时。这个问题您有没有什么思路呢？展开作者回复: 解决性能问题，一般有两种方法：经验派和“理论”派，前者就是基于自己的经验概率，将能想到的优化方法都试一遍，这种方式通常又有效又快速，但无法解决复杂的问题。
所谓理论派，就是沿着固定的思路，使用二分法，从高至低慢慢下沉到细节。具体到你的问题，我建议你先看看，CPU占用是用户态还是系统态，用户态的话就要分析代码了，系统态还要进一步分析。火焰图通常是个很好的办法，虽然搭能画火焰图的环境很麻烦，但这种底层方法很有效的。 2 2
2020-04-28对比开篇树图，numa架构貌似还没说，后续会提到吗？作者回复: 你好Oliver，第1讲的初稿是有提的，但因为numa架构其实是讲访问非本地主存时，性能的降低问题，所以与CPU缓存关系不太直接，后面删除了。本来后面也不会再提到，不过中间有个10道面试题，我跟编辑商量下能不能放在那里提下。
1
2020-04-28思考题猜测是False sharing导致的，非常热的数据最好cache line对齐。作者回复: 是的，好吃不贵的答案更加简洁！
1
2020-04-28https://zxs.io/s/o 我之前写过一篇博客详细介绍了cpu分支预测和性能差异，有兴趣可以参考下。作者回复: 谢谢分享！
1
2020-04-27前几天学习了一下计算机组成原理。大部分都能听懂，开心~~~
本节讲到的性能优化实际上是涉及到了计算机组成原理中的【内存的局部性原理】以及【cpu的分支预测】。
对于课后的问题，因为多线程操作某些共享变量，涉及到变量的有效性问题（是否过期），如果变量在一个线程被修改，其他核心中的缓存失效啦。其他线程调用该变量的时候会从内存中重新加载到缓存。
所谓的如何解决，应该是解决缓存失效和保持数据一致性的问题，应该满足两点：
1. 写传播，即通知其他核心，某个缓存失效，需要从内存读取一下
2. 保证事务串行化，事务请求的顺序不能变化
我看资料了解到解决方案是基于总线嗅探机制的MESI协议来解决数据一致性问题。
在Java中，volatile 会确保我们对于这个变量的读取和写入，都一定会同步到主内存里，而不是从 Cache 里面读取，保证了数据一致性问题。
这是我最近学习计算机组成原理后见解，不知道自己理解的有没有问题。有问题希望陶辉老师指正一下。展开作者回复: 你好ByiProX，能够从留言中感受到你最近的进步，非常棒！ 你的理解都是正确的，关于思考题你可以看下二星球的留言，他说得很清楚^_^
1 1
2020-04-27老师代码准备的真多！
思考题有同学已经回答的非常准确了。
虽然已经看过了 linux性能优化 计算机组成原理 和 性能工程高手课 ，但看起老师的文章还是很有意思。
一些知识也加深了印象。
perf工具看来是要找个时间好好看看了。
最早是在linux性能优化专栏看到用到，今天在一篇公众号上看别人用这个快速定位了线上有问题的死循环函数，今天老师又提到了用它看命中率。
工具用好了真的是方便，lsof之前也没用过，后来用了几次觉得非常好用，现在就经常用了。展开作者回复: 我来也同学每篇必有留言被编辑小姐姐选为精品，^_^
perf没有侵入性，使用简单，效果非常棒，值得你投入精力好好学一学！ 1
2020-04-28配置 nginx server_names_bucket_siz 的大小
而桶大小为 50 字节，会导致最坏 2 次访问内存，而 70 字节最坏会有 3 次访问内存。
----------------------------------------------------
为什么 50字节会访问2次内存呢？ 不是可以加载 64k数据到缓存，包含了 50个字节，一次不就够了吗？
70k 也是同样的问题，为什么是3次啊展开
2020-04-28这是因为在多处理器开发中为了保证共享变量的“可见性”。比如声明了volitate的变量，会向处理器发送一条Lock指令。Lock指令会将处理器缓存行中的数据刷回内存，并使其他cpu核心存储了该内存地址的缓存行失效。展开
2020-04-28不同线程使用的CPU核心会存在差异，虽然访问的都是同一块连续的变量，但是仅仅只是其中的一个，将后面连续的变量读入缓存没有任何的作用。
另外就算是在同一个cpu上运行的不同线程，访问变量大概率也是有跳跃性的，所以缓存基本就失效了。
不知道理解对不对，请老师指正展开
2020-04-28老师，思考题您最后会给一个“官方”的答案吗？展开作者回复: 你好走马，会的，不过目前二星球的答案已经非常准确啦
2020-04-28要学的课程太多了，一入IT深似海。展开作者回复: 哈哈，不是说，咱们这行业只看能力，学历、专业都不看的，要想保持目前IT行业相对其他行业的高薪资，就得提升入行门槛啊^_^
2020-04-28回答完问题，从文章整体的角度又简单理解一下，有些疑惑:
1，关于cpu缓存这块儿老师重点剖析了一级缓存的数据缓存和指令缓存，简单来说呢，数据缓存的大体意思就是尽量访问同一块内存上数据；指令缓存呢就是尽量像cpu的分支预测上面靠。这两个点呢，感觉还是比较薄，要达到这种预期，实际情况下也需要注意一些基础的编程规范。当然可能是我理解的比较浅显哈！请问老师在一级缓存这块儿，还有什么大神级的骚操作吗？毕竟这篇专栏的题目是怎样写代码才……
2，关于cpu二级缓存,三级缓存的优化还会聊到吗？展开- 2020-04-28这应该是涉及并发编程要解决的可见性问题吧，虽说被缓存了(还是相邻的)，但是为了保证可见性的话这种缓存也是不可用的。所以如果要保证并发安全也只能是按需禁用缓存了
2020-04-28设置cpu亲和性的时候，如果不同线程处于不同CPU，而又有需要共享的变量，线程切换的时候会造成cache miss，重新加载，性能反而下降。展开 2
