导读：对于工程教训比拟丰盛的同学，并发应该也并不是生疏的概念了，然而每个人所了解的并发问题，却又往往并不对立，本文零碎梳理了百度 C ++ 工程师在进行并发优化时所作的工作。

全文 15706 字，预计浏览工夫 24 分钟。

一、背景

简略回顾一下，一个程序的性能形成要件大略有三个，即算法复杂度、IO 开销和并发能力。因为古代计算机体系结构复杂化，造成很多时候，工程师的性能优化会更集中在算法复杂度之外的另外两个方向上，即 IO 和并发，在之前的《百度 C ++ 工程师的那些极限优化（内存篇）》中，咱们介绍了百度 C ++ 工程师工程师为了优化性能，从内存 IO 角度登程所做的一些优化案例。

这次咱们就再来聊一聊另外一个性能优化的方向，也就是所谓的 并发优化。和 IO 方向相似，对于工程教训比拟丰盛的同学，并发应该也并不是生疏的概念了，然而每个人所了解的并发问题，却又往往并不对立。所以上面咱们先回到一个更基本的问题，从新梳理一下所谓的并发优化。

是的，这个问题可能有些跳跃，然而在天然地停顿到如何解决各种并发问题之前，咱们的确须要先停下来，回忆一下为什么咱们须要并发？

这时第一个会冒出来的概念可能会是 大规模，例如咱们要设计大规模互联网利用，大规模机器学习零碎。可是咱们认真思考一下，无论应用了那种水平的并发设计，这样的规模化零碎背地，都须要成千盈百的实例来撑持。也就是，如果一个设计（尤其是无状态计算服务设计）曾经能够反对某种小规模业务。那么当规模扩充时，很可能伎俩并不是晋升某个业务单元的解决能力，而是减少更多业务单元，并解决可能遇到的分布式问题。

其实真正让并发编程变得有价值的背景，更多是业务单元自身的解决能力无奈满足需要，例如一次申请解决工夫过久，业务精细化导致复杂度积攒晋升等等问题。那么又是什么导致了近些年来，业务单元解决能力问题有余的问题出现更加突出的趋势？

可能上面这个统计会很阐明问题：

（https://www.karlrupp.net/2015…）

上图从一个长线角度，统计了 CPU 的外围指标参数趋势。从其中的晶体管数目趋势能够看出，尽管可能逐步艰巨，然而摩尔定律仍然尚能维持。然而近十多年，出于管制功耗等因素的思考，CPU 的主频增长根本曾经停滞，继续减少的晶体管转而用来构建了更多的外围。

从 CPU 厂商角度来看，单片处理器所能提供的性能还是放弃了继续晋升的，然而单线程的性能增长曾经显著放缓。从工程师角度来看，最大的变动是硬件红利不再能通明地转化成程序的性能晋升了。随时代提高，更精准的算法，更简单的计算需要，都在对的计算性能提出继续晋升的要求。早些年，这些算力的增长需要大部分还能够通过处理器更新换代来天然解决，可是随着主频增长停滞，如果无奈利用多外围来减速，程序的解决性能就会随主频一起面临增长停滞的问题。因而近些年来，是否可能充分利用多外围计算，也越来越成为高性能程序的一个标签，也只有具备了充沛的多外围利用能力，能力随新型硬件演进，持续体现出指数级的性能晋升。而随同多外围多线程程序设计的遍及，如何解决好程序的并发也逐步成了工程师的一项必要技能。

上图形容了并发减速的基本原理，首先是对原始算法的繁多执行块拆分成多个可能同时运行的子工作，并设计好子工作间的协同。之后利用底层的并行执行部件能力，将多个子工作在工夫上真正重叠起来，达到真正晋升处理速度的目标。

须要留神的是还有一条从下而上的反向剪头，次要表白了，为了正确高效地利用并行执行部件，往往会反向领导下层的并发设计，例如正确地数据对齐，正当的临界区实现等。尽管减速看似齐全是由底层并行执行部件的能力所带来的，程序设计上只须要做到子工作拆分即可。然而现阶段，执行部件对下层还无奈达到通明的水平，导致这条反向依赖对于最终的正确性和性能仍然至关重要。既理解算法，又了解底层设计，并联合起来实现正当的并发革新，也就成为了工程师的一项重要技能。

三、单线程中的并行执行

提到并行执行部件，大家的第一个印象往往时多外围多线程技术。不过在进入到多线程之前，咱们先来看看，即便是单线程的程序设计中，仍然须要关注的那些并行执行能力。回过头再认真看前文的处理器趋势图其实能够发现，尽管近年主频不再增长，甚至稳中有降，然而单线程解决性能其实还是有轻微的晋升的。这其实意味着，在单位时钟周期上，单核心的计算能力仍然在晋升，而这种晋升，很大水平上就得益于单核心单线程内的细粒度并行执行能力。

3.1 SIMD

其中一个重要的细粒度并行能力就是 SIMD（Single Instruction Multiple Data），也就是多个执行单元，同时对多个数据利用雷同指令进行计算的模式。在经典分类上，个别单核心 CPU 被纳入 SISD（Single Instruction Single Data），而多外围 CPU 被纳入 MIMD（Mingle Instruction Multiple D ata），而 GPU 才被纳入 SIMD 的领域。然而古代 CPU 上，除了多外围的 MIMD 根底模型，也同时附带了细粒度 SIMD 计算能力。

上图是 Intel 对于 SIMD 指令的一个示意图，通过减少更大位宽的寄存器实现在一个寄存器中，“压缩”保留多个较小位宽数据的能力。再通过减少非凡的运算指令，对寄存器中的每个小位宽的数据元素，批量实现某种雷同的计算操作，例如图示中最典型的对位相加运算。以这个对位相加操作为例，CPU 只须要增大寄存器，内存传输和计算部件位宽，针对这个非凡的利用场景，就晋升到了 8 倍的计算性能。相比将外围数通用地晋升到 8 倍大小，这种形式付出的老本是非常少的，指令流水线零碎，缓存零碎都做到了复用。

从 CPU 倒退的视角来看，为了可能在单位周期内解决更多数据，减少外围数的 MIMD 强化是最直观的实现门路。然而减少一套外围，就象征减少一套 残缺的指令部件、流水线部件和缓存部件，而且理论利用时，还要思考额定的外围间数据扩散和聚合的传输和同步开销。一方面昂扬的部件需要，导致残缺的外围扩大老本过高，另一方面，多外围间传输和同步的开销针对小数据集场景额定耗费过大，还会进一步限度利用范畴。为了最大限度利用好无限的晶体管，古代 CPU 在塑造更多外围的同时，也在另一个维度上扩大单核心的解决和计算位宽，从而实现晋升实践计算性能（外围数 * 数据宽度）的目标。

不过提起 CPU 上的 SIMD 指令反对，有一个绕不开的话题就是和 GPU 的比照。CPU 上晚期 SIMD 指令集（MMX）的诞生背景，和 GPU 的功能定位就非常相似，专一于减速图像相干算法，近些年又随着神经网络计算的衰亡，转向通用矩阵类计算减速。然而因为 GPU 在设计根底上就以面向密集可反复计算负载设计，指令部件、流水线部件和缓存部件等能够远比 CPU 简洁，也因而更容易在量级上进行扩大。这就导致，当计算密度足够大，数据的传输和同步开销被足够冲淡的状况下（这也是典型神经网络计算的的个性），CPU 仅作为控制流进行指挥，而数据批量传输到 GPU 协同执行反而 会更简略高效。

因为 Intel 本身对 SIMD 指令集的宣传，也集中围绕神经网络类计算来开展，而在以后工程实践经验上，支流的密集计算又以 GPU 实现为主。这就导致了不少 CPU 上 SIMD 指令集无用论应运而生，尤其是近两年 Intel 在 AVX512 初代型号上的降频事件，进一步强化了『CPU 就应该做好 CPU 该做的事件』这一论调。然而单单从这一的视角来意识 CPU 上的 SIMD 指令又未免有些全面，容易漠视掉一些真正有意义的 CPU 上 SIMD 利用场景。

对于一段程序来讲，如果将每读取单位数据，对应的纯计算复杂度大小定义为计算密度，而将算法在不同数据单元上执行的计算流的雷同水平定义为模式反复度，那么能够以此将程序划分为 4 个象限。在大密度可反复的计算负载（典型的重型神经网络计算），和显著小密度和非反复计算负载（例如 HTML 树状解析）场景下，业界在 CPU 和 GPU 的选取上其实是有绝对明确“最优解”的。不过对于过渡地带，计算的反复特色没有那么强，或者运算密度没有那么大的场景下，单方的弱点都会被进一步放大。即使是规整可反复的计算负载，随着计算自身强度减小，传输和启动老本逐步显著。另一方面，即使是不太规整可反复的计算负载，随着计算负荷加大，外围数有余也会逐步成为瓶颈。这时候，引入 SIMD 的 CPU 和引入 SIMT 的 GPU 间如何抉择和应用，就造成了没有那么明确，见仁见智的衡量空间。

即便排除了重型神经网络，从程序的个别个性而言，具备肯定规模的反复个性也是一种普遍现象。例如从概念上讲，程序中的循环段落，都或多或少意味着批量 / 反复的计算负载。只管因为掺杂着分支管制，导致反复得没有那么纯正，但这种肯定规模的细粒度反复，正是 CPU 上 SIMD 施展独特价值的中央。例如最常见的 SIMD 优化其实就是 memcpy，古代的 memcpy 实现会探测 CPU 所能反对的 SIMD 指令位宽，并尽力应用来减速内存传输。另一方面古代编译器也会利用 SIMD 指令来是优化对象拷贝，进行简略循环向量化等形式来进行减速。相似这样的一类优化办法偏『主动通明』，也是默默撑持着主频不变状况下，性能稍有回升的重要推手。

惋惜这类简略的主动优化能做到的事件还相当无限，为了可能充分利用 CPU 上的 SIMD 减速，现阶段还十分依赖程序层进行被动算法适应性革新，有 目的地应用，换言之，就是被动施行这种单线程内的并发革新。一个无奈主动优化的例子就是《内存篇》中提到的字符串切分的优化，现阶段通过编译器剖析还很难从循环 + 判断分支提取出数据并行 pattern 并转换成 SIMD 化的 match&mask 动作。而更为显著的是近年来一批针对 SIMD 指令从新设计的算法，例如 Swiss Table 哈希表，simdjson 解析库，base64 编解码库等，在各自的畛域都带来了倍数级的晋升，而这一类算法适应性革新，就曾经齐全脱离了主动通明所能涉及的范畴。能够预知近些年，尤其随着先进工艺下 AVX512 降频问题的逐步解决，还会 / 也须要涌现出更多的传统根底算法的 SIMD 革新。而纯熟使用 SIMD 指令优化技术，也将成为 C ++ 工程师的一项必要技能。

3.2 OoOE

另一个重要的单线程内并行能力就是乱序执行 OoOE（Out of Order Execution）。经典教科书上的 CPU 流水线机制个别形容如下（经典 5 级 RISC 流水线）。

指令简化表白为取指 / 译码 / 计算 / 访存 / 写回环节，当执行环节遇到数据依赖，以及缓存未命中等场景，就会导致整体进展的产生。其中 MEM 环节的影响尤其显著，次要也是因为缓存档次的深入和多外围的共享景象，带来单次访存所需周期数参差不齐的景象越来越重大。上图中的流水线在多层缓存下的体现，可能更像下图所示：

为了加重进展的影响，古代面向性能优化的 CPU 个别引入了乱序执行联合超标量的技术。也就是一方面，对于重点执行部件，比方计算部件，访存部件等，减少多份来反对并行。另一方面，在执行部件前引入缓冲池 / 队列机制，通用更长的预测执行来尽可能打满每个部件。最终从流水线模式，转向了更相似『多线程』的设计模式：

乱序执行零碎中，个别会将通过预测保护一个较长的指令序列，并构建一个指令池，通过解析指令池内的依赖关系，造成一张 DAG（有向无环图）组织的网状结构。通过对 DAG 关系的计算，其中依赖就绪的指令，就能够进入执行态，被提交到理论的执行部件中解决。执行部件相似多线程模型中的工作线程，依据个性细分为计算和访存两类。计算类个别有绝对固定可预期的执行周期，而访存类因为指令周期差别较大，采纳了异步回调的模型，通过 Load/Store Buffer 反对同时发动数十个访存操作。

乱序执行零碎和传统流水线模式的区别次要体现在，当一条访存指令因为 Cache Miss 而无奈立刻实现时，其后无依赖关系的指令能够插队执行（相似于多线程模型中某个线程阻塞后，OS 将其挂起并调度其余线程）。插队的计算类指令能够填补空窗充分利用计算能力，而插队的访存指令通过更早启动传输，让访存进展期尽量重叠来减小整体的进展。因而乱序执行零碎的效率，很大水平上会受到窗口内指令 DAG 的『扁平』水平的影响，依赖深度较浅的 DAG 能够提供更高的指令级并发能力，进而提供更高的执行部件利用率，以及更少的进展周期。另一方面，因为 Load/Store Buffer 也有最大的容量限度，解决较大区域的内存拜访负载时，将可能带来更深层穿透的访存指令尽量凑近排布，来进步访存进展的重叠，也可能无效缩小整体的进展。

尽管实践比拟清晰，可是在实践中，仅仅从内部指标观测到的性能体现，往往难以定位乱序执行零碎外部的热点。最直白的 CPU 利用率其实只能表白线程未受阻塞，实在在应用 CPU 的工夫周期，然而其实并不能体现 CPU 外部部件真正的利用效率如何。略微进阶一些的 IPC（Instruction Per Cyc le），能够绝对深刻地反馈一些利用效力，然而影响 IPC 的因素又多种多样。是指令并行度有余？还是长周期 ALU 计算负载大？又或者是访存进展过久？甚至可能是分支预测失败率过高？实在程序中，这几项问题往往是并存的，而且繁多地统计往往又难以对立比拟，例如 10 次访存进展 /20 次 ALU 未打满 /30 个周期的页表遍历，到底意味着瓶颈在哪里？这个问题繁多的指标往往就难以答复了。

3.3 TMAM

TMAM（Top-down Microarchitecture Analysis Method）是一种利用 CPU 外部 PMU（Performance Monitoring Unit）计数器来从上至下合成定位部件瓶颈的伎俩。例如在最顶层，首先以标定最大指令实现速率为规范（例如 Skylake 上为单周期 4 条微指令），如果无奈达到标定，则认为瓶颈在于未能充分利用部件。进一步细分以指令池为分界线，如果指令池未满，然而取指部件又无奈满负荷输入微指令，就表明『前端』存在瓶颈。另一种无奈达到最大指令速率的因素，是『前端』尽管在发射指令到指令池，然而因为谬误的预测，最终没有产出无效后果，这类损耗则被纳入『谬误预测』。除此以外的问题就是因为指令池调度执行能力有余产生的反压进展，这一类被归为『后端』瓶颈。进一步例如『后端』瓶颈还能够根 据，进展产生时，是否随同了 ALU 利用不充沛，是否随同了 Load/Store Buffer 满负荷等因素，持续进行合成细化，造成了一套整体的分析方法。例如针对 Intel，这一过程能够通过 pmu-tools 来被主动实现，对于领导精细化的程序瓶颈剖析和优化往往有很大帮忙。

int array\[1024\];
for (size\_t i = 0; i < 1024; i += 2) {int a = array\[i\];
 int b = array\[i + 1\];
 for (size\_t j = 0; j < 1024; ++j) { 
 a = a + b;
 b = a + b;}
 array\[i\] = a;
 array\[i + 1\] = b;
}

例如这是里演示一个多轮计算斐波那契数列的过程，因为计算特色中深层循环有强指令依赖，且内层循环长度远大于惯例乱序执行的指令池深度，存在较大的计算依赖瓶颈，从工具剖析也能够印证这一点。

程序的 IPC 只有 1，外部瓶颈也显示集中在『后端』外部的部件利用效率（大多工夫只利用了一个 port），此时乱序执行并没有发挥作用。

int array\[1024\];
for (size\_t i = 0; i < 1024; i += 4) {int a = array\[i\];
  int b = array\[i + 1\];
  int c = array\[i + 2\];
  int d = array\[i + 3\];
  for (size\_t j = 0; j < 1024; ++j) {
    a = a + b;
    b = a + b;
    c = c + d;
    d = c + d;
  }
  array\[i\] = a;
  array\[i + 1\] = b;
  array\[i + 2\] = c;
  array\[i + 3\] = d;
}

这里演示了典型的的循环展开办法，通过在指令窗口内同时进行两路无依赖计算，进步了指令并行度，通过工具剖析也能够确认到成果。

不过实际中，可能在寄存器上重复迭代的运算并不常见，大多状况下比拟轻的计算负载，搭配比拟多的访存动作会更常常遇到，像上面的这个例子：

struct Line {char data\[64\];
};
Line\* lines\[1024\]; // 其中乱序寄存多个缓存行
for (size\_t i = 0; i < 1024; ++i) {Line\* line = lines\[i\];
  for (size\_t j = 0; j < 64; ++j) {line->data\[j\] += j; 
 }
}

这是一个非间断内存上进行累加计算的例子，随外层迭代会跳跃式缓存行拜访，内层循环在间断缓存行上进行无依赖的计算和访存操作。

能够看到，这一次的瓶颈到了穿透缓存后的内存访存提早上，但同时内存拜访的带宽并没有被充分利用。这是因为指令窗口内尽管并发度不低，不过因为缓存档次零碎的个性，内层循环中的多个访存指令，其实最终都是期待同一行被从内存加载到缓存。导致真正触发的底层访存压力并不足以打满传输带宽，然而程序却体现出了较大的进展。

for (size\_t i = 0; i < 1024; i += 2) {Line\* line1 = lines\[i\];
  Line\* line2 = lines\[i + 1\];
  ...
  for (size\_t j = 0; j < 64; ++j) {line1->data\[j\] += j;
    line2->data\[j\] += j;
    ...
   }
 }

通过调整循环构造，在每一轮内层循环中一次性计算多行数据，能够在尽量在进展到来的指令窗口内，让更多行出于同时从内存零碎进行传输。从统计指标上也能够看出，瓶颈重心开始从穿透访存的提早，逐渐转化向访存带宽，而理论的缓存传输部件 Fill    Buffer 也开始呈现了满负荷运作的状况。

3.4 总结一下单线程并发

古代 CPU 在遇到主频瓶颈后，除了改为减少外围数，也在单核心内逐渐强化并行能力。如果说多过程多线程技术的遍及，让多外围的利用技术多少不那么常见和艰难，那么单核心内的并行减速技术，因为更加黑盒（多级缓存加乱序执行），规范性有余（SIMD），绝对遍及度和利用率都会更差一些。尽管硬件更多的细节向应用层裸露让程序的实现更加艰难，不过艰难和机会往往也是随同呈现的，既然主观倒退上这种复杂性减少曾经无可避免，那么是否能善加利用也成了工程师进行性能优化时的一项利器。随着体系结构的进一步复杂化，可见的将来一段时间里，是否利用一些体系结构的原理和工具来进行优化，也会不可避免地成为服务端工程师的一项重要技能。

四、多线程并发中的临界区爱护

相比单线程中的并发设计，多线程并发应该是更为工程师所相熟的概念。现在，将计算划分到多线程执行的利用技术自身曾经绝对成熟了，置信各个服务端工程师都有各自相熟的队列 + 线程池的小工具箱。在不做其余额定思考的状况下，单纯的大工作分段拆分，提交线程池并回收后果可能也仅仅是几行代码就能够解决的事件了。真正的难点，其实往往不在于『拆』，而在于『合』的局部，也就是工作拆分中无奈防止掉的共享数据操作环节。如果说更高的分布式层面，还能够尽可能地利用 Share Nothing 思维，在计算产生之前，就先尽量通过工作划分来做到尽可能充沛地隔离资源。然而深刻到具体的计算节点外部，如果再进行一些细粒度的拆分减速时，共享往往就难以彻底防止了。如何正确高效地解决这些无奈防止的共享问题，就波及到并发编程中的一项重要技术，临界区爱护。

4.1 什么是临界区

算法并发革新中，个别会产生两类段落，一类是多个线程间无需交互就能够独立执行的局部，这一部分随着外围增多，能够顺利地程度扩大。而另一类是须要通过操作共享的数据来实现执行，这部分操作为了可能正确执行，无奈被多个外围同时执行，只能每个线程排队通过。因而临界区内的代码，也就无奈随着外围增多来扩大，往往会成为多线程程序的瓶颈点。也是因为这个个性，临界区的效率就变得至关重要，而如何保障各个线程平安地通过临界区的办法，就是临界区爱护技术。

4.1.1 Mutual Exclusion

最根本的临界区爱护办法，就是互斥技术。这是一种典型的乐观锁算法，也就是假如临界区高概率存在竞争，因而须要先利用底层提供的机制进行仲裁，胜利取得所有权之后，才进入临界区运行。这种互斥算法，有一个典型的全局阻塞问题，也就是上图中，当临界区内的线程产生阻塞，或被操作系统换出时，会呈现一个全局执行空窗。这个执行空窗内，不仅本身无奈持续操作，未取得锁的线程也只能一起期待，造成了阻塞放大的景象。然而对于并行区，繁多线程的阻塞只会影响本身，同样位于在上图中的第二次阻塞就是如此。

因为实在产生在临界区内的阻塞往往又是不可预期的，例如产生了缺页中断，或者为了申请一块内存而要先进行一次比较复杂的内存整理。这就会让阻塞扩散的问题更加重大，很可能改为让另一个线程先进入临界区，反而能够更快顺利完成，然而当初必须所有并发参与者，都一起期待临界区持有者来实现一些并没有那么『要害』的操作。因为存在全局阻塞的可能性，采纳互斥技术进行临界区爱护的算法有着最低的阻塞容忍能力，个别在『非阻塞算法』畛域作为典型的反面教材存在。

4.1.2 Lock Free

针对互斥技术中的阻塞问题，一个改进型的临界区爱护算法是无锁技术。尽管叫做无锁，不过次要是取自非阻塞算法等级中的一种分类术语，实质上是一种乐观锁算法。也就是首先假如临界区不存在竞争，因而间接开始临界区的执行，然而通过良好的设计，让这段事后的执行是无抵触可回滚的。然而最终设计一个须要同步的提交操作，个别基于原子变量 CAS（Compare And Swap），或者版本校验等机制实现。在提交阶段如果发生冲突，那么被仲裁为失败的各方须要对临界区预执行进行回滚，并从新发动一轮尝试。

无锁技术和互斥技术最大的区别是，临界区外围的执行段落是能够相似并行段落一样独立进行，不过又不同于真正的并行段落，同时执行的临界区中，只有一个是真正无效的，其余最终将被仲裁为有效并回滚。然而引入了冗余的执行操作后，当临界区内再次发生阻塞时，不会像互斥算法那样在参加线程之间进行流传，转而让一个次优的线程胜利提交。尽管从每个并发算法参加线程的角度，存在没有执行『本质无效』计算的段落，然而这种节约计算的段落，肯定对应着另一个参加线程执行了『无效』的计算。所以从整个算法层面，可能保障不会全局进展，总是有一些无效的计算在运行。

4.1.3 Wait-Free

无锁技术次要解决了临界区内的阻塞流传问题，然而实质上，多个线程仍然是排队程序通过临界区。形象来说，有些相似交通中的三叉路口会合，无论是互斥还是无锁，最终都是把两条车道汇聚成了一条单车道，区别只是指挥是否高超能保障没有断流呈现。可是无论如何，临界区内全局吞吐升高成串行这点是独特的缺点。

而 Wait Free 级别和无锁的次要区别也就体现在这个吞吐的问题上，在无全局进展的根底上，Wait Free 进一步保障了任意算法参加线程，都应该在无限的步骤内实现。这就和无锁技术产生了区别，不只是整体算法时时刻刻存在无效计算，每个线程视角仍然是须要继续进行无效计算。这就要求了多线程在临界区内不能被细粒度地串行起来，而必须是同时都能进行无效计算。回到下面三叉路口汇聚的例子，就认为着在 Wait Free 级别下，最终汇聚的路线仍旧须要是多车道的，以保障能够同时都可能有停顿。

尽管实践角度存在不少有 Wait Free 级别的算法，不过大多为概念摸索，并不具备工业应用价值。次要是因为 Wait Free 限度了同时有停顿，然而并没有形容这个停顿有多快。因而进一步又提出了细分子类，以比拟有实际意义的 Wait-Free Population Oblivious 级别来说，额定限度了每个参加线程必须要在事后可给出的明确执行周期内实现，且这个周期不能和与参加线程数相干。这一点明确回绝了一些相似线程间合作的计划（这些计划往往引起较大的缓存竞争），以及一些须要很长很长的无限步来实现的设计。

上图实例了一个典型的 Wait Free Population Oblivious 思路。进行临界区操作前，通过一个协同操作为参加线程调配独立的 ticket，之后每个参加线程能够通过获取到的 ticket 作为标识，操作一块独立的互不烦扰的工作区，并在其中实现操作。工业可用的 Wait Free 算法个别较难设计，例如 ticket 机制要求在协调动作中原子实现工作区调配，而很多数据结构是不容易做到这样的拆分的。时至今日各种数据结构上工业可用的 Wait    Free 算法仍旧是一项继续摸索中的畛域。

4.2 无锁不是万能的

从非阻塞编程的角度看，下面的几类临界区解决计划优劣有着显著的偏序关系，即 Wait Free > Lock Free > Mutual Exclusion。这次要是从阻塞适应性角度进行的掂量，原理上并不能间接对应到性能纬度。然而仍然很容易给工程师造成一个普适印象，也就是『锁是很邪恶的货色，不应用锁来实现算法能够显著进步性能』，再联合广为流传的锁操作本身开销很重的认知，很多工程师在实践中会有对锁敬而远之的偏向。那么，这个指导思想是否是完全正确的？

让咱们先来一组试验：

// 在一个 cache line 上进行指定步长的斐波那契计算来模仿临界区计算负载
uint64\_t calc(uint64\_t\* sequence, size\_t size) {
    size\_t i;
    for (i = 0; i < size; ++i) {sequence\[(i + 1) & 7\] += sequence\[i & 7\];
    }
    return sequence\[i & 7\];
}
{   // Mutual Exclusion
    ::std::lock\_guard<::std::mutex> lock(mutex);
    sum += calc(sequence, workload);
}
{   // Lock Free / Atomic CAS
    auto current = atomic\_sum.load(::std::memory\_order\_relaxed);
    auto next = current;
    do {next = current + calc(sequence, workload);
    } while (!atomic\_sum.compare\_exchange\_weak(current, next, ::std::memory\_order\_relaxed));
}
{   // Wait Free / Atomic Modify
    atomic\_sum.fetch\_add(calc(sequence, workload), ::std::memory\_order\_relaxed);
}

这里采纳多线程累加作为案例，别离采纳上锁后累加，累加后 CAS 提交，以及累加后 FAA（Fetch And Add）提交三种办法对全局累加后果做临界区爱护。针对不同的并发数量，以及不同的临界区负载，能够造成如下的三维曲线图。

其中 Latency 项除以临界区规模进行了归一，便于形象展现临界区负载变动下的临界区爱护开销趋势，因而跨不同负载等级下不具备横向可比性。Cycles 项示意多线程协同实现总量为同样次数的累加，用到的 CPU 周期总和，总体随临界区负载变动有大量人造歪斜。100/1600 两个截面图将 3 中算法叠加在一起展现，便于直观比照。

从下面的数据中能够剖析出这样一些信息

1、基于 FAA 的 Wait Free 模式各方面都显著胜过其余办法；

2、无锁算法相比互斥算法在均匀吞吐上有肯定劣势，然而并没有达到数量级程度；

3、无锁算法随竞争晋升（临界区大小增大，或者线程增多），cpu 耗费显著回升；

基于这些信息来剖析，会发现一个和之前提到的『锁性能』的惯例认知相悖的点。性能的分水岭并没有呈现在基于锁的互斥算法和无锁算法两头，而是呈现在同为『未应用锁』的 Lock Free 和 Wait Free 算法两头。而且从 CPU 耗费角度来看，对临界区比较复杂，竞争强度高的场景，甚至 Lock Free 因为『有效预测执行』过多反而引起了过多的耗费。这表明了锁操作自身的开销尽管稍重于原子操作，但其实也并非洪水猛兽，而真正影响性能的，是临界区被迫串行执行所带来的并行能力折损。

因而当咱们遇到临界区爱护的问题时，能够先思考一下，是否能够采纳 Wait Free 的办法来实现爱护动作，如果能够的话，在性能上可能靠近齐全打消了临界区的成果。而在少数状况下，往往还是要采纳互斥或 Lock Free 来进行临界区的爱护。此时临界区的串行不可避免，所以充沛缩减临界区的占比是共性的第一要务，而是否进一步采纳 Lock Free 技术来缩小临界区爱护开销，探讨的前提也是临界区曾经显著很短，不会引起过多的有效预 测。除此以外，因为 Lock Free 算法个别对临界区须要设计成两阶段提交，以便反对回滚撤销，因而往往须要比对应的互斥爱护算法更简单，局部性也可能更差（例如某些场景必须引入链表来替换数组）。综合来看，个别如果无奈做到 Wait Free，那么无需对 Lock Free 适度执着，充沛优化临界区的互斥办法往往也足以提供和 Lock Free 相当的性能体现了。

4.3 并发计数器优化案例

从上文针对临界区爱护的多种办法所做的试验，还能够发现一个景象。随着临界区逐步减小，保护措施开销随线程数量减少而晋升的趋势都预发显著，即使是设计上效率和参加线程数本应无关的 Wait Free 级别也是一样。这对于临界区极小的并发计数器场景，依旧会是一个显著的问题。那么咱们就先从锁和原子操作的实现角度，看看这些损耗是如何导致的。

首先给出一个典型的锁实现，左侧是锁的 fast path，也就是如果在外层的原子变量操作中未发现竞争，那么其实上锁和解锁其实就只经验了一组原子变量操作。当 fast  path 检测到可能呈现抵触时，才会进入内核，尝试进行排队期待。fast  path 的存在大幅优化了低抵触场景下的锁体现，而且古代操作系统内核为了优化锁的内存开销，都提供了『Wait On Address』的性能，也就是为了反对这套排队机制，每个锁常态只须要一个整数的存储开销即可，只有在尝试期待时，才会创立和占用额定的辅助构造。

因而理论设计中，锁能够创立很多，甚至十分多，只有可能达到足够细粒度拆解抵触的成果。这其中最典型的就是 brpc 中计数器框架 bvar 的设计。

这是 bvar 中根底统计框架的设计，部分计数和全局汇聚时都通过每个 tls 附加的锁来进行临界区爱护。因为采集周期很长，抵触能够疏忽不记，因而尽管默认应用了大量的锁（统计量 * 线程数），然而并没有很大的内存耗费，而且运行开销其实很低，可能用来反对任意的汇聚操作。这个例子也能进一步体现，锁自身的耗费其实并不显著，竞争带来的软件或硬件上的串行化才是开销的外围。

不过即便竞争很低，锁也还是会由一组原子操作实现，而当咱们本人查看原子操作时，理论是由 cache 锁操作爱护的原子指令形成，而且这个指令会在乱序执行中起到内存屏障的成果升高访存重叠的可能性。因而针对十分罕用的简略计数器，在百度外部咱们进行了进一步去除部分锁的革新，来试图进一步升高统计开销。

例如对于须要同时记录次数和总和的 IntRecorder，因为须要两个 64 位加法，已经只能依赖锁来保障原子更新。但随着新 x86 机型的一直遍及，在比拟新的 X86 和 ARM 服务端机型上曾经能够做到 128bit 的原子 load/store，因而能够利用相应的高位宽指令和正确对齐来实现锁的去除。

另一个例子是 Percentile 分位值统计，因为抽样数据是一个多元素容器，而且分位值统计须要周期清空重算，因而惯例也是采纳了互斥爱护的办法。不过如果引入版本号机制，将清空操作转交给计数线程本人实现，将 sample 区域的读写齐全拆散。在这个根底上，就能够比较简单的做到线程平安，而且也不必引入原子批改。严格意义上，异步清空存在边界样本收集失落的可能性，不过因为外围的蓄水池抽样算发自身也具备随机性，在监控指标统计畛域曾经领有足够精度。

除了运行时操作，线程局部变量的组织形式原先采纳锁爱护的链表进行治理，采纳分段数据联合线程编号的办法替换后，做到空间间断化。最终整体进一步改善了计数器的性能。

4.4 并发队列优化案例

另一个在多线程编程中经常出现的数据结构就是队列，为了保障能够平安地解决并发的入队和出队操作，最根底的算法是整个队列用锁来爱护起来。

这个办法的毛病是不言而喻的，因为队列往往作为多线程驱动的数据中枢地位，大量的竞争下，队列操作被串行很容易影响整体计算的并行度。因而一个天然的改良点是，将队列头尾离开爱护，先将生产者和消费者解耦开，只追加必要的同步操作来保障不会适度入队和出队。这也是 Jave 中 LinkedBlockingQueue 所应用的做法。

在头尾拆散之后，进一步的优化进入了两个方向。首先是因为单节点的操作具备了 Lock Free 化的可能，因而产生了对应的 Michael & Scott 无锁队列算法。业界的典型实现有 Java 的 ConcurrentLinkedQueue，以及 boost 中的 boost::lockfree::queue。

而另一个方向是队列分片，行将队列拆解成多个子队列，通过支付 token 的形式抉择子队列，而子队列外部应用传统队列算法，例如 tbb:: concurrent\_queue 就是分片队列的典型实现。

对两种形式进行比照，能够发现，在强竞争下，分片队列的成果其实显著胜过单纯的无锁解决，这也是前文对于无锁技术实在成果剖析的一个体现。

除了这类通用队列，还有一个强化竞争公布，串行生产的队列也就是 bthread::ExecutionQueue，它在是 brpc 中次要用于解决多线程竞争 fd 写入的问题。利用一些乏味的技巧，对多线程生产侧做到了 Wait Free 级别。

整个队列只持有队尾，而无队头。在生产侧，第一步间接将新节点和以后尾指针进行原子替换，之后再将之前的队尾连接到新节点之后。因为无论是否存在竞争，入队操作都能通过固定的两步实现，因而入队算法是 Wait Free 的。不过这给生产侧带来的麻烦，生产同样从一个原子替换开始，将队尾置换成 nullptr，之后的生产动作就是遍历取到的单链表。然而因为生产操作分了两部实现，此时可能发现局部节点尚处于『断链』状态，因为消费者无从通晓后续节点信息，只能轮询期待生产者最终实现第二步。所以实践上，生产 / 生产算法其实甚至不是 Lock Free 的，因为如果生产者在两阶段两头被换出，那么消费者会被这个阻塞流传影响，整个生产也只能先阻塞住。然而在排队写入 fd 的场景下，专项优化生产并发是正当，也因而能够取得更好的执行效率。

不过为了能利用原子操作实现算法，bthread::ExecutionQueue 引入了链表作为数据组织形式，而链表人造存在访存跳跃的问题。那么是否能够用数组来同样实现 Wait Free 的生产甚至生产并发呢？

这就是 babylon::ConcurrentBoundedQueue 所心愿解决的问题了。

不过介绍这个队列并发原理之前，先插入一个勘误信息。其实这个队列在《内存篇》最初也简略提到过，不过过后粗略的评测显示了 acquire- release 等级下，即便不做 cache line 隔离性能也能够保障。文章发表后收到业界同好反馈，探讨发现过后的测试用例命中了 Intel Write Combining 优化技术，即当仅存在惟一一个处于期待加载的缓存行时，只写动作能够无阻塞提前完成，等缓存行实在加载结束后，再对立提交失效。然而因为内存序问题，一旦触发了第二个待加载的缓存行后，对于第一个缓存行的 Write Combine 就无奈持续失效，只能期待第二个缓存行的写实现后，能力持续提交。原理上，Write Combine 技术的确缓解了只写场景下的 False Sharing，然而只能期待一个缓存行的限度在实在场景下想要针对性利用起来限度相当大。例如在队列这个典型场景下，往往会同时两路操作数据和实现标记，很可能同时处于穿透加载中，此时是无奈利用 Write Combine 技术的。此外，可能在缓存行加载周期内，有如此充沛的同行写入，可能也只有并无实在意义的评测程序能力做到。所以从论断上讲，通常意义上的多线程 cache line 隔离还是很有必要的。

回到 babylon::ConcurrentBoundedQueue 的设计思路上，其实是将子队列拆分做到极致，将同步量粒度升高到每个数据槽位上。每个入队和出队  申请，首先利用原子自增支付一个递增的序号，之后利用循环数组的存储形式，就能够映射到一个具体的数据槽位上。依据操作是入队还是出队，在循环数组上产生了多少次折叠，就能够在一个数据槽位上造成一个间断的版本序列。例如 1 号入队和 5 号出队都对应了 1 号数据槽位，而 1 号入队预期的版本转移是 0 到 1，而 5 号出队的版本转移是 2 到 3。这样针对同一个槽位的入队和出队也能够造成一个间断的版本变更序列，一个领到序号的具体操作，只须要明确检测版本即可确认本人以后是否能够开始操作，并通过本人的版本变更和后续的操作进行同步。

通过同步量下放到每个元素的形式，入队和出队操作在能够除了最开始的序号支付存在原子操作级别的同步，后续都能够无烦扰并行发展。而更间断的数据组织，也解决了链表存储的访存跳跃问题。生产生产双端可并发的特点，也提供了更强的泛用性，理论在 MPMC（Multiple Producer Mult iple Consumer）和 MPSC（Multiple Producer Single Consumer）场景下都有不错的性能体现，在具备肯定小批量解决的场景下尤其显著。

招聘信息

欢送杰出的 C ++ 工程师退出百度，与大神一起成长。关注同名公众号百度 Geek 说，输出内推即可，咱们期待你的退出！

举荐浏览

|百度 C ++ 工程师的那些极限优化（内存篇）

|百度大规模 Service Mesh 落地实际

|一种基于实时分位数计算的零碎及办法

———- END ———-

百度 Geek 说

百度官网技术公众号上线啦！

技术干货 · 行业资讯 · 线上沙龙 · 行业大会

招聘信息 · 内推信息 · 技术书籍 · 百度周边

欢送各位同学关注