DeepRoute Lab | 缓存对多线程程序性能的影响

当我们的多线程程序遇到性能问题时，通常我们会下意识地觉得这是由于上下文切换、cpu 迁移等因素导致的。那么，如何更进一步地分析究竟是哪一部分语句造成了什么样的影响呢？这篇分享将从计算机体系结构的角度，结合非常典型的代码案例，为你解惑。

在进入正题之前，如果对缓存还不了解的读者，可以先看看这篇分享。
DeepRoute Lab | 【C++性能】CPU Cache Serial 1

01引子

1.1 第一个代码片段

（点击查看大图）

1.2 第二个代码片段

（点击查看大图）

1.3 转置

代码片段一里面，GoodWorker的效率（计算的耗时）

是 BadWorker 的 10 倍左右（取决于具体硬件条件和其他相关因素）。

在不知道其他背景知识的前提下，我们怎么来定位这个问题呢？加耗时的打印？- 不好意思，面对这种已经只剩大量基本操作的代码，没法做到更细粒度的耗时打印了。看火焰图？

（点击查看大图）

可以看到，除了 GoodWorker 在整个 workload 上的占比（83%）比 BadWorker （96%） 略低以外（也不能提供其他进一步的指导意义了）， 两个函数在火焰图上都可谓是“一马平川”，火焰图在这种情况下也失去了指导意义。难道就没有任何办法了吗？开什么玩笑，如果没有办法，这篇文章也就写不下去了！那么答案是什么呢！

02Perf Events 初探

2.1 代码片段一的性能数据

在详细介绍 perf events 之前，让我们直观地通过数据来体会一下它在分析这类问题上的强大之处。下面所有类似的结果均采用 perf events 生成。

（点击查看大图）

以上分别是 BadWorker 和 GoodWorker 使用 Perf Events 诊断的结果，可以看到已经有大量的差异巨大的数值和比例了。我们通过一个表格对比一下几个主要的指标：

我们可以看到，GoodWorker 相较于 BadWorker，表面上除了 backend stall rate 处于劣势以外，其他均全面占优，其中 frontend stall rate 和 LLC load miss 的性能达到了百倍的差距（虽然表面上 LLC miss rate 只有不到两倍，但是数量上大于百倍）。BadWorker 另一个明显的数据 pattern 如下（后文会解释这些数值的意义，不要着急！）

• Frontend stall rate 【显著高于】
• backend stall rateL1-icache miss rate【在数量级上接近】
• L1-dcache miss rateLLC miss rate 的【数值也不低】
• Branch miss rate 【显著升高】（这个与具体代码中是否存在分支有关）
  并且我们知道，在 GoodWorker 的对比下，BadWorker 一定是一种有问题的实现方式。

那么至此，我们至少对一种问题代码的 perf events 的数据模式有了一个初步的认识。

2.2  问题小结

在进一步介绍 perf events 的细节之前，我们先对上述代码片段的问题做一个小小的阐述。相信在多线程领域比较有经验的同事已经看出了问题，这是典型的 false sharing。那我们怎么把上文中提到的 perf events 数据和这个问题的原理联系起来呢？这就需要进一步了解这些数据背后的意义了！

03揭开 Perf Events 数据的神秘面纱

3.1  从 perf event 指令说起

-e 后面紧接着的、用逗号分隔的就是每一个 perf event（基于本次测试机器的架构）。

我们可以简单地把这些 perf event 分成几类：

• cpu指令和时钟周期相关 

  • cpu-cycles 
  • instructions 
  • stalled-cycles-frontend
  • stalled-cycles-backend

• 缓存相关
  L1 缓存

  • L1-dcache-loads
  • L1-dcache-load-misses
  • L1-icache-loads
  • L1-icache-load-misses
    L3 缓存（Last-level-cache，LLC）
  • LLC-loads
  • LLC-load-misses

• 其他
  各类 faults

  • major
  • faults
  • page-faults
  • minor-faults
    分支相关
  • branch-load-misses
  • branch-loads
    调度相关
  • context-switches

在进一步阐述相关数值背后具体含义之前，有必要对上述提到的 events 做一些解释。

相信大家对其中绝大部分的含义已经是比较了解了，这里专门解释一下 stalled-cycles-frontend 和stalled-cycles-backend。根据本次测试的机器在接近完美的 pipeline 下，IPC 可以达到 10 左右。但是我们可以看到 GoodWorker 的 IPC 也只能达到 3.40，那是什么因素导致了如此巨大的理想与现实的鸿沟呢？答案就在 stalled-cycles-frontend 和 stalled-cycles-backend 身上。

对于现在主流的超标量 OoO 处理器，可以把它的每个 pipeline 分成 3 个主要部分：

• 对指令流顺序取址和译码 —— Front End
• 乱序执行 —— Back End
• 顺序提交Front End 与指令密切相关。Back End 与数据密切相关。

上述三个部分中的任何一个部分发生了阻塞，都会严重影响 cpu pipeline 的效率。

顺序提交的前提是指令依赖解决且执行完成，这两个部分分别发生在 Front End 和 Back End。因此顺序提交不会发生任何 pipeline stall(idle)，它不会破坏 cpu pipeline 的执行效率。

那就只能是 Front End 和 Back End 了（也正好对应了 stalled-cycles-frontend 和 stalled-cycles-backend）

• 对于 Front End，任何导致指令获取、译码阻塞的原因都可能打断 pipeline- misprediction
• 对于 Back End，任何导致数据获取、执行阻塞的原因都可能打断 pipeline- read L2/L3/memory 

3.2 Case study ——一个非常明显的 false sharing

回到我们 前面的第一个例子，GoodWorker和BadWorker主要的 perf events 性能数据如下。

我们应该怎么对这些数据进行解释呢？

表格数据的解释：

• Branch miss rate 升高 ⇔ L1-icache miss rate 升高

  • 代码中存在分支语句，cpu 会做分支预测 —— preload 相关的指令（预测的结果）到 L1-icache。
    
  • 因为存在 false sharing，指令会被频繁地 invalidate 和替换（因为相应的 dcache 中的数据也失效了），那么本来已经被 preload 进入到 L1-icache 的指令可能并不会被执行，导致 L1-icache miss rate 升高。
  • 更进一步，因为频繁地 invalidate 和替换，发生 cache thrashing，导致未执行的指令积压，使得指令执行落后于分支预测，进一步使得 branch miss rate 升高。

• frontend stall rate 显著升高

  • branch miss rate 和 L1-icache miss rate 都升高了，整个 Front End 的 pipeline 被完全破坏，stall rate 自然会显著升高。

• context switch 显著升高 

  • 因为存在 false sharing，指令和数据会被频繁地 invalidate 和替换，cpu 为了保证 cache 一致性，可能会不得以进行更多的 context switch。
  • 同时，context switch 本身也会加剧各个 level 的 cache miss。

• – L1-dcache-load-misses 巨幅升高 ⇒ LLC  load miss 巨幅升高

  • L1-dcache 中的数据频繁失效，导致数据需要频繁地从 LLC中读取。

• – stalled-cycles-backend 貌似降低

  • 从比例上看貌似降低了 75% 左右，但是实际上，从总量上来看，是 3775M vs 1080M，仍然是升高了不少的。

看 LLC miss 的时候，miss rate 虽然是一个指标，但不是最重要的。因为 LLC load miss 直接决定了内存访问次数的多少，这将显著地导致整个系统处于内存性能瓶颈。

如果代码里不可避免地需要使用多个线程来进行写操作，需要关注被写对象的内存布局。

3.3 Case study —— 一个比较隐蔽的 false sharing

代码片段二也有比较隐蔽的 false sharing 问题。这里

的修复方式是增加一行代码

或者

我们参照上面的方式，也来对修复前后的主要 perf events 性能指标做一个对比。

（点击查看大图）

可以看到，表格中的数据在定性上也和第一个例子中的非常类似。

有意思的是， Without Padding 版本的 LLC-load-miss 数量几乎等于 L1-dcache-load-misses 的数量了，L2 cache 在这会儿几乎完全失效了。

这是因为主线程只有 1 个，而并发线程也只有 1 个，再加上没有发生 cpu-migration（始终在使用同一个 core 的 L1、L2 缓存），但是在 false-sharing 的情况下，L1、L2、乃至 L3 的数据可能一直都在失效，所以会出现这种

• L1-dcache-load-misses
• l2d_cache_lmiss_rd
• LLC-loads
• LLC-load-misses
  的数值几乎相等的情况，也即是说 L1 缓存中无法读取的数据，在 L2、L3缓存都层层失效，导致几乎全部需要从内存读取。

我们来总结一下上述两种 false sharing 发生的情况：

• 代码片段一里面，导致问题的代码如下
  
  可以看到，这里是 8 个线程在同时写同一个 cache line，这将导致最严重的 cache thrashing，就像是经过专门设计的一样，很难有应用层的代码可以如此“巧合”地导致这么严重的问题了。

* 代码片段二里面，导致问题的代码如下

在这个例子里面，主线程和另一个子线程在同一个 cache line 上的同时的读写操作，同样会导致非常严重的 cache thrashing 问题。

如果代码里不可避免地需要使用多个线程来进行写操作，需要关注被写对象的内存布局。

3.4 Case study —— 传引用比传值还慢？

（点击查看大图）

我们不论这个代码具体实现的细节，先思考这么一个问题 —— 在功能正确的前提下，在什么情况下，通过引用传递函数参数的性能反而会比通过值传递还差？这似乎是一个不太能想得出答案的问题，直到我们来看上面程序运行的结果。

（点击查看大图）

简单对这个输出做一个概括：

• 单线程性能强于多线程
• 在单线程的时候，使用 引用传递 和 值传递 的效率基本差不多 —— 符合预期
• 在多线程的时候，使用 引用传递 的效率 显著低于 值传递

在看过前面的例子后，相信大家对这种多线程性能不如单线程的问题已经见怪不怪了。但是仍然令人充满不解的是，为什么通过引用传递参数的效率会比通过值传递还低呢？

这是一个叠加的原因 —— 一定发生在多线程的情况下。

• 多个线程同时写一个 unordered_map，由于 unordered_map 不是线程安全的，因此我们对它加了一个粒度非常大的锁，每个线程都单独地占有了 unordered_map，临界区的竞争被显著放大了。
• 在我们调用 PassByReference 或者 PassByValue 之前，key 是通过引用获取的 —— cpu 至今只需要有 key 的一个地址（指针），还不需要真正（从缓存/内存）读取 key 的值。
  
• 当我们调用 PassByReference 的时候
  
  在进入临界区之前，cpu 同样只需要有 key 的一个地址（指针），还不需要真正（从缓存/内存）读取 key 的值。

只有在进入临界区之后，需要使用 key 的值来构造 table_ 的一个元素了，已经不可避免地需要访问它的值了，然而它还在内存里！历经 L1、L2、L3 的层层 miss，终于从内存里读取到了。最为致命的是，这所有的事情，都发生在临界区内！也就意味着，其他线程全部会白白等待这些因为访问内存带来的巨大 overhead，就像是他们都完整地经历了 cache miss 一样。

• 当我们调用 PassByValue 的时候
  
  编译器因为我们做值传递而不得不进行的一次拷贝反而拯救了我们 —— 这次拷贝发生在临界区之前。其他的应该不用再解释了吧。
  

（点击查看大图）

这里对这 “pass by reference” 和 “pass by value” 两个版本的 perf event 的数据分析如下：

由于这两个版本都是明显的 memory-bound 型（backend stall rate 过高），我们这里重点看一下上表中的数据。

• ipc: “reference” 版本稍高，这一点在意料之外又在情理之中 —— 两者过高的 backend stall rate 使得彼此就像是菜鸡互啄。现代处理器主要瓶颈在数据获取而非指令译码，因此在 frontend stall rate 区别不大（没有数量级差距）的前提下，越是有更重（密集而非绝对数量）的内存操作，越可能影响 ipc。
• context switch 和 L1-icache miss rate 分别达到了百倍和十倍之巨大，这是导致 “reference” 版本性能更差（耗时更长）的根本原因 ——  增加了数倍的 frontend stall rate。可以想象，一条流水线中，同样降低一定的比例，越是高效的部分对系统的影响越大。

ipc 本质来说还是一个比例，它不能简单地作为作为评判绝对性能的指标。

所以，这里如果做如下的修改，调用 PassByReference 的时候，也可以“意外”地提升性能（虽然整体还是不如单线程）。它的原理和上面调用 PassByValue 一样，无非就是让这次拷贝更加提前了。

我们不妨看看这么修改后的 perf event 数据：

（点击查看大图）

可以看到和上面的数据 pattern 几乎是一模一样的。不过究其根源，并不是因为传递引用本身比传递值更慢，而是不合理的临界区的设置在背后捣乱。如果代码里不可避免地需要使用多个线程来进行写操作，需要关注临界区的设置。

04总结

自C++11以后，随着std::thread和std::async和一系列配套工具的引入，多线程已经可以像数组链表等一样在程序里被轻松使用了。然而，相比于普通的数据结构，多线程涉及的硬件和系统只是更多，也更容易踩不管是正确性还是性能的坑。如果有可能的话，首要的一点是应该避免使用它。在万不得已必须使用的时候，也应该尽可能多地了解底层和硬件的知识，避免踩坑。祝愿各位的多线程代码都没有bug。

参考文献 / 资料[1]https://armkeil.blob.core.windows.net/developer/Files/pdf/whi…

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net