并发成本层次结构

并发性很难纠正，至少对于我们这些不幸地用直接暴露并发硬件内部的语言编写的人来说是这样的：线程和共享内存。正确而快速地获得并发性也很困难。您的单线程优化知识通常对您没有帮助：在微(指令)级别，我们不能简单地应用μ操作、依赖链、吞吐量限制等常见规则。规则是不同的。

如果第一段让您燃起了希望，那么第二段将使您的希望破灭：我实际上不打算深入研究并发性能的非常低层次的方面。有很多事情我们只是不知道原子指令和栅栏是如何执行的，我们将把这些留到另一天再说。

相反，我将描述一个更高级别的分类法，我用它来考虑并发性能。我们将并发操作的性能分为从快到慢的六个大致级别，每个级别与其相邻级别的性能相差大约一个数量级。

当我需要高性能并发性时，我经常发现自己在考虑这些类别：对于给定的问题，我实际能达到的最佳级别是什么？牢记这些级别在初始设计期间(有时需求或高级别设计中的小更改可以使您达到更好的级别)和评估现有系统时(更好地了解现有性能并评估改进阻力最小的路径)都很有用。

我不希望这是完全抽象的，所以我们将使用一个真实的If-You-Cinting1运行示例：跨线程安全地递增整数计数器。安全地说，我的意思是不会丢失增量，不会产生突如其来的值，不会炸毁RAM，也不会在时空中产生更小的裂痕。

这里提供了每个基准测试的源代码，因此您可以跟踪，甚至可以重现结果或在您自己的硬件上运行基准测试。此处讨论的所有结果(以及更多)都可以在同一存储库中找到，并且每个绘图都包括一个指向用于生成绘图的特定子集的[数据表]链接。

所有的性能结果都是针对几个不同的硬件平台提供的：Intel Skylake、Ice Lake、Amazon Graviton和Graviton 2。不过，除了我明确提到其他硬件之外，这篇散文都是指Skylake上的结果。虽然具体数字各不相同，但大多数定性关系也适用于硬件，但并非总是如此。不仅硬件会有所不同，操作系统和库实现也会有所不同。

这几乎是不可避免的，这将被用来跨硬件进行比较(“哇，Graviton 2确实踢了Graviton 1的屁股”)，但这不是我的目标。编写基准主要是为了梳理不同级别的特征，而不是作为硬件对决。

你可能会认为这个层次结构会从快到慢，或者从快到慢，或者反之亦然，但我们在这里都是关于打破预期的，我们将从中间开始，向外努力。中间部分(向下舍入)被证明是第2级，这就是我们要跳进去的地方。

安全修改任何共享对象的最基本方法是使用锁。它主要只适用于任何类型的对象，无论其结构或修改的性质如何。几乎所有过去三十年的主流CPU都有用户空间可访问的某种类型的LOCK3指令。

因此，我们的基线增量实现将使用类型T的简单互斥锁来保护纯整数变量：

我们将这个实现称为mutex add，在我的4CPU Skylake-Si7-6700HQ机器上，当我使用vanilla std：：mutex时，我得到了2到4个线程的以下结果：

这表明，对于两个线程，修改受锁保护的整数的基线争用成本开始于大约125纳秒，并且随着线程数量的增加而略有增加。

我已经听到有人说：如果您只是修改单个64位整数，那么跳过锁，直接使用大多数ISA支持的原子操作！

当然，让我们添加几个可以做到这一点的变体。原子模板使得这一点变得很简单：我们可以包装满足一些基本要求的任何类型，然后对其进行原子操作。其中最简单的是使用std：：atom<；uint64>；：：Operator++()4，这给我们提供了原子add：

另一种常见的方法是使用比较和交换(CAS)来加载现有值，添加一个值，如果值没有更改，则用CAS将其返回。如果它已更改，则增量与另一个线程竞争，我们再试一次。

请注意，即使您在源代码级别使用增量，如果您的硬件不支持原子增量5，或者如果您的编译器或运行时只是没有利用原子操作，即使它们是可用的(例如，看看ICC的最新版本对原子增量做了什么，Java在第6年做了什么)，程序集实际上也可能最终使用CAS。然而，这一警告不适用于我们测试的任何平台。

让我们添加一个如上所述使用CAS的计数器实现，我们将其命名为cas add：

std：：atom<；uint64_t>；cas_counter；void cas_add(Size_T Iters){while(iters--){uint64_t v=cas_counter。Load()；While(！CAS_COUNTER。比较_交换_弱(v，v+1))；}}。

第一个结论是，至少在这个不切实际的最大争用基准测试中，使用原子添加(硬件级别的锁定xadd)比使用CAS要好得多。第二个可能是std：：mutex在Skylake上看起来并没有那么糟糕。它只比CAS方法在2核上稍微差一点，在3核和4核上比CAS方法差一点。它比原子增量方法慢，但比原子增量方法慢不到三倍，而且似乎正在以合理的方式进行扩展。

所有这些操作都属于层次结构中的级别2。级别2的主要特征是它们对共享变量进行争用访问。这意味着，包含数据的行至少需要移出到管理一致性7的缓存代理，然后返回到接下来将接收所有权的核心。仅操作8就至少需要70个周期。

再往上一层(“up”在这里不好用，…)。这一级别的实现的关键特征是它们几乎对每个操作都进行系统调用。

很容易编写无条件进行系统调用的并发原语(例如，总是试图通过Futex(2)调用唤醒服务员的锁，即使没有调用)，但我们不会在这里讨论这些。相反，我们将查看这样一种情况：编写快速路径是为了避免系统调用，但是它的设计或使用方式意味着，无论如何都会发生这样的调用。

具体地说，我们将查看一些公平的锁。公平锁允许线程以它们开始等待的相同顺序进入临界区。也就是说，当临界区变为可用时，等待时间最长的线程将有机会使用它。

听起来是个好主意，对吧？有时是这样的，但正如我们将看到的那样，它可能会对性能产生重大影响。

第一个是在旋转循环中带有SCHED_YIELD的票证锁定。产量的概念是让其他可能持有锁的线程有时间运行。并发专家9公开反对这种收益()方法，他们有时会继续使用它。

/*在等待*提供票证时使用SCHED_YIELD()的票证锁。*/class Ticket_Year{std：：atom<；size_t>；分配器{}，服务{}；public：void lock(){自动票证=分配器。FETCH_ADD(1，STD：：MEMORY_ORDER_RELAX)；WHILE(票证！=服务。load(std：：Memory_Order_Acquisition))SCHED_YIELD()；}void unlock(){serving.。商店(服务。load()+1，std：：Memory_Order_Release)；}}；

这是级别3可视化的：它比级别2的方法慢一个数量级。速度减慢来自sched_Year调用：这是一个系统调用，它们通常在100纳秒10的数量级上，并且它显示在结果中。

这个锁有一个快速路径，其中不调用SCHED_YIELD：如果锁可用，则不会发生旋转，也不会调用SCHED_YIELD。然而，公平锁和此测试中的高争用相结合意味着锁护航很快形成(稍后我们将更详细地描述这一点)，因此基本上每次调用lock()时都会进入自旋循环。

那么，我们现在已经完全探测到了缓慢并发构造的深度了吗？一点都不接近。我们现在才刚刚要过冥河。

在我们继续之前，根据我们对级别3的定义，让我们快速回顾一下级别2中讨论的std：：mutex实现，因为级别3需要系统调用。std：：mutex不也进行系统调用吗？如果线程试图锁定已经锁定的std：：mutex对象，我们预计该线程会使用操作系统提供的原语进行阻塞。那么，为什么不是3级，而且不是像票面收益率那样缓慢呢？

主要原因是它在实践中很少进行系统调用。通过旋转和不公平的组合，我测量到每个增量大约只有0.18个系统调用，在我的Skylake机器上有三个线程。因此，大多数增量都是在没有系统调用的情况下进行的。另一方面，票证收益率每个增量进行大约2.4次系统调用，比原来多一个数量级，因此它的性能会相应降低。

下一级是当实现强制执行大量并发操作以导致上下文切换时。

让位锁不会导致很多上下文切换，因为我们运行的线程不比内核多，所以通常没有其他可运行的进程(除了偶尔的后台进程)。因此，当我们调用SCHED_YIELD时，当前线程停留在CPU上。当然，这会消耗大量CPU。

正如专家建议的那样，每当有人建议在旋转循环中屈服时，让我们尝试一下阻塞锁。

我们的第一个阻塞锁同样是基于票证的设计，除了这一次，当它检测到它不是第一个被服务的线程(即，锁由另一个线程持有)时，它使用一个条件变量来阻塞。我们将其命名为票务阻塞，如下所示：

void BLOCKING_TICKET：：LOCK(){自动票证=分配器。FETCH_ADD(1，STD：：MEMORY_ORDER_RELAX)；IF(票证==服务。LOAD(STD：：MEMORY_ORDER_ACCENTER))RETURN；//无争用案例STD：：UNIQUE_LOCK<；STD：：Mutex>；lock(Mutex)；While(Ticket！=Serving。Load(std：：Memory_Order_Acquisition)){CVAR.。WAIT(LOCK)；}}void BLOCKING_TICKET：：UNLOCK(){std：：Unique_lock<；std：：mutex>；lock(Mutex)；auto s=服务。LOAD(STD：：MEMORY_ORDER_RELAX)+1；服务。STORE(s，std：：MEMORY_ORDER_RELEASE)；AUTO D=分配器。Load(std：：MEMORY_ORDER_RELAX)；ASSERT(s<；=d)；IF(s<；d){//唤醒所有服务员CVAR。NOTIFY_ALL()；}}。

与早期实现occrs的主要不同之处在于，当我们没有立即获取锁时(我们不会在标记为//无争用大小写的位置返回)。我们没有在循环中让步，而是获取与条件变量相关联的互斥体，并等待直到得到通知。每次我们接到通知，我们都会检查是否轮到我们了。

即使没有虚假唤醒，我们也可能被唤醒多次，因为这个锁存在雷鸣般的群组问题，每个服务员都会在unlock()上被唤醒，尽管最终只有一个人能够获得锁。

我们还将尝试第二种设计，它不会受到雷鸣般的羊群的影响。这是一个排队锁，其中每个锁在等待者队列中的自己的私有节点上等待，因此在解锁时只有一个等待者(新锁所有者)被唤醒。我们将其称为队列FIFO，如果您对实现感兴趣，可以在这里找到它。

您现在可能看到了模式：与之前的竞争者相比，性能再次达到了一个糟糕的新水平。大约比屈服方法慢一个数量级，后者已经比早期的方法慢了一个数量级，早期的方法现在只有几个像素高的薄片。排队版本的锁在增加线程计数方面稍好一些(特别是在Graviton[2]上)，因为缺少雷鸣般的羊群效应可以预期到这一点，但是仍然非常慢，因为主要问题不是雷鸣般的羊群，而是锁护送。

那么，您是否厌倦了看到新引入的算法将包的其余部分降级到x轴附近的小块颜色的主要是白色的图表？

我只剩下一个人在天平的慢端。与其他例子不同的是，我在现实生活中实际上没有诊断出如此糟糕的情况，但例子是存在的。

这是一个票锁，它与我们看到的第一个票锁相同，只是sched_Year()；替换为；。也就是说，它忙于等待，而不是屈服(在这里寻找专门用于共享票锁模板的Spin风格)。您也可以将其替换为特定于CPU的“RELAX”指令，如Pause，但它不会改变结果(请参见此处)。我们称它为Ticket Spin，以下是它与现有候选产品相比的表现：

什么？那看起来一点也不差。事实上，它只比2级机组人员稍差一点，这是我们到目前为止看到的最快的12级机组人员。

如果我们显示最多6个线程的结果，而不是只显示4个线程的结果，则情况会发生变化。由于我有4个可用内核13，这意味着并非所有测试线程都能同时运行：

现在很清楚为什么这个水平被称为灾难性的。一旦我们超额订阅了可用核心的数量，性能就会下降约500倍。我们从100纳秒到100微秒。我没有显示更多的线程，但是随着您添加更多的线程，情况只会变得更糟。

我们也比上一级别的最佳解决方案(排队FIFO)慢一个数量级，尽管它因硬件而异：在Ice Lake上，差异大约是40倍，而在Graviton上，这个解决方案在17个线程上实际上比票证阻塞(也是4级)略快。还要注意巨大的误差栏。这是最不一致的基准测试，表现出很大的差异，最慢和最快的运行可能相差100倍。

它类似于上面描述的锁护航：由于公平的设计，所有线程都在锁上排队并以循环顺序获取它。不同之处在于，当线程无法获取锁时，它们不会阻塞。这在核心没有超额认购时效果很好，但在其他情况下却会跌落悬崖。

假设有5个线程，T1、T2、…。，T5，其中T5是当前未运行的那个。一旦T5是需要获取下一个锁的线程(即，T5的保存票值等于分配)，就不会发生任何事情，因为T1到T4正忙于旋转，等待轮到它们。操作系统调度程序认为没有理由中断它们，直到它们的时间片到期。时间片通常以毫秒为单位测量。一旦一个线程被抢占，比方说T1，T5将有机会运行，但在轮到T1之前，最多只能发生4次获取(T5加上T2、T3、T4中的任何一个)。T1正在等待他们再次运行的机会，但是由于每个人都在旋转，这在另一个时间片到期之前不会发生。

因此，每个时间片只能获取锁几次(最多$(Nproc)次)，或者最少获取一次14次。使用CFS的现代Linux没有固定的时间片，但在我的系统上，sched_latent_ns是18,000,000，这意味着我们预计竞争一个内核的两个线程将获得9ms的典型时间片。测量到的数字与一位数毫秒的时间片大致一致。

考虑这一点的另一种方式是，在这种超订用情况下，票证旋转锁意味着与阻塞票证锁15大致相同的上下文切换次数，但是在前一种情况下，每个上下文切换都伴随着由于耗尽时间片的需要而导致的巨大延迟，而在阻塞情况下，我们仅受上下文切换发生的速度的限制。

有趣的是，虽然这个基准测试在每个内核上都使用100%的CPU，但是在超订用情况下基准测试的性能几乎不取决于您的CPU速度！如果我将CPU调节到1 GHz，或者将Turbo调到3.5 GHz，性能大致相同。所有其他实现几乎都与CPU频率成正比地扩展。基准测试确实可以通过调整到sched_Latay_ns(如果前者设置得足够低，则还可以调整为sched_min_gramality_ns)进行很好的扩展：随着时间片的缩小，较低的调度延迟值可以提供成比例的更好的性能，这有助于证实我们关于这是如何工作的理论。

此行为还解释了可用核心超额订阅后出现的巨大差异：根据定义，并非所有线程都将同时运行，因此测试对未运行的线程在何处进行上下文切换变得非常敏感。在测试开始时，6个线程中只有4个线程在运行，并且这两个线程将被切换，仍然在等待同步测试开始的障碍。由于两个切换出的线程还没有尝试获取锁，因此四个正在运行的线程将能够快速地在它们之间共享锁，因为六线程队列还没有设置。

这会在随机变化的初始时间段内运行“迭代计数”(已完成的工作)，直到第一次上下文切换让第五个线程加入竞争，然后车队设置为16。这就是灾难开始的时候。这使得结果非常嘈杂：例如，如果您为一项试验设置了太短的时间段，整个测试就是由这个初始阶段组成的，结果被人为地“好”了。

我们也许可以发明一些更糟糕的东西，但现在已经足够了。让我们转到比使用普通原子添加更快的场景。

回想一下，我们从第2级开始：争用原子。这个名字暴露了它：下一个更快的级别是使用原子操作，但没有争用，无论是出于设计还是出于运气。您可能已经注意到，到目前为止，我们只显示了至少两个线程的结果。这是因为单线程情况不涉及争用，因此如果在单线程17上运行，那么到目前为止每个实现都是级别1。

以下是我们到目前为止针对单个线程查看的所有实现的结果：

最快的实现大约在10纳秒内运行，这比2个或更多线程的最快解决方案快5倍。一个线程的最慢实现(排队FIFO)与最快的实现(原子添加)在两个线程上持平，而在三个或四个线程上轻松击败它。

覆盖在每个条上的数字是每个实现每次递增进行的原子操作18的数目。显然，性能几乎与原子指令的数量成正比。另一方面，性能与任何类型的指令总数没有太大关系，即使在具有相同性能的算法之间也有很大差异，如下表所示：

特别地，请注意，与cas add相比，mutex add的指令数量是cas add的9倍多，但运行速度仍然只有cas add的一半，与原子的2：1比率一致。类似地，票证产量和票证旋转性能略好于cas add，尽管它们的指令数量大约是cas add的两倍，这与它们都具有单个原子运算符是一致的。

..