第 16 章性能

第 3 级：经验

高山红嘴鸦在高海拔的稀薄空气中生活和繁殖；人们曾在喜马拉雅山脉海拔 8,000 米以上见到它。

在这一层，我们会更深入地探究若干专题的细节。第一个专题是性能——这正是人们选择 C 而非其他编程语言的主要原因之一。因此，第 16 章是所有 C 软件设计者的必读内容。

第二个专题是 C 颇为独特的一项特性：类函数宏。由于它们复杂而且显然不够美观，其他编程社群大多对其颇有微词。不过，我们仍须在一定程度上掌握它们，因为它们能够提供易用接口，例如类型泛型程序设计接口，以及更精细的形参核验接口。

第 19 章和第 20 章随后说明怎样弱化程序顺序执行这一通常假设，以便异步处理问题（使用长跳转或信号处理程序），或者并行执行线程。这些机制会带来保证数据一致性方面的特殊问题，因此最后的第 21 章将更深入地探究原子数据的处理和一般意义上的同步。

本章涵盖：

编写内联函数
限制指针
测量并审视性能

当你越来越习惯用 C 编码时，或许会忍不住做一些复杂的事情来“优化”代码。不论自以为在优化什么，都很可能把事情弄错：过早优化会在可读性、健全性、可维护性等方面造成巨大伤害。

Knuth [1974] 创造了下面这句话；它应当成为整个第 3 级的座右铭。

要点 16 #1

过早优化是万恶之源。

C 的良好性能经常被视为它得到广泛应用的主要原因之一。复杂度相近时，许多 C 程序确实胜过其他编程语言编写的代码；这种说法有一定道理，但 C 的这项优势可能伴随高昂代价，尤其是在安全性方面。这是因为 C 在许多地方不强制执行规则，而把核验责任交给程序员。重要示例包括：

越过数组边界访问；
访问未初始化的对象；
在对象生存期结束后访问对象；
整数溢出。

这些问题可能造成程序崩溃、数据丢失、结果错误、敏感信息泄露，甚至导致金钱或生命损失。

要点 16 #2

不要以安全性换取性能。

近年来，C 编译器已经大有进步；基本上，凡是编译期能够发现的问题，它们都会发出警告。不过，试图卖弄聪明的代码里仍可能隐藏着未被发现的严重问题。许多问题都可以用非常简单的手段避免，或至少能够发现：

所有块作用域对象都应初始化，从而消除半数与未初始化对象有关的问题。
只要适用，动态分配就应使用 calloc，而非 malloc。这样可以再避免四分之一与未初始化对象有关的问题。
对于动态分配的复杂数据结构，应实现专门的初始化函数。这样可以消除其余与未初始化对象有关的问题。
接收指针的函数应使用数组语法，并区分以下情况：
- 指向该类型单个对象的指针——这类函数应使用 static 1 记法，从而表明它们期望接收非空指针：
  c
```
void func(double a[static 1]);
```
  1
- 指向已知数量对象集合的指针——这类函数应使用 static N 记法，从而表明它们期望接收至少指向这么多个元素的指针：
  c
```
void func(double a[static 7]);
```
  1
- 指向未知数量对象集合的指针——这类函数应使用 VLA 记法，但仍通过 static 表明：界限保证了可访问元素的数量：
  c
```
void func(size_t n, double a[static n]);
```
  1
  乍看之下，这似乎限制很大：要使其有效，必须始终把大小形参声明在数组形参之前。第 18.2 节会介绍一种技巧，创建宏和内联接口，以便在无法修改的函数接口（例如 snprintf）之外绕过这一要求。
- 指向单个对象、数组或为空的指针——这种函数必须保证：即使收到空指针，执行也仍处于已定义状态：
  c
```
void func(double* a);
```
  1
一些编译器开发者才刚开始实现对这些情况的核验，所以错误可能（尚）无法自动发现。有些编译器已经做得相当好，至少在函数调用使用整数常量表达式作为大小表达式、数组大小也在编译期已知时如此。无论如何，把这些要求明确写下来，都有助于避免越界错误。
应尽可能避免取得块作用域（局部）对象的地址。因此，在复杂代码中用 register 标记所有局部对象是一项良好实践。
循环索引应使用无符号整数类型，并显式处理回绕。例如，可以在递增操作之前，把循环对象与该类型的最大值比较。

尽管一些坊间传说声称相反，应用这些规则通常不会损害代码性能。

要点 16 #3

优化器足够聪明，能够消除未使用的初始化。

要点 16 #4

函数指针实参的不同记法会产生相同的二进制代码。

要点 16 #5

不取得局部对象的地址会抑制别名，因而有助于优化器。

应用这些规则并确保实现安全以后，便可以考察程序性能。什么是良好性能、怎样测量性能，本身都是困难的课题。面对性能时，首先永远要问它是否有意义。例如，把交互程序的运行时间从 1 ms 缩短到 0.9 ms 通常毫无意义；为此付出的任何努力，大概用在别处都更有价值。

为了掌握评估性能瓶颈所需的工具，我们会讨论怎样测量性能（第 16.4 节）。这部分放在本章末尾，因为要充分理解性能测量，首先必须更好地理解改善性能的工具。

很多情况下，我们可以帮助当前编译器（以及未来版本的编译器）更好地优化代码，因为我们能够写明某些代码性质，而编译器无法自动推导它们。C 为此引入了一些相当特别的特性：它们约束的不是编译器，而是程序员。所有这些特性都有一项共同性质：从出现这些特性的有效代码中删去它们，不应改变语义。

由于这项性质，它们有时被说成毫无用处，甚至已经过时。遇到这种说法时务必谨慎：作出这类断言的人，往往没有深入理解 C、C 的内存模型或 C 的优化可能性；尤其是，他们似乎没有深入理解因果关系。

引入这些优化机会的特性包括：

register（C89）；
inline、restrict（均来自 C99）；
alignas（对应早期的 _Alignas，C11）；
[[unsequenced]] 与 [[reproducible]]（均来自 C23）。

如上所示，它们都具有这样的性质：从有效程序中省略它们不会改变程序语义。

第 13.2 节已经在一定程度上讨论了 register，这里不再深入。只需记住，它有助于避免函数中局部定义的对象产生别名。正如前文所述，我认为 C 社群严重低估了这项特性。

第 12.7 节还讨论过 C11 的 alignas 及相关的 alignof。它们有助于把对象放在缓存边界上，从而改善内存访问。这里也不再深入探究这些专门特性。

余下特性——C99 的 inline（第 16.1 节）与 restrict（第 16.2 节），以及 C23 的 [[unsequenced]] 与 [[reproducible]]（第 16.3 节）——在易用性方面大不相同。

第一项 inline 相对容易使用，没有特别的危险。它已经得到广泛应用，可以确保短函数的代码能够直接集成到函数调用方，并在那里接受优化。

第二项 restrict 放宽了基于类型的别名考量，以便实现更好的优化。因此，它用起来很微妙，使用不当会造成重大危害。库接口中经常能够见到它，用户代码里则少得多。

对于最后两项属性，尤其是 [[unsequenced]]，前文已经见过许多涵盖纯函数情形的用法。它们是方便的注解，告诉编译器函数调用可以移动和合并。但其可能用途并不限于简单的纯函数，也可以为带有指针形参或指针返回值的函数建模。函数必须满足的条件，会复用 restrict 所引入的许多性质。

本章余下部分（第 16.4 节）将深入性能测量和代码审视，使我们能够评估性能本身，以及产生良好或糟糕性能的原因。

16.1 内联函数

对于 C 程序，编写模块化代码的标准工具是函数。正如已经看到的，函数有多项优点：

函数清晰地分隔接口与实现。因此，我们可以从一个修订版到下一个修订版逐步改善代码；必要时，也可以从头重写功能。
如果不通过全局对象与其余代码通信，就能确保函数所访问的状态是局部的。这样一来，状态只存在于调用形参和局部对象中，也就更容易发现优化机会。

遗憾的是，从性能角度看，函数也有一些缺点：

即使在现代平台上，函数调用也有一定开销。调用函数时，通常要留出一些栈空间，并初始化或复制局部对象。控制流会跳转到可执行程序中的另一个位置，而该位置可能存在于执行缓存中，也可能不在其中。
视平台的调用约定而定，如果函数返回值是 struct，可能必须把整个返回值复制到函数调用方期望结果出现的位置。

如果调用方代码（比如 fcaller）与被调用方代码（比如 fsmall）恰好位于同一个翻译单元（TU），优秀的编译器可以通过内联避免这些缺点。编译器所做的事情，等价于用 fsmall 自身的代码替换对它的调用。这样就不再发生调用，也不再有调用开销。

更好的是，由于 fsmall 的代码如今已经内联，它的所有指令都出现在新的语境中。例如，编译器可以发现：

永远不会执行的死分支；
结果已经已知，却重复计算的表达式；
在具体调用方式下，只可能返回某一类值的函数。

要点 16.1 #1

内联可以开启大量优化机会。

传统 C 编译器只能内联它同时知道定义的函数；只有声明还不够。因此，程序员与编译器开发者一直在研究怎样让函数定义可见，以提高内联机会。如果语言不额外提供支持，有两种策略：

把项目所有代码连接成一个大文件，再将全部代码编译为一个巨大的 TU。系统地完成这件事并没有听起来那么容易：必须确保源文件的连接次序不会产生定义环，而且不存在命名冲突（例如两个 TU 各有一个名为 init 的 static 函数）。
把应当内联的函数放入头文件，再由所有需要它们的 TU 包含。为避免每个 TU 都产生函数符号的多重定义，这些函数必须声明为 static。

第一种方法对大型项目并不可行，第二种方法则相对容易实现。不过，它仍有缺点：

如果函数太大，编译器无法内联，就会在每个 TU 中分别实例化。也就是说，这种大函数可能产生大量副本，增加最终可执行程序的大小。
取得这种函数的指针时，得到的是当前 TU 中具体实例的地址。比较从不同 TU 获得的两个这类指针时，结果并不相等。
如果在头文件中声明的这种 static 函数未被某个 TU 使用，编译器通常会警告它未被使用。因此，如果头文件中有大量这类小函数，就会看到许多警告，产生大量误报。

为了避免这些缺点，C99 引入了关键字 inline。与名称可能暗示的不同，它不会强制内联函数，只提供一种允许内联的方式：

声明为 inline 的函数定义可以在多个 TU 中使用，而不会造成多重符号定义错误。
指向同一个内联函数的所有指针都会比较相等，即使它们来自不同 TU。
某个内联函数如果在特定 TU 中未使用，就会完全从该 TU 的二进制代码中消失，尤其不会增加其大小。

最后一点通常是优点，却带来一个简单问题：即使程序可能需要函数符号，也永远不会生成这个符号。以下常见情况都需要符号：

程序直接使用或存储指向该函数的指针。
编译器判定函数太大或太复杂，无法内联。这种情况并不固定，取决于若干因素：
- 编译采用的优化级别；
- 是否启用调试选项；
- 函数自身是否使用某些 C 库函数。
函数属于某个库，而这个库要交付并链接到未知程序。

为了提供这种符号，C99 为内联函数引入了一条特殊规则。

要点 16.1 #2

增加一个不带 inline 关键字的兼容声明，可以确保在当前 TU 中生成函数符号。

例如，假设头文件 toto.h 中有下面的内联函数：

// 头文件中的内联定义。
// 函数实参名和局部对象对预处理器可见，
// 必须谨慎处理。
inline
toto* toto_init(toto* toto_x){
  if (toto_x) {
    *toto_x = (toto){ };
  }
  return toto_x;
}

这样的函数非常适合内联。它确实很小，而且对任意 toto 类型对象的初始化，最好就在原处完成。调用开销与函数内部部分的开销处在同一量级；许多情况下，函数调用方甚至可以省去 if 测试。

要点 16.1 #3

内联函数定义在所有 TU 中可见。

看到这段代码的所有 TU 中，编译器都可以内联该函数，但没有任何 TU 会实际生成符号 toto_init。不过，我们可以（而且应当）在恰好一个 TU 中强制生成它，例如在 toto.c 中增加：

#include "toto.h"

// 恰好在一个 TU 中实例化。
// 省略形参名，以避免宏替换。
toto* toto_init(toto*);

要点 16.1 #4

内联定义应放在头文件中。

要点 16.1 #5

不带 inline 的附加声明应恰好放在一个 TU 中。

如前所述，内联函数机制旨在帮助编译器决定是否真的内联函数。大多数情况下，编译器开发者为此实现的启发式方法完全适当，你无法做得更好。他们对具体编译目标平台的了解远胜于你；甚至可能在你编写代码时，该平台还不存在。因此，他们更适合权衡不同可能方案。

第 10.2.2 节介绍的纯函数，是可能受益于内联定义的一大类函数。回顾 rat 结构体示例（清单 10.1），可以看到所有函数都隐式复制函数实参与返回值。如果在头文件中把这些函数全部重写为 inline，优化编译器就能避免所有这些复制。

练习 1

用 inline 重写第 10.2.2 节的示例。

练习 2

重新审视第 7 章的函数示例，分别说明每个函数应当还是不应当定义为 inline。

因此，内联函数可以成为构建高性能可移植代码的宝贵工具；我们只是帮助编译器作出适当决定。遗憾的是，使用内联函数也有一些缺点，应当在设计时加以考虑。

首先，要点 16.1 #3 意味着：内联函数的任何改动，都会触发整个项目及其所有使用者的完整重建。

要点 16.1 #6

只有当你认为函数已经稳定时，才把它公开为 inline。

其次，函数定义全局可见，还意味着函数的局部标识符（形参或局部对象）可能遭到我们根本不知道的宏展开。在示例中，我们使用 toto_ 前缀，保护函数形参不受其他包含文件中的宏展开影响。

要点 16.1 #7

内联函数的所有局部标识符都应通过方便的命名约定加以保护。

第三，与常规函数定义不同，内联函数并不与某个特定 TU 关联。常规函数可以访问 TU 的局部状态和函数（static 对象与函数）；而对于内联函数，并不清楚这些名称究竟指向哪个 TU 中的哪一个副本。

要点 16.1 #8

inline 函数不能按名称访问 static 函数。

要点 16.1 #9

inline 函数不能按名称访问可修改的 static 对象。

这里强调的是：受限的是对标识符的访问，不是对象或函数本身。把指向 static 对象或函数的指针传给内联函数，并无问题。

不过，即使不存在标识符——例如复合字面量——仍然不允许定义 static 对象。

要点 16.1 #A

inline 函数不能定义可修改的 static 对象。

16.2 使用 `restrict` 限定符

我们已经见过许多 C 库函数使用关键字 restrict 限定指针的示例，也曾为自己的函数使用这种限定。restrict 的基本思想相对简单：它告诉编译器，所讨论的指针是访问其所指对象的唯一途径。因此，编译器可以假定：只有通过同一个指针才能改变该对象，该对象不会意外发生改变。换言之，使用 restrict 时，我们告诉编译器：该对象与编译器在这部分代码中处理的任何其他对象都不存在别名。

要点 16.2 #1

由 restrict 限定的指针必须提供独占访问。

与 C 中经常出现的情况一样，这种声明把核验该性质的责任交给调用方。

要点 16.2 #2

restrict 限定会约束函数调用方。

例如，考察 memcpy 与 memmove 的区别：

void* memcpy(void*restrict s1, void const*restrict s2, size_t n);
void* memmove(void* s1, const void* s2, size_t n);

对于 memcpy，两个指针都由 restrict 限定。因此，在该函数执行期间，通过两个指针进行的访问都必须具有独占性，否则执行失效。s1 和 s2 还必须具有不同的值，任何一方都不能提供对另一方对象任意部分的访问。换言之，memcpy 通过两个指针“看到”的两个对象不得重叠。作出这一假设有助于优化函数。

相比之下，memmove 不作这样的假设。因此，s1 和 s2 可以相等，两个对象也可以重叠。函数必须能够处理这种情况。所以，它可能效率较低，但更加通用。

第 12.3 节已经看到，对编译器而言，判断两个指针是否可能实际指向同一个对象（别名）十分重要。指向不同基本类型的指针不应产生别名，除非其中一个是字符类型。因此，fputs 的两个形参都声明为 restrict：

int fputs(const char *restrict s, FILE *restrict stream);

不过，似乎不太可能有人会用同一个指针值作为两个形参来调用 fputs。

这项规定对 printf 及相关函数更加重要：

int printf(const char *restrict format, ...);
int fprintf(FILE *restrict stream,
            const char *restrict format, ...);

形参 format 不应与可能传给 ... 部分的任何实参产生别名。例如，执行到以下代码时，程序执行失效：

char const* format = "format printing itself: %s\n";
printf(format, format); // 违反 restrict

这个示例很可能仍会做出你所认为的事情。但如果滥用 stream 形参，程序可能直接爆炸：

char const* format = "First two bytes in stdin object: %.2s\n";
char const* bytes = (char*)stdin; // 到 char 的合法转换
fprintf(stdin, format, bytes);    // 违反 restrict

当然，这样的代码在实际程序中不太可能出现。但请牢记，字符类型在别名方面具有特殊规则，因此所有字符串处理函数都可能错失优化机会。如果字符串形参只会通过所讨论的指针独占访问，那么许多位置都可以增加 restrict 限定。

16.3 未定序属性与可复现属性

许多示例函数使用属性 [[unsequenced]]（或者对头文件安全的形式 [[unsequenced]]）表明函数是纯函数。

要点 16.3 #1

所有纯函数都应具有属性 [[unsequenced]]。

与前面的 restrict 不同，这种带注解的纯函数通常可以自由使用，不受限制。如果函数定义经过核实，编译器便可利用这项知识，更好地优化调用位置。

本节前半部分先假定这种情形，也就是带属性的函数确实为纯函数。稍后会看到，这些定义怎样扩展到具有指针实参或返回值的函数，以及具有 [[reproducible]] 属性时可以拥有内部状态的函数。

因此，这里的核验责任在函数定义的编写者身上。对于简单的纯函数情形，一般不难：必须确保函数只依赖实参，除了返回值以外不产生其他效果。该要求可以拆成几项相对容易核实的性质。

关于状态依赖的部分，规定如下。

要点 16.3 #2

具有属性 [[unsequenced]] 的函数不得读取非常量全局对象或系统状态。

这里的危险不仅来自可能在我们不知情时发生改变的全局对象。执行状态中还有一些更微妙的部分，函数可能依赖它们，而我们并不容易察觉。浮点舍入模式就是这种隐式状态的一个好例子。遗憾的是，C 库在一些地方仍沿用颇为陈旧的浮点模型调节方式：使用编译指示修改线程局部状态。

#pragma FP_CONTRACT OFF
#pragma FENV_ROUND FE_TONEAREST

例如，这里设置全局线程局部状态，使浮点表达式不发生缩并，并使舍入结果始终指向最近的可表示数。由于程序设计接口能够访问这种状态，一个我们以为纯净的函数，其使用者确实可能依赖在不同调用之间发生改变的状态。

要点 16.3 #3

一般而言，使用浮点算术的函数不是纯函数，不得具有属性 [[unsequenced]]。

这项陈述尤其包括头文件 <math.h>、<tgmath.h> 和 <complex.h> 中的所有函数。“真令人失望。”我听到你这样说。但请耐心一些，后文至少有一项局部补救办法。不过眼下，情况甚至还会变得更糟。

要点 16.3 #4

具有属性 [[unsequenced]] 的函数不得对全局对象或系统状态施加可见修改。

许多 C 库函数再次因此不合要求，因为它们使用另一种依赖全局状态的陈旧模型：errno。

要点 16.3 #5

通过 errno 返回潜在错误的函数不是纯函数，不得具有属性 [[unsequenced]]。

幸运的是，可以借助编译指示 FP_CONTRACT 和 FENV_ROUND 绕过这一问题。下面的示例来自最初为 C23 提出这项特性的论文：^[1]

#include <math.h>
#include <fenv.h>
inline double distance(double const x[restrict static 2])
  [[reproducible]] {
# pragma FP_CONTRACT OFF
# pragma FENV_ROUND FE_TONEAREST
  // 我们断言，不会以无效实参调用 sqrt，
  // 而且结果只依赖实参值。
  extern double sqrt(double) [[unsequenced]];
  return sqrt(x[0]*x[0] + x[1]*x[1]);
}

这里，我们手工提供了几项 sqrt 在一般情况下并不满足的保证：

在该语境中，永远不会以负实参调用函数，因为平方和总为正。因此，这里的所有调用都有效，绝不会设置 errno。
在 distance 函数的作用域内，两项编译指示始终设置为相同状态，所以 sqrt 调用始终看到同一个状态。

在这个特殊语境中，sqrt 确实是纯函数，可以用该属性注解。保证这一点的机制有两个方面。

要点 16.3 #6

改变浮点状态的编译指示，只在当前作用域内局部生效。

在示例中，这意味着舍入模式可能在编译指示所在位置发生改变，并在含有该编译指示的作用域末尾恢复原值。

要点 16.3 #7

类型属性会在当前作用域内累积。

这里意味着：只要仍位于 distance 内部，编译器就会看到带有该属性的 sqrt，并可利用这项信息进行局部优化。其他语境中的函数用法不受影响。

函数 distance 还带有另一个属性：[[reproducible]]。顾名思义，其思想是：对于一组给定实参，我们只需保证调用的结果与效果始终相同，而不论函数内部怎样做到这一点。这项属性的前提较弱，因而带来的优化机会也较少。我们的函数显然有一项性质，使它无法成为未定序函数：它改变了全局状态，即浮点性质。

要点 16.3 #8

具有属性 [[reproducible]] 的函数可以临时修改全局状态，只要随后将其恢复为原值。

distance 还通过指针形参接收一个含两个元素的向量 x，所以按照前文所见经典意义，它同样不是纯函数。不过，这两个属性扩展了经典概念：只要指针形参和指针返回值满足与 restrict 限定指针形参相同的要求，就可以把属性应用于带有这些内容的函数。

要点 16.3 #9

对具有 [[unsequenced]] 或 [[reproducible]] 属性的函数，应以 restrict 注解其指针形参。

增加这项限定其实是冗余的。属性自身已经施加了相应性质，但显式注解有助于提醒偶尔阅读代码的人注意这些限制。

与为 sqrt 提供局部保证的精神相同，在明知不会改变浮点环境的语境中，也可以改善有关 distance 的局部知识。

double g(double y[static 1], double const x[static 2]) {
  // 我们断言，distance 不会看到浮点环境的不同状态。
  extern double distance(double const x[restrict static 2])
    [[unsequenced]];
  y[0] = distance(x);
  ...
  return distance(x); // 可以替换为 y[0]。
}

对这两项属性，我们还必须考虑这种函数可能改变的内部状态，也就是具有静态存储期的局部对象。

要点 16.3 #A

具有属性 [[unsequenced]] 的函数不得修改局部静态状态，即使通过其他函数调用也不行。

满足所有这些要求时，多个 [[unsequenced]] 函数调用甚至可以交错执行，而不会改变最终结果。对于 [[reproducible]]，这项要求同样稍有放宽。

要点 16.3 #B

具有属性 [[reproducible]] 的函数只能在局部静态状态无法从函数外部观察时修改该状态。

为了看清区别，考虑具有以下函数 hash 的接口：

size_t hash(char const[restrict static 32]) [[reproducible]];

如果以相同字符串实参调用，该函数应当返回相同整数值。不过，它可以把见过的实参结果记忆在一个声明为 static 的内部表中。因此，以同一个字符串反复调用可能更高效，而函数外部的可见状态没有任何可观察差异。尽管如此，这种函数不能带有 [[unsequenced]] 属性，因为各次调用不能交错；hash 调用始终必须依次正确排序。

16.4 测量与审视

我们已经多次谈到程序性能，却还没有讨论评估性能的方法。事实上，人类非常不擅长预测代码性能，尤其是在 CPU 和编译器优化经常更新的环境中。

要点 16.4 #1

不要臆测代码性能；应当严谨验证。

深入一个可能对性能敏感的代码项目时，第一步始终是选择解决当前问题的最佳算法。这一步甚至应在编码开始之前完成，所以我们必须先论证（而非臆测）算法行为，对复杂度作出初步评估。

要点 16.4 #2

评估算法复杂度需要证明。

遗憾的是，复杂度证明的讨论远远超出本书范围，这里无法深入。幸运的是，已经有许多其他著作专门讨论该主题。感兴趣的读者可以参阅 Cormen 等人 [2001] 的教材，或 Knuth 的知识宝库。

要点 16.4 #3

评估代码性能需要测量。

实验科学中的测量是一门困难学问，显然无法在这里完整处理。不过，我们应当意识到：测量这一行为会改变被观察对象。这在物理学中成立——测量物体质量必然使其发生位移；在生物学中成立——采集物种样本会杀死动物或植物；在社会学中也成立——测试前询问性别或移民背景，会改变受试者的行为。

毫不意外，它在计算机科学中同样成立，尤其适用于时间测量，因为所有时间测量本身都需要花费时间。

要点 16.4 #4

所有测量都会引入偏差。

最糟糕时，时间测量的影响并不限于测量本身额外花费的时间。例如，对 timespec_get 的调用，是一项在不测量时根本不会存在的函数调用。编译器必须在任何这类调用前采取一些预防措施，尤其是保存硬件寄存器，并放弃对执行状态作出的若干假设。因此，时间测量可能压制优化机会。

此外，这类函数调用通常会转换成系统调用（对操作系统的调用），进而影响程序执行的许多性质，例如进程或任务调度，甚至可能使数据缓存失效。

要点 16.4 #5

插桩会改变编译期性质与运行时性质。

实验科学的艺术在于处理这些问题，并确保测量所引入的偏差足够小，从而能够定性评估实验结果。具体而言，在对感兴趣的代码执行任何时间测量之前，必须评估时间测量引入的偏差。

减少测量偏差的一般策略是多次重复实验，并收集结果的统计信息。该语境中最常用的统计量十分简单，包括实验次数、平均值 μ、标准差，有时还包括偏度。

来看样本 S，它由以下 20 个以秒为单位的计时值组成：

text

0.7, 1.0, 1.2, 0.6, 1.3, 0.1, 0.8, 0.3, 0.4, 0.9,
0.5, 0.2, 0.6, 0.4, 0.4, 0.5, 0.5, 0.4, 0.6, 0.6

图 16.1 是该样本的频率直方图。这些值在 0.6（μ(S)，平均值）周围波动很大，从 0.1（最小值）一直到 1.3（最大值）。事实上，波动大到我个人不敢断言这个样本具有多少参考意义。这些虚构的测量很糟糕，但究竟有多糟？

图 16.1　样本的频率直方图

text

频数
 8 ┤
 7 ┤
 6 ┤         █
 5 ┤         █
 4 ┤      █  █
 3 ┤      █  █
 2 ┤   █  █  █     █
 1 ┤█  █  █  █  █  █  █
 0 ┼────────────────────────
    0  .2 .4 .6 .8 1  1.2 1.4  秒

该图显示每个测量值出现的频数。

标准差 σ(S) 衡量观测样本偏离理想世界的程度；在理想世界中，所有计时都会得到完全相同的结果。该样本的标准差为 0.31，单位同样是秒。较小的标准差意味着，我们观察的现象很可能遵循这种理想情况。反过来，如果标准差过高，可能是现象本身不具备理想性质（有某种事物扰乱计算），也可能是测量不可靠（有某种事物扰乱测量），还可能两者兼有。

在这个示例中，相比平均值 0.6，标准差 0.31 相当可观：相对标准差 σ(S)/μ(S) 为 0.52，即 52%。只有处于较低百分比范围的值，才能视为良好。

要点 16.4 #6

运行时间的相对标准差必须处于较低百分比范围。

最后一个可能令我们感兴趣的统计量是偏度；样本 S 的偏度为 0.79。它衡量样本的偏斜程度（或不对称程度）。围绕平均值对称分布的样本，其偏度为 0。正值表示右侧存在一条“尾巴”。

时间测量通常不对称。从样本中很容易看到这一点：最大值 1.3 与平均值相差 0.7。若要使样本围绕平均值 0.6 对称，就需要有一个 −0.1，而这是不可能的。

如果你不熟悉这些非常基本的统计概念，大概应当现在稍加复习。本节将看到，所有这些令我们感兴趣的统计量，都可以用原始矩计算：

text

              Σ sᵏ
mₖ(S) =
          对所有 s ∈ S 求和

因此，第 0 阶原始矩对样本数计数；第 1 阶把所有值相加；第 2 阶是各值平方之和，依此类推。

在计算机科学中，可以轻松自动重复实验：把待取样代码放进 for 循环，并在循环前后执行测量。这样就能执行样本代码数千次乃至数百万次，再计算每次循环迭代所花时间的平均值。我们的希望是：整个实验可能花费数秒，而时间测量本身只花费几毫秒，因而可以忽略时间测量的成本。

本节示例代码将评估 timespec_get 的性能，以及一个把测量统计信息收集到 s、accu0 等对象中的小工具。清单 16.1 围绕几种不同版本的待研究代码放置了若干 for 循环。时间测量被收集到一个统计对象中（未显示），并使用从 timespec_get 获得的 tv_nsec 值。这里报告的实验采用 iterations 值 2²⁴ − 1。

清单 16.1　反复测量若干代码片段

timespec_get(&t[0], TIME_UTC);
/* 把 i 声明为 volatile，确保循环确实执行 */
for (uint64_t volatile i = 0; i < iterations; ++i) {
  /* 不做任何事情 */
}
timespec_get(&t[1], TIME_UTC);
/* s 必须是 volatile，确保循环确实执行 */
for (uint64_t i = 0; i < iterations; ++i) {
  s = i;
}
timespec_get(&t[2], TIME_UTC);
/* 不透明计算确保循环确实执行 */
for (uint64_t i = 1; accu0 < upper; i += 2) {
  accu0 += i;
}
timespec_get(&t[3], TIME_UTC);

如果现在把 timespec_get 调用加入循环体（见清单 16.2），实验引入的偏差显而易见：我们用 timespec_get 调用测量它自身的性能。不过，这种偏差很容易控制：增加迭代次数即可降低偏差。

清单 16.2　反复测量 timespec_get 调用

/* 函数调用通常无法被优化掉。 */
for (uint64_t i = 0; i < iterations; ++i) {
  timespec_get(&tdummy, TIME_UTC);
  accu1 += tdummy.tv_nsec;
}
timespec_get(&t[4], TIME_UTC);

这个近乎不言自明的观察并不是目标，只是充当待测代码的示例。清单 16.3 中的 for 循环采用逐步增强的精细程度收集统计信息。目标是逐步断言，这种不断提高的精细程度怎样影响计时。

清单 16.3　为 timespec_get 调用测量不同层次的统计信息

/* 函数调用通常无法优化掉，但内联函数可以。 */
for (uint64_t i = 0; i < iterations; ++i) {
  timespec_get(&tdummy, TIME_UTC);
  stats_collect1(&sdummy[1], tdummy.tv_nsec);
}
timespec_get(&t[5], TIME_UTC);
for (uint64_t i = 0; i < iterations; ++i) {
  timespec_get(&tdummy, TIME_UTC);
  stats_collect2(&sdummy[2], tdummy.tv_nsec);
}
timespec_get(&t[6], TIME_UTC);
for (uint64_t i = 0; i < iterations; ++i) {
  timespec_get(&tdummy, TIME_UTC);
  stats_collect3(&sdummy[3], tdummy.tv_nsec);
}
timespec_get(&t[7], TIME_UTC);

stats_collect1 等函数使用的对象如下：

struct timespec tdummy;
stats sdummy[4] = { };

从第 70 行开始的循环累加所有值，使我们能够确定平均值。下一个循环（第 77 行）使用 stats_collect1 函数维护一个动态更新的平均值。也就是说，它实现了一条公式：用 δₙ(xₙ, μ_n−1) 修正前一个平均值，其中 xₙ 是新测量，μ_n−1 是前一个平均值，从而计算新的平均值 μₙ。

另外两个循环（第 82 与 87 行）分别使用 stats_collect2 和 stats_collect3；它们为第 2 阶矩与第 3 阶矩使用类似公式，以计算方差与偏度。稍后会讨论这些函数。

不过，先来看看为代码插桩所用的工具。对于前面展示的每个循环，我们先使用第 11.2 节的 timespec_diff，计算数组 t 中两个测量值之间的时间差，再用 stats_collect2 汇总统计信息。

清单 16.4　使用 timespec_diff 和 stats_collect2 收集时间统计信息

for (unsigned i = 0; i < loops; i++) {
  double diff = timespec_diff(&t[i+1], &t[i]);
  stats_collect2(&statistic[i], diff);
}

随后，整个过程又包在另一个循环里（未显示），把实验重复 10 次。循环结束后，使用 stats 类型的函数打印结果。

清单 16.5　使用 stats_mean 和 stats_rsdev_unbiased 打印时间统计信息

for (unsigned i = 0; i < loops; i++) {
  double mean = stats_mean(&statistic[i]);
  double rsdev = stats_rsdev_unbiased(&statistic[i]);
  printf("loop %u: E(t) (sec):\t%5.2e ± %4.02f%%,\tloop body %5.2e\n",
         i, mean, 100.0*rsdev, mean/iterations);
}

显然，stats_mean 提供对测量平均值的访问。函数 stats_rsdev_unbiased 返回无偏相对标准差，也就是不带偏差^[2]、并以平均值归一化的标准差。

我的笔记本计算机上，一次典型输出如下：

console

loop 0: E(t) (sec): 3.31e-02 ± 7.30%,  loop body 1.97e-09
loop 1: E(t) (sec): 6.15e-03 ± 12.42%, loop body 3.66e-10
loop 2: E(t) (sec): 5.78e-03 ± 10.71%, loop body 3.45e-10
loop 3: E(t) (sec): 2.98e-01 ± 0.85%,  loop body 1.77e-08
loop 4: E(t) (sec): 4.40e-01 ± 0.15%,  loop body 2.62e-08
loop 5: E(t) (sec): 4.86e-01 ± 0.17%,  loop body 2.90e-08
loop 6: E(t) (sec): 5.32e-01 ± 0.13%,  loop body 3.17e-08

这里的循环 0、1 和 2 尚未讨论；循环 3 至 6 对应已经见过的循环。后四项的相对标准差小于 1%，所以可以断言统计结果良好，右侧时间也能很好地估计每次迭代的成本。

例如，在我的 2.1 GHz 笔记本计算机上，循环 3、4、5 和 6 每次迭代分别约需 36、55、61 和 67 个时钟周期。因此，用 stats_collect1 取代简单求和会额外花费 19 个周期；从这里改为 stats_collect2 还需 6 个周期；使用 stats_collect3 则再增加 6 个周期。

stats_collect2

向统计对象 c 加入值 val。

收集样本数、平均值和标准差。

inline
void stats_collect2(stats c[static 1], double val)
  [[__reproducible__]] {
  stats_collect(c, val, 2);
}

为了看出这个结果为何合理，来看 stats 类型与 stats_collect 函数。stats 为每一个统计矩保留一个 double；stats_collect 则说明收集新值时怎样更新这些矩。

stats

一种简单数据结构，用来收集统计量的第 0 至第 3 阶矩。

WARNING

由于样本数也使用 double，这一切只对约 2⁵⁰ ≈ 10¹⁵ 个样本有效。

struct stats {
  double moment[4];
};
typedef struct stats stats;

:::

stats_collect

向统计对象 c 加入值 val。

moments 是要收集的统计矩数量，必须位于 0 到 3 的闭区间内。

inline
void stats_collect(stats c[static 1],
                   double val, unsigned moments)
  [[__reproducible__]] {
  double n = stats_samples(c);
  double n0 = n-1;
  double n1 = n+1;
  double delta0 = 1;
  double delta = val - stats_mean(c);
  double delta1 = delta/n1;
  double delta2 = delta1*delta*n;
  switch (moments) {
  default:
    c->moment[3] += (delta2*n0 - 3*c->moment[2])*delta1;
    [[__fallthrough__]];
  case 2:
    c->moment[2] += delta2;
    [[__fallthrough__]];
  case 1:
    c->moment[1] += delta1;
    [[__fallthrough__]];
  case 0:
    c->moment[0] += delta0;
  }
}

如前所述，这是一种相对简单、逐步更新各矩的算法。与朴素方法相比，它有两项重要性质：使用当前平均值估计与新值之差，避免数值不精确；不存储所有样本也能完成计算。Welford [1962] 首次针对平均值和方差（第 1、2 阶矩）描述这种方法，Pébay [2008] 随后将它推广到更高阶矩。事实上，stats_collect1 等函数只是为选定矩数实例化该方法。

stats_collect2 的汇编清单表明，前面发现该函数需要 25 个周期是合理的。它对应少量算术指令、加载指令与存储指令。^[3]

清单 16.6　GCC 为 stats_collect2(c) 生成的汇编

asm

vmovsd 8(%rdi), %xmm1
vmovsd (%rdi), %xmm2
vaddsd .LC2(%rip), %xmm2, %xmm3
vsubsd %xmm1, %xmm0, %xmm0
vmovsd %xmm3, (%rdi)
vdivsd %xmm3, %xmm0, %xmm4
vmulsd %xmm4, %xmm0, %xmm0
vaddsd %xmm4, %xmm1, %xmm1
vfmadd213sd 16(%rdi), %xmm2, %xmm0
vmovsd %xmm1, 8(%rdi)
vmovsd %xmm0, 16(%rdi)

不过，这些示例测量仍有一项系统性错误：测量点位于 for 循环之外。这样一来，测量还会包含与循环自身对应的指令。清单 16.7 给出先前讨论中跳过的三个循环。它们基本为空，目的是测量这种循环本身的贡献。

清单 16.7　使用 struct timespec 为三个 for 循环插桩

timespec_get(&t[0], TIME_UTC);
/* 把 i 声明为 volatile，确保循环确实执行 */
for (uint64_t volatile i = 0; i < iterations; ++i) {
  /* 不做任何事情 */
}
timespec_get(&t[1], TIME_UTC);
/* s 必须是 volatile，确保循环确实执行 */
for (uint64_t i = 0; i < iterations; ++i) {
  s = i;
}
timespec_get(&t[2], TIME_UTC);
/* 不透明计算确保循环确实执行 */
for (uint64_t i = 1; accu0 < upper; i += 2) {
  accu0 += i;
}
timespec_get(&t[3], TIME_UTC);

尝试测量内部没有语句的 for 循环时，会面临一个严重问题：没有效果的空循环可以而且会被优化器在编译期消除。正常生产条件下，这是好事；但在这里，我们想要测量，它就很恼人。因此，我们展示三种不应被优化掉的循环形式。

第一种把循环对象声明为 volatile，因此编译器必须生成该对象上的所有操作。清单 16.8 和 16.9 分别给出 GCC 与 Clang 版本的循环。可以看到，为了遵守循环对象的 volatile 限定，两者都必须发出若干加载和存储指令。

清单 16.8　GCC 生成的清单 16.7 第一个循环

asm

.L510:
  movq 24(%rsp), %rax
  addq $1, %rax
  movq %rax, 24(%rsp)
  movq 24(%rsp), %rax
  cmpq %rax, %r12
  ja .L510

清单 16.9　Clang 生成的清单 16.7 第一个循环

asm

.LBB9_17:
  incq 24(%rsp)
  movq 24(%rsp), %rax
  cmpq %r14, %rax
  jb .LBB9_17

下一个循环试图更节省一些，只强制向辅助对象 s 执行一次 volatile 存储。从清单 16.10 可以看到，所得汇编代码相当高效，只包含四条指令：一次加法、一次比较、一次跳转和一次存储。

清单 16.10　GCC 生成的清单 16.7 第二个循环

asm

.L509:
  movq %rax, s(%rip)
  addq $1, %rax
  cmpq %rax, %r12
  jne .L509

为了更接近真实测量使用的循环，下一个循环采用一种技巧：执行索引计算和比较，并使其结果对编译器不透明。清单 16.11 表明，它产生了与前一个循环相似的汇编代码，只是现在第二次加法替代了存储操作。

清单 16.11　GCC 生成的清单 16.7 第三个循环

asm

.L500:
  addq %rax, %rbx
  addq $2, %rax
  cmpq %rbx, %r13
  ja .L500

表 16.1　测量结果比较

循环	内容	每次迭代秒数	差值	增益/损失	结论明确
0	`volatile` 循环	1.97·10⁻⁹
1	`volatile` 存储	3.66·10⁻¹⁰	−1.60·10⁻⁹	−81%	是
2	不透明加法	3.45·10⁻¹⁰	−2.10·10⁻¹¹	−6%	否
3	再加 `timespec_get`	1.77·10⁻⁸	1.74·10⁻⁸	+5043%	是
4	再加平均值	2.62·10⁻⁸	8.5·10⁻⁹	+48%	是
5	再加方差	2.90·10⁻⁸	2.8·10⁻⁹	+11%	是
6	再加偏度	3.17·10⁻⁸	2.7·10⁻⁹	+9%	是

表 16.1 汇总了这里收集的结果，并比较不同测量之间的差异。正如预期，带 volatile 存储的循环 1，比带 volatile 循环计数对象的循环快 80%。因此，使用 volatile 循环计数对象并不是好主意，它会扭曲测量。

另一方面，从循环 1 改到循环 2 的效果并不明显。6% 的增益小于测试的标准差，所以甚至不能确定增益是否真实存在。若想知道两者是否确有差异，就必须执行更多测试，并希望标准差能够收窄。

不过，对于评估观察结果的时间影响这一目标，测量结果已经相当明确。for 循环的版本 1 和 2 所产生的影响，比 timespec_get 或 stats_collect 调用的影响低大约一至两个数量级。因此，可以认为循环 3 至 6 的值很好地估计了被测函数的期望时间。

这些测量中还有一个强烈依赖平台的组成部分：用 timespec_get 测量时间。事实上，这次经历告诉我们：在我的机器上，^[4] 时间测量与统计收集的成本处在同一数量级。对我个人而言，这是个意外发现；写这一节时，我原以为时间测量会昂贵得多。

我们还了解到，标准差这样的简单统计量很容易取得，并有助于证实关于性能差异的断言。

要点 16.4 #7

收集测量结果的高阶矩以计算方差与偏度，既简单又廉价。

因此，今后每当你作出性能断言，或者看到他人作出这类断言时，都要确保至少已经处理结果的波动。

要点 16.4 #8

运行时间测量必须用统计方法加固。

小结

不应以正确性换取性能。
inline 是在调用位置优化小型纯函数的适当工具。
restrict 有助于处理函数形参的别名性质。使用它必须谨慎，因为它会向函数调用方施加限制，而这些限制未必能在编译期强制执行。
属性 [[unsequenced]] 与 [[reproducible]] 可以为编译器提供大量优化机会。
声称性能有所改善时，必须附带充分的测量与统计。方法正确时，测量和统计收集的开销可以忽略。

É. Alepins、J. Gustedt，Unsequenced functions，2022，https://open-std.org/JTC1/SC22/WG14/www/docs/n2956.htm。 ↩︎
也就是说，它真正估计期望时间的标准差，而不只是任意样本自身的标准差。 ↩︎
这里的汇编展示了一些尚未见过的 x86_64 特性：浮点硬件寄存器与指令，以及 SSE 寄存器与指令。内存位置 (%rdi)、8(%rdi) 和 16(%rdi) 分别对应 i = 0、1、2 时的 c->moment[i]；去掉 v 前缀后的指令名，其 sd 后缀表示所执行的操作；vfmadd213sd 是浮点乘加指令。 ↩︎
一台普通的 Linux 笔记本计算机，采用截至 2016 年较新的系统和现代编译器。 ↩︎

第 16 章 性能 ​

16.1 内联函数 ​

16.2 使用 restrict 限定符 ​

16.3 未定序属性与可复现属性 ​

16.4 测量与审视 ​

小结 ​

第 16 章性能

16.1 内联函数

16.2 使用 `restrict` 限定符

16.3 未定序属性与可复现属性

16.4 测量与审视

小结