编写高效的 C++ 代码

本文最初以波兰语发表于 2013 年第 4 期（第 11 期）《Programista》杂志。

尽管高级语言——无论是脚本语言、解释型语言，还是运行在虚拟机中的语言——拥有诸多优势，并且是众多应用的首选，但有时我们仍需要编写尽可能高效的代码。仅仅选择 C++ 等原生语言是不够的。只有掌握相关知识并熟悉良好实践，才能最大程度地榨取硬件算力。

引言

C++ 是一门不太寻常的语言：复杂、难以精通，且在某些方面颇具争议。然而，在许多应用中，尤其是在性能至关重要的场景（如游戏编程）里，它往往是最佳甚至唯一的选择。这是因为 C++ 具备一种独特的性质，使其成为一种折中的方案。它兼具高层特性：支持面向对象编程，并能便捷地使用或创建自定义类型及数据结构，如向量、字符串以及其他 STL 容器。同时，它又足够底层，以某种方式让我们直接触及硬件本身，或者更准确地说，是操作系统：没有任何虚拟机或框架挡在中间。我们必须自行管理内存的分配与释放，但这同时也意味着没有垃圾收集器在不确定的时刻以它的方式介入。此外，针对 C++（以及与其部分向后兼容的 C 语言）存在海量的库，且编译器可用于众多平台。

从某种意义上说，原生代码正重新获得青睐。尽管软件日趋复杂、硬件飞速提升，我们编写程序时仍需要高效代码。有人声称，更快的处理器或更多内存的成本，低于优秀程序员的工时。但如果一个程序要运行许多年，或者被安装到数百万台设备上呢？在计算集群和数据中心里，电力和散热成本高昂，性能至关重要；在手机和平板这类小型设备上，性能同样关键，因为用户追求尽可能长的电池续航。还有一些应用要求代码必须达到特定速度，不容妥协。比如实时数据处理程序：游戏中，帧率（FPS）下降会破坏流畅的动画体验，导致令人不适的卡顿；以特定码率进行媒体流实时处理也是如此。而且，我们也不能随意设定极高的硬件要求。以游戏主机为例，其处理器速度和内存容量是固定的。如果我们在开发一款简单的休闲游戏，而非新版《孤岛危机》（Crysis），也不该要求 PC 配备最新组件。

数据导向设计

面向对象编程似乎是一种解决方案，帮助那些觉得以“传统”方式结构化编写大型系统难度太大的程序员和团队。在面向对象编程中，代码由类组成。类不仅将数据（字段）和操作它们的过程（方法）分组，更重要的是，它们作为现实世界或问题领域概念的抽象。理论上，类还应尽可能独立，以便在其他地方复用。

不过，面向对象编程有两种理解方式：一种是从概念层面，思考其元素背后的哲学；另一种是从技术层面，将其视为一种为提高便利性而使用的编程语言机制。理解其底层运作方式及由此产生的属性和限制也很有价值。如果只遵循第一种方法，当目标是编写高效代码时，可能会让我们离程序员应停留的层面太远。

那么，解决方案是什么？一种叫做数据导向设计（Data-Oriented Design，DOD）的方法支持者提出了一种颇为不同的思路。这个术语近年来流行起来，尤其在游戏程序员群体中。它的意思是：在设计编码时优先关注将要存储的数据——它在内存中的布局以及合适数据结构的设计——然后再考虑操作这些数据的算法。这看似是结构化编程老思想的回归，但并不排斥使用类和面向对象编程的各种好处。它更像是一种更贴近硬件的思维方式，利用语言提供的机制写出不仅“优雅”、而且简单高效的代码。

看图 1，它示意性地展示了数据在内存中的布局。左边是彼此相距很远、通过指针连接的结构。这种情况出现在我们使用大量相互引用的、不同类的小对象时。这样写的代码效率低下有两个原因。第一个是遍历这类数据时频繁的 cache miss，因为我们在通过指针“跳跃”。后面会详细讨论这一点。

第二个原因是，操作这类对象的代码难以并行化。如果手里只有类的 public 方法（通常是 virtual 的），而我们假设不知道它们内部（或其所有派生类内部）发生了什么，那么按定义我们就无法安全地把它们放到多个线程上运行——因为我们不知道这些操作期间它们引用了哪些其他对象。而使用线程往往需要用 mutex（临界区）保护共享数据，这会实际串行化代码，使其无法真正完全并行运行。

图右侧则展示了常规数据结构（如数组）的处理思想：对它执行一系列操作，例如排序、更新特定字段、删除元素，或将每个元素转换为另一种形式。如果数据是“透明”的，我们清楚知道想要执行的具体操作，且将该操作应用于集合中的每个元素时，彼此之间以及与程序其余部分相互独立，那么算法就很容易被并行化，例如将元素范围分配给不同的线程。

盲目遵循面向对象编程还会带来其他陷阱。有些人会下意识地为自己使用的每一项功能（比如某个库）包一层自己的 wrapper，意图简化其接口或（主观上）让它更优雅。这种额外的层，尤其是当它引入了自己的逻辑或使用虚方法时，会增加运行时开销。我建议养成一种习惯，每次都要问自己：在这个具体案例中，我们是否可以直接使用某些函数和类，而不必增加另一层抽象？还有种类似倾向，就是试图让一切都尽可能通用。定义一个全由虚方法组成的接口，并自欺欺人地认为可以无需更改接口就完全替换底层实现，这很诱人，但我们真的在此时此刻需要这样做吗？设计模式有时也被过度用作现成的解决方案，取代了对代码更深入的思考。事实上，简单的方案往往最佳。如果我们尽可能直接地表达程序需要存储哪些数据、以及必须对这些数据执行哪些操作，代码就会同时具备简单、优雅、可读和高效的特点。这与流行的观点相悖——那种观点认为优化意味着让代码变得复杂且难以阅读。

内存与缓存

乍看之下，似乎每条处理器指令都会在一个周期内从内存的指定地址读取数据，对其执行操作（如加法），并将结果写回内存。实际上没这么简单。构成 x86 代码的复杂 CISC 指令会在处理器内部被翻译为微码，并在多个步骤中执行，耗时或长或短。操作本身可能很简单，但从内存中读取或写入数据需要额外时间。

在20世纪80年代，处理器确实能直接访问 RAM 并在单周期内完成此类操作。如今，遗憾的是，处理器计算速度的提升远快于 RAM 性能的改进。这种差距持续扩大，从现代计算机主存中读取数据（哪怕只是一个字节）所需的时间，已经相当于数百个处理器周期！请记住，带宽指数据传输速率（以比特/秒衡量），而延迟指请求数据到达目的地所需的时间（以秒的分数衡量）。

计算机设计者自然在寻求解决方案，Cache（缓存）应运而生：它是一种处理器内存，用于存放最近使用过的数据，访问速度比主 RAM 更快。我们可以将其视为一个完整的内存层次结构，其每一级容量递增，但速度递减。举例来说，对于一个运行在 3 GHz 的处理器，粗略估算，它每秒可执行 30 亿次操作，因此一个简单的操作（如加法）大约需要 0.33 纳秒。如果访问 L1 cache 中的值需要 1 纳秒，这相当于执行 3 条指令（3 个周期）。表 1 给出了此类示例计算机系统中内存层次的估算数据。

内存类型	访问时间	容量
处理器寄存器	0.33 纳秒	1 个周期
L1 缓存	1 纳秒	3 个周期	32 KB
L2 缓存	4.7 纳秒	14 个周期	6 MB
RAM	83 纳秒	250 个周期	8 GB
硬盘	15 毫秒	4500 万个周期	1 TB
互联网	80 毫秒	2.4 亿个周期

表 1：内存层次结构

在典型的计算机系统中，我们并不直接控制缓存。缓存由系统自动管理，用来加速对最近使用数据的访问。那么，我们怎样才能利用缓存的速度优势呢？前提是对它的工作原理有个基本了解。当程序访问一段之前没在缓存里的 RAM 数据时，这段数据会被读取并参与计算，同时也会进入缓存。数据的传输不是逐字节进行的，而是按整条缓存行（cache line）传输，比如一条 64 字节宽的缓存行。整行数据从 RAM 读入并保存在缓存中，只要它没有被其他数据替换掉（缓存比 RAM 小得多，只能保存最近使用的条目），访问其中的任何字节都很快，因为处理器可以直接使用缓存而不必访问 RAM。这叫做缓存命中（cache hit）。反之心是缓存未命中（cache miss），此时需要访问主内存，耗时长得多。

这对我们意味着什么？要发挥缓存的作用，就应该合理安排数据在内存中的布局，让经常一起使用的数据紧挨着存放。这样，代码需要这些数据时，它们很可能已经在缓存里了。因此，好的实践包括：

• 使用能把数据连续存放在一起的数据结构，比如普通数组或 std::vector。
• 了解所用语言如何在内存中布局数据（数据类型大小、对齐、填充），并在写代码时牢记这些因素。
• 把数据 packed 到尽可能小的类型里（比如 8 位或 16 位整数、位域）。即便解包这些数据需要额外的指令，其开销也远小于缓存未命中后再访问内存的代价。

相反，坏的做法是使用大量分散在内存各处、单独分配的小对象。同理，频繁的缓存未命中还会拖慢那些靠指针“跳转”遍历的数据结构，比如链表、树和图。

举个例子，我们需要在程序中构建、驻留内存、按序遍历并快速查找一组对象。为保持有序，可能会选用二叉树等能维持顺序、且以 $O(\log n)$ 复杂度查找元素的结构，比如 STL 里的 std::set 或 std::map。但这些结构在堆上动态分配每个节点，并用指针串联，导致构建和遍历效率低下。虽然搜索的渐近复杂度优秀，但正如前文所述，较大的常数因子会让实际性能变得很差。

有时能找到一种理论复杂度不更差、实际运行却更快的替代方案。如果结构只需构建一次，后续不再涉及插入或删除，不妨直接用数组。添加完所有元素后，只需排序一次。之后就能在有序数组里用二分查找以 $O(\log n)$ 复杂度定位元素。得益于出色的缓存命中，遍历会快得多，因为连续元素在内存中也相邻。

不同操作的开销

上文的内存层级里，每下沉一级访问就更慢。类似地，这个“金字塔”模型（就像需求层次之类）也适用于其他操作。想象一座“性能金字塔”（图 2），它并非严格分类，只是挑选出若干操作的一种示意：每往下走一级，操作耗时至少比上一级慢一个数量级。要写出高效代码，就应了解这一点，并尽量避免频繁调用更下层（更慢）的操作。各层含义如下：

• 处理器能执行的最快计算，是加减乘等算术指令以及按位操作。
• 超越函数指令，即执行正弦、余弦、对数、开方、幂运算等复杂数学操作以及除法的指令，速度远慢于上述指令。因此应避免使用这些操作。例如，与其反复用某个数做除法，不如先算出它的倒数，然后用乘法代替。
• 访问 RAM 可能耗费相当于数百个处理器周期的时间（特别是在缓存未命中时），正如前文所述。这种情况不仅发生在遍历由散落在内存各处的小对象构成的数据结构（如链表）时，也发生在调用虚方法时，甚至当我们跳转到代码中一段许久未使用的远程代码段时（代码本身也存储在 RAM 中，且当前使用的部分会进入指令缓存）。
• 通过系统分配器进行动态内存分配是一项高开销操作。值得设法减少分配次数，例如复用现有缓冲区、将大量数据项存储在一块连续的内存区域（数组）中，或者编写自定义分配器，从一个预先从系统分配的内存池中划出小块空间。
• 创建和使用线程、文件及各种句柄（包括 WinAPI 句柄）等系统资源，通常都被视为高开销操作。当然，具体开销取决于资源类型和操作系统，但系统调用（尤其是需要进入内核的调用）耗时通常长于调用自身函数。资源操作还可能涉及不确定数量的内存访问、分配及其他高开销操作。因此，应尽量减少 I/O 调用的次数，在每次调用中读写尽可能多的数据，避免像 fread 或 fwrite 这样逐字节调用函数。
• 最后，所有的输入输出操作——即与 RAM 外部世界（如硬盘、SSD、CD/DVD 或网络）进行数据读写——其速度都远慢于前述操作。这类操作所需的耗时难以预测。因此，最好将其放在后台异步执行，或在一个独立的工作线程中运行。

AOS 与 SOA

粒子系统是 3D 图形中常见的特效。简单来说，它存储一组粒子及其属性（如当前位置、速度和颜色），然后在每一动画帧（每秒多次）中更新并渲染它们。从上一节你应该能猜到，我们不应该把粒子结构作为独立对象动态分配，而应存放在数组中——也就是一块连续的内存。接下来看看还能怎样进一步优化。请看代码清单 1。第一种方式叫 AOS（Array of Structures，结构数组），看起来很直观：我们定义一个结构体来表示单个粒子，描述它的所有参数，然后由负责整个粒子特效的类保存粒子数量和指向该结构体数组的指针。

代码清单 1. 粒子系统中的 AOS 与 SOA 对比

// AOS - Array of Structures
struct Particle
{
    vec3 Position;
    vec3 Velocity;
    vec4 Color;
};

class ParticleSystem
{
    Particle* Particles;
    size_t Count;
};

// SOA - Structure of Arrays
class ParticleSystem
{
    vec3* Positions;
    vec3* Velocities;
    vec4* Colors;
    size_t Count;
};

还有另一种方式，即第二种示例中的 SOA（Structure of Arrays，数组结构）。这时粒子系统类直接存储若干数组，分别保存各个粒子的单项参数：一个位置数组、一个速度数组、一个颜色数组，等等，数组元素个数都相同，等于粒子总数。视具体情况而定，这种方式可能更高效，因为它按使用模式组织数据，把“热”数据（当前需要、会进入缓存的数据）与“冷”数据分离开来。例如，当我们要遍历所有粒子并根据速度更新位置时，第二种方式让这些值在内存中靠得更近，不会混入当前用不到的颜色数据。布局如图 3 所示。

C++ 语言特性

编写高效代码，不仅仅是高层设计数据结构和算法的问题。即便只是在写单独的函数，我们也有很多办法可以避免那些不必要的性能陷阱。C++ 提供了许多便利，但也允许我们选择是使用这些便利，还是像在 C 语言中那样写代码。

因此，在很多情况下，放弃甚至完全禁用某些特性（如异常处理或 RTTI）是值得的。尽管这个话题略带争议，但人们有时认为这些机制会对代码性能产生负面影响。这并不意味着它们毫无价值或实现得不好，我们可以问问自己程序是否真的需要它们；如果不需要，就在编译器选项中将其禁用。

有一种被反复提及的说法认为，我们写不过编译器、标准库或某个流行且经过验证的库，这是错误的。它们的代码确实由优秀程序员编写，但在编写自己的程序时，我们清楚需要某个特性的具体场景：它的需求和约束。因此，运行时类型识别、错误处理以及许多其他任务，有时我们可以自行实现，以更好地契合项目需求。内存分配便是个最佳例证。系统分配器作为通用分配器已经很好，但如果程序某一部分需要分配已知固定大小的对象，且我们知道数量的上限，那么基于预分配空闲单元池（即空闲链表）的自定义分配器无疑会更高效。

同样的道理也适用于 STL。这是一个优秀的库，甚至可以认为它以安全性为代价换取了性能：例如，使用 [] 运算符访问 vector 元素时，它并不会检查边界（至少在 Release 配置下如此；Visual Studio 的实现会在 Debug 模式下通过断言进行检查）。使用 STL 仍需具备相关知识与意识，不仅包括可用的函数和概念（如迭代器），还涉及其内部实现机制。容器 list、set、multiset、map 和 multimap 会在内存中为每个元素动态分配独立对象，这出于前文所述原因会影响性能。相比之下，std::vector 在连续的内存区域存储元素，类似于普通数组，因此我们可以将其作为动态分配数组的便捷替代，而无须担心性能损失（再次强调，这是在 Release 配置下；由于额外的安全检查，大量使用 STL 的代码在 Debug 模式下性能会显著下降）。不过，有些东西可以写得更好，例如 Electronic Arts 的程序员创建 EASTL（一种针对游戏编程优化的 STL 替代库）时就是这样做的，他们不久前曾将 EASTL 的代码（尽管并不完整）在互联网上免费公开。

编译器优化

对编译器所做的优化保持一定的怀疑态度是有益的。举个最初的例子，考虑解引用传入的指针。我们知道，C++ 关键字 volatile 用于防止值被以允许编译器将其保留在处理器寄存器中（而非每次从原始内存位置获取）的方式优化。当某个值可能意外改变时，我们会使用它，例如因为硬件或另一个线程的影响。

但这只是问题的一部分。即使没有那个关键字，编译器有时也无法确定某个值不会发生意外变化，因此不能把它保存在寄存器里。比如清单 2 中的函数就会出现这种情况。这段简单的代码把作为最后一个参数传入的向量加到数组中的每个向量上。常量向量 s 本可以保存在寄存器或栈上。但在不了解上下文的情况下（例如函数不是 inline 的），编译器无法确定指针 s 没有指向数组 tab 中某个元素的同一块内存——那样的话，某次循环迭代就会改变它的值。因此编译器每次都必须重新读取 s 所指向的值。这就是所谓的指针别名（pointer aliasing）。

清单 2. 指针别名

void AddVectorToArray(vec3* tab, size_t n, const vec3* s)
{
    for(size_t i = 0; i < n; ++i)
        tab[i] += *s;
}

要解决这个问题，可以把向量 s 显式拷贝到局部变量、按值传参，或者使用非标准关键字 __restrict。最后这个关键字会告诉编译器，在当前作用域内不存在指针别名。 另一个例子是在循环内声明变量。编译器对 int 这类简单类型的变量处理得很好，但对更复杂的结构就帮不上忙了。我们用 std::string 类型的变量做个实验。清单 3 是第一版代码：循环执行两百万次，每次用前缀、数字和后缀拼出一个字符串，然后拷贝到全局变量的某个位置。在我的电脑上，这段代码平均耗时 0.36 秒。

清单 3. 在循环内声明字符串

for(int i = 0; i < 2000000; ++i)
{
    std::string s;

    s += "ITER_";

    char sz[16];
    itoa(i, sz, 10);
    s += sz;

    s += ".txt";

    memcpy(g_Buf, s.c_str(), s.length() + 1);
}

下面做一个简单的优化。清单 4 的新版本中，字符串在循环之前声明，每次迭代开始时只需调用 clear 清空。在我的电脑上，这段代码平均耗时 0.27 秒。

清单 4. 在循环外声明字符串

std::string s;
for(int i = 0; i < 2000000; ++i)
{
    s.clear();

    s += "ITER_";

    char sz[16];
    itoa(i, sz, 10);
    s += sz;

    s += ".txt";

    memcpy(g_Buf, s.c_str(), s.length() + 1);
}

仅做一处简单改动——修改两行代码而不改变逻辑——便节省了 25% 的运行时。这是如何做到的？答案在于 STL string 类的内部设计。在我使用的 Visual C++ 2012 实现中，string 对象（类似 vector）可通过重新分配内部存储来扩展，但不会收缩。删除元素甚至完全清空该对象时，只将当前长度置零，已分配的内存块保持不变（若要真正释放容器内存，需使用所谓的 swap 技巧）。因此，复用该对象时，若新内容不比之前长，便无需重新分配。而在之前的代码中，每次循环迭代都创建新对象，需分配必要内存，并在到达右花括号时析构释放内存。

尽管如此，编译器仍执行许多巧妙的优化。我们可以通过开关来控制这些优化。大家可能都熟悉通用优化级别的开关 /O2，它在 Visual Studio 的 Release 配置中默认启用。还建议在项目的 配置属性 > C/C++ 设置中启用其他若干开关（先阅读文档了解各选项的作用及后果）：

• 优化 > 启用本征函数 = 是 (/Oi)
• 代码生成 > 启用扩展指令集 = Streaming SIMD Extensions 2 (/arch:SSE2)
• 代码生成 > 浮点模型 = Fast (/fp:fast)

过早优化？

许多人想象所谓的“优化”意味着将特定例程重写为晦涩难懂的汇编语言。如今，这种做法很少必要。编译器在单条指令级别的代码优化方面表现优异。不过，了解足够的汇编以偶尔检查和理解编译器生成的代码仍是有价值的。

许多人在处理代码性能时要么不愿、要么不会、要么不敢，他们常常引用唐纳德·克尼（Donald Knuth）的名言“过早优化是万恶之源”来为自己开脱。不过，克尼的完整表述其实是：我们应该忘掉小范围的效率提升——大约97%的情况。过早优化是万恶之源（引自 Knuth, Donald (1974年12月). “Structured Programming with go to Statements.” ACM Journal Computing Surveys 6 (4): 268）。这句话仅指他在前文提到的一个案例：通过添加一个 goto 语句让循环代码提速12%。重点在于，我们不应完全忽视优化。从设计阶段到使用语言特性时养成良好习惯，我们在编写代码的全过程中都应始终关注性能。 有些人认为优化是在程序写好之后才做的事：运行性能分析工具，找出占用总执行时间30%的函数，然后尝试优化它。但有时，并不存在某个单独的函数或一小群函数对性能至关重要。程序的各个部分各自只占用少量时间，但由于整体编写质量低下，导致程序整体运行缓慢。即使我们发现优化某个耗时函数需要重新设计数据结构并重写程序的大部分代码，情况也不会因此变好。这就是为什么在我们的日常编程工作中关注代码性能是有价值的。

1. Daniel Collin，“Introduction to Data-Oriented Design”
2. Tony Albrecht，“Pitfalls of Object Oriented Programming”
3. Gustavo Duarte，“What Your Computer Does While You Wait”
4. Mick West，“MatureOptimization”, GameDeveloper Magazine, 2006

Adam Sawicki
2013年4月