性能优化---内存篇

行不更名坐不改姓

一般来说，一个程序的性能构成要件有三点，即算法复杂度、IO开销、并发能力。
首要的影响因素是大家都熟悉的算法复杂度。一次核心算法优化和调整，可以对应用性能产生的影响甚至是代差级别的。例如LSM Tree对No-SQL吞吐的提升，又例如事件触发对epoll大并发能力的提升。通过深入利用底层（比如依赖库或指令集）特性，依然能够取得倍数甚至数量级的优化效果。这和近些年体系结构变得越发复杂有很大关联，而这些变化，典型的体现场景就是IO和并发。并发的优化，对于工程经验比较丰富的同学应该已经不陌生了，但是关于IO，尤其是『内存IO』可能需要特别说明一下。
与代码中显示写出的read/write/socket等设备IO操作不同，存储系统的IO很容易被忽略，因为这些IO透明地发生在普通CPU指令的背后，


虽然已经是十多年前的数据，但是依然可以看出，最快速的L1 cache命中和Main memory访问之间，已经拉开了多个数量级的差距。这些操作并不是在代码中被显式控制的，而是CPU帮助我们透明完成的，在简化编程难度的同时，却也引入了问题。也就是，如果不能良好地适应体系结构的特性，那么看似同样的算法，在常数项上就可能产生数量级的差异。而这种差异因为隐蔽性，恰恰是最容易被新工程师所忽略的。
内存分配

要使用内存，首先就要进行内存分配。进入了c++时代后，随着生命周期管理的便捷化，以及基于class封装的各种便捷容器封装的诞生，运行时的内存申请和释放变得越来越频繁。但是因为地址空间是整个进程所共享的一种资源，在多核心系统中就不得不考虑竞争问题。有相关经验的工程师应该会很快联想到两个著名的内存分配器，tcmalloc和jemalloc，分别来自google和facebook。下面先来对比一下两者的大致原理。
tcmalloc和jemalloc

针对多线程竞争的角度，tcmalloc和jemalloc共同的思路是引入了线程缓存机制。通过一次从后端获取大块内存，放入缓存供线程多次申请，降低对后端的实际竞争强度。而典型的不同点是，当线程缓存被击穿后，tcmalloc采用了单一的page heap（简化了中间的transfer cache和central cache，他们也是全局唯一的）来承载，而jemalloc采用了多个arena（默认甚至超过了服务器核心数）来承载。因此和网上流传的主流评测推导原理一致，在线程数较少，或释放强度较低的情况下，较为简洁的tcmalloc性能稍胜过jemalloc。而在核心数较多、申请释放强度较高的情况下，jemalloc因为锁竞争强度远小于tcmalloc，会表现出较强的性能优势。
内存访问

内存分配完成后，就到了实际进行内存访问的阶段了。一般我们可以将访存需求拆解到两个维度，一个是单线程的连续访问，另一个是多个线程的共享访问。下面就分拆到两个部分来分别谈谈各个维度的性能优化方法。
顺序访问内存的优化

一般来说，当我们要执行大段访存操作时，如果访问地址连续，那么实际效率可以获得提升。典型例如对于容器遍历访问操作，数组组织的数据，相比于比链表组织的数据，一般会有显著的性能优势。其实在内存分配的环节，我们引入的让连续分配（基本也会是连续访问）的空间地址连续性更强，也是出于这一目的。
那么下面我们先来看一看，连续性的访问产生性能差异的原理是什么。


当硬件监测到连续地址访问模式出现时，会激活多层预取器开始执行，参考当前负载等因素，将预测将要访问的数据加载到合适的缓存层级当中。这样，当后续访问真实到来的时候，能够从更近的缓存层级中获取到数据，从而加速访问速度。因为L1容量有限，L1的硬件预取步长较短，加速目标主要为了提升L2到L1，而L2和LLC的预取步长相对较长，用于将主存提升到cache。

在这里局部性概念其实充当了软硬件交互的某种约定，因为程序天然的访问模式总有一些局部性，硬件厂商就通过预测程序设计的局部性，来尽力加速这种模式的访问请求，力求做到通用提升性能。而软件设计师，则通过尽力让设计呈现更多的局部性，来激活硬件厂商设计的优化路径，使具体程序性能得到进一步优化。某种意义上讲，这不失为一个相生相伴的循环促进。
easfire：操作系统 · 虚拟内存 1（局部性&页面置换&缺页中断）
并发访问内存的优化

提到并发访问，可能要先从一个概念，缓存行（cache line）说起。
为了避免频繁的主存交互，其实缓存体系采用了类似malloc的方法，即划分一个最小单元，叫做缓存行（主流CPU上一般64Bytes），所有内存到缓存的操作，以缓存行为单位整块完成。例如对于连续访问来说，第一个Byte的访问就会触发全部64Bytes 数据都进入L1，后续的63Bytes 访问就可以直接由L1提供服务了。所以，并发访问中的第一个问题就是要考虑缓存行隔离，也就是一般可以认为，位于不同的两个缓存行的数据，是可以被真正独立加载/淘汰和转移的（因为cache间流转的最小单位是一个cache line）。
典型的问题一般叫做false share现象，也就是不慎将两个本无竞争的数据，放置在一个缓存行内，导致因为体系结构的原因，引入了『本不存在的竞争』。
缓存的一致性问题

排除了false share现象之后，其余就是真正的共享问题了，也就是确实需要位于同一个缓存行内的数据（往往就是同一个数据），多个核心都要修改的场景。由于在多核心系统中cache存在多份，因此就需要考虑这多个副本间一致性的问题。这个一致性一般由一套状态机协议保证（MESI及其变体）。
大体是，当竞争写入发生时，需要竞争所有权，未获得所有权的CPU核，只能等待同步到修改的最新结果之后，才能继续自己的修改。这里要提一下的是有个流传甚广的说法是，因为缓存系统的引入，带来了不一致，所以引发了各种多线程可见性问题。这么说其实有失偏颇，MESI本质上是一个『一致性』协议，也就是遵守协议的缓存系统，其实，对上层CPU多个核心做到了顺序一致性。比如对比一下就能发现，缓存在竞争时表现出来的处理动作，其实和只有主存时是一致的。


只是阻塞点从竞争一个物理主存单元的写入，转移到了虽然是多个缓存物理单元，但是通过协议竞争独占上。不过，正因为竞争阻塞情况并没有缓解，所以cache的引入其实搭配了另一个部件也就是写缓冲（store buffer）。


写缓冲的引入，真正开始带来的可见性问题。
以x86为例，当多核发生写竞争时，未取得所有权的写操作虽然无法生效到缓存层，但是可以在改为等待在写缓冲中。而CPU在一般情况下，可以避免等待而先开始后续指令的执行，也就是虽然CPU看来是先进行了写指令，后进行读指令，但是对缓存而言，先进行的是读指令，而写指令被阻塞到缓存重新同步之后才能进行。要注意，如果聚焦到缓存交互界面，整体依然是保证了顺序一致，但是在指令交互界面，顺序发生了颠倒。这就是典型的StoreLoad乱序成了LoadStore，也是x86上唯一的一个乱序场景。而针对典型的RISC系统来说（arm/power），为了流水线并行度更高，一般不承诺写缓冲FIFO，当一个写操作卡在写缓冲之后，后续的写操作也可能被先处理，进一步造成 StoreStore乱序。
写缓冲的引入，让竞争出现后不会立即阻塞指令流，可以容忍直到缓冲写满。但因为缓存写入完成需要周知所有L1执行作废操作完成，随着核心增多，会出现部分L1作废长尾阻塞写缓冲的情况。因此一些RISC系统引入了进一步的缓冲机制。


进一步的缓冲机制一般叫做失效队列，也就是当一个写操作只要将失效消息投递到每个L1的失效队列即视为完成，失效操作长尾不再影响写入。这一步改动甚至确实地部分破坏了缓存一致性，也就是除非一个核心等待当前失效消息排空，否则可能读取到过期数据。
到这里已经可以感受到，为了对大量常规操作进行优化，近代体系结构设计中引入了多个影响一致性的机制。但是为了能够构建正确的跨线程同步，某些关键节点上的一致性又是必不可少的。
因此，配套的功能指令应运而生，例如x86下mfence用于指导后续load等待写缓冲全部生效，armv8的lda用于确保后续load等待invalid生效完成等。这一层因为和机型与指令设计强相关，而且指令的配套使用又能带来多种不同的内存可见性效果。这就大幅增加了工程师编写正确一致性程序的成本，而且难以保证跨平台可移植。于是就到了标准化发挥作用的时候了，这个关于内存一致性领域的标准化规范，就是内存序（memory order）。
memory order 内存序

作为一种协议机制，内存序和其他协议类似，主要承担了明确定义接口层功能的作用。体系结构专家从物理层面的优化手段中，抽象总结出了多个不同层级的逻辑一致性等级来进行刻画表达。这种抽象成为了公用边界标准之后，硬件和软件研发者就可以独立开展各自的优化工作，而最终形成跨平台通用解决方案。
对于硬件研发者来说，只要能够最终设计一些特定的指令或指令组合，支持能够实现这些内存序规范的功能，那么任意的设计扩展原理上都是可行的，不用考虑有软件兼容性风险。同样，对于软件研发者来说，只要按照标准的逻辑层来理解一致性，并使用正确的内存序，就可以不用关注底层平台细节，写出跨平台兼容的多线程程序。


在这个样例中可以看到，在编译层，默认对于无关指令，会进行一定程度的顺序调整（不影响正确性的前提下）。另一方面，编译器默认可以假定不受其他线程影响，因此同一个数据连续的多次内存访问可以省略。
easfire：C++ · 多线程编程 3 （结构体/ 条件变量/ 原子操作）

• relaxed
  

下面看一下最基础的内存序等级，relaxed。


在使用了基础的内存序等级relaxed之后，编译器不再假设不受其他线程影响，每个循环都会重新加载flag。另外可以观测到flag和payload的乱序被恢复了，不过原理上relaxed并不保证顺序，也就是这个顺序并不是一个编译器的保证承诺。总体来说，relaxed等级和普通的读写操作区别不大，只是保证了对应的内存访问不可省略。

• consume-release
  

更进一步的内存序等级是consume-release，不过当前没有对应的实现案例，一般都被默认提升到了下一个等级，也就是第一个真实有意义的内存序等级acquire-release。先从原理上讲，一般可以按照满足条件/给出承诺的方式来简化理解，即：

• 要求：对同一变量M分别进行写（release）A和读（acquire）B，B读到了A写入的值。
  
• 承诺：A之前的所有其他写操作，对B之后的读操作可见。
  
• 实际影响：
  

• 涉及到的操作不会发生穿越A/B操作的重排；
  
• X86：无额外指令；
  
• ARMv8：A之前排空store buffer，B之后排空invalid queue，A/B保序；
  
• ARMv7&Power：A之前全屏障，B之后全屏障。
  

由于x86默认内存序不低于acquire-release，这里用ARMv8汇编来演示效果。可以看出对应指令发生了替换，从st/ld变更到了stl/lda，从而利用armv8的体系结构实现了相应的内存序语义。

• sequentially-consistent
  

再进一步的内存序，就是最强的一级sequentially-consistent，其实就是恢复到了MESI的承诺等级，即顺序一致。同样可以按照满足条件/给出承诺的方式来简化理解，即：

• 要求：对两个变量M，N的（Sequentially Consistent）写操作Am，An。在任意线程中，通过（Sequentially Consistent）的读操作观测到Am先于An。
  
• 承诺：在其他线程通过（Sequentially Consistent）的读操作B也会观测到Am先于An。
  
• 实际影响：
  

• X86：Am和An之后清空store buffer，读操作B无额外指令；
  
• ARMv8：Am和An之前排空store buffer， B之后排空invalid queue，A/B保序；
  
• ARMv7：Am和An前后全屏障，B之后全屏障；
  
• POWER：Am和An前全屏障，B前后全屏障。
  

值得注意的是，ARMv8开始，特意优化了sequentially-consistent等级，省略了全屏障成本。推测是因为顺序一致在std::atomic实现中作为默认等级提供，为了通用意义上提升性能做了专门的优化。
理解 memory order 如何帮助我们

先给出一个基本测试的结论，看一下一组对比数据：

• 多线程竞争写入近邻地址sequentially-consistent：0.71单位时间
  
• 多线程竞争写入近邻地址release：0.006单位时间
  
• 多线程竞争写入cache line隔离地址sequentially-consistent：0.38单位时间
  
• 多线程竞争写入cache line隔离地址release：0.02单位时间
  

这里可以看出，做cache line隔离，对于sequentially-consistent内存序下，有一定的收益，但是对release内存序，反而有负效果。这是由于release内存序下，因为没有强内存屏障，写缓冲起到了竞争缓解的作用。而在充分缓解了竞争之后，因为cache line隔离引入了相同吞吐下更多cache line的传输交互，反而开销变大。
在这个信息指导下，我们在实现无锁队列时，采用了循环数组 + 分槽位版本号的模式来实现。因为队列操作只需要acquire-release等级，分槽位版本号间无需采用cache line隔离模式设计，整体达到了比较高的并发性能。



参考资料：
百度C++工程师的那些极限优化（内存篇）
https://www.cs.cornell.edu/projects/ladis2009/talks/dean-keynote-ladis2009.pdf
TCMalloc Overview
UncP：JeMalloc
hellocode：图解 TCMalloc
easfire：操作系统 · 虚拟内存 1（局部性&页面置换&缺页中断）
https://en.wikipedia.org/wiki/MESI_protocol
std::memory_order - cppreference.com

闲着玩

OMG！介是啥东东！！！