第 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 循环计数对象的循环相比，带 volatile 存储的循环 1 耗时减少约 81%，速度约为前者的 5.4 倍。（译者注：原书此处作“快 80%”，与表中耗时变化 −81% 的含义不符，已改正。）因此，使用 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 前缀表示 VEX 编码，sd 后缀表示标量双精度（scalar double），中间部分表示所执行的操作；vfmadd213sd 是浮点融合乘加指令，213 表示操作数的顺序。 ↩︎
一台普通的 Linux 笔记本计算机，使用 2016 年时较新的系统和现代编译器。 ↩︎

↩︎
↩︎
↩︎
↩︎

第 16 章：性能 ​

16.1 内联函数 ​

16.2 使用 restrict 限定符 ​

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

16.4 测量与审视 ​

小结 ​

第 16 章：性能

16.1 内联函数

16.2 使用 `restrict` 限定符

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

16.4 测量与审视

小结