第五种优化方式：关于 Parallelisation 的思考

The Fifth Kind of Optimisation

Source | HN Comments

文章讨论了并行化作为一种重要的优化方式，作者反思了之前文章中未提及并行化的原因。文章首先通过网站构建器的例子说明了并行化带来的效率提升。接着，作者分析了并行化的优势，尤其是在测试框架中的应用。文章深入探讨了并行化的技术挑战，包括硬件和编程语言的限制，以及多线程编程中遇到的问题，例如数据竞争和编译器优化带来的复杂性。最后，作者推荐了 Rust 语言，因为它通过 `Send` 和 `Sync` 特征以及所有权规则，使得多线程编程变得相对容易和安全。

Home > Blog ≡ Home> Blog | email Bluesky Mastodon Twitter Bluesky Twitter
---|---

第五种优化方式：关于 Parallelisation 的思考

RSS feed: whole site or just the blog

前不久，我写了一篇文章，总结了我认为的四种主要的优化方式：

使用更好的算法。
使用更好的数据结构。
使用更底层的系统。
接受精度较低的解决方案。

就像有 10 个“第五位披头士乐队成员”一样，我还可以添加许多其他的优化方式，但我只想专注于我的经验表明的主要竞争者。特别是，我收到了关于“接受精度较低的解决方案”的一些反对意见，但我认为过去 18 个月 LLM 的发展已经最终表明，在很多情况下，这种优化方式都是适用的。

然而，这并不能为我忽略了一种技术的事实开脱，即使在我写那篇文章时，我也经常使用它：

使用 Parallelisation。

这篇文章不仅仅是一篇 mea culpa （我的过失），而是试图为我的愚蠢行为提供一些回顾性的理由。

Parallelisation 真的有用吗？

几年前，当我将这个网站迁移到一个基于 Rust 的 markdown 系统时，我的软件最初一次只处理一个页面。令人恼火的是，我经常会保存一个页面，这会自动重建网站，切换到我的浏览器，按下刷新，然后发现……什么都没有改变。在我网站在后台重建完成之前，我已经完成了所有这些操作，这让我非常困惑！

快速测量显示，以“快速”模式重建网站大约需要 0.6 秒。不幸的是，性能分析并没有显示任何我可以尝试优化的突出热点。

幸运的是，我有一个秘诀：我让我的网站构建器使用多线程并行处理页面。 “快速”构建时间缩短了一半以上（低于 0.3 秒），突然之间，我无法在网站重建完成之前刷新我的浏览器了。多线程的好处更多地体现在“deploy”模式下——你目前正在阅读的输出——速度提高了 3 倍以上。

使用多个线程来并行化我的网站构建器并不是为了提高性能而提高性能：我从 Parallelisation 中获得的更好的性能提高了我的效率。

事实上，Parallelisation 非常适合某些问题，以至于如果我必须使用非并行化版本，我会感到痛苦。例如，我们都知道测试软件是一件好事——但由于各种原因[1]，测试框架通常会串行运行测试（即一个接一个地运行）。这不仅在计算资源的使用方面效率低下，而且还降低了我们编写尽可能多的测试的可能性，因为我们会开始担心测试套件的执行时间太长。

当我编写 lang_tester 时——一个主要用于测试编译器、VM 等的测试框架——我从一开始就有意让它并行运行测试。我很幸运能够访问一台 72 核的服务器进行开发，并且 lang_tester 的 Parallelisation 使我非常关心的一个测试套件的运行时间从 37 秒缩短到 2.5 秒[2]。速度如此之快，以至于我能够测试即使是很小的更改，而不必担心我的榆木脑袋会偏离我正在解决的问题。

至此，我希望你也同意我的观点，即 Parallelisation 可以是一种强大的优化方式。为什么我没有想到在我的原始博客文章中提到它呢？

我认为，我犯这个错误主要有两个原因：

长时间以来，我们的硬件没有提供足够的 Parallelisation 潜力，使其值得付出太多的努力。如今，价格实惠的台式电脑配备了许多 CPU 核心——我用来撰写这篇文章的机器有 16 个物理核心。按照这种标准，相对经济实惠的服务器开始配备三位数的 CPU 核心数量。
即使我们的硬件确实开始提供足够的 Parallelisation 机会，也很难在我们的编程语言中安全地使用 Parallelisation。

现代硬件中的 Parallelisation 潜力

操作系统长期以来都给人一种并行计算的错觉：多个进程可以在单个 CPU 核心上运行，每个进程在下一个进程轮到之前都会获得一小“片”时间。这是计算领域的一项基础性进步，主要有两个原因：它允许多个人使用一台机器，而无需了解其他用户；当一个程序正在等待外部资源（例如存储或网络）时，另一个程序可以取得进展[3]。

然而，如果你有一个 CPU bound 程序——即一个需要 CPU 做大量工作的程序——那么这些都没有帮助，因为在任何时候都不会并行进行计算。随着时间的推移，这被称为 concurrency，以明确[4]“parallelism”是一种错觉：CPU 只是频繁地在不同的计算之间切换，根据需要暂停和恢复它们。

就本文而言，我们将说只有当 CPU 有多个 cores [5] 可以同时执行两个或多个独立计算[6]时，才会发生“真正的”并行性[7]。

长期以来，拥有多个 CPU/CPU 核心的计算机都是奇异的珍品。消费级多核 CPU 相对较新（大约在 2005 年），并且在它们刚出现时，有点让人失望。我记得我得到一个 2 核 CPU，并且意识到虽然它让我的操作系统运行得更快——我的 Web 浏览器可以在我的编译器在终端中运行时渲染一个页面——但没有单个程序从中直接受益。因此，我认为这种“操作系统 Parallelisation”是我们将从多核中受益的主要方式。

这种 Parallelisation 的问题在于，单个人类很难利用它——它迫使我们进行多任务处理，无休止地在后台启动作业。这会扰乱我们的流程，即使它确实有效地利用了可供我们使用的多个 CPU 核心。某些计算可以拆分为多个进程，但大多数计算不能（任何使用过 Python 的 multiprocessing 模块的人都可以证明）。

显而易见的替代方案是允许 多线程 程序。有必要明确我们所说的“线程”是什么意思，因为随着时间的推移，该术语有不止一种含义[8]。本质上，一个 Unix 进程由一个或多个线程组成。每个线程都是程序的一个半独立的执行：不同的线程可以执行程序的不同部分，每个线程在不同的堆栈上运行；进程中的所有线程共享同一个堆。至关重要的是，线程可以并行执行：一个 n 核 CPU 可以同时执行 n 个线程。

多线程承诺了很多好处，但也带来了很多问题。从硬件的角度来看，编写多线程程序的问题之一是软件不知道硬件给它什么保证，硬件也不确定给软件什么保证。

尽管在 1990 年代初期，在服务器领域中已经探索了许多这些问题，但消费 CPU 必须学习——并且在我理解历史的范围内——扩展这些经验教训。一些后果仍然伴随着我们：最明显的是，x86 具有“强内存模型”，而 Arm 具有“弱内存模型”。我发现这些术语经常被误解，但一个好的直觉是：弱内存模型需要更明确的同步。人们会期望弱内存架构能够表现更好，但缺点是它们更有可能突出由于马虎编程而引起的问题。

x86 和 Arm 之间存在差异并不会让任何人感到惊讶。但是，你可能会更惊讶地发现，即使在 2010 年，AMD 和 Intel 的 x86 内存模型既不彼此兼容，也没有考虑到所有的极端情况。指出前进方向的开创性论文包含这句非常枯燥的句子：

我们回顾了几个最新的 Intel 和 AMD 规范，表明所有规范都包含严重的歧义，有些规范可以说太弱而无法在其之上进行编程，有些规范对于实际硬件而言根本是不合理的。

当它发布时，我并没有真正意识到正在取得的进展：我仍然在阅读关于看似合理的程序在真实 CPU 上无法按预期工作的方式。

我认为直到我拿到一个 8 核[9] CPU（其中第一个仅在 2014 年发布！）时，我才意识到我以前的想法正在变得过时。最明显的是，8 个核心意味着巨大的 Parallelisation 潜力！而且，我逐渐明白，CPU 已经解决了早些时候让我（以及比我了解更多的人）担心的大部分主要问题。

我之所以要讲这段简短的历史课程，是因为像我们中的许多人一样，我现在理所当然地认为多核 CPU 是理所当然的，但值得记住的是：

多核 CPU 的出现是多么的晚。多核 CPU 出现的时间还不到我职业生涯的一半！
多核 CPU 的引入并没有立即导致 可靠的可编程 多核 CPU 的出现。

Parallelisation 和编程语言

至此，让我们假设我们所有人都可以获得可靠、经过深思熟虑且文档齐全的多核 CPU。我们如何让我们的程序利用它们并可靠地做到这一点？尽管有一些可能的方法来编程这些设备，但我将坚持使用多线程作为主要的机会和挑战。

早些时候，我在对多线程的定义中插入了这个短语：“进程中的所有线程共享同一个堆”。事实证明，这是大多数多线程问题的根源。大多数程序中的大多数线程都需要与其他线程通信，这实际上意味着多个线程需要加载和存储到共享堆的同一部分。为了可靠地完成此操作，线程需要同步它们的加载和存储。

乍一看，线程之间的同步似乎并不比普通编程中的共享突变更具挑战性。但是，你越深入研究它，你遇到的惊喜就越多。让我们考虑以下 C 代码：

void inc(long *p) {
  long x = *p;
  x = x + 1;
  *p = x;
}

给定一个指向堆上整数的指针，inc 将从堆中加载一个整数值，将其递增 1，然后将其存储回堆中。

想象一下，两个不同的线程同时调用这个函数，并且都使用相同的指针 P。如果存储在 P 中的整数值最初为 0，我可能会想象这两个并行函数的最终结果是在 P 中存储值 2。但是，如果两个线程同时加载值 0，它们都会将 0 递增到 1，然后将 1（两次！）存储回 P 中。多线程导致我们丢失了一个整数增量！

你越深入研究这个问题，你就会发现同步导致意外情况的方式就越多。如果我在 32 位系统上运行该程序，其中 long 是 64 位，我可能会遇到“撕裂”现象，其中 64 位整数的两个 32 位部分被单独读取和写入，从而产生潜在的随机结果。这不仅仅是 C 等低级语言的问题：我相信 Java 仍然可能发生这种撕裂现象。

丢失的写入和撕裂听起来像是硬件让我们失望了，但另一个例子表明编译器也可能造成混乱。最近，我看到一个程序，省略了不相关的细节，其中包含以下代码段：

bzero(p, 1024);
pthread_exit(0);

目的是在线程退出之前将共享堆的一部分归零。众所周知，另一个线程在调用 pthread_exit 之后很久才能读取该内存。然而，事实证明，无论等待多久，其他线程都没有看到共享内存被归零。

这里的问题是 C 了解一些关于内存同步的信息，并且上面的程序没有通知编译器它想要进行任何形式的“与其他线程同步”写入。编译器意识到这些写入因此隐式地是线程本地的，因此删除了 bzero 调用。换句话说，CPU 在这个看似“不正确的同步”中没有发挥任何作用——这纯粹是一个编译时决策。

为了通知编译器 bzero 不能被编译器删除，需要在 pthread_exit 之前插入对诸如 atomic_signal_fence 之类的指令的显式调用。然而，atomic_signal_fence 不会导致任何运行时操作：bzero 调用不会被删除，但只有当前线程可能“看到”来自 bzero 的写入。如果我们希望其他线程（在某个时候……）获取这些写入，我们需要使用诸如 atomic_thread_fence 之类的指令。

如果此时你感觉到我可以进一步深入细节，那么你是对的：多线程编程很难。存在许多超出非多线程编程的细节；许多意外情况；并且大多数意外情况都是非确定性发生的。这使得调试（从而理解）成为一场噩梦：你可能只在数千次执行中的一次中遇到令人惊讶的结果[10]，并且尝试调试该错误的行为可能会导致它消失！

我的经验是，程序员倾向于将注意力集中在理解硬件的工作原理上。从某种意义上说，这是合理的，但如果你的编程语言被充分地指定，你只需要知道它的同步语义是什么：它应该抽象出不同硬件的差异。

然而，令许多人惊讶的是，在编程语言引入对多线程的支持之后很长一段时间内，它们并没有完全且准确地指定程序在多线程上下文中将如何工作。

Java 从 1995 年开始就支持多线程[11]，但问题开始堆积起来：2004 年的 JSR 133 迈出了一大步。但这还不是结束：发现了更多的问题（例如这个），并进行了更多的调整。

这意味着，多年来，认为他们正在编写正确的程序的多线程 Java 程序员不一定这样做。这不应该被认为是 Java 的轻视：C 直到 2011 年才获得大致相当于 Java 质量的内存模型[12]。

换句话说：在我这样的平民可以购买多核 CPU 之后很多年，我们仍然无法可靠地编程它们，因为我们的语言尚未获得足够的支持来可靠地进行多线程编程。

哪些语言适合多线程编程？

即使编程语言已经解决了所有允许有足够动机和技巧的程序员编写正确的程序的所有细节，我仍然主要选择不这样做。坦率地说，在编写了一些 C 代码来并行化我关心的问题之后，我很快就失去了推理多线程的能力，我发现我降低了它的速度，并引入了当时我根本不理解的错误。

好消息是，其他语言通过主要回避同步问题使多线程编程变得容易。最明显的是，如果你的语言只支持不可变的数据类型，那么许多同步问题（例如前面提到的“丢失写入”问题）根本不会发生。或者，如果你的语言要求其他线程以半隔离的方式运行（例如，许多 actor 语言），其中通信仅涉及不可变的数据类型，那么许多同步问题也会消失。

但是，这两类语言都存在问题：它们可能会使表达某些类型的软件非常尴尬；而且，通常，它们的性能不是很好。冒着冒犯许多人的风险，与 C 相比，你的一般 Haskell 或 Erlang 程序在单线程和多线程上下文中都会慢至少一点，可能很多，并且通常“太慢”。我见过[13]不止一次尝试将单线程 C 程序重写为另一种具有更友好多线程支持的语言，从而导致整体性能更差。

因此，多年来，我一直感到很困扰：我想进行多线程编程；我不相信自己能够编写多线程 C；而且其他对多线程更安全的语言（包括 Java）不适合我所需要的东西。

我不仅开始认为这种令人沮丧的情况是不可避免的，而且我不再将多线程视为解决性能问题的潜在解决方案。

还有其他选择

我在 2014 年底开始编写 Rust 代码，并很快意识到我已经找到了一种非常适合我关心的许多编程任务的语言。当时我没有意识到的是，我也购买了一种能够使多线程编程相当容易、相当安全且非常快速的语言。

长话短说，Rust 中的多线程编程效果很好，因为 (1) Send 和 Sync 特征 (2) 以及 Rust 的正常所有权规则。

Send 表示其实例可以移动（发送）到另一个线程的类型；Sync 表示其实例可以在多个线程之间安全共享的类型。这些特征（大部分）是自动实现的，它们几乎不可能以不正确的方式使用类型：尝试在多线程上下文中对 Rc<T>（既不是 Send 也不是 Sync）执行某些操作，你会收到编译时错误。

我现在已经编写了大量的多线程 Rust 代码，并且我在 C 中会犯（并且确实犯了！）的几个“经典”多线程错误根本没有在 Rust 中发生。值得注意的是，我没有遇到任何数据竞争——一个也没有！这太令人印象深刻了，以至于我很惊讶没有更多的人大声疾呼[14]：我们现在有一种命令式语言，具有良好的性能，即使对于像我这样的非天才，也可以实现可靠的多线程编程！

现在，这并不是说 Rust 中的多线程是完美的。为了使借用检查器感到满意，在将数据移动到线程时，通常需要使用 clone ——这些会以稍微令人沮丧的方式使代码变得混乱。临时生命周期扩展与互斥锁交互不良，并在我的代码中引起了令人困惑的死锁[15]。

Rust 也没有——并且可能主要是不能——保护我免受奇怪的平台差异的影响。例如，我喜欢使用条件变量[16]来避免繁忙轮询，但如果发生暂停/恢复周期，不同的平台会以不同的方式解释“等待超时”。与“正常”编程相比，多线程编程仍然存在更多粗糙的边缘！

总结

长期以来，Parallelism 一直充满希望，但长期以来，在并行编程方面，我们无法依赖硬件或编程语言。我希望我已经解释清楚了为什么我——以及我认为许多其他程序员——因此害怕利用 Parallelisation。

几乎所有这些问题现在都已成为过去——并且最终！——我们开始看到对利用硬件 Parallelisation 潜力的软件的广泛使用。就我个人而言，我现在经常从一开始就考虑如何并行化我的软件。

我希望，尽管我忘记（或愚蠢）地从我的原始文章中遗漏了 Parallelisation，你也会认为它是一种可行的优化工具！

鸣谢：感谢 Davin McCall 的评论。

2025-04-02 11:20 Older

如果你想获得有关新博客文章的更新：请在 Mastodon 或 Twitter 上关注我；或订阅 RSS feed；或订阅电子邮件更新： Failed to subscribe: please load page and try again Sending...

Footnotes

[1] 这些范围从“我的编程语言实现没有正确地进行多线程处理”（例如 CPython）到“我的测试框架没有考虑多线程”再到“我的测试不是线程安全的”。 ☒ 这些范围从“我的编程语言实现没有正确地进行多线程处理”（例如 CPython）到“我的测试框架没有考虑多线程”再到“我的测试不是线程安全的”。 [2] 与 Parallelisation 常见的是，加速与核心数量的比例不是完全线性的。在这种情况下，我无法控制的常数因子很多（例如，设置各种测试），并且这些常数因子往往在短期运行测试中特别明显：测试运行的时间越长，lang_tester 的感知加速就越大。 ☒ 与 Parallelisation 常见的是，加速与核心数量的比例不是完全线性的。在这种情况下，我无法控制的常数因子很多（例如，设置各种测试），并且这些常数因子往往在短期运行测试中特别明显：测试运行的时间越长，lang_tester 的感知加速就越大。 [3] 这种好处被大多数人遗忘了，但我们这些使用过合作式多任务操作系统的人知道这会带来多大的不同。一个不合作的程序是一个巨大的痛苦。 ☒ 这种好处被大多数人遗忘了，但我们这些使用过合作式多任务操作系统的人知道这会带来多大的不同。一个不合作的程序是一个巨大的痛苦。 [4] “清楚”是一个相对的术语。我不觉得“concurrency”与“parallelism”直观地意味着这个，每次使用它们时我都必须仔细思考。 ☒ “清楚”是一个相对的术语。我不觉得“concurrency”与“parallelism”直观地意味着这个，每次使用它们时我都必须仔细思考。 [5] 或者同一主板上的多个 CPU。从这篇文章的角度来看，这是等效的，我将使用“多核”来涵盖这两个变体。 ☒ 或者同一主板上的多个 CPU。从这篇文章的角度来看，这是等效的，我将使用“多核”来涵盖这两个变体。 [6] 与现代单核 CPU 可以在某种程度上并行处理的有点相关的计算不同。 “乱序”执行是一个奇迹，但不是我在这篇文章中要介绍的内容。 ☒ 与现代单核 CPU 可以在某种程度上并行处理的有点相关的计算不同。 “乱序”执行是一个奇迹，但不是我在这篇文章中要介绍的内容。 [7] 我只考虑通用 CPU 内部的 parallelism。我不考虑向量指令、GPU 或其他类似的计算模式：它们确实实现了真正的 parallelism，但属于不同的种类。 ☒ 我只考虑通用 CPU 内部的 parallelism。我不考虑向量指令、GPU 或其他类似的计算模式：它们确实实现了真正的 parallelism，但属于不同的种类。 [8] 例如，“绿色线程”曾经很流行，并且仍然不时出现——即使它们不允许并行计算！最好将它们视为合作式多任务处理的一种形式。 ☒ 例如，“绿色线程”曾经很流行，并且仍然不时出现——即使它们不允许并行计算！最好将它们视为合作式多任务处理的一种形式。 [9] 在历史的这一点上，需要开始区分“物理上不同的”核心和“超线程”。后者将一个物理核心变成两个“虚拟”核心。在早期，超线程的性能优势充其量是微不足道的——有时甚至是负面的！——而且它们更容易受到侧通道攻击。我相信它们的性能优势现在可能为正，但还不够大，以至于我不需要理会它们。 ☒ 在历史的这一点上，需要开始区分“物理上不同的”核心和“超线程”。后者将一个物理核心变成两个“虚拟”核心。在早期，超线程的性能优势充其量是微不足道的——有时甚至是负面的！——而且它们更容易受到侧通道攻击。我相信它们的性能优势现在可能为正，但还不够大，以至于我不需要理会它们。 [10] 更糟糕的是，某些类型的问题只能在某些类型的硬件上发生。特别是，诸如 Arm 之类的弱内存架构可以突出显示在诸如 x64 之类的强内存架构上未被注意到的某些错误。 ☒ 更糟糕的是，某些类型的问题只能在某些类型的硬件上发生。特别是，诸如 Arm 之类的弱内存架构可以突出显示在诸如 x64 之类的强内存架构上未被注意到的某些错误。 [11] 我强烈怀疑这反映了它起源于 Sun，该公司在多核 CPU 在消费设备中可用之前很久就一直在销售具有多个 CPU 的服务器。 ☒ 我强烈怀疑这反映了它起源于 Sun，该公司在多核 CPU 在消费设备中可用之前很久就一直在销售具有多个 CPU 的服务器。 [12] C11 内存模型是大多数其他语言的内存模型语义的基础（例如，Rust 的）。 ☒ C11 内存模型是大多数其他语言的内存模型语义的基础（例如，Rust 的）。 [13] 并听到了一些非常昂贵的故事。 ☒ 并听到了一些非常昂贵的故事。 [14] 令人惊讶的是，我没有看到 Rust 在多线程编程方面的优势像 async 一样经常被提及。我说“令人惊讶”，因为多线程 Rust 不需要学习任何新的语言功能，因此对库没有影响。相反，async 需要学习许多新功能，其中一些功能非常复杂，并且对库有重大影响。async 有一些非常明确的用例，但就我个人而言，我还没有发现需要它们。 ☒ 令人惊讶的是，我没有看到 Rust 在多线程编程方面的优势像 async 一样经常被提及。我说“令人惊讶”，因为多线程 Rust 不需要学习任何新的语言功能，因此对库没有影响。相反，async 需要学习许多新功能，其中一些功能非常复杂，并且对库有重大影响。async 有一些非常明确的用例，但就我个人而言，我还没有发现需要它们。 [15] 虽然这至少在一个月前已部分修复。 ☒ 虽然这至少在一个月前已部分修复。 [16] 令人沮丧的是，条件变量似乎被严重低估了。当我第一次尝试使用它们时，我发现文档——以任何语言！——令人困惑。也许因为这个原因，大量的在线示例都是错误的。我不确定情况是否有所改善，但我怀疑没有。 ☒ 令人沮丧的是，条件变量似乎被严重低估了。当我第一次尝试使用它们时，我发现文档——以任何语言！——令人困惑。也许因为这个原因，大量的在线示例都是错误的。我不确定情况是否有所改善，但我怀疑没有。