C++ 高性能编程实战系列（1）

ainatipen

在主流的编程语言中，C++ 算是比较晦涩和难以上手的，特别是对于新手 C++ 程序员，基本就是 C 语言带 STL. 而那些 C++ 的拥趸们最引以为豪的就是 C++ 的高性能（低延迟），这样的论调随处可见，而关于具体如何操作却很少提及。笔者试图总结下这方面的实战经验，大家一起交流学习。部分内容来源于网络，部分来源于个人工作中的实践。
1、高性能编程关注点

1. 系统层面

• 简化控制流程和数据流程
  
• 减少消息传递次数
  
• 负载均衡，比如避免个别服务器成为性能瓶颈
  
• 充分利用硬件性能，比如打满 CPU
  
• 减少系统额外开销，比如上下文切换等
  
• 批处理与数据预取、内存屏障、绑核、伪共享、核隔离等
  

2. 算法层面

• 高效算法降低时间和空间复杂度
  
• 高效的数据结构设计，比如
  

• 增加任务的并发性（如协程）、减少锁的开销（lock_free）
  

3. 代码层面

• I-cache（指令），D-cache（数据） 优化
  
• 代码执行顺序的调整，比如减少分支预测失败率
  
• 编译优化选项，比如 PGO、LTO、BOLT等
  
• 语言本身相关的优化技巧
  
• 减少函数调用栈的深度
  
• 操作放置到编译期执行，比如模板
  

2、预置知识 - Cache

1. Cache hierarchy
Cache（缓存）一般分为 3 级：L1、L2、L3. 通常来说 L1、L2是集成在 CPU 里面的（可以称之为On-chip cache），而 L3 是放在 CPU 外面（可以称之为 Off-chip cache）。当然这个不是绝对的，不同 CPU 的做法可能会不太一样。当然，Register（寄存器）里的数据读写是最快的。
2. Cache size
Cache 的容量决定了有多少代码和数据可以放到 Cache 里面，如果一个程序的热点（hotspot）已经完全填充了整个 Cache，那 么再从 Cache 角度考虑优化就是白费力气了。
3. Cache line size
CPU 从内存 Load 数据是一次一个 cache line；往内存里面写也是一次一个 cache line，所以一个 cache line 里面的数据最好是读写分开，否则就会相互影响。
4. Cache associative
全关联(full associative)：内存可以映射到任意一个 Cache line；
N-way 关联：这个就是一个哈希表的结构，N 就是冲突链的长度，超过了 N，就需要替换。
5. Cache type
I-cache（指令）、D-cache（数据）、TLB（MMU 的 cache），参考：
3、系统优化方法

1. Asynchronous
异步，yyds！
2. Polling
Polling 是网络设备里面常用的一个技术，比如 Linux 的 NAPI 或者 epoll。与之对应的是中断，或者是事件。Polling 避免了状态切换的开销，所以有更高的性能。但是，如果系统里面有多种任务，如何在 Polling 的时候，保证其他任务的执行时间？Polling 通常意味着独占，此时系统无法响应其他事件，可能会造成严重后果。凡是能用事件或中断的地方都能用 Polling 替代，是否合理，需要结合系统的数据流程来决定。
3. 静态内存池
静态内存有更好的性能，但是适应性较差（特别是系统里面有多个 任务的时候），而且会有浪费（提前分配，还没用到就分配了）。
4. 并发优化：lock-free 和 lock-less。
lock-free 是完全无锁的设计，有两种实现方式：
Per-cpu data， 上文已经提及过，就是 thread local
CAS based，CAS 是 compare and swap，这是一个原子操作（spinlock 的实现同样需要 compare and swap，但区别是 spinlock 只有两个状态 LOCKED 和 UNLOCKED，而 CAS 的变量可以有多个状态）；其次，CAS 的实现必须由硬件来保障(原子操作)，CAS 一次可以操作 32 bits，也有 MCAS，一次可以修改一块内存。基于 CAS 实现的数据结构没有一个统一、一致的实现方法，所以有时不如直接加锁的算法那么简单，直接，针对不同的数据结构，有不同的 CAS 实现方法，读者可以自己搜索。
lock-less 的目的是减少锁的争用（contention），而不是减少锁。这个和锁的粒度（granularity）相关，锁的粒度越小，等待的时间就越短，并发的时间就越长。
锁的争用，需要考虑不同线程在获取锁后，会执行哪些不同的动作。比如多线程队列，一般情况下，我们一把锁锁住整个队列，性能很差。如果所有的 enqueue 操作都是往队列的尾部插入新节点，而所有的 dequeue 操作都是从队列的头部删除节点，那么 enqueue 和 dequeue 大部分时候都是相互独立的，我们大部分时候根本不需要锁住整个队列，白白损失性能！那么一个很自然就能想到的算法优化方案就呼之欲出了：我们可以把那个队列锁拆成两个：一个队列头部锁（head lock)和一个队列尾部锁(tail lock)，伪代码如下：
typedef struct node_t {
    TYPE value;
    node_t *next
} NODE;

typedef struct queue_t {
    NODE *head;
    NODE *tail;
    LOCK q_h_lock;
    LOCK q_t_lock;
} Q;

initialize(Q *q) {
   node = new_node()   // Allocate a free node
   node->next = NULL   // Make it the only node in the linked list
   q->head = q->tail = node   // Both head and tail point to it
   q->q_h_lock = q->q_t_lock = FREE   // Locks are initially free
}

enqueue(Q *q, TYPE value) {
   node = new_node()       // Allocate a new node from the free list
   node->value = value     // Copy enqueued value into node
   node->next = NULL       // Set next pointer of node to NULL
   lock(&q->q_t_lock)      // Acquire t_lock in order to access Tail
      q->tail->next = node // Link node at the end of the queue
      q->tail = node       // Swing Tail to node
   unlock(&q->q_t_lock)    // Release t_lock
｝

dequeue(Q *q, TYPE *pvalue) {
   lock(&q->q_h_lock)   // Acquire h_lock in order to access Head
      node = q->head    // Read Head
      new_head = node->next       // Read next pointer
      if new_head == NULL         // Is queue empty?
         unlock(&q->q_h_lock)     <span class="c1">// Release h_lock before return
         return FALSE             // Queue was empty
      endif
      *pvalue = new_head->value   // Queue not empty, read value
      q->head = new_head  // Swing Head to next node
   unlock(&q->q_h_lock)   // Release h_lock
   free(node)             // Free node
   return TRUE            // Queue was not empty, dequeue succeeded
}
具体实现可参考：高性能多线程队列、
5. 进程间通信 - 共享内存
关于各种进程间通信的方式详细介绍和比较，下面这篇文章讲得非常详细：
对于本地进程间需要高频次的大量数据交互，首推共享内存这种方案。
现代操作系统普遍采用了基于虚拟内存的管理方案，在这种内存管理方式之下，各个进程之间进行了强制隔离。程序代码中使用的内存地址均是一个虚拟地址，由操作系统的内存管理算法提前分配映射到对应的物理内存页面，CPU在执行代码指令时，对访问到的内存地址再进行实时的转换翻译。


从上图可以看出，不同进程之中，虽然是同一个内存地址，最终在操作系统和 CPU 的配合下，实际存储数据的内存页面却是不同的。而共享内存这种进程间通信方案的核心在于：如果让同一个物理内存页面映射到两个进程地址空间中，双方不是就可以直接读写，而无需拷贝了吗？


当然，共享内存只是最终的数据传输载体，双方要实现通信还得借助信号、信号量等其他通知机制。
6.  I/O 优化 - 多路复用技术
网络编程中，当每个线程都要阻塞在 recv 等待对方的请求，如果访问的人多了，线程开的就多了，大量线程都在阻塞，系统运转速度也随之下降。这个时候，你需要多路复用技术，使用 select 模型，将所有等待（accept、recv）都放在主线程里，工作线程不需要再等待。


但是，select 不能应付海量的网站访问。这个时候，你需要升级多路复用模型为 epoll。select 有三弊，epoll 有三优：

• select 底层采用数组来管理套接字描述符，同时管理的数量有上限，一般不超过几千个，epoll使用树和链表来管理，同时管理数量可以很大
  
• select不会告诉你到底哪个套接字来了消息，你需要一个个去询问。epoll 直接告诉你谁来了消息，不用轮询
  
• select进行系统调用时还需要把套接字列表在用户空间和内核空间来回拷贝，循环中调用 select 时简直浪费。epoll 统一在内核管理套接字描述符，无需来回拷贝
  

7. 线程池技术  
使用一个公共的任务队列，请求来临时，向队列中投递任务，各个工作线程统一从队列中不断取出任务来处理，这就是线程池技术。


多线程技术的使用一定程度提升了服务器的并发能力，但同时，多个线程之间为了数据同步，常常需要使用互斥体、信号、条件变量等手段来同步多个线程。这些重量级的同步手段往往会导致线程在用户态/内核态多次切换，系统调用，线程切换都是不小的开销。具体实现，请参考这篇文章：
4、算法优化

比如高效的过滤算法、哈希算法、分治算法等等，大家在刷题的过程中估计都能感受到算法的魅力了，这里不再赘述。
5、代码层次优化

1. I-cache 优化
一是相关的源文件要放在一起；二是相关的函数在object文件里面，也应该是相邻的。这样，在可执行文件被加载到内存里面的时候，函数的位置也是相邻的。相邻的函数，冲突的几率比较小。而且相关的函数放在一起，也符合模块化编程的要求：那就是 高内聚，低耦合。
如果能够把一个 ode path 上的函数编译到一起（需要编译器支持，把相关函数编译到一起）， 很显然会提高 I-cache 的命中率，减少冲突。但是一个系统有很多个 code path，所以不可能面面俱到。不同的性能指标，在优化的时候可能是冲突的。所以尽量做对所以 case 都有效的优化，虽然做到这一点比较难。
常见的手段有函数重排（获取程序运行轨迹，重排二进制目标文件（elf 文件）里的代码段）、函数冷热分区等。
2. D-cache相关优化

• Cache line alignment （cache 对齐）
  

数据跨越两个 cacheline，就意味着两次 load 或者两次 store。如果数据结构是 cacheline 对齐的，就有可能减少一次读写。数据结构的首地址 cache line 对齐，意味着可能有内存浪费（特别是数组这样连续分配的数据结构），所以需要在空间和时间两方面权衡。

• 分支预测
  

likely/unlikely

• Data prefetch (数据预取）
  

使用 X86 架构下 gcc 内置的预取指令集：
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int binarySearch(int *array, int number_of_elements, int key) {
         int low = 0, high = number_of_elements-1, mid;
         while(low <= high) {
                 mid = (low + high)/2;
            #ifdef DO_PREFETCH
            // low path
            __builtin_prefetch (&array[(mid + 1 + high)/2], 0, 1);
            // high path
            __builtin_prefetch (&array[(low + mid - 1)/2], 0, 1);
            #endif

                 if(array[mid] < key)
                         low = mid + 1;
                 else if(array[mid] == key)
                         return mid;
                 else if(array[mid] > key)
                         high = mid-1;
         }
         return -1;
}

• Register parameters （寄存器参数）
  

一般来说，函数调用的参数少于某个数，比如 3，参数是通过寄存器传递的（这个要看 ABI 的约定）。所以，写函数的时候，不要带那么多参数。

• Lazy computation （延迟计算）
  

延迟计算的意思是最近用不上的变量，就不要去初始化。通常来说，在函数开始就会初始化很多数据，但是这些数据在函数执行过程中并没有用到（比如一个分支判断，就退出了函数），那么这些动作就是浪费了。
变量初始化是一个好的编程习惯，但是在性能优化的时候，有可能就是一个多余的动作，需要综合考虑函数的各个分支，做出决定。
延迟计算也可以是系统层次的优化，比如 COW(copy-on-write) 就是在 fork 子进程的时候，并没有复制父进程所有的页表，而是只复制指令部分。当有写发生的时候，再复制数据部分，这样可以避免不必要的复制，提供进程创建的速度。

• Early computation （提前计算）
  

有些变量，需要计算一次，多次使用的时候。最好是提前计算一下，保存结果，以后再引用，避免每次都重新计算一次。

• Allocation on stack （局部变量）
  

适当定义一些全局变量避免栈上的变量

• Per-cpu data structure (非共享的数据结构）
  

比如并发编程时，给每个线程分配独立的内存空间

• Move exception path out （把 exception 处理放到另一个函数里面）
  

只要引入了异常机制，无论系统是否会抛出异常，异常代码都会影响代码的大小与性能；未触发异常时对系统影响并不明显，主要影响一些编译优化手段；触发异常之后按异常实现机制的不同，其对系统性能的影响也不相同，不过一般很明显。所以，不用担心异常对正常代码逻辑性能的影响，同时不要借用异常机制处理业务逻辑。现代 C++ 编译器所使用的异常机制对正常代码性能的影响并不明显，只有出现异常的时候异常机制才会影响整个系统的性能，这里有一些测试数据。
另外，把 exception path 和 critical path 放到一起（代码混合在一起），就会影响 critical path 的 cache 性能。而很多时候，exception path 都是长篇大论，有点喧宾夺主的感觉。如果能把 critical path 和 exception path 完全分离开，这样对 i-cache 有很大帮助

• Read, write split （读写分离）
  

伪共享(false sharing)：就是说两个无关的变量，一个读，一个写，而这两个变量在一个cache line里面。那么写会导致cache line失效（通常是在多核编程里面，两个变量在不同的core上引用）。读写分离是一个很难运用的技巧，特别是在code很复杂的情况下。需要不断地调试，是个力气活（如果有工具帮助会好一点，比如 cache miss时触发 cpu 的 execption 处理之类的）
6、总结

上面所列举的大多数还是通用的高性能编程手段，从物理硬件 CPU、内存、硬盘、网卡到软件层面的通信、缓存、算法、架构每一个环节的优化都是通往高性能的道路。软件性能瓶颈定位的常用手段有 perf（火焰图）以及在 Intel CPU 上使用 pmu-tools 进行 TopDown 分析。接下来，我们将从 C++ 编程语言本身层面出发，探讨下不同场景下最高效的 C++ 代码实现方式。

RecursiveFrog

请问有没有书籍推荐呢或者有路线图么

JoshWindsor

我也没看到哇，只能在实践中摸索…

mastertravels77

给前辈点赞！