旭穹の陋室

契约编程 在Java和Rust这样的“安全”语言中，通常对每一个可能的操作和每一个潜在的输入都有定义良好的行为。有些东西是非严格定义的（under-defined），比如哈希表中键的顺序或std::vector的扩容因子，但这些通常是一些待实现的小细节，为了以后获得潜在的性能提升。 相反，C和C++将未定义行为的概念提升到了另一个层次。某些操作在编译或运行时不会导致错误，但却是不被允许的——从程序员和编译器之间存在契约的角度看，如果出现未定义的行为，编译器做任何事情都是合法的，包括炸毁监视器或格式化硬盘。但编译器工程师对此（炸毁你的监视器）并不感兴趣。相反，未定义的行为常被用来保证没有corner cases和帮助优化。 为什么存在未定义的行为 导致未定义行为的行为主要有两类： 一些无意的错误操作，如除以零、对空指针解引用或读取未初始化的内存。你会希望在测试过程中尽快定位到这些错误，因此让程序崩溃或出现不确定的行为会比让它们总是执行固定的回退操作（如返回零）要好。 可以编译并运行带有sanitizers的程序，以便尽早捕获未定义的行为。在GCC和Clang中，可以使用-fsanit ...

特定场景优化 大多数由-O2和-O3启用的编译器优化都可以保证提高性能，或者至少不会严重损害性能。那些没有包含在-O3中的要么不严格符合标准，要么是非常不直接的，需要程序员提供一些额外的输入来帮助决定使用它们是否有益。 让我们讨论一下我们之前在本书中讨论过的最常用的优化方法。 循环展开 默认情况下，循环展开是禁用的，除非循环在编译时进行少量常数的迭代——在这种情况下，它将被完全无跳转的重复指令序列所取代。它可以通过-funroll-loops标志全局启用，该标志将展开迭代次数在编译时或进入循环前可以确定的所有循环。 你也可以使用pragma来标记特定循环： #pragma GCC unroll 4for (int i = 0; i < n; i++) { // ...} 循环展开会使二进制文件变得更大，所以可能会也可能不会（指令cache miss）使代码运行得更快。不要狂热地使用它。 函数内联 内联最好由编译器决定，但你可以使用inline关键字来提示编译器： inline int square(int x) { return x * ...

编译标志与编译目标 从编译器获得高性能的第一步是要求它这么做，这是通过一百多个不同的编译器选项、属性和杂注来完成的。 优化等级 GCC中的速度优化主要有四个半级别： -O0是默认选项，不进行优化（尽管从某种意义上说，它确实在编译时间上做了优化）。 -O1（别名为-O）做了一些“唾手可得”的优化，且几乎不影响编译时间。 -O2使能所有已知几乎没有负面副作用并且编译时间时间相对合理的优化（这是大多数项目用于生产构建的选项）。 -O3会做非常激进的优化，几乎使能所有GCC中实现的正确的优化。 -Ofast在-O3优化的基础上，再加上一些优化标志，这些标志可能会破坏严格的标准规定，但对大多数应用程序并不至关重要（例如，浮点运算可能会被重新排列，从而使结果在尾数中偏离几位）。 还有许多优化标志甚至没有包含在-Ofast中，因为它们只针对具体场景，默认情况下启用它们更有可能损害性能，而不是提高性能，我们将在下一节中讨论其中的一部分。 指定目标平台 下一件你可能想做的事是告诉编译器更多关于这个代码应该在哪些计算机平台上运行的信息：平台集范围越小，优化效果越好。默认情况下，编译器将生成可以在任何相 ...

编译阶段 在直接跳到编译器优化（这是本章的大部分内容）之前，让我们先简要回顾一下“大局”。跳过无聊的部分，将C程序转化为可执行程序有4个阶段： 预处理（preprocessing）：宏展开，从头文件中提取包含的源代码，并从源代码中删除注释：gcc-E Source.c（将预处理的源代码输出到stdout） 编译（compiling）：解析源代码，检查语法错误，将其转换为中间表示形式（intermediate representation，IR），执行优化，最后将其翻译为汇编语言：gcc -S file.c（生成.S文件） 汇编（assembly）：将汇编语言转换为机器代码，除了像printf这样的外部函数调用外都被占位符取代：gcc -c file.c（生成一个.o文件，称为对象文件（object file）） 链接（linking）：最后通过插入函数调用的实际地址来解决函数调用问题，并生成一个可执行的二进制文件：gcc -o binary file.c 在这些阶段中的每一个阶段都有提高程序性能的可能性。 程序间优化 程序是逐个文件编译的，然后再将这些文件链接在一起。这样更容易也更 ...

编译 学习汇编语言的主要好处不是能够用汇编语言编写程序，而是了解编译代码过程中发生的事情及其对性能的影响。 在极少数情况下，我们确实需要切换到手写汇编以获得最大性能，但大多数情况下，编译器能够自己生成接近最佳的代码。当编译器没有这样做时，通常是因为程序员对问题的认知比能从源代码中推断出的要多，且未能将这些额外信息传达给编译器。 在本章中，我们将讨论让编译器完全按照我们的要求进行编译的复杂性，以及收集可以指导进一步优化的有用信息的复杂性。

吞吐量计算 针对延迟的优化通常与针对吞吐量的优化大不相同： 当优化数据结构查询算法、小型一次性算法或分支算法时，你需要查询所用指令的延迟，在脑海中构建计算的执行图，然后尝试重新组织它，使关键路径更短。 在优化热循环（hot loops）和大型数据集算法时，你需要查询所用指令的吞吐量，计算每次迭代每个指令的使用次数，确定其中哪一个是瓶颈，然后尝试重组循环，以减少其使用频率。 最后一条建议仅适用于数据并行(data-parallel)循环，其中每次迭代都完全独立于前一次迭代。当连续迭代之间存在某种相互依赖性时，由于下一次迭代正在等待上一次迭代完成，因此可能存在由数据冒险导致的流水线停滞。 例子 作为一个简单的例子，考虑对数组求和： int s = 0;for (int i = 0; i < n; i++) s += a[i]; 让我们暂时假设编译器不会对这个循环进行矢量化，不存在内存带宽问题，并且循环是展开的，这样我们就不会因需要维护循环变量而支付任何额外的成本。在这种情况下，计算变得非常简单： int s = 0;s += a[0];s += a[1];s += a[2] ...

指令表 执行阶段交错是数字电子学中的一个通用概念，它不仅应用于主CPU流水线，还应用于独立的指令和内存级别。大多数执行单元都有自己的小流水线，可以在前一个指令后的一到两个周期接收另一条指令。 在这种情况下，需要使用两种不同的“代价”来评估指令： 延迟（latency）：需要多少个周期来获取指令的结果。 吞吐量（Throughput）：平均每个周期可以执行多少指令 你可以从称为指令表的特殊文档中获得特定架构下指令的延迟和吞吐量。以下是我的Zen 2的一些示例值（对应32位操作数，可能存在差异）： Instruction Latency R-Throughput jmp - 2 mov r, r - 1/4 mov r, m 4 1/2 mov m, r 3 1 add 1 1/3 cmp 1 1/4 popcnt 1 1/4 mul 3 1 div 13-28 13-28 一些注释： 因为我们的已经习惯了“更多”意味着“更糟”的代价模型，所以人们大多使用吞吐量的倒数（reciprocals），而不是吞吐量。 如果某条指令执行地很频 ...

无分支程序设计 正如我们在上一节中所述，CPU无法有效预测分支的成本高昂，因为在分支预测错误后获取新指令，可能会导致长时间的流水线停滞。在本节中，我们首先讨论移除分支的方法。 预测 我们将继续之前提到的相同案例——创建一个随机数数组，并将其所有小于50的元素相加： for (int i = 0; i < N; i++) a[i] = rand() % 100;volatile int s;for (int i = 0; i < N; i++) if (a[i] < 50) s += a[i]; 我们的目标是消除if语句带来的分支。我们可以试着这样摆脱它： for (int i = 0; i < N; i++) s += (a[i] < 50) * a[i]; 现在循环迭代每个元素需要约7个周期，而不是原来的约14个。此外，如果我们将50更改为其他阈值，性能保持不变，因此它不取决于分支概率。 但是等等…难道这里不是一个分支吗？(a[i] < 50)是如何映射到汇编的？ 汇编中没有布尔类型，也没有任何基于比较结果得到1或0 ...

分支的代价 当CPU遇到条件跳转或任何其他类型的分支时，在计算出跳转条件之前，CPU不会一直处于空闲状态，而是开始推测性地执行（speculatively executing）似乎更可能立即执行的分支。在执行过程中，CPU会统计每条分支执行的概率，一段时间后，它们开始通过识别常见模式来预测它们。 因此，分支的真正“代价”很大程度上取决于CPU对它的预测能力。如果这是一个纯粹的50/50掷硬币的随机过程，你必须承受控制冒险，并丢弃整个流水线，再花15-20个周期才能重新建立起来。如果分支总是被执行或从未被执行，除了检查条件外，你几乎不付出任何代价。 实验 作为一个案例，我们将创建一个0到99之间的随机整数数组： for (int i = 0; i < N; i++) a[i] = rand() % 100; 然后我们创建一个循环，将其中所有小于50的元素加起来： volatile int s;for (int i = 0; i < N; i++) if (a[i] < 50) s += a[i]; 我们设置N=106N = 10^6N=106并 ...

流水线冒险 流水线操作可以通过并行地执行指令来隐藏指令的延迟，但也会产生一些潜在的问题——通常称为流水线冒险（pipeline hazards），即下一条指令无法在下一个时钟周期执行的情况。 这种情况可能通过多种方式发生： 当两个或多个指令需要CPU的同一部分（例如执行单元）时，就会发生结构冒险（structural hazard）。 当必须等待从前面的某个步骤计算而得的操作数时，就会发生数据冒险（data hazard）。 当CPU无法判断下一步需要执行哪些指令时，就会发生控制冒险（control hazard）。 解决冒险的唯一方法是流水线停滞（pipeline stall）：停止之前所有步骤的进度，直到阻塞的原因消失。这会在流水线中产生气泡（bubbles）——类似于流体管道中的气泡——即执行单元处于空闲状态且没有做任何有用功的一种时间传递状态。 不同的冒险有不同的代价： 在结构冒险中，你必须等待（通常再等待一个周期），直到执行单元准备就绪。它们是性能的基本瓶颈，无法避免——你在设计代码时不得不与其同行。 在数据冒险中，你必须等待计算所需的数据（关键路径（cr ...