同一块内存，连续两次memset，耗时相差4倍！

SMT技术分享

大家好，我是江南一散人，本文是程序性能调优系列专题第六篇。
本专题除讲解常见性能问题以及分析、调优手段外，还会重点讲解一些对系统性能至关重要，却又经常被忽视的高级话题，如Cache、指令流水线、Superscalar、SIMD、分支预测、内存屏障等。此外，还会涉及到编译器、操作系统等话题。
有这么一道题:

vyvrxq2ntjy64014916530.png

问：
1. 三次memset()的性能有差异吗？
2. 为什么？
3. 如何调优？
[/ol]该如何回答呢？
先简单验证下这三次memset()的性能到底有没有差异。
测试代码代码很简单，申请一块内存，连续三次调用memset()，并且测量这三次memset()的耗时：

odsdk5fwpcy64014916630.png

编译运行一下：

ezpkqaue4vl64014916730.png

第一次memset()耗时约0.66秒，第二次和第三次耗时0.17秒，这是为什么呢？
内容提要本文会详细分析这三次memset()的性能差异的原因，并给出优化方案，最终使得三次memset的性能基本一致，结果如下：

o0gznhpujze64014916830.png

在解释这三次memset()的性能差异以及优化方案之前，需要先介绍一些关于内存管理的基础知识。
虚拟地址我们知道，应该程序只能看到虚拟地址，必须要先转换成物理地址，然后才能通过地址总线访问到物理内存。
那么，虚拟地址是怎么转换为物理地址的呢？
这个过程有点抽象，且比较复杂，为了方便理解，先举一个例子吧。
注：对MMU不熟悉的童鞋，建议仔细理解一下这个例子，能够很好地帮助理解下文要讲的地址转换过程。如果你已经很熟悉的话，可以跳过，直接看后面的原因分析和优化方法。
实例：设计一个学号查询系统假设，我们要设计一个学号查询系统，给全国所有的大、中、小学生分配一个全国唯一的学号，给定一个学号能够立即对应到具体的学生。再假设，要求我们必须用一个48bit的数字来表示这个学号。
我们可以这样设计学生学号：用9个bit表示省份，9个bit表示城市，9个bit表示区县，9个bit表示学校，12个bit表示学生在学校内的编号。如下图所示：

ug0wp0pwmlw64014916930.png

接下来，我们来设计这个查询系统。经分析，我们需要至少5种表，分别是：
? 省份表：包含所有的省份，一个省份对应一个表项，每个表项是一个指针，指向本省的城市表
? 城市表：每个省都有一个自己的城市表，包含本省所有的城市，一个城市对应一个表项，每个表项是一个指针，指向本市的区县表
? 区县表：每个市都有一个自己的区县表，包含本市所有的县/区，每个区县对应一个表项，每个表项是一个指针，指向本县/区内的学校表
? 学校表：每个县/区都有一个学校表，包含本县/区内所有的大、中、小学，每个学校对应一个表项，每个表项是一个指针，指向本学校的学生表
? 学生表：包含一个学校内的所有的学生，每个表项是一个特定的学生。
现在，给定一个学号：0x010203040506，我们可以立即根据这个学号找到对应的学生，如下图所示：

vsmg0m13pcp64014917030.png

简单解释一下这个过程：
0. 我们把省份表存放在固定的一个地方，称之为全局表指针，每次查询时直接从这里获取省份表
1. 根据省份索引在省份表中找到了浙江省的城市表
2. 根据城市索引在城市表中找到了杭州市的区县表
3. 根据区县索引在区县表中找到了西湖区的学校表
4. 根据学校索引在学校表中找到了浙江大学的学生表
5. 根据学生校内编号在学生表中找到了对应的学生，张三
[/ol]这个过程是不是很简单？给定任意一个学号，我们立刻可以对应到：A省B市C区D学校的学生E。
不过，虽然这个查询过程很简单，但是每次都要查询5张表才能找到具体的某个学生，这样效率太低了。有没有什么办法可以提高整体查询效率呢？
性能优化：引入快表经过统计研究，我们发现一个很重要的规律：如果我们查询了一个学生，我们通常会很快再次查询这个学生，或者同一个学校的其他学生。
于是，我们又设计了一张新的表，称为快表，把我们最近查询的学生所在的学校对应的学生表直接记录下来，那么下次在查询同一个学校的学生的时候，就可以从快表中直接取到学生表，然后从中找到对应的学生。
比如，我们刚刚查询了学号0x010203040506，也就是浙江省杭州市西湖区浙江大学的张三，于是我们在快查表中记录这么一个表项：
0x01020304->浙江大学学生表然后，我们又查询学号0x010203047777，先用学校信息0x01020304在快表里查询，发现对应浙江大学的表项，于是直接取得浙江大学的学生表，然后用后面的学生编码0x7777找到浙江大学的学生李四。可见，这个过程比从省表、市表、区县表、学校表逐级查询要快很多。
现在，我们查询另外一个学号0x050903016666，同样，先用学校信息0x05090301在快表里查找，没找到对应学校的表项，于是必须逐级从省表、市表、区县表、学校表里逐级查询，最后找到：江苏省南京市栖霞区南京大学的小明。于是，在快表中再加入一条记录：
0x01020304->浙江大学学生表
0x05090301->南京大学学生表现在，快表中有浙江大学和南京大学的两条记录了，之后再查询这两个学校的学生时，就可以直接从快表中取得学生表，然后快速定位到具体的学生。
不过，快表的容量很小，最多只能容纳5个学校的记录，当快表被填满时，就要用新的信息把旧的记录替换掉，这样一来，下次再查询旧信息对应学校的学生时，就必须要逐级查询了。
Finally！终于把这个有点蹩脚的例子讲完了，居然占了这么大的篇幅。。。不知是否看明白了呢？
啰里啰唆了半天，这个学号查询系统，跟虚拟地址到物理地址的转换，到底有什么关系呢？
MMU(Memory Management Unit)从虚拟地址到物理地址的转换，是由CPU内部一个专门的部件自动完成的，也就是MMU(Memory Management Unit)。
MMU以Page为单位进行虚拟地址和物理地址的映射，所谓一个Page，就是一块地址连续的内存，不同的CPU，支持的Page大小不同。以x64为例，CPU支持4KB、2MB、1GB大小的Page，但目前大部分系统上默认使用4KB的Page，如Linux。
如果把虚拟地址比作学生学号的话，那么物理地址就是具体的某个学生，而MMU就是我们上面设计的学生ID查询系统。MMU把虚拟地址转换成物理地址的过程，与学生学号对应到具体学生的过程，是非常相似的。
下面以X64 CPU为例进行讲解。X64虽然理论地址宽度是64bit，但目前大部分CPU只支持48bit共256TB的虚拟地址空间。对于4KB大小的页面，MMU采用4级页表进行地址转换，分别是：
? PML4(Page Map Level 4)，第4级页映射表，每个表项指向一个PDPT
? PDPT(Page Directory Pointer Table)，页目录指针表，每个表项指向一个PDT
? PDT(Page Directory Table)，页目录表，每个表项指向一个PT
? PT(Page Table)，页表，每个表项指向一个物理页面
和学生学号一样，48bit的有效虚拟地址被划分成了5部分：
? 9bit PML4索引
? 9bit PDPT索引
? 9bit PDT索引
? 9bit PT索引
? 12bit 页内偏移

ekqkvpmk2aq64014917130.png

给定一个虚拟地址0x010203040506，转换为物理地址过程如下图所示：

3m22gmlttbf64014917230.png

这个过程和上文讲的学号对应到具体学生的例子非常相似。解释下这个过程：
0. 从CR3寄存器中取得PML4表的地址。
1. 根据虚拟地址中的PML4索引字段，在PML4中找到对应的表项PML4E，指向PDPT的地址。
2. 根据PDPT索引，在PDPT中找到对应的表项PDPTE，指向PDT的地址。
3. 根据PDT索引，在PDT中找到对应的表项PDTE，指向PT的地址。
4. 根据PT索引，在PT中找到对应的表项PTE，指向一个物理页面的地址。
5. 获取到物理页的地址后，再加上页内偏移，就取得了最终的物理地址。
[/ol]一句话概括，就是根据虚拟地址中各个部分的索引，逐级在PML4、PDPT、PDT、PT中检索，找到物理页面的地址后，再加上页内偏移，就得到最终的物理地址了。
MMU的性能问题这个转换过程，虽然是MMU硬件自动完成的，但各级页表本身仍然存放在内存中，一次地址转换过程中，可能要多次访问内存，因此，这个转换过程的开销非常大。
如果每次访问内存，MMU都要经过这么复杂的转换才能得到物理地址的话，必然会严重影响程序的性能。怎么解决这个问题呢？
还记得我们是怎么优化学号查询系统的性能的吗？我们把最近查询的学生所在学校的学生表地址，缓存在额外的一张"快表"中，每次查询时，先用学号里的学校信息在快表中查找，如果找到，就直接把快表里缓存的学生表取出来，然后用学号里的校内编号就可以直接对应到具体的学生了，如此就避免了逐级查询的开销。
虚拟地址到物理地址的转换，是不是也可以借鉴这种方法呢？
引入TLB之前文章讲过，为了解决内存和CPU之间速度严重不匹配的问题，利用程序局部性原理，在CPU和内存之间引入了L1，L2，L3高速缓存，也就是Cache，把最近访问到的数据存放在Cache中，以此减少直接内存访问。
这个思路，在这里同样适用。虚拟地址转换为物理地址时，为了避免每次MMU都必须要逐级查询页表，CPU内部专门设计了一个部件-TLB(Translation Lookaside Buffer)，通常称为"快表"。TLB本质上是虚拟页地址和物理页地址对应关系的Cache。
CPU把最近访问到的虚拟页的地址，和它所映射的物理页的地址，组成一个地址对，直接缓存在TLB中。这样一来，每次通过虚拟地址访问内存时，CPU会先用虚拟页的地址在TLB中查找，如果找到，称为TLB Hit，就直接得到物理页的地址，然后加上页内偏移就能得到物理地址。如果找不到，称为TLB Miss，就必须通过MMU逐级检索页表进行地址转换了。
但是，TLB的容量一般非常小，只能缓存很少的页面地址对，当TLB被占满时，旧的地址对会被新的替换掉。
当然，这只是TLB的基本原理，实际上的实现要复杂的多，而且不同的CPU上TLB也各有差异，限于篇幅，不再展开。
malloc()和缺页异常应用程序一般通过glibc来申请内存，如malloc()等函数返回的都是虚拟地址。
glibc以内存池的方式进行内存管理，应用程序调用malloc()申请内存时，如果内存池中有合适大小的内存块，就直接取出使用，如果没有合适的，就把大的内存块切分成合适的内存块，返回给应用程序。如果连大的内存块都没有的话，就通过系统调用，向内核申请一块新的虚拟内存。
内核为应用程序分配虚拟内存的时候，只是在虚拟地址空间中划分一块指定大小的地址范围出来，并不会立即为其分配物理内存。
应用程序拿到malloc()返回的虚拟地址后，就可以访问这块内存空间了。第一次访问这段虚拟地址的一个页面时，由于kernel还没有为其映射物理页面，所以会触发缺页异常(Page Fault)，进入内核态缺页异常处理流程。内核会分配一个物理页面，并把物理页面的地址和虚拟地址的映射关系更新到页表中，本次缺页异常处理就结束了，然后切换到用户态，继续被中断的内存访问。
这个过程，对用户态程序是透明的，它甚至根本意识不到缺页异常的存在。当应用程序再次访问到同一个虚拟页面时，就能够正常访问了，不会再次触发缺页异常(除非这个页面又被内核swap出去了)。
整个过程如下图所示：

hv414nx5hor64014917330.png

缺页异常的开销是非常大的，主要因为：
1. CPU异常处理机制本身的开销。
2. 用户态和内核态上下文切换的开销。
3. 分配物理页面的开销。
4. 如果物理页面不足，可能触发内存回收动作。
5. 如果物理页面被swap出去，就需要通过disk I/O把页面重新swap进来，这个开销非常大。
6. 被缺页异常打断的线程，甚至有可能会被调度出去。
[/ol]看到这里，应该已经明白为什么文章开头test.c中第一次memset()要比第二次和第三次性能差那么多了吧？
为什么第一次memset()那么慢？test.c用malloc()分配了1GB的虚拟内存，内核并没有立即为其分配物理内存，所以每当第一次访问一个虚拟页面，都会触发缺页异常。
也就意味着，第一次memset()的时候，会触发1GB / 4KB = 262144次缺页异常，而当第二次和第三次memset()的时候，内核已经分配好了物理内存，不会再次触发缺页异常，所以性能比第一次memset()要好的多。
这只是理论分析，现在我们来验证一下。先把第二次和第三次memset()注释掉:

kim34yocu4j64014917430.png

编译运行，并用perf统计下一共触发多少次缺页异常：

x4t4j3wnorb64014917530.png

可以看到，只有一次memset的时候，一共触发了262199次缺页异常，比我们计算的262144多了55次，这是因为程序的数据段、代码段、栈空间等运行时也可能会触发缺页异常。
现在把第二次和第三次memset()重新加回去，重新编译运行，再用perf统计一下：

yofa33yyyfh64014917630.png

缺页异常仍然触发了262199次，和只有一次memset()时一模一样，可见，第二次和第三次memset()连一次缺页异常都没触发！
另外，也留意一下，现在执行三次memset()时，一共触发了2574501次dTLB-load-misses，我们后面优化之后，会再对比一下这个数据。
现在知道了第一次memset()性能差的原因，那么，如何进行优化呢？
一种常用的优化方式是，采用Huge Page替代默认的4KB Page。
Huge Page随着计算机技术的不断发展，物理内存速度越来越快，容量也越来越大。当前计算机的物理内存动辄就是几十GB，或者上百GB，有些高性能服务器上甚至达到TB的级别。在这个背景下，传统的4KB页面的内存管理，显然对一些内存需求量大的程序已经不适合了。
传统4KB页面的局限以4GB虚拟内存为例，如果采用4KB页面进行管理，就要有4GB/4KB = 1048576个Page，也就意味着需要1048576个页表项，再加上中间各级页表目录，就会占用大量的内存来存储各级页表。
更重要的是，程序访问这4GB内存，至少要经过1048576次TLB Miss和缺页异常，才能把这4GB虚拟内存全部映射到物理内存。
此外，即便物理内存映射全部完成之后，程序在正常运行时，由于TLB容量极其有限，这么多的页表项必然会引发大量的TLB Miss，严重影响程序性能，尤其当程序局部性不好，内存随机访问比较多的时候(如大量引用和遍历链表等数据结构时)，这种性能影响会尤为明显。
前面介绍MMU地址转换的时候讲过，CPU一般支持多种大小的Page，比如X64就支持4KB、2MB、1GB大小的Page。那么，既然传统的4KB页面内存管理，存在各种性能问题，能否用更大的页面呢？
是的，现在的操作系统，虽然默认采用4KB的页面进行内存管理，但同时也支持更大的页面。以Linux为例，内核引入了Huge Page的特性，可以使用2MB或1GB的大页来代替传统的4KB页面。
这样一来，同样的4GB虚拟内存，使用2MB的大页，只需要4GB/2MB = 2048个Page，缺页异常和TLB都会大幅下降，能显著提升程序性能。而用1GB的页面的话，只需4GB / 1GB = 4个Page，此时，缺页异常和TLB Miss的影响被降到了最小。
MMU对大页的支持对MMU来说，使用更大的页面，虽然和使用4KB的页面本质上没有区别，但是可以减少页表层级。此外，使用大页后，页面映射少了，对TLB的压力也就小了，可以降低TLB Miss的概率。
如X64上，使用2MB的页面，只需要3级页表就可以了，相比4KB的页面，减少一级页表，地址转换过程如下图：

inhoy0bookw64014917730.png

如果使用1GB页面的话，就只需要2级页表，相比4KB页面，减少了2级页表，地址转换过程如下图：

j0bw1ycs0gi64014917830.png

简单来说，Huge Page的引入，可以带来这些好处：
1. 大大减少Page Fault的次数
2. 大大降低TLB Miss的概率
3. 减少了MMU地址转换需要的页表层级，不但节省了内存，还能提高MMU地址转换的效率。
4. Huge Page可以永驻内存，避免被swap出去。
[/ol]当然，大量使用Huge Page的话，也可能会导致部分内存的浪费。
Huge Page的应用非常广泛，很多高性能场景中，都会通过使用Huge Page来提升整体性能，如DPDK等。
Linux对Huge Page的支持Linux支持两种Huge Page：
? 一种是标准的Huge Page，需要预先分配，管理和使用起来稍显麻烦，但实际场景中用的比较多。
? 另一种叫透明大页(Transparent Huge Pages)，可以在使用时动态分配，使用相对简单，但只支持2MB的大页，而且仍然有可能被swap出去。
下面，以我系统上默认支持的2MB的标准Huge Page来验证下，是否能提升第一次memset的性能。
为避免影响，先把透明大页关闭：
echo never > /sys/kernel/mm/transparent_hugepage/enabled然后，确认下默认支持的Huge Page的大小确实是2MB：
root@ubuntu:test# cat /proc/meminfo | grep Hugepagesize
Hugepagesize:       2048 kB然后预分配1024个Huge Page，也就是2GB的内存：
root@ubuntu:test# cat /proc/sys/vm/nr_hugepages
0
root@ubuntu:test# echo 1024 > /proc/sys/vm/nr_hugepages再确认一下：
root@ubuntu:test# cat /proc/meminfo | grep Huge
AnonHugePages:         0 kB
ShmemHugePages:        0 kB
FileHugePages:         0 kB
HugePages_Total:    1024
HugePages_Free:     1024
HugePages_Rsvd:        0
HugePages_Surp:        0
Hugepagesize:       2048 kB
Hugetlb:         2097152 kB把代码稍微修改一下，以便启用Huge Page：

rxstkqjwfxb64014917930.png

重新编译运行：

mbjphebkohc64014918030.png

第一次memset()耗时降到了从使用4KB页面时的0.659秒，降到了0.238秒，第二次和第三次memset的耗时也稍有降低！
用perf看下性能数据：

ryscxmsamod64014918130.png

缺页异常次数从使用4KB页面时的262199次，降到了568次，而dTLB-load-misses也从2574501次，降到了27004次！
由此可见，与默认的4KB的Page相比，使用2MB的Huge Page确实显著降低了缺页异常和dTLB Miss的数量！
但是第一次memset()性能仍然比第二次和第三次慢了很多，还能再继续优化吗？
当然可以！
提前映射页面使用2MB的Huge Page虽然显著降低了缺页异常，但并没有完全消除，因此第一次memset()仍然比第二次和第三次慢了很多。
不过，mmap提供了一个MAP_POPULATE标记，可以在分配内存的时候提前把页面映射好，从而避免运行时的缺页异常。
咱们来验证一下，简单修改下代码，调用mmap()的时候，加上MAP_POPULATE标记：

5dlqx3spvkd64014918231.png

重新编译运行：

看到了吧，现在三次memset()性能几乎一样了！
最后，再用perf看下缺页异常次数是否有变化：

dubmzdq0khg64014918331.png

果然，现在缺页异常只有55次，可见三次memset()过程中不会再触发任何缺页异常了！
其他可能的优化点对于内存需求量大的应用场景，除了Huge Page外，还可以考虑从这些方向进行优化：
? 让程序保持较好的局部性，顺序访问优于随机访问，如数组访问优于链表访问。
? 预读或预热，如进入关键路径之前，先确保物理内存已经被分配。比如，有些系统设计为了解决这类问题，甚至会专门创建一个helper线程，专门负责预读，不仅适合文件I/O，也适合内存访问量比较大的场景。
? 禁用swap。swap虽然可以一定程度上缓解物理内存短缺的问题，但是却可能会影响系统整体性能，尤其在热点路径上，如果发生页面swap，会对程序性能产生严重影响。
? 考虑NUMA的影响，程序访问本地node上的内存比访问远程node内存快的多。
精彩内容：嵌入式中，日志调试法的一些规则！
汇总嵌入式中一些实用的辅助工具！
易懂 | 手把手教你编写你的第一个上位机
来了解一下较受欢迎的Git可视化工具！
轻如羽翼，超轻量的嵌入式数据库！
推荐一个好用的嵌入式静态代码扫描工具！
嵌入式中，升级时涉及的协议兼容性问题？
嵌入式，可测试性软件设计！几个备受推崇的C语言项目，你了解几个？