旭穹の陋室

浮点数 浮点运算的使用者可以被描绘为一个智商（IQ）正态分布（或者说钟形曲线）图的模样，因为他们对于浮点运算的理解和使用进程往往会经历三个阶段，形成一种典型的分布态势： 初级程序员通常会无处不在的使用浮点数，好像它是一种神奇的无限精度的数据类型。 然后他们发现0.1 + 0.2并不等于0.3，或者遇到其他的奇怪问题，他们会感到困惑和恐慌，开始误以为每次运算都会加入一些随机的误差，因此在很多年里，他们避免使用任何实数（浮点数）类型。 最后，他们终于鼓起勇气去读IEEE-754浮点数标准，理解浮点数是如何工作的，并开始适应如何正确地使用浮点数。 不幸的是，仍有许多人停留在对于浮点数运算的误解阶段。他们潜在的认知误区导致他们对浮点数运算存有种种错误认知——以为它基本上是不精确和不稳定的，而且比整数运算慢。 但这些都是错误的认知。首先，浮点运算其实往往比整数运算更快，这是因为有专门的指令用于加速浮点数的运算。其次，实数（如浮点数）的表示方式是有严谨标准的，并且在进行运算时，也遵循简单且确定的规则，比如四舍五入等舍入规则。这使得我们可以可靠地处理计算误差。 实际上，浮点数的使用是非常可靠的 ...

算术运算 正如我们在本书中多次指出的，了解指令集的更深层次的知识是非常有益的，尤其是在CISC平台（如x86体系架构）下，它目前有大概1000到4000种不同的指令，具体数量取决于你的统计方法。 这些指令中的大部分都与算术运算有关。有效地使用这些指令以优化算术运算需要大量的知识、技能和创造力。因此，在这一章，我们将讨论数字的表达方式及其在数字算法中的运用。

获得准确的结果 某个算法有两个库实现并不罕见，每个库都维护自己的基准测试代码，并且每个库都声称比另一个更快。这让所有相关人员都感到困惑，尤其是不得不在两者之间做出选择的用户。 这种情况通常不是由作者的欺诈行为造成的；他们只是对“更快”的含义有不同的定义，事实上，只定义和使用一个性能指标往往是非常有问题的。 测量正确的事情 有很多事情会在基准测试中引入误差。 不同的数据集 许多算法的性能在某种程度上取决于数据集的分布。例如，为了定义什么是最快排序、最短路径或二分查找算法，你必须修正运行该算法的数据集。 这有时甚至适用于处理输入相对单一的算法。例如，向GCD实现提供顺序的数字不是一个好主意，因为它使分支非常容易预测： // don't do thisint checksum = 0;for (int a = 0; a < 1000; a++) for (int b = 0; b < 1000; b++) checksum ^= gcd(a, b); 然而，如果我们随机采样相同范围的数字，分支预测会变得更加困难，基准测试也需要更长的时间，因为尽管处理 ...

基准测试 大多数好的软件工程实践都以这样或那样的方式解决了加快开发周期的问题：你希望更快地编译软件（构建系统），尽快发现错误（静态分析、持续集成），在新版本准备好后立即发布（持续部署），并毫不拖延地对用户反馈做出反应（敏捷开发）。 性能工程也不例外。如果你做得正确，它也应该类似于一个周期： 运行程序并收集指标。 找出瓶颈在哪里。 移除瓶颈，然后转到步骤1。 在本节中，我们将讨论基准测试，并讨论一些实用的技术，这些技术可以缩短此周期并帮助你更快地迭代。大多数建议都来自于本书的编写，因此你可以在本书的代码库中找到许多真实示例。 C++内部的基准测试 编写基准测试代码有很多方法。最流行的方法也许是在一个文件中包含几个要比较的相同语言实现，从主函数中分别调用它们，并在同一源文件中计算所有需要的指标。 这种方法的缺点是，你需要编写大量的样板代码（boilerplate code），并为每个实现重复它，但这可以用元编程（metaprogramming）解决一部分。例如，当你要对多个gcd实现进行基准测试时，可以使用此高阶函数来显著减少基准测试代码： const int N = 1e6, T = ...

机器码分析器 机器码分析器（machine code analyzer）是一种程序，它提取一小段汇编代码，使用编译器可用的信息模拟其在特定微架构上的执行，并输出整个块的延迟和吞吐量，以及CPU内各种资源的完美周期（cycle-perfect，指可以仿真可以完美还原原处理器每个时钟周期的行为）利用率。 使用llvm-mca 有很多种机器代分析器，但我个人更喜欢llvm-mca，你可以通过包管理器和clang一起安装它。也可以通过名为UICA的web工具访问它，或者在 Compiler Explorer 中语言一栏选择“Analysis”。 llvm-mca所做的是，对给定的汇编片段执行一定次数的迭代，并计算每条相关指令的资源使用情况的统计信息，这对于找出瓶颈所在非常有用。 考虑数组求和的简单示例： loop: addl (%rax), %edx addq $4, %rax cmpq %rcx, %rax jne loop 以下是llvm-mca在Skylake架构下的分析结果： Iterations: 100Instructions: 4 ...

程序仿真 最后一种分析方法（或者更确切地说是一组分析方法）不是通过实际运行程序来收集数据，而是通过使用专用工具模拟程序来分析应该发生的事情。 这种profilers有很多类别，区别在于模拟计算过程中的不同部分。在本文中，我们将重点关注缓存和分支预测，并为此使用Cachegrind，这是Valgrind中一个面向性能分析的部分，Valgrind 是一个有名的内存泄漏检测和内存调试工具。 使用Cachegrind进行性能分析 Cachegrind本质上检查二进制文件中是否有“感兴趣的”指令——执行内存读/写和条件跳转/间接跳转的指令——并用相应的代码替换它们，这些代码使用软件数据结构模拟相应的硬件操作。因此，它不需要访问源代码，可以分析已经编译的程序，并且可以在任何程序上运行，如下所示： valgrind --tool=cachegrind --branch-sim=yes ./run# also simulate branch prediction ^ ^ any command, not necessarily one process 它检测所有涉及的二进制文件，运行它 ...

Instrumentation是一种相当乏味的分析方法，尤其是当你对程序的多个片段感兴趣时。即使它可以被工具部分自动化，但由于其固有的开销，它仍然无法帮助你收集一些细粒度的统计信息。 另一种侵入性较小的分析方法是以随机间隔中断程序的执行，并查看指令指针的位置。指针停在每个函数块中的次数与执行这些函数所花费的总时间大致成比例。你还可以通过这种方式获得一些其他有用的信息，比如通过检查调用堆栈来找出哪些函数被哪些函数调用。 原则上，这可以通过运行一个带有gdb和ctrl+c的程序来实现，但现代CPU和操作系统为这种类型的分析方法提供了特殊的实用程序。 硬件事件 硬件性能计数器是内置在微处理器中的特殊寄存器，可以存储某些硬件相关活动的计数。它们可以很容易地被添加到微芯片上，因为它们基本上只是带有激活连线的二进制计数器。 每个性能计数器都连接到一个很大的电路子集，可以配置为在特定硬件事件（如分支预测失误或缓存未命中）时递增。你可以在程序开始时重置计数器，然后运行，并在结束时输出其存储值，该值将等于某个事件在整个执行过程中被触发的确切次数。 你还可以通过多路复用来跟踪多个事件，也就是说，以均匀的间 ...

性能检测（Instrumentation）是一个非常复杂的术语，意思是将计时器和其他跟踪代码插入程序中。最简单的例子是在类Unix系统中使用time来测量整个程序的执行持续时间。 更一般的情况，我们想知道程序的哪些部分需要优化。编译器和IDE附带的一些工具可以自动对指定函数进行计时，但使用本语言提供的任何与时间交互的方法，手动执行计时更为鲁棒： clock_t start = clock();do_something();float seconds = float(clock() - start) / CLOCKS_PER_SEC;printf("do_something() took %.4f", seconds); 这里的一个细节是，你不能用这种方式测量特别快速的函数的执行时间，因为clock函数以微秒(10−610^{-6}10−6)为单位返回当前时间戳，并且其本身也需要高达几百纳秒才能完成。类似地，所有其他与时间相关的实用程序都具有至少微秒的粒度，这在低级别优化的世界中是约定俗成的。 为了获得更高的精度，可以在循环中重复调用待测函数，对整个过程计时一次，然后 ...

性能分析 关注源代码或其汇编代码是一种发现性能问题的流行方法，但不最有效的方法。当性能达不到预期时，你可以使用一种统称为profiler的特殊程序分析工具更快地确定根本原因。 有许多不同类型的profiler。我倾向于通过类比物理学家或其他自然科学家如何研究小分子来探讨它们，即要根据所需的精度水平来选择正确的工具： 当物体在微米尺度上时，他们使用光学显微镜。 当物体在纳米尺度上，光不再与它们相互作用时，它们会使用电子显微镜。 当物体更小时（例如，原子内部），他们会求助于关于事物如何运转的理论和假设（并使用复杂和间接的实验来验证这些假设）。 同样，我们有三种主要的profiling技术，每种技术有不同的原理，不同的适用领域，不同的精度水平： 通过性能检测（Instrumentation），你可以对整个程序或部分程序进行计时，并统计你感兴趣的特定事件。 通过统计分析（Statistical profiling），你可以深入到汇编级别，跟踪各种硬件事件（hardware events），如分支预测失误或缓存未命中，这些对性能至关重要。 通过程序仿真（Program simulation ...

预计算 当编译器可以推断某个变量不依赖于任何用户提供的数据时，他们可以在编译时计算其值，并将其嵌入生成的机器代码，转化为常量。 这种优化对性能有很大帮助，但它不是C++标准的一部分，所以编译器不必这么做。当编译时计算很难实现或时间密集时，编译器可能会错过这个机会。 常量表达式 一个更可靠的解决方案，在现代C++中，可以将函数标记为constexpr；如果它是通过传递常量来调用的，则其值保证在编译时计算： constexpr int fibonacci(int n) { if (n <= 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2);}static_assert(fibonacci(10) == 55); 这些函数有一些限制，比如它们只能调用其他constexpr函数，不能进行内存分配，但除此之外，它们还是会“按原样”执行。 请注意，虽然constexpr函数在运行时不会花费任何费用，但它们仍然会增加编译时间，因此至少还是要关心一下它们的效率，不要在其中放入非确定性多项式 ...