《提高C++性能的编程技术》笔记：设计优化/可扩展性/系统体系结构

笔记列表

1. 设计优化

我们可以粗略地将性能优化分为两种类型：编码优化和设计优化。编码优化定义为不需要完整理解要解决的问题或者应用程序的执行流程就能实施的优化。通过定义看出，编码优化用于局部代码，同时该过程不牵涉周围的代码。除了这些容易实现的优化之外，剩下的所有优化都可以归结为设计优化。这些优化是系统性的----它们依赖于其它组件甚至一些关联度很低的模块的代码。设计优化贯穿于所有代码。

设计灵活性：软件库是通用的，但应用程序却不是。将关注的焦点集中于代码的细节将会产生更高效的代码。可以通过降低灵活性来增加效率。

缓存：缓存先前的结果有多种不同的方式。其中的一种方式是将其作为对象的成员数据。如果你发现自己的程序不断重复地使用一个对象来获得一个相关的结果，那么更好的做法是将这个结果作为此对象的数据成员保存起来，并在将来的计算中使用。

高效的数据结构：软件性能通常等同于算法和所使用的数据结构的效率，有时算法和数据结构的效率被认为是影响软件性能的最重要因素。不论事实如何，使用高效率的算法是实现软件高效率的一个必要条件，这是毋庸置疑的。

延迟计算：许多性能优化通过更高效的计算方法来获取速度。一些重大的性能优化不仅可以通过提高计算速度实现，还通过消除计算来获得。

无用计算：

无效代码：造成的损害包括增加了可执行程序的规模、增大了内存占用，以及产生了源代码冗余。充斥着失效代码和僵死代码的源代码难于理解、维护和扩展。

在软件性能和灵活性之间存在一种基本的平衡。对于在80%时间内执行的20%的软件，性能通常损失在灵活性上。

在代码细节中可以利用缓存优化代码，在这个程序设计中也能采用这种方法。通常可以通过将先前的计算结果保存起来避免大量的计算。

对于软件的高效性而言，使用高效的算法和数据结构是必要条件，但并非充分条件。

有些计算只有在特定执行条件下才需要。这些计算应该被推迟到确实需要它们的路径上来完成。如果过早地执行计算，那么其结果可能并没有被调用。

大型软件往往会变得错综复杂，杂乱不堪。混乱软件的一大特点就是执行失效代码：那些曾经用来实现某个目标，但现在已经不需要的代码。定期清理失效和僵死代码可以增强软件性能，同时对于软件也是一种维护。

2. 可扩展性

可扩展性面对的挑战是使应用程序的运行速度跟得上处理器能力的提升。

主流的单处理器架构由一个CPU和一个主存模块组成，其中程序数据和指令存储在主存中。因为CPU的速度至少比主存快一个数量级，所以我们在处理器(CPU)和主存之间插入了一块快速内存作为缓冲。这块内存也被称为缓存。缓存可以提供更快的速度来访问程序数据和指令。缓存分为两个物理模块，其中一个存储数据，另一个存储指令。为了获取指令本身，对于每条指令处理器至少需要访问一次内存。而绝大多数的指令都需要额外内存参照物来获取数据。每当处理器需要访问内存时，首先会在缓存里寻找，因为缓存的访问命中率高达90%，所以访问主存的次数很少。

应用程序是由一个进程或多个协作进程组成。而每个进程由一个或多个线程组成。在现代操作系统中，调度的实体就是线程。操作系统执行的是线程，而不是进程。线程都放在系统的运行队列(Run Queue)里等待调度。在队列前端的线程就是下一个即将被执行的线程。

现代单处理器计算机由抢占式多任务处理操作系统控制，而该操作系统造成了程序是并发执行的错觉。从用户的角度来看，多个程序在并发执行。但正如所说的，这是一个错觉。在硬件的层面上，任意时刻内都仅有一个线程在单CPU上运行，多任务是通过线程轮流使用CPU来完成的。

对称多处理器(Symmetric MultiProcessor, SMP)架构：特点：首先是多处理器(MP)，这种系统包含多个同样的CPU；其次是对称的，所有的处理器对于系统来说都是一样的，都有相同的处理能力。例如，它们都有一样的访问内存中的任何位置和任意I/O设备的能力。最后，剩余的组成部分是唯一的。这种架构只有一个内存系统、一个操作系统拷贝和一个运行队列。SMP架构具有扩展性的潜力。

Amdahl定律：针对应用程序的顺序执行部分会限制其可扩展性的情况，Amdahl定律做了量化分析。顺序(单线程)计算是可扩展性的主要绊脚石。

多线程和同步：以下面的简单代码为例：x = x + 1; 假设两个线程执行上面的语句，我们期望x的值变为x+2，当然其它的结果都是不正确的。但问题是这个语句并不是原子执行，实际上它会被分解为以下汇编语句：

1
2
3

load x, r5 // 将x的值读入r5寄存器
add r5, 1 // r5寄存器加1
store r5, x //将r5寄存器的值存回x

如果两个线程几乎同时执行这段代码，它们的指令可能以某种方式交替执行，而这种方式会导致x+1成为x的新值，而不是x+2。这种不合适的交叉执行线程被称为竞争条件，为了解决竞争条件，就需要保证这些汇编代码块是原子执行的，我们称这些代码块为临界区。一旦有线程进入临界区，只有当进入的线程离开后其它的线程才能进入。在这种情况下，我们称这两个线程是同步的(或者说串行化的)，同时称该临界区是互斥的。因为变量x可以被多个线程访问，所以我们称它为共享数据，临界区就是为解决对共享数据的访问而设置的。为了保证共享数据的访问安全(以及正确执行)，我们使用一个锁----一个标记(比特位或者整型)与共享数据相关联。线程进入临界区之前首先要检查锁的状态，如果锁的状态是关闭的，则说明当前没有其它线程在临界区内执行，因此允许该线程进入临界区，同时将锁的状态变为打开，以此来表示已有线程进入到临界区内(检查和设定锁状态的操作由硬件来保证是原子的)。如果锁是打开的，该线程必须要等待当前在临界区中执行的线程改变锁的状态后才能进入临界区。当临界区由锁来保护时，我们称它的执行是顺序进行的，因为想进入临界区的线程必须得在队列里等候，并且每次仅进入一个。

将任务分解为多个子任务：为了发挥可扩展性的潜力，应用程序必须将计算任务分为多个可以并行执行的子任务。

缓存共享数据：一旦能越过临界区访问，就会看到可扩展性为应用程序所带来的好处。这个想法的最简答的应用就是缓存共享数据，这些数据在将来的访问中不需要锁来控制就能重用。

无共享：减少共享是件好事，但并没有完全消除竞争。有时，可以为每个线程提供仅供其使用的私有资源而非共享资源，来完全消除共享。

部分共享：当每个线程都需要资源的单个实例时，可以使实例成为线程私有对象来轻松地消除竞争。如果不能事先确定所需实例的数量，你就需要使用资源池，让所有线程共享。这样共享资源经常成为线程竞争的焦点，会严重地降低性能和可扩展性，导致线程大量时间都处于空转状态。部分共享资源池提供了一种解决这种激烈竞争的方法。

锁粒度：使用单个锁来保护多个不相关的共享资源，一般来说都不是一个好主意。这样做会扩大临界区的范围，并造成其它不相关的线程间冲突。此规则的唯一例外是在满足以下两个条件时：所有共享资源总是一起操作；任何共享资源的操作都不会消耗大量的CPU周期。

伪共享：缓存的原子单元以行为单位。一般来说一个缓存行可以存储大量字节,典型的缓存行有128字节。当从主内存加载4字节的整数时，并不是仅加载这4字节，而是把包含它的整个行立即加载到缓存。同样，当另外的缓存(在不同的处理器上运行)使这个整数无效时，整个缓存行都是无效的。因此，变量在物理内存中的布局对于SMP的可扩展性十分重要。缓存一致性风暴将会严重地降低性能和可扩展性。

惊群现象：当线程无法获取繁忙的锁时，将会使用下面两种方式之一处理：(1). 进入自旋，每次循环都尝试获取锁。这对于短时的锁有效，但在空自旋等待资源可用的同时，长时间的自旋锁会导致线程耗尽CPU资源。(2). 线程进入休眠并等待唤醒，当锁释放后，所有等待的线程将醒来。我们把这种类型的锁称为简单锁，用来区分自旋锁。

当很多的线程并发地竞争简单锁，那么除了获得锁的线程，其余线程都进入休眠状态。当锁最后变得可用时，将会出现两种情况：(1). 只有一个线程被唤醒，它一般是等待队列上优先级最高的线程。(2). 所有的线程都被唤醒，这会导致”惊群线程”。唤醒所有等待线程的问题在于只有一个线程是真正被唤醒的，其余线程仍旧要回去等待。鉴于线程上下文切换的耗费巨大，我们会遭到性能和可扩展性上的巨大损失。

读/写锁：另一种消除同步问题的方式是放宽只能有一个线程独占访问共享数据的要求。共享数据有时候需要顺序来访问，是因为共享数据也许只被访问它的其中一个线程修改过。所以我们可以只允许一个修改数据的线程(写者)访问共享数据。相反，只读取共享数据的线程(读者)可以同时访问共享数据。读/写锁允许多个读者线程访问共享数据而不用等待独占访问。线程对共享数据进行读访问必须满足以下条件之一：(1). 没有其它线程访问数据；(2). 所有访问数据的线程都是读者线程。如果写者线程已获取访问权，所有的读者线程都必须等待写者线程离开临街区。当且仅当没有其它线程获取对共享资源的访问权，才可以授予写者线程访问权限。如果所有线程都要修改一个共享资源，读/写锁将不会有任何的帮助。实际上，这种类型的锁会降低性能，因为它们的实现更为复杂，所以性能就低于普通锁。但如果你的共享数据在绝大多数时间里在执行读操作，而读/写锁将消除读者线程间的竞争，所以能提高扩展性。

SMP是多处理器架构。它通过一条总线连接多个对称的处理器和一个内存系统。总线是SMP架构可扩展性的薄弱环节。让每个处理器都有自己的大缓存可以有效地控制总线的竞争。

Amdahl定律给出了一个应用的可扩展性的上限，顺序化计算限制了扩展性。

实现可扩展性的技巧是减少或者消除顺序化的代码。以下是可以达到这个目标的一些步骤：

任务分解：将大的任务分为小任务，使线程并发地执行这些小任务。

代码移出：临界区应该只包含关键代码，不直接操作共享资源的代码不要放在临界区内。

利用缓存：有时，通过缓存之前访问过的数据，可以消除对临界区的访问。

无共享：如果需要少量、数目固定的资源实例，可以不使用公共资源池。你可以把这些资源实例设为线程私有，并最后回收。

部分共享：有两个一样的资源池可以减少一半的竞争。

锁粒度：不要用同样的锁来保护所有资源，除非这些资源是同时更新的。

伪共享：不要在类定义里把两个使用频度都很高的锁放太靠近。你肯定不希望它们共享同一个缓存并触发缓存一致性风暴。

惊群现象：仔细分析你的锁调用的特征。当锁被释放时，是所有的等待线程都被唤醒还是只唤醒一个线程？唤醒所有线程会威胁到应用的可扩展性。

系统和类库调用：考察这些调用的实现特征。它们有可能是隐藏了顺序化的代码。

读/写锁：以读为主的共享数据会从这种锁中获益，使用这种锁，可以消除读者线程之间的竞争。

3. 系统体系结构相关话题

存储器层级：所有对性能的讨论最终都会集中到存储器使用和存储器使用模式上。通常来说，算法复杂度最核心的方面是算法需要的存储器访问量和访问类型。通常来说,一般的计算机都至少有5个存储器层级，而一些主要的存储器层级有时还包含子层级。存储器层级从最快(访问时间最短)到最慢(访问时间最长)其排序为：寄存器、L1(第一级)芯片内缓存、L2(第二级)芯片外缓存、主存(半导体动态随机访问内存：DRAM、SDRAM、RAMBUS、SyncLink等等)、磁盘存储器。

很多人仅根据访问时间和处理器速度来研究内存访问。然而，这种观点忽视了延时和带宽的交互作用。访问时间是一个延时问题。总线宽度和脉冲时间是带宽问题。延迟并不会和带宽以同样的比例改善，或者说，我们可以用较快的速度移动数据块，但是，访问内存中的单个字节的速度提升很慢。

寄存器：存储器之王。在存储器层级上的所有实体中，寄存器延迟最短，带宽最高，开销最小。寄存器可由机器代码直接寻址。存储器层次结构的所有其它级别都基于虚拟或物理地址划分，或基于操作系统管理的存储系统(文件系统)索引来划分。保留字register告诉编译器，不要把变量放在内存，或者更精确地说，不要给变量分配内存地址。这只是一种建议，如inline保留字一样，编译器可能不理会。一些编译器会完全忽略寄存器指令。是否将一个变量放到寄存器，一个重要依据是变量被加载和存储的次数。正确地使用寄存器存放变量可以使某些编译器产生的个别方法在性能上大幅提升。

磁盘和内存结构：一般来说,程序代码会显示出很好的局域性，而对代码的存储进行管理似乎并没有必要。在一些例子里，程序代码的活动集尺寸过于庞大时，就应该根据执行情况来重新安排代码的存储位置，将相关的代码放到同一个或者多个文件中去。因为性能原因而进行代码重组是另外一个方面的考虑，这种重组可以反馈给编译器，使编译器提供更好的自动优化。

缓存效应：缓存不仅可以提供对访问过的数据更快的访问速度，同时可以为以前访问过的数据提供一小块预取内存区域。缓存每次提取几行数据，并对其进行管理。典型的缓存行包含32字节数据，这些数据按32位边界对齐。通常缓存只能管理完整的缓存行。

缓存抖动：在多处理系统中，最有趣的缓存效应是缓存一致性协议给缓存性能带来的影响。缓存一致性协议是由内存/缓存控制器所使用的一种机制，该控制器维护多个内存的一致性，否则它们会成为不相关的缓存。缓存一致性协议是基于内存所有者的概念，以及同位缓存作读操作的显示验证。这些基本相当于一种协议，该协议允许多个缓存共享一个数据的拷贝，但在一个时间点只有一个缓存有写操作的权限。缓存一致性协议要求缓存之间直接通信。这种大量通信会降低系统的性能。主要的原因是缓存之间的通信通路是系统的共享资源，这样的通信必须是顺序进行的。如果内存总线忙于处理其它缓存事务，缓存就必须等待其它忙完后才能通信。这种等待缓存更新访问被称为缓存抖动(cache thrash)。缓存抖动是典型的多处理器不能维持其它处理器关系而导致的问题。

避免跳转：最快的代码是直线型的代码：没有条件判断，没有循环，没有调用，没有返回。一般来说，程序的关键路径越像一条直线，执行速度就越快。请记住：短小而带有很多分支的代码要比长而没有分支的代码所用的执行时间长。

使用简单计算代替小分支：分支是性能的敌人。而很多时候，分支是不可避免的，但有时分支可以用计算来代替。这可能是一个重要的性能提升策略。

线程化的影响：多进程和多线程是两个关系密切但又相区别的并发编程类型。多进程允许多个独立的大进程相互通信。线程是子进程，它们是大进程的片段，但是它们都可以独立的调度。凡是从应用的角度讨论多任务都应该包含阻塞这个主题。这里有两种常见的I/O请求：阻塞和非阻塞，或者称为同步和异步。同步I/O要等待I/O请求完成后才能切换上下文，然后继续处理，也就是说同步I/O请求首先要求阻塞，直到I/O请求完成才做下一步的处理。异步I/O是在满足请求之前可以尽可能多地处理I/O事务，并要把所取得的进展返回到进程上下文，无论处理完多少事务，都不进行阻塞处理。通常还有一种中间I/O请求，这种类型的请求在某些时间里进行同步操作，而其余时间是异步操作。虽然在同步和异步操作之间的中间层可以给任务提供更有趣的操作能力，但是从性能的角度来看，它本质上仍是一种同步操作。

线程只有在同步请求资源或数据不可用时，才会阻塞。请求线程必须等待系统满足请求，而要满足这个请求就要完成I/O操作。当一个线程在等待相应的I/O操作完成时，要把它从处理器中切换出去，让其它没有被阻塞的线程运行。在I/O操作完成之后，线程再次变成可调度状态，并最终切换到处理器里运行。被阻塞的高优先级的线程将在I/O请求处理完成后立即恢复执行。

常见的程序是同步的单线程，它在某一时刻只能做一件事。一旦请求无法立即得到满足，整个程序就会被阻塞并等待操作系统完成它的请求。相反的是，一些复杂的程序会使用多个逻辑并发的物理和逻辑处理流来编写。这使得程序可执行多个相对独立的片段，而不用管它们在某个时间点是否完成了I/O请求。

多线程是一种相当有用的机制，而且在合适的系统中能带来巨大的性能优势，但错误地使用线程概念会导致严重的性能问题。多线程要求要进行上下文切换，而这种切换会耗费上千个处理周期。多线程还要频繁地使用锁来保护共享内存区域。锁也会浪费大量的处理周期，却对程序的完成没有任何作用。

上下文切换：是指将一个进程(线程)从处理器移出并把另外一个进程移入处理器。这个过程中要保存进程和处理器的状态。保存进程的状态是为了维护进程执行点的精确记录。保存处理器的状态是为了在相关进程继续执行时，处理器能返回原状态。处理器状态是进程状态的一部分，但不是全部。

进程上下文是操作系统所定义的一种结构，因此与操作系统关系密切。操作系统对该结构进行管理，这个结构包含进程的相关信息，如分配的内存范围、页映射表、打开的文件指针、子进程、处理器状态变量(寄存器、程序计数器、可能还有旁路转换缓冲，即Translation-Lookaside Buffer, TLB)，还有进程状态变量如优先级、所有者、运行时间和当前状态(可调度、已阻塞、运行中)。大多数进程状态保存在内存里，只会偶尔访问，但进程上下文的处理器状态部分一直是由处理器使用的，并且必须放在处理器里用于进程执行。每次进程换出时，与进程相关的处理器状态要从处理器移到内存里，每次进程换入时，处理器要把这部分数据加载进来。

上下文切换有三个主要的开销：处理器上下文迁移、缓存和TLB丢失，以及调度开销。上下文切换和缓存之间的交互对程序的性能影响是最有害的。缓存的结构类型对系统性能的特性有显著的影响。根据访问缓存时所用的地址类型可以将缓存分为两类。虚拟地址缓存从进程的虚拟地址空间访问。虚拟地址与进程无关。另一种缓存类型是物理地址缓存，本质上与有ID标记的虚拟缓存相同。不同点在于，它不依赖于标记里的ID地址对，而是在提交缓存之前强制系统将虚拟地址转换为物理地址。

内核交叉：异步轮询相对于同步线程而言是一个很好的替代方案。虽然异步不是一种简单的软件技术，但在一些系统里，它可以带来很多性能的优势。这个问题与内核交叉的代价联系密切，同时又与上下文切换相关。在程序显式地调用服务例程，而该例程需要以内核权限执行时，就会发生内核交叉。在发生内核交叉时下面两件事中的一件也会发生：胖系统调用和瘦系统调用；而具体发生哪一个则取决于系统所使用的机制和服务请求的类型。

线程化选择：有3种主要的划分线程的方法：单个、小型和大型。单线程简单的形式就是一个程序，只由一个线程控制。然而，在更为复杂形式中，单线程程序可以使用异步I/O来实现逻辑并发和独立操作。单线程异步模型依赖于程序内部结构来监视程序各个部分的状态，同时依赖轮询来测试这些部分的I/O有效性。使用异步I/O可以保证：第一，没有子任务会因为一些I/O请求不能立即满足而阻塞整个任务；第二，程序的控制元素可以决定什么时候交出处理器的控制权，还可以决定什么时候继续处理。这样的系统往往围绕一个中央控制循环来构造，并顺序执行每个子任务。虽然这是一个很复杂的方法，但是在一些环境里，这种方法可以提供比多线程环境更好的性能。但如果使用不当，会出现无止境的空轮询，导致任务没有进展。大型线程是一种把请求当做独立处理实体的机制。可以理解为这种线程划分方法把每个重要的对象方法都看作一个线程。当重要对象被创建时，为其分配自己的线程，该线程将伴随对象的整个生命周期，从创建到销毁。这种机制可能非常高效，但也会在上下文切换时出现问题。小型多线程是将单线程和大型多线程方法相结合的机制。小型线程倾向于把子任务的完成作为中心，而不是把完成整改独立请求作为中心。决定采用何种线程时，最重要的方面可能是将要支持程序运行的硬件。

要使用的存储器离处理器越远，访问所需的时间就越长。离处理器最近的是寄存器，虽然容量很少，但是速度很快。对寄存器的优化对程序的性能提升而言是极其有意的。

虚拟存储器并不是无偿的，不加选择地依赖系统管理的虚拟结构可能会影响性能，而且一般都是降低性能。

上下文切换的开销巨大，需避免上下文切换。

以下是测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <string.h>
#include <iostream>
#include <chrono>
#include <string>
#include <numeric>
#include <vector>
 
namespace design_optimizations_ {
 
// reference: 《提高C++性能的编程技术》：第十四章：设计优化
namespace {
 
void stringSum1(const std::vector<std::string>& vs, std::string& result)
{
	int vectorSize = vs.size();
	int* stringSizes = new int[vectorSize];
	int totalInputLength = 0;
 
	for (int i = 0; i < vectorSize; ++i) {
		stringSizes[i] = vs[i].length();
		totalInputLength += stringSizes[i];
	}
	
	char* s = new char[totalInputLength+1];
	memset(s, 0, totalInputLength+1);
 
	int sp = 0;
	for (int i = 0; i < vectorSize; ++i) {
		memcpy(&s[sp], vs[i].c_str(), stringSizes[i]);
		sp += stringSizes[i];
	}
 
	delete[] stringSizes;
	result = s;
	delete[] s;
}
 
} // namespace

} // namespace design_optimizations_
using  namespace design_optimizations_;

int main()
{
	std::chrono::high_resolution_clock::time_point time_start, time_end;
	const int count{100000}, count2{100000};
	std::vector<std::string> vectorx;
	for (int i = 0; i < 100; ++i) {
		vectorx.emplace_back("abcd");
	}
 
{ // test string add: std::accumulate: 此函数的性能弱点测试
	time_start = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < count; ++i) {
		std::string empty;
		std::string result = std::accumulate(vectorx.cbegin(), vectorx.cend(), empty);
		// fprintf(stdout, "result: %s\n", result.c_str());
	}
	time_end = std::chrono::high_resolution_clock::now();	
    fprintf(stdout, "string add operation std::accumulate time spend: %f seconds\n",
		(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}
 
{ // test string add: custom function: 为了提高性能而牺牲了通用性
	time_start = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < count; ++i) {
		std::string result;
		stringSum1(vectorx, result);
		//fprintf(stdout, "result: %s\n", result.c_str());
	}
	time_end = std::chrono::high_resolution_clock::now();	
	fprintf(stdout, "string add operation custom function time spend: %f seconds\n",
		(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}
 
	return 0;
}
 

利用 godbolt 执行，相应代码见 点击这里 测试结果如下：

1
2

string add operation std::accumulate time spend: 0.416788 seconds
string add operation custom function time spend: 0.040471 seconds