四种类型的优化 (Four Kinds of Optimisation)
四种类型的优化 (Four Kinds of Optimisation)
RSS feed: whole site or just the blog Recent posts The Fifth Kind of Optimisation Better Shell History Search Can We Retain the Benefits of Transitive Dependencies Without Undermining Security? Structured Editing and Incremental Parsing How I Prepare to Make a Video on Programming pizauth: HTTPS redirects Recording and Processing Spoken Word Why the Circular Specification Problem and the Observer Effect Are Distinct What Factors Explain the Nature of Software? Some Reflections on Writing Unix Daemons Blog archive
过早优化是万恶之源，但优化不足则是所有挫败感的根源。无论硬件变得多么快，我们总能轻易地编写出运行缓慢的程序。通常，这一点并不立即显现。用户可能多年来都没有认为程序的性能存在问题，但突然之间，问题就变得突出——通常是在一个工作日之内。
我一生中花费了太多的时间在优化上，这让我有了两个观察：
- 人类的乐观情绪使我们相信，我们可以很容易地知道程序的大部分时间花在哪里。
- 人类的乐观情绪使我们相信，我们可以很容易地知道如何使程序的慢速部分运行得更快。
你不会惊讶地发现，我认为这两种乐观情绪都用错了地方。部分原因是，随着硬件和软件变得更加复杂，理解它们对性能的影响变得更加困难。但是，也许更根本的是，我们倾向于高估我们对正在开发的软件的了解。我们过分强调我们亲自参与的系统部分，特别是我们最近参与的部分。我们低估了系统的其他部分，包括依赖项（例如，库）的影响。
第一个观察结果的解决方案广为人知——在假设知道程序的大部分时间花在哪里之前，应该严格地分析程序。我特意说“严格地分析”，因为人们经常将“我已经分析过一次程序”与“我已经建立了程序在各种情况下的良好性能模型”相混淆。有时，快速分析就足够了，但它也可能产生误导。通常，有必要使用不同的输入、有时在不同的机器或网络配置上分析程序，并使用各种采样和非采样方法1。
但是，我认为，对于第二个观察结果的多种解决方案及其不可避免的权衡，人们认识不足。我倾向于认为有四种主要解决方案：
- 使用更好的算法。
- 使用更好的数据结构。
- 使用更底层的系统。
- 接受不太精确的解决方案。
在这篇文章的其余部分，我将介绍其中的每一个，并为涉及的权衡提供一些建议。
使用更好的算法
让我们假设——而且我真的见过这种情况！——在仔细分析了一个 Python 程序之后，我发现我的大部分时间都花在如下所示的函数中：
def f1(l):
while True:
c = False
for i in range(0, len(l) - 1):
if l[i+1] < l[i]:
t = l[i]
l[i] = l[i+1]
l[i+1] = t
c = True
if not c: return l
这是一个 bubble sort（冒泡排序）！在这一点上，很多人都会开始嘲笑，因为这显然是一种排序元素的慢方法。但是，冒泡排序相对于许多“更好”的算法来说，有一个经常被遗忘的优势：它以恒定的内存运行2。我可以赌我的程序不需要使用恒定的内存，但如果我不确定，我可以选择另一种保持此属性的算法。让我们尝试一下 selection sort（选择排序）：
def f2(l):
for i in range(0, len(l) - 1):
m = i
for j in range(i + 1, len(l)):
if l[j] < l[m]: m = j
if m != i:
t = l[i]
l[i] = l[m]
l[m] = t
return l
如果我使用这个快速测试代码：
import random, time
l = [random.random() for _ in range(1000)]
before = time.time()
l1 = f1(l[:])
print(time.time() - before)
before = time.time()
l2 = f2(l[:])
print(time.time() - before)
并在 Linux 服务器上的 CPython 3.11 上运行它，我始终得到如下的时间：
0.0643463134765625
0.020025014877319336
换句话说，在我的测试中，选择排序比冒泡排序快大约三倍。
你不需要我告诉你选择排序不是最快的排序算法，但是“最快”是一个比它最初看起来更难捉摸的概念。例如，上面的选择排序算法对于随机数据来说比冒泡排序更快，但是冒泡排序对于排序的数据来说要快得多3。输入和算法性能之间的关系可能很微妙。众所周知，如果在实现 quicksort（快速排序）时选择了一个不幸的“pivot”（轴心），你会发现它非常不快速（例如，你可以使它在已经排序的数据上像上面的选择排序一样慢）。
我们可以从中概括出“使用更好的算法”需要理解你的系统的更广泛的上下文和你正在考虑使用的算法的性质。例如，我经常看到人们混淆算法的最佳情况、平均情况和最坏情况性能——但是当我在优化程序时，这三个信息之间的差异可能至关重要。有时我可能对我的程序有所了解（例如，输入的性质），这使我有信心最坏情况不会发生，或者我不认为最坏情况是一个问题（例如，它是一个批处理作业，没有人会注意到偶尔的延迟）。但是，一般来说，我更关心最坏情况而不是最佳情况，因此我相应地选择算法。
算法具有良好的理论性能但实际性能较差的情况也很常见（大 O 符号可以隐藏许多罪恶）。如果有疑问，我会尝试逐渐增加测试数据，直到我确信我真正理解了不同选择的实际后果。
也很容易忽略复杂性。从根本上说，更快的算法之所以更快，是因为它们观察到计算中的某些步骤可以绕过。我仍然记得第一次阅读 description for timsort：其算法观察的美妙之处一直伴随着我。但是验证这些观察结果比我们想象的要困难——即使是 timsort，由我遇到过的最伟大的程序员之一创建的，也存在一个微妙的错误4。
当我们凡人实现更快的算法时，它们通常会稍微不正确，特别是在新实现时，要么产生错误的结果，要么不具有预期的性能特征5。例如，并行化一个算法通常会导致巨大的加速，特别是随着 CPU 获得更多的内核，但是我们有多少人对 C11 内存模型有足够的了解，能够确信并行化的后果？
(不)正确性和理解算法快速运行的上下文的困难相结合意味着我经常鼓励人们从一个简单的算法开始，并且只有在他们真正发现需要时才转移到“更快”的东西。为手头的任务挑选（并在必要时实现）正确的算法是一项非常困难的技能！
使用更好的数据结构
让我们假设我分析了另一个程序，发现我的大部分时间都花在以下函数中：
def f3(l, e):
for x in l:
if x == e: return True
return False
这是一个存在性检查函数！优化这些函数可能非常有趣，因为我的选择将取决于传递给此函数的列表的使用方式。例如，我可以将列表更改为二叉树。但是，如果我可以判断出（正如不少见的那样）我们重复检查列表中元素的存在，该列表在初始创建后永远不会发生变异，我可能会使用一个非常简单的数据结构：一个排序的列表。这听起来可能很奇怪，因为“排序列表”听起来不太像数据结构，但这允许我进行 binary search（二分查找）。对于任何但最小的列表6，二分查找比上面的线性查找快得多。
正如“使用更好的算法”一样，“使用更好的数据结构”需要仔细的思考和测量7。总的来说，虽然我经常发现有必要实现我自己的“更好的算法”，但我很少发现有必要实现我自己的“更好的数据结构”。部分原因是我的懒惰，但主要是因为数据结构比更好的算法更容易打包在库中8。
“更好的数据结构”有一个重要的战术变体，也许最好将其视为“让你的 structs/classes 减肥”。如果一个程序分配了大量的给定 struct/class，那么该 struct/class 的大小（以字节为单位）本身可能会成为一个重要的成本。当我在 error recovery in grmtools 中工作时，我发现简单地将最常分配的 struct 的大小减少 8 个字节就将整个程序性能提高了 5%——我记得我重复了两次这个技巧！
有很多类似这样的策略，例如减少“指针追逐”（通常通过将多个 struct/class 折叠成一个）、鼓励内存局部性等等。然而，虽然很容易测量 struct/class 的大小以及它被分配的频率，但很难衡量诸如内存局部性之类的事物的间接影响——我听说过将这些因素归咎于糟糕的性能，但我看到这些因素被证明是造成糟糕性能的原因的情况要少得多。总的来说，我只有在变得绝望时才会关注这些因素。
使用更底层的系统
一个历史悠久的传统是用更底层的编程语言重写程序的一部分。让我们将我们的 Python 冒泡排序重写为 Rust：
use std::cmp::PartialOrd;
fn f1<T: Copy + PartialOrd>(l: &mut Vec<T>) {
loop {
let mut c = false;
for i in 0..l.len() - 1 {
if l[i + 1] < l[i] {
let t = l[i];
l[i] = l[i + 1];
l[i + 1] = t;
c = true;
}
}
if !c {
return;
}
}
}
我稍微采用了我之前的 Python 程序来保存 1000 个随机浮点数，并在 Rust 中添加了以下测试代码：
use {env::args, fs::read_to_string, time::Instant};
fn main() {
let mut l = read_to_string(args().nth(1).unwrap())
.unwrap()
.lines()
.map(|x| x.parse::().unwrap())
.collect::>();
let before = Instant::now();
f1(&mut l);
println!("{}", (Instant::now() - before).as_secs_f64());
}
我的 Rust 冒泡排序在 0.001 秒内运行，比 Python 版本快大约 60 倍。这看起来是“用更底层的编程语言重写”的巨大成功——但你可能已经注意到我将本节的标题命名为“使用更底层的系统”。
与其花费 15 分钟编写 Rust 代码，不如更聪明地认识到我的 Python 冒泡排序可能会强调 CPython（Python 最常见的实现）的弱点。特别是，CPython 会将我概念上认为的浮点数列表表示为指向单独堆分配的 Python 对象的指针数组。这种表示具有通用性的优点，但不具有效率。
虽然经常被遗忘，但 CPython 并不是 Python 的唯一实现。其中的替代方案包括 PyPy，它恰好 represent lists of floats as efficiently as Rust。简单地输入 pypy 而不是 python 就可以将我的冒泡排序速度提高 4 倍！我几乎没有什么改变能给我带来如此大的性能提升，而且付出的努力如此之少。这并不是说 PyPy 运行我的程序的速度与 Rust 一样快（PyPy 仍然慢大约 15 倍），但它可能足够快，这才是真正重要的。
我见过多个组织犯了通过用更底层的编程语言重写他们的软件来解决性能问题的错误，而他们本可以通过弄清楚如何更快地运行他们现有的软件来获得足够的好处。通常，人们可以在这里做多件事，从使用不同的语言实现到检查你是否已打开编译器优化9，到使用更快的库或数据库等等。有时用更底层的编程语言重写确实是正确的事情，但这很少是一项快速的工作，并且不可避免地会引入一个不稳定时期，同时将错误从新版本中抖掉。
接受不太精确的解决方案
我们面临的一个常见问题是我们有 n 个元素的某种东西，我们想要了解最适合我们情况的子集或排序。让我们假设我已经实现了一个编译器和 30 个单独的优化过程。我知道如果某些优化过程在其他优化过程之后运行会更有效，但我不知道所有过程的最有效排序是什么。
我可以编写一个程序来枚举这 30 个过程的所有排列，针对我拥有的基准套件运行它们，然后选择最快的排列。但是，如果我的基准套件需要 1 秒才能运行，那么评估所有可能性大约需要 2.82 亿年——这比当前宇宙的年龄要长得多。显然，我不能等那么久才能得到答案：我只能运行所有排列的子集。在这种情况下，我必须接受我永远无法确定什么是最佳答案：但是，至少我可以确保最终得到的答案比什么都不尝试要好。
有多种方法可以解决这个问题，但大多数都归结为 local search（局部搜索）。本质上，我们定义一个度量标准（在我们的运行示例中，我们的基准套件运行的速度有多快）允许我们比较两个解决方案（在我们的例子中，更快更好）并丢弃最差的解决方案。然后，我们需要一种为我们已经拥有的解决方案生成邻居解决方案的方法，此时我们重新计算指标并丢弃旧解决方案和新解决方案中较差的解决方案。在固定时间限制之后，或者如果我们找不到可以提高我们指标的解决方案，我们返回我们找到的最佳解决方案。这种简单技术（核心算法是几行代码）的有效性往往会让新手感到震惊，因为 local optima（局部最优）的明显问题似乎应该破坏整个想法。
正如我上面概述的那样，通常实现的局部搜索会产生正确的但可能非最优的解决方案。然而，有时，我们准备接受一个不太精确的答案，因为它是可能“不正确”的。通过这种方式，我的意思不是程序存在错误，而是程序可能会故意产生与我们认为的“完整和正确的”答案不完全匹配的输出。
“正确”的含义因情况而异。例如，fast inverse square root（快速逆平方根）近似于乘法逆：对于诸如游戏之类的场景，其快速但几乎正确的答案比缓慢但肯定正确的答案更好。Bloom filter（布隆过滤器）可以给出误报：接受这种可能性使其在内存使用方面异常节俭。JPEG 图像压缩故意丢弃图像的一些精细细节，以使图像更易于压缩。与其他图像压缩方法不同，我无法从 JPEG 中完美地恢复原始图像，但通过放弃一点图像质量，我最终得到要传输的小得多的文件。
我认为，总的来说，大多数程序员都很难接受有时可以权衡正确性——就个人而言，这违背了我内心深信程序应该是正确的信念。可能因为这个原因，我认为这种技术的使用频率低于应有的水平。
然而，最近，由于 ML（机器学习）的爆炸式增长，我们变得更加愿意接受不正确的答案。虽然局部搜索要求我们明确说明如何创建新的解决方案，但 ML 是根据以前的数据训练的，然后从该数据生成新的解决方案。这可能是一种非常强大的技术，但 ML 不可避免的“幻觉”实际上只是一种不正确的形式。
因此，我们可以看到接受不精确解决方案有两种不同的方式：可能非最优；以及可能不正确。我开始意识到很多人认为它们是同一件事，但可能的不正确性更经常导致问题。我可能很乐意为了更好的压缩而牺牲一点图像质量，但是如果一个 ML 系统重写了我的代码并遗漏了一个“not”（非），我会很不高兴。我的经验法则是，除非你确信你可以容忍不正确性，否则最好假设你不能。
总结
我上面列出了四种优化方法，按照我看到它们的使用频率（从最常用到最少用）排列。
你可能不会感到惊讶，我最不喜欢的优化方法是“用更底层的编程语言重写”，因为它往往提供最差的改进/成本比率。这并不意味着它总是错误的方法，但我们倾向于在充分考虑更便宜的替代方案之前就使用它。相比之下，我认为直到最近我们才很少使用“接受不太精确的解决方案”，尽管 ML 的爆炸式增长已经迅速改变了这一点。
就个人而言，当我想优化程序时，我倾向于首先使用最简单的技巧。我发现令人惊讶的一件事是，我第一次尝试优化通常是寻找使用哈希图的地方——我很少去寻找要使用的奇异数据结构。我很少转向聪明的算法。在我自己实现的那些聪明算法中，我怀疑二分查找是我最常用的算法，而且我可能最多每年使用一两次——每次我实现它时，我都必须查找正确的做法10！
最终，在撰写完这篇文章后，我开始意识到有三个教训贯穿了所有方法。
首先，当可以牺牲正确性来换取性能时，这是一种强大的技术——但我们经常在无意中牺牲正确性来换取性能。当我们需要优化程序时，最好使用能够给我们想要性能的最不复杂的优化，因为这可能会引入最少的错误。
其次，人类时间很重要。因为我们程序员非常喜欢复杂性，所以我们很可能会过早地使用复杂的优化。即使他们成功地提高了性能——但他们通常不会！——他们往往会比我们需要的性能改进花费更多的时间。
第三，我认为优化知识的广度比优化知识的深度更重要。在我在这篇文章中列出的每种方法中，我都有一些我经常使用的技巧。即使我不知道具体细节，这也有助于我对当前性能问题最合适的总体方法有一个合理的直觉。
致谢： 感谢 Carl Friedrich Bolz-Tereick 和 Jake Hughes 的评论。
**更新（2023-11-14）：**我对 Bloom filter 的原始措辞可以以一种似乎是矛盾的方式阅读。我已经调整了措辞以避免这种情况。