过早的优化可能是万恶之源，但 逾期优化是所有挫败感的根源。不管怎样 硬件变得多么快，我们发现编写运行起来的程序也很容易 慢。这通常不会立即显现出来。用户可以持续数年 而不考虑程序的性能是摆在它面前的问题 突然变得如此——通常在一个工作日的时间里。
我一生中对优化的投入比我所关心的要多， 这段经历使我得出了两点看法：
- 人类的乐观主义使我们相信，我们可以很容易地知道程序在哪里 大部分时间都花在了身上。
- 人类的乐观主义使我们相信，我们可以很容易地知道如何使 程序的慢速部分运行得更快。
你不会惊讶地发现，我认为这两种形式的 乐观主义放错了地方。这在一定程度上是因为，硬件和软件都具有 变得越来越复杂，越来越难以理解它们的影响 关于性能。但是，也许更根本的是，我们倾向于高估如何 我们对我们正在开发的软件了解很多。我们过分强调 我们亲自研究过的系统，尤其是我们最近开发的系统 继续工作。我们淡化了系统的其他部分，包括 依赖项（例如库）。
第一个观察结果的解决方案是相当广为人知的——一个 在假设一个人知道它在哪里之前，应该严格分析一个程序 大部分时间都花在了上。我特意说“严谨剖析”，因为人们 经常将“我曾经分析过一个程序”与“我已经建立了一个良好的程序”混淆 程序在各种情况下的表现模型”。有时，一个 快速分析工作就足够了，但它也可能产生误导。通常有必要 使用不同的输入来分析程序，有时在不同的机器上或 网络配置，并可采用多种采样和非采样方式 方法[1]。
然而，多种解决方案及其不可避免的权衡，对 我认为，第二个观察结果被低估了。我倾向于认为 主要有四种解决方案：
- 使用更好的算法。
- 使用更好的数据结构。
- 使用较低级别的系统。
- 接受不太精确的解决方案。
在这篇文章的其余部分，我将逐一介绍并给出一些 有关权衡的建议。
使用更好的算法
让我们想象一下，而且我确实见过这种情况发生！在仔细对一个Python程序进行性能分析之后，我发现大部分时间都花在一个看起来像这样的函数上：这是一个冒泡排序！在这一点上，很多人会开始咕噜咕噜，因为这显然是一种排序元素的缓慢方式。然而，冒泡排序在许多“更好”的算法上常常被忽视的优势是：它在常数内存中运行[2]。我可以赌一把，认为我的程序不需要使用常数内存，但如果我不确定，我可以使用另一种保留这个属性的算法。让我们尝试选择排序：如果我使用这段快速测试代码：并在Linux服务器上的CPython 3.11上运行它，我会始终得到类似以下的计时结果：换句话说，在我的测试中，选择排序大约比冒泡排序快三倍。
0.0643463134765625
0.020025014877319336
你不需要我告诉你，选择排序不是最快的 可能的排序算法，但“最快”是一个比第一个更滑溜的概念 出现。例如，上面的选择排序算法比气泡快 对随机数据进行排序，但对排序数据进行气泡排序要快得多 [3]。输入与算法性能之间的关系 可能很微妙。众所周知，如果你选择了一个不幸的 实现快速排序时的“枢轴”， 你会发现它非常不快（例如，你可以在已经排序的数据上让它变慢 作为上面的选择排序）。
我们可以由此概括出，“使用更好的算法”需要 了解系统的更广泛上下文和算法的性质 你正在考虑使用。例如，我经常看到人们将 算法的最佳情况、平均情况和最坏情况的性能 - 但 这三条信息之间的差异在我 优化程序。有时我可能会对我的程序有所了解（例如 其输入的性质），这让我确信最坏的情况不会发生，或者我 不要认为最坏的情况是一个问题（例如，这是一个批处理作业，没有人会这样做 注意偶尔的延迟）。但是，一般来说，我更关心最坏的情况 而不是最好的情况，我相应地选择算法。
这种情况也并不少见 理论性能好的算法在现实世界中表现不佳 性能（大O符号可以隐藏许多罪恶）。如有疑问，我会尝试 逐渐增加测试数据，直到我觉得我真正理解了实际情况 不同选择的后果。
忽视复杂性也是很容易的。从根本上说，更快的算法之所以更快，是因为它们观察到计算中的某些步骤可以被绕过。我仍然记得我第一次阅读timsort的描述时的情景：它的算法观察之美至今仍然让我难以忘怀。但验证这些观察比我们想象的要困难——即使是由我曾经遇到的最伟大的程序员之一创造的timsort，在其中也存在一个微妙的错误[4]。
当我们凡人实现更快的算法时，他们是 通常略有不正确，尤其是在新实施时， 要么产生错误的结果，要么没有达到预期的性能 特征[5]。 例如，并行化算法通常可以带来巨大的加速， 特别是随着 CPU 获得更多内核，但我们中有多少人了解 C11 内存模型足以对后果或并行化充满信心？
（不）正确性和理解困难的结合 算法速度快的上下文意味着我经常鼓励人们 从一个简单的算法开始，只有在他们 真的发现他们需要。选择（并在必要时实施）正确的 手头任务的算法是一项非常困难的技能！
使用更好的数据结构
让我们想象一下，我分析了另一个程序，发现我花了大部分时间 在以下函数中： 这是一个存在检查功能！优化这些可能非常有趣， 因为我的选择将取决于传递给此函数的列表的方式 使用。例如，我可以将列表更改为二叉树。但 如果我能说，这并不少见，我们反复检查是否存在 列表中的元素在初始创建后永远不会发生突变，我可能是 能够摆脱一个非常简单的数据结构：排序列表。那可能 听起来很奇怪，因为“排序列表”听起来不像是数据结构， 但这允许我进行二进制搜索。 对于除最小列表 [6] 以外的任何内容，二进制 搜索比上面的线性搜索快得多。
就像“使用更好的 算法“、”使用更好的数据结构“需要仔细思考和测量[7]。总的来说，虽然我经常发现有必要实现我自己的“更好 算法“，我很少发现有必要实现我自己的”更好 数据结构”。这在一定程度上是我的懒惰，但主要是因为 数据结构比更好的算法更容易打包到库中[8]。
关于“更好的数据结构”，有一个重要的战术变体，也许是 最好的想法是“把你的结构/类节食”。如果程序是 分配大量给定结构/类，该结构/类的大小 以字节为单位本身就可能成为一项重大成本。当我处理错误时 在grmtools中恢复，我发现只需减少最常分配的 结构体大小增加了 8 个字节，将程序总性能提高了 5% — 一个 从记忆中，我重复了两次！
有很多类似的策略， 例如，减少“指针追逐”（通常通过折叠多个结构/类 合二为一），鼓励记忆局部性等。然而，虽然它很容易 测量结构/类的大小及其分配频率，它是 很难衡量记忆局部性等因素的间接影响—— 我听到这些因素被归咎于表现不佳的次数比我多得多 看到这些因素被证明是导致表现不佳的原因。一般来说，我 只有在我绝望的时候才考虑这些因素。
使用较低级别的系统
一个历史悠久的传统是在较低级别重写程序的某些部分 程序设计语言。让我们将 Python 冒泡排序重写为 Rust：我温和地采用了之前的 Python 程序来保存 1000 个随机 浮点数，并在 Rust 中添加了这个测试代码： 我的 Rust 冒泡排序在 0.001 秒内运行，比 Python 版本快约 60 倍。 这看起来是“在低级编程中重写”的巨大成功 语言“——但你可能已经注意到，我把这一部分的标题定为”使用 下级系统”。
与其花 15 分钟编写 Rust 代码，不如 我更聪明地认识到我的 Python 冒泡排序可能是 强调 CPython（Python 最常见的实现）的弱点。 特别是，CPython 将代表我在概念上认为的列表 的浮点数作为指向单个指针的数组 堆分配的 Python 对象。这种表现形式具有以下优点： 通用性，但不是效率。
尽管经常被遗忘，CPython并不是Python的唯一实现。在替代方案中，有PyPy，它刚好像Rust一样高效地表示浮点数列表。仅仅将“typing”改为“float”就使我的冒泡排序速度提高了4倍！我很少能做出如此少的努力，却能获得如此大的性能提升。这并不是说PyPy能像Rust一样快地运行我的程序（PyPy仍然慢大约15倍），但它可能足够快，这才是真正重要的。
我见过多个组织 犯了试图解决性能问题的错误 用低级编程语言重写他们的软件，当他们愿意的时候 从研究如何运行现有软件中获得了足够的好处 快一点。在这里，人们通常可以做很多事情，从 不同的语言实现，以检查您是否有编译器 优化已开启 [9]，以使用更快的库 或数据库，等等。有时用较低级别的编程语言重写 确实是正确的做法，但这很少是一件快速的工作，而且它 不可避免地会引入一段不稳定的时期，而错误则被甩出 新版本。
接受不太精确的解决方案
我们面临的一个常见问题是，我们有 n 个元素和 我们想了解适合我们情况的最佳子集或顺序。 假设我实现了一个编译器和 30 个单独的优化 通过。我知道，如果运行某些优化通道，它们会更有效 经过其他优化后，但我不知道最有效的排序是什么 所有的通行证都是。
我可以编写一个程序来枚举所有 这 30 个通道的排列，根据我拥有的基准套件运行它们， 然后选择最快的排列。但是，如果我的基准测试套件需要 1 秒 要运行，大约需要 282 年来评估所有 可能性 — 这比当前年龄要长得多 宇宙。显然，我迫不及待地想得到答案：我只能运行一个 所有排列的子集。在这样的情况下，我不得不接受 我永远无法确定最好的答案是什么：但是， 也就是说，我至少可以确保我最终得到一个更好的答案 尝试任何事情。
有多种方法可以解决这个问题，但大多数都归结为本地搜索。从本质上讲，我们定义了一个指标（在我们的运行示例中，有多快 我们的基准测试套件运行），这允许我们比较两个解决方案（在我们的例子中， 越快越好），并丢弃最坏的。然后，我们需要一种方法来生成一个 邻接解，此时我们重新计算 指标并丢弃新旧解决方案中较差的。在任一 固定的时间限制，或者如果我们找不到改善指标的解决方案，我们 返回我们找到的最佳解决方案。这个简单的有效性 技术（核心算法是几行代码）往往会让新手目瞪口呆， 因为局部最优的明显问题似乎应该破坏整个想法。
正如我所概述的那样，通常实现的本地搜索 上面它产生了正确但可能不是最优的解决方案。有时 但是，我们准备接受一个不太精确的答案 感觉到它可能是“不正确的”。我并不是说 程序有问题，但程序可能故意 产生的输出与我们认为的“完整和适当”的答案不完全匹配。
究竟什么是“正确” 因情况而异。例如，快速反转平方根近似乘法逆：对于 游戏等情况，其快速近乎正确的答案是 比缓慢的绝对正确的答案更好的权衡。Bloom 过滤器可能会给出 false 积极的一面：接受这种可能性可以使它变得异常 节俭的记忆。JPEG 图像压缩 故意丢弃图像的一些细节，以使 图像更可压缩。与其他图像压缩方法不同，我不能 从 JPEG 中完美地恢复原始想象，但要放弃一点 一点图像质量，我最终要传输的文件要小得多。
我认为，一般来说，大多数程序员都很难接受这一点 正确性有时是可以权衡的——就个人而言，它冒犯了 我内心深处坚信程序应该是正确的。可能 正因为如此，我认为该技术的使用频率低于它 应该是。
然而，最近，我们变得更愿意接受不正确的东西 答案要归功于ML（机器学习）的爆炸式增长。而本地搜索 要求我们明确说明如何创建新的解决方案，ML是经过训练的 ，然后从该数据生成新的解决方案。这可以 是一种非常强大的技术，但 ML 不可避免的“幻觉”是 实际上只是一种不正确的形式。
因此，我们可以看到有两种不同的方式来接受不精确 解决方案：可能不是最优的;并且可能不正确。我开始意识到 很多人认为它们是一回事，但可能不正确更多 经常引起问题。我可能很乐意交易一下 图像质量以获得更好的压缩效果，但是如果 ML 系统重写了我的代码和 留下一个“不”我不高兴。我的经验法则是，除非你是 确信你可以容忍不正确，你最好假设你 不能。
总结
我列出了上面的四种优化方法，这些方法在我所使用的频率中 看到它们被使用（从使用最多到最少使用）。
我最不喜欢的方法是 “用低级编程语言重写”，从某种意义上说，它倾向于 提供最差的改进/成本比率。这并不意味着它总是如此 错误的方法，但我们倾向于在充分之前伸手去拿它 被认为是更便宜的替代品。相比之下，我认为直到最近我们 很少达到“接受不太精确的解决方案”，尽管 ML 爆炸迅速改变了这一点。
就我个人而言，当我尝试优化一个程序时，我倾向于伸手去 首先是最简单的技巧。我发现让人们感到惊讶的一件事是频率 我的第一次优化尝试是寻找使用哈希图的地方——只是很少 我是否去寻找要使用的异国情调的数据结构。我很少转向聪明 算法。我怀疑，在那些聪明的算法中，我倾向于自己实现 二叉搜索是我最常使用的搜索，我可能在 大多数一年一到两次——每次我实施它时，我都必须查找 正确的方法[10]！
最终，写完这篇文章后，我开始意识到有 贯穿所有方法的三个教训。
首先，当可以为了性能而牺牲正确性时，它是一个强大的 技术——但我们经常为了性能而牺牲正确性 不经意间。当我们需要优化程序时，最好使用最少的 复杂的优化将给我们带来我们想要的性能，因为这是 可能会引入最少的错误。
其次，人的时间很重要。因为我们程序员非常喜欢复杂性， 我们很想过早地进行复杂的优化。便 他们成功地提高了性能——而他们往往做不到！– 他们往往会消耗很多 比我们所需的性能改进所需的时间更多。
第三，我认为优化知识的广度比 深度的优化知识。在我列出的每种方法中 在这篇文章中，我有一些定期部署的技巧。这很有帮助 给我一个合理的直觉，了解什么是最合适的整体方法 以我目前的表现可能很糟糕，即使我不知道具体情况。