百度C 工程师的那些极限优化（并发篇）
时间：2021-07-03 15:15:34
手机看文章
扫描二维码
随时随地手机看文章
[导读]对于工程经验比较丰富的同学，并发应该也并不是陌生的概念了，但是每个人所理解的并发问题，却又往往并不统一，本文系统梳理了百度C 工程师在进行并发优化时所作的工作。
导读：对于工程经验比较丰富的同学，并发应该也并不是陌生的概念了，但是每个人所理解的并发问题，却又往往并不统一，本文系统梳理了百度C 工程师在进行并发优化时所作的工作。
全文15706字，预计阅读时间24分钟。
一、背景
简单回顾一下，一个程序的性能构成要件大概有三个，即算法复杂度、IO开销和并发能力。由于现代计算机体系结构复杂化，造成很多时候，工程师的性能优化会更集中在算法复杂度之外的另外两个方向上，即IO和并发，在之前的《百度C 工程师的那些极限优化（内存篇）》中，我们介绍了百度C 工程师工程师为了优化性能，从内存IO角度出发所做的一些优化案例。
这次我们就再来聊一聊另外一个性能优化的方向，也就是所谓的并发优化。和IO方向类似，对于工程经验比较丰富的同学，并发应该也并不是陌生的概念了，但是每个人所理解的并发问题，却又往往并不统一。所以下面我们先回到一个更根本的问题，重新梳理一下所谓的并发优化。
这时第一个会冒出来的概念可能会是大规模，例如我们要设计大规模互联网应用，大规模机器学习系统。可是我们仔细思考一下，无论使用了那种程度的并发设计，这样的规模化系统背后，都需要成百上千的实例来支撑。也就是，如果一个设计（尤其是无状态计算服务设计）已经可以支持某种小规模业务。那么当规模扩大时，很可能手段并不是提升某个业务单元的处理能力，而是增加更多业务单元，并解决可能遇到的分布式问题。
其实真正让并发编程变得有价值的背景，更多是业务单元本身的处理能力无法满足需求，例如一次请求处理时间过久，业务精细化导致复杂度积累提升等等问题。那么又是什么导致了近些年来，业务单元处理能力问题不足的问题呈现更加突出的趋势？可能下面这个统计会很说明问题：（https://www.karlrupp.net/2015/06/40-years-of-microprocessor-trend-data/）
上图从一个长线角度，统计了CPU的核心指标参数趋势。从其中的晶体管数目趋势可以看出，虽然可能逐渐艰难，但是摩尔定律依然尚能维持。然而近十多年，出于控制功耗等因素的考虑，CPU的主频增长基本已经停滞，持续增加的晶体管转而用来构建了更多的核心。
从CPU厂商角度来看，单片处理器所能提供的性能还是保持了持续提升的，但是单线程的性能增长已经显著放缓。从工程师角度来看，最大的变化是硬件红利不再能透明地转化成程序的性能提升了。随时代进步，更精准的算法，更复杂的计算需求，都在对的计算性能提出持续提升的要求。早些年，这些算力的增长需求大部分还可以通过处理器更新换代来自然解决，可是随着主频增长停滞，如果无法利用多核心来加速，程序的处理性能就会随主频一同面临增长停滞的问题。因此近些年来，是否能够充分利用多核心计算，也越来越成为高性能程序的一个标签，也只有具备了充分的多核心利用能力，才能随新型硬件演进，继续表现出指数级的性能提升。而伴随多核心多线程程序设计的普及，如何处理好程序的并发也逐渐成了工程师的一项必要技能。
上图描述了并发加速的基本原理，首先是对原始算法的单一执行块拆分成多个能够同时运行的子任务，并设计好子任务间的协同。之后利用底层的并行执行部件能力，将多个子任务在时间上真正重叠起来，达到真正提升处理速度的目的。
需要注意的是还有一条从下而上的反向剪头，主要表达了，为了正确高效地利用并行执行部件，往往会反向指导上层的并发设计，例如正确地数据对齐，合理的临界区实现等。虽然加速看似完全是由底层并行执行部件的能力所带来的，程序设计上只需要做到子任务拆分即可。但是现阶段，执行部件对上层还无法达到透明的程度，导致这条反向依赖对于最终的正确性和性能依然至关重要。既了解算法，又理解底层设计，并结合起来实现合理的并发改造，也就成为了工程师的一项重要技能。
上图是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
全文15706字，预计阅读时间24分钟。
一、背景
简单回顾一下，一个程序的性能构成要件大概有三个，即算法复杂度、IO开销和并发能力。由于现代计算机体系结构复杂化，造成很多时候，工程师的性能优化会更集中在算法复杂度之外的另外两个方向上，即IO和并发，在之前的《百度C 工程师的那些极限优化（内存篇）》中，我们介绍了百度C 工程师工程师为了优化性能，从内存IO角度出发所做的一些优化案例。
这次我们就再来聊一聊另外一个性能优化的方向，也就是所谓的并发优化。和IO方向类似，对于工程经验比较丰富的同学，并发应该也并不是陌生的概念了，但是每个人所理解的并发问题，却又往往并不统一。所以下面我们先回到一个更根本的问题，重新梳理一下所谓的并发优化。
二、为什么我们需要并发？
是的，这个问题可能有些跳跃，但是在自然地进展到如何处理各种并发问题之前，我们确实需要先停下来，回想一下为什么我们需要并发？这时第一个会冒出来的概念可能会是大规模，例如我们要设计大规模互联网应用，大规模机器学习系统。可是我们仔细思考一下，无论使用了那种程度的并发设计，这样的规模化系统背后，都需要成百上千的实例来支撑。也就是，如果一个设计（尤其是无状态计算服务设计）已经可以支持某种小规模业务。那么当规模扩大时，很可能手段并不是提升某个业务单元的处理能力，而是增加更多业务单元，并解决可能遇到的分布式问题。
其实真正让并发编程变得有价值的背景，更多是业务单元本身的处理能力无法满足需求，例如一次请求处理时间过久，业务精细化导致复杂度积累提升等等问题。那么又是什么导致了近些年来，业务单元处理能力问题不足的问题呈现更加突出的趋势？可能下面这个统计会很说明问题：（https://www.karlrupp.net/2015/06/40-years-of-microprocessor-trend-data/）
上图从一个长线角度，统计了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
下载文档
