关于缓存: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…