每个人都应该了解SIMD

# 每个人都该了解 SIMD 来源：https://mitchellh.com/writing/everyone-should-know-simd SIMD（https://en.wikipedia.org/wiki/Single_instruction,_multiple_data）以复杂著称。我遇到过许多非常优秀的软件工程师，他们认为 SIMD 过于复杂而放弃学习，或者认为它只是为最高性能软件准备的极端优化手段，在日常编程中毫无用处。我认为这种看法是错误的。SIMD 可以很容易理解¹（https://mitchellh.com/writing/everyone-should-know-simd#user-content-fn-1），而那种常见的“一次处理 N 个值”的 SIMD 代码用来加速朴素 for 循环时，几乎都遵循同样的通用模式。一旦你掌握了基础，编写 SIMD 就和写 for 循环差不多简单。就算不简单，那也是个好信号，说明暂时跳过它。每个开发者至少应该了解这么多 SIMD。 本文使用 Zig 作为示例，但内容具有普遍性，适用于任何编程语言。不同编程语言对 SIMD 指令的支持各不相同，我希望未来能有更多编程语言暴露这些通用概念！我讨厌每篇文章都要说明，但这里还是提一下：本文完全由手工撰写，未使用任何 AI 辅助。 ## 目录 - 背景：什么是 SIMD？（https://mitchellh.com/writing/everyone-should-know-simd#background-what-is-simd） - 通用模式（https://mitchellh.com/writing/everyone-should-know-simd#the-common-shape） - 一个实际例子（https://mitchellh.com/writing/everyone-should-know-simd#a-real-example） - 步骤 1：广播常量（https://mitchellh.com/writing/everyone-should-know-simd#step-1-broadcast-constants） - 步骤 2：每次循环一个向量（https://mitchellh.com/writing/everyone-should-know-simd#step-2-loop-one-vector-at-a-time） - 步骤 3：执行 SIMD 操作（https://mitchellh.com/writing/everyone-should-know-simd#step-3-perform-the-simd-operation） - 步骤 4：规约向量结果（https://mitchellh.com/writing/everyone-should-know-simd#step-4-reduce-the-vector-result） - 步骤 5：用标量尾处理收尾（https://mitchellh.com/writing/everyone-should-know-simd#step-5-finish-with-the-scalar-tail） - 回顾：通用模式（https://mitchellh.com/writing/everyone-should-know-simd#recap-the-common-shape） - 为什么编译器不能自动做到？（https://mitchellh.com/writing/everyone-should-know-simd#why-cant-the-compiler-do-this） - 每个人都该了解 SIMD（https://mitchellh.com/writing/everyone-should-know-simd#everyone-should-know-simd） ## 背景：什么是 SIMD？ 如果你已经知道什么是 SIMD，可以跳过本节。SIMD（https://en.wikipedia.org/wiki/Single_instruction,_multiple_data）允许 CPU 并行操作多个值。例如，CPU 不再一次比较一个字节，而是可以用一条指令同时比较 4、8 甚至更多个字节。如果你在代码中看到这样的循环： ``` for (byte in bytes) { /* ... */ } for (character in string) { /* ... */ } for (value in array) { /* ... */ } ``` 那么就有机会使用 SIMD。SIMD 把这些循环变成这样： ``` for (8 byte chunk in bytes) { /* ... */ } ``` 这会带来局部的加速，与并行度直接对应：你以 4 倍、8 倍甚至更快的速度处理数据。唯一真正的要求是你需要经常处理足够大量的字节。如果你的 for 循环只在几十个字节的数据上操作，那就没必要。但如果它迭代数百、数千、数百万字节，收益将非常巨大。 基本概念就是这样。像 simdutf（https://github.com/simdutf/simdutf）和 simdjson（https://github.com/simdjson/simdjson）这样的项目将 SIMD 用到了极致，使用了很难理解的技巧。但你并不需要写出那样的算法才能从 SIMD 中受益。常见的情况要简单得多。 ## 通用模式 常见的“一次处理 N 个值”的 SIMD 代码遵循以下五个步骤： 1. 广播所需的任何常量，并初始化向量累加器（如果有的话）。 2. 每次以向量宽度为一块，循环遍历输入。 3. 在所有通道上并行执行比较或算术运算。 4. 按需规约或存储向量结果。 5. 用标量尾处理剩余的元素。 标量尾就是你向量化之前原本的普通循环，但它只处理那些凑不满一个完整向量的剩余部分。当你做多了之后，你会自然地将每个 for 循环分解为这五个步骤，编写 SIMD 也就会像编写标量循环一样自然。 ## 一个实际例子 让我们看一个来自 Ghostty 的实际例子。我们先看标量实现，再看 SIMD 实现，然后将它映射回上面的通用模式。 我有一个解码后的码点切片，我想持续消费直到看到一个值 ≤ `0xF`（C0 控制字符）²（https://mitchellh.com/writing/everyone-should-know-simd#user-content-fn-3）。终端中大部分是待打印的普通字符，所以我们希望一次性批量处理所有普通字符。因此这个循环尽可能快地找到下一个可打印字符运行序列的结尾。 标量循环只有一行： ``` while (end < cps.len and cps[end] > 0xF) end += 1; ``` 它一次处理一个码点。很好理解。 下面是通用的向量版本，没有 CPU 特定的内建函数³（https://mitchellh.com/writing/everyone-should-know-simd#user-content-fn-4），也没有注释。稍后我会详细解释。 ``` if (simd.lanes(u32)) |lanes| { const V = @Vector(lanes, u32); const threshold: V = @splat(0xF); while (end + lanes <= cps.len) : (end += lanes) { const values: V = cps[end..][0..lanes].*; const greater_than_threshold = values > threshold; if (@reduce(.And, greater_than_threshold)) continue; const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold); end += @ctz(~mask); break; } } while (end < cps.len and cps[end] > 0xF) end += 1; ``` 多了 12 行代码。这可以将循环的吞吐量提升高达：ARM NEON（包括 Apple Silicon）上为 4 倍，AVX2（多数现代 x86 CPU）上为 8 倍，AVX-512（部分 Intel CPU 以及 AMD Zen 4 及以上）上为 16 倍。在 AVX2 Intel 台式机上，从终端程序到最终终端状态的端到端实际吞吐量提升更像是 5 倍。你总会因为 SIMD 代码周围的其他因素损失一部分理想加速，但……那仍然是 5 倍！ 好了，我知道对这 12 行代码，不熟悉这些概念的人会觉得很陌生。现在我们回过头来逐步解释，并直接映射到之前提到的通用模式上。 ## 步骤 1：广播常量 我们先看前三行： ``` if (simd.lanes(u32)) |lanes| { const V = @Vector(lanes, u32); const threshold: V = @splat(0xF); ``` `simd.lanes(u32)` 是 Ghostty 中的一个辅助函数，返回目标 CPU 一次能处理的 `u32` 值的数量。这些单独的值被称为**通道**。ARM 上返回 4，AVX2 返回 8，AVX-512 返回 16。如果目标没有我们想用的向量大小，返回 `null`，我们就跳过所有 SIMD 代码，不做任何 SIMD 工作。 `@Vector(lanes, u32)` 创建向量类型。如果 `lanes` 是 8，那么 `V` 就是一个包含八个 `u32` 值的单一类型，CPU 可以并行操作它们。依此类推。 最后，我们需要将每个值与 `0xF` 进行比较。向量比较要求两边都是向量，所以 `@splat(0xF)` 将 `0xF` 复制或**广播**到每个通道中。结果是一个像这样的向量： ``` { 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF } ``` 这就是步骤 1：准备向量类型并广播任何常量。有些算法还会在此处初始化向量累加器，但这个算法不需要。 ## 步骤 2：每次循环一个向量 接下来，我们每次循环处理一个完整的向量： ``` while (end + lanes <= cps.len) : (end += lanes) { const values: V = cps[end..][0..lanes].*; ``` 如果 `lanes` 是 8，我们只有在至少还剩 8 个值时才进入循环。在循环内部，我们把这 8 个值加载到向量 `values` 中。每次循环结束时，`end += lanes` 会向前移动 8 个值而不是 1 个。 需要**完整**向量的前提很重要。如果只剩 5 个值，我们就无法加载一个 8 通道的向量。有很多技巧可以处理这种情况，但这里我们选择简单的做法：通过稍后在步骤 5 中讲到的标量尾来处理它们。 这就是步骤 2：每次以向量宽度为一块加载并循环遍历输入。你在这里就能看到通道数带来的加速！ ## 步骤 3：执行 SIMD 操作 现在执行比较： ``` const greater_than_threshold = values > threshold; ``` `values` 和 `threshold` 都是向量，所以这映射为一次向量操作（一条实际的向量 CPU 指令）。一个 `>` 比较 `values` 中的每个通道与 `threshold` 中对应的通道。如果有 8 个通道，这相当于执行标量比较 `cps[end] > 0xF` 八次，但只需要一条 CPU 指令⁴（https://mitchellh.com/writing/everyone-should-know-simd#user-content-fn-5）。 结果是一个向量，每个通道有一个布尔值。概念上看起来像这样： ``` values: { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 } threshold: { 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF } greater_than_threshold: { true, true, true, false,true, true, true, true } ``` 这就是实际的 SIMD 操作。没有显式的内部循环。`>` 运算符并行应用于每个通道。比较只是其中一个例子。也可以是加法、乘法、最小值、最大值，或向量类型支持的任何其他操作。关键在于代码仍然保持相同的模式。 ## 步骤 4：规约向量结果 现在我们有了一个布尔向量，但原始循环需要知道第一个 ≤ `0xF` 的值的位置。首先，处理最常见的情况：每个值都大于 `0xF`： ``` if (@reduce(.And, greater_than_threshold)) continue; ``` `@reduce(.And, ...)` 使用 `and` 将每个布尔值组合起来并返回一个布尔值。如果每个通道都是 `true`，我们就 `continue`，处理下一个向量。在我们的例子中，通道 3 是 `false`，所以 `@reduce` 返回 `false`，我们继续往下走，找出具体哪个通道失败了。 如果有任何通道是 `false`，我们就得找出具体哪个通道失败了： ``` const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold); end += @ctz(~mask); break; ``` `@bitCast` 将布尔向量转换为一个整数，每个通道对应一位。`1` 位表示值大于 `0xF`，`0` 表示不大于。我们对掩码取反，使失败的比较变成 `1`，然后 `@ctz` 统计第一个失败之前的零位个数。这个计数就是第一个失败通道的索引。我们将该索引加到 `end` 并跳出循环，因为我们已经找到了控制字符。 使用步骤 3 中的相同值，我们可以看到每个通道的这个转换： ``` values: { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 } greater_than_threshold: { true, true, true, false,true, true, true, true } mask: { 1, 1, 1, 0, 1, 1, 1, 1 } ~mask: { 0, 0, 0, 1, 0, 0, 0, 0 } ``` `@ctz(~mask)` 统计第一个 `1` 之前的零位数量是三个，所以返回 `3`。将 `3` 加到 `end` 指向通道 3，其中包含 `0x0A`，即第一个控制字符。 这就是步骤 4：将向量结果规约为原始算法所需的任何形式。这一步也是不同算法之间差异最大的地方。求和可能将向量累加器规约为一个数字。变换可能将整个向量存储到输出缓冲区。我们的扫描将向量转换为位掩码，以便找到某个特定通道。 ## 步骤 5：用标量尾处理收尾 在向量循环之后，我们运行最初的那个标量循环： ``` while (end < cps.len and cps[end] > 0xF) end += 1; ``` 如果输入长度不是向量宽度的整数倍，这个循环处理剩余的值。例如，8 通道向量循环会留下 0 到 7 个值给这个循环。这被称为**标量尾**。 这个循环也处理 `simd.lanes(u32)` 返回 `null` 的 CPU 的情况。在这种情况下，我们跳过所有 SIMD 代码，标量循环处理整个输入。原始实现同时作为后备方案和尾处理。 这就是步骤 5。它仅仅是正常的循环。 ## 回顾：通用模式 让我们将整个实现映射回五个步骤： 1. `@splat(0xF)` 将比较值广播到每个通道。 2. `while` 循环每次加载 `lanes` 个值。 3. `values > threshold` 并行比较每个通道。 4. `@reduce`、`@bitCast` 和 `@ctz` 找到第一个失败的比较。 5. 原始标量循环处理剩余部分和不支持的 CPU。 步骤 4 的细节一开始需要花点时间理解，但总体模式是直接的。而且步骤 1、2、3 和 5 在不同算法中几乎完全相同。每当你看到 `for (byte in bytes)` 时，这就是你要映射到的模式。 ## 为什么编译器不能自动做到？ 有时它可以！编译器可以对简单的循环进行自动向量化（https://llvm.org/docs/Vectorizers.html），特别是那些没有复杂控制流的常规算术循环。你应该始终在开启优化的情况下编译标量版本，并在手动编写 SIMD 之前检查你的编译器产生了什么。但编译器能自动向量化的范围非常有限，而且总体而言非常差。自动向量化是编译器研究领域一个活跃了数十年的课题，而最近的研究（https://arxiv.org/abs/2406.04693）仍然从观察结论开始：生产级编译器经常错过向量化机会。我不认为这个问题会很快消失。 更重要的是，当这个循环重要到让我关心 5 倍加速时，我希望向量化是明确且可预测的。我不希望一个无关的代码更改或编译器更新悄悄地将它变回标量循环。 ## 每个人都该了解 SIMD 每个开发者都应该能识别出这样的机会，最重要的是，**不要害怕 SIMD**。如果你看到一个热循环在扫描、比较、计数或转换大量连续数据，你应该能想象出以向量宽度为一块来处理它。本文展示了这些常见情况遵循一种非常规律的模式，你会很快习惯。而且有了好的语言支持，你不需要知道任何汇编或 CPU 特定的技巧就能获得轻松的改进。每个人都应该了解足够的 SIMD 来做这件事。⁵（https://mitchellh.com/writing/everyone-should-know-simd#user-content-fn-2） 1. 像 simdutf 和 simdjson 这样令人印象深刻的项目使用了极其复杂的 SIMD 技巧来实现目标。但这并非我所说的“日常 SIMD”。↩（https://mitchellh.com/writing/everyone-should-know-simd#user-content-fnref-1） 2. C0 控制字符不仅限于 `0xF`。这是 Ghostty 在此特定代码路径中使用的截止点；ESC 和其他控制序列的处理发生在其他地方。↩（https://mitchellh.com/writing/everyone-should-know-simd#user-content-fnref-3） 3. 通用向量去掉了 CPU 特定的语法，但并未去除 CPU 特定的代码生成。Zig 仍然将这些操作降低到目标架构支持的指令集。当 Ghostty 无法选择合适的向量宽度时，它会回退到标量代码。↩（https://mitchellh.com/writing/everyone-should-know-simd#user-content-fnref-4） 4. 比较本身是一次向量操作。加载向量、规约结果以及定位失败通道需要额外的指令。关键在于我们一次进行了多个比较。↩（https://mitchellh.com/writing/everyone-should-know-simd#user-content-fnref-5） 5. 本文基于我在 Lobsters 上写的一条评论（https://lobste.rs/s/gkcjic/simd_for_collision#c_pwdpep）。↩（https://mitchellh.com/writing/everyone-should-know-simd#user-content-fnref-2）