在有符号32位除法上击败编译器

# 在有符号 32 位除法上胜过编译器 来源：https://lemire.me/blog/2026/10/31/beating-the-compiler-at-signed-32-bit-division/ 在我们的处理器上，整数除法很慢。32 位除法的开销如下： | 处理器 | 延迟 | 吞吐量 | | --- | --- | --- | | Emerald Rapids | 约 12 个周期 | 每 6 个周期一次 | | Zen 4 | 9 到 12 个周期 | 每 6 个周期一次 | | Zen 5 | 10 到 13 个周期 | 每 6 个周期一次 | | Arrow Lake 性能核 | 12 个周期 | 每 6 个周期一次 | | Apple M4 性能核 | 7 个周期 | 每 2 个周期一次 | 在 Zen 4 和 Zen 5 上，延迟取决于输入。x86 那几行对应的是 `idiv`（[uops.info](https://uops.info/html-instr/IDIV_R32.html)）。Apple 那一行对应的是 `sdiv`（[测量数据](https://jia.je/hardware/2025/05/21/apple-m4/)）。 一次乘法的延迟是 3 个周期。Emerald Rapids 每周期可以做一次乘法。Zen 5 和 Arrow Lake 每周期可以做三次 64 位乘法（[uops.info](https://uops.info/html-instr/IMUL_R64_R64.html)）。 值得庆幸的是，当除数是常量时，编译器会把除法替换为乘法加移位（Granlund 和 Montgomery，1994 年）。除以 7 就相当于乘以 1/7。在整数运算中，我们乘以一个接近 2^s/7 的整数 *c*，再通过右移除以 2^s。我们能做得比编译器更好吗？在 64 位系统上处理有符号 32 位整数时，往往可以。 ## 编译器的做法 让我们把一个有符号 32 位整数除以 7： ``` int32_t div7(int32_t x) { return x / 7; } ``` GCC 14 在 x64 处理器上生成如下代码： ``` movsx rax, edi imul rax, rax, -1840700269 shr rax, 32 add eax, edi sar edi, 31 sar eax, 2 sub eax, edi ret ``` 它乘以一个 32 位常量，保留最高的 32 位，然后把 *x* 加回去（`add eax, edi`）。接着做移位。指令 `sar edi, 31` 和 `sub eax, edi` 在 *x* 为负数时会加 1，使结果按 C 语言的要求向零取整。 为什么要加回 *x*？7 对应的理想乘数是 2454267027，需要 33 位，无法放入有符号 32 位整数。所以编译器存储 2454267027 − 2³² = −1840700269，并通过加回 *x* 来修正结果。 这并不少见：在 3 到 1000 之间的除数中（排除 2 的幂），有 38% 需要这种修正（990 个中有 376 个）。在这个范围内，GCC 和 LLVM 选择的乘数相同，都遵循 Henry S. Warren, Jr. 的整数与位运算小算法书《Hacker's Delight》。 ## 33 位乘数 但我们用的是 64 位处理器！把 32 位整数乘以 33 位整数，最多可以得到 65 位……但这里说的是*有符号*整数。有符号 32 位整数的绝对值最大为 2³¹。我们的乘数作为有符号数需要 33 位，但它小于 2³²：作为*无符号*数可以放进 32 位。因此乘积的绝对值小于 2⁶³，可以放进有符号 64 位整数。 我们需要选择乘数。在与 Colin Bartlett 和 Owen Kaser 合作的论文《[Integer division by constants: optimal bounds](https://arxiv.org/abs/2012.12369)》中，我们证明了（定理 1）：对所有 [0, N] 区间内的整数 *n*，⌊*c·n/m*⌋ = ⌊*n/d*⌋ 当且仅当 $$\frac{1}{d} \leq \frac{c}{m} < \left(1 + \frac{1}{N - ((N+1) \bmod d)}\right) \cdot \frac{1}{d}$$ 我们取 *m* = 2^s，即满足 *m* ≥ *d*·2³¹ 的最小 2 的幂，并向上取整：*c* = ⌈*m/d*⌉。于是 *c·d* − *m* < 2^s。 ``` template <int32_t d> int32_t div32(int32_t x) { constexpr int s = 31 + std::bit_width(uint32_t(d - 1)); // 31 + ceiling(log2(d)) constexpr int64_t c = (int64_t(1) << s) / d + 1; // ceiling(2^s / d) // floor(c * x / 2^s)，x 为负时加一 return int32_t((int64_t(x) * c) >> s) - (x >> 31); } ``` 我假设除数为正且不是 2 的幂。GCC 14 把 `div32<7>` 编译为： ``` movsx rax, edi mov edx, 2454267027 shr edi, 31 imul rax, rdx sar rax, 34 add eax, edi ret ``` 乘法之后没有修正步骤。最长的依赖指令链现在是 `movsx`、`imul`、`sar`、`add`，而不是 `movsx`、`imul`、`shr`、`add`、`sar`、`sub`。这个常量作为*无符号*值可以放进 32 位，因此加载它很便宜。 在 ARM（Apple M4）上，编译器给出的是： ``` _compiler_div7: mov w8, #9363 movk w8, #37449, lsl #16 smull x8, w0, w8 lsr x8, x8, #32 add w8, w8, w0 asr w9, w8, #2 add w0, w9, w8, lsr #31 ret ``` 而新方法给出的是： ``` _div32_7: sxtw x8, w0 mov w9, #9363 movk w9, #37449, lsl #16 mul x8, x8, x9 asr x8, x8, #34 add w0, w8, w0, lsr #31 ret ``` 为什么编译器不这样做？我不知道。 ## 性能 我对 16384 个随机有符号整数做除法。在*吞吐量*测试中，各次除法相互独立。在*延迟*测试中，每次除法依赖于前一次。延迟中包含两个周期的开销（用于让每次除法依赖于前一次）。我禁用了自动向量化。我使用的平台是 Intel Xeon Gold 6548N（Emerald Rapids）搭配 GCC 14 和 clang 21，以及 Apple M4 Max 搭配 Apple clang 17。 *Intel，每次除法的周期数：吞吐量（延迟）* | 除数 | Intel 上的延迟（周期） | GCC: x / d | GCC: div32 | clang: x / d | clang: div32 | | --- | --- | --- | --- | --- | --- | | 7 | | 2.0（10.0） | 2.0（8.0） | 1.76（10.4） | 1.38（8.0） | | 60 | | 2.0（10.0） | 2.0（8.0） | 1.76（10.4） | 1.38（8.0） | | 365 | | 2.0（10.0） | 2.0（8.0） | 1.76（10.6） | 1.38（8.0） | | 1000 | | 2.0（8.0） | 2.0（8.0） | 1.35（8.0） | 1.38（8.0） | *Apple M4，每次除法的纳秒数：吞吐量（延迟）* | 除数 | x / d | div32 | | --- | --- | --- | | 7 | 0.34（2.01） | 0.29（1.77） | | 60 | 0.31（2.00） | 0.27（1.77） | | 365 | 0.34（2.00） | 0.28（1.77） | | 1000 | 0.29（1.57） | 0.27（1.77） | 对于 7、60 和 365，使用 GCC 时延迟降低了 2 个周期（从 10 降到 8），使用 clang 时从 10.4 或 10.6 降到 8。在 M4 上降低了 12%。在 Intel 处理器上使用 clang 时，吞吐量提升了 20% 以上。使用 GCC 时，在我的基准测试中吞吐量没有变化。 除数 1000 是对照组。编译器的乘数是 274877907，可以放进有符号 32 位寄存器，因此不需要加回任何东西。在 Intel 处理器上两个版本都耗时 8 个周期。两者都以 `movsx` 开头，然后是一次乘法、一次移位和一次加法或减法。在 M4 上，`div32` 略慢：1.77 ns 对比 1.57 ns。编译器的乘数可以放进有符号 32 位寄存器，所以它使用 `smull`，在乘法过程中对 *x* 做符号扩展。我们的乘数（2199023256）放不进有符号 32 位寄存器，因此乘法前需要一条单独的 `sxtw` 指令。所以，只在编译器需要修正步骤时才应该使用 `div32`。 ## 当除数不是常量时 当除数只在运行时已知时，编译器无能为力，只能发出除法指令。多年前，我写了一个小型库 [fastmod](https://github.com/lemire/fastmod)，它预先计算一个 64 位乘数 *M*（约为 2⁶⁴/|*d*|），之后用乘法来做除法。它在《[Faster Remainder by Direct Computation](https://arxiv.org/abs/1902.01961)》（*Software: Practice and Experience*, 2019）中有描述。它的有符号除法函数把 *M* 当作无符号整数。无符号 64 位整数乘以有符号整数时，如果该有符号整数为负，就需要修正。0.1.0 版本的代码根据 *x* 的符号分支。在 x64 上，编译器保留了这个分支。当符号随机时，它经常被预测失败：在我的测试中，36% 到 48% 的除法会发生分支预测失败。 同样的观察成立：*x* 的绝对值最大为 2³¹，只要 |*d*| > 2，*M* 就小于 2⁶³。所以一次*有符号* 64 位乘法可以直接得到正确答案。当 |*d*| = 2 时，我们把 *x* 加回去。新函数没有分支： ``` int32_t fastdiv_s32(int32_t a, uint64_t M, int32_t d) { int64_t signed_M = (int64_t)M; int64_t highbits = mul128_s64_hi(a, signed_M) + (a & (signed_M >> 63)); // 向零取整：a < 0 时加一。 int32_t q = (int32_t)highbits + (a < 0 ? 1 : 0); // d < 0 时取反。 int32_t sign_d = d >> 31; return (q ^ sign_d) - sign_d; } ``` 函数 `mul128_s64_hi` 返回两个有符号 64 位整数乘积的最高 64 位：它编译为单条指令（x64 上是 `imul`，ARM 上是 `smulh`）。值 `signed_M >> 63` 除了 |*d*| = 2 的情况外都是零；它只依赖于除数，所以编译器可以在循环外计算一次。 我把这个改动作为 [fastmod 0.2.0](https://github.com/lemire/fastmod/releases/tag/v0.2.0) 发布。 以下是除数（7）通过命令行传入、符号随机时的结果。我报告的是每次除法的纳秒数：吞吐量（延迟）。 | 系统 | 除法指令 | fastmod 0.1.0 | fastmod 0.2.0 | | --- | --- | --- | --- | | Intel, GCC 14 | 1.72（4.0） | 3.07（4.2） | 0.77（3.2） | | Intel, clang 21 | 1.72（4.0） | 3.42（3.4） | 0.78（2.9） | | Apple M4 | 0.44（2.2） | 0.39（2.0） | 0.38（2.0） | 除数仅在运行时已知时的延迟（纳秒） 在 Intel 处理器上，由于随机符号下的分支预测失败，该库的旧版本比除法指令*更慢*。新版本比旧版本快四倍，比除法指令快两倍以上。在 Apple M4 上，旧版本没有分支（编译器计算了两种情况并选择其一），所以标量代码中差别不大。不过，没有分支后，clang 可以部分向量化调用新函数的循环：如果允许自动向量化，新版本在 M4 上只需 0.22 ns。 ## 结论 在 64 位处理器上做有符号 32 位整数除法时，有一个空闲的位。编译器没有利用它。对于超过三分之一的除数，我们可以消除关键路径上的两条指令；而在一个使用运行时除数的库中，我们可以消除一个分支。 这次探索源于 Ben Joffe 最近关于[常量快速向下取整除法](https://www.benjoffe.com/fast-floordiv)的文章，你值得一读。我的源代码在[这里](https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/2026/10/signeddiv)。 **参考文献** - Daniel Lemire, Colin Bartlett, Owen Kaser, *Integer division by constants: optimal bounds* (https://arxiv.org/abs/2012.12369), Heliyon 7 (6), 2021. - Daniel Lemire, Owen Kaser, Nathan Kurz, *Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries* (https://arxiv.org/abs/1902.01961), Software: Practice and Experience 49 (6), 2019. - Torbjörn Granlund, Peter L. Montgomery, *Division by invariant integers using multiplication*, PLDI 1994. - Henry S. Warren, Jr., *Hacker's Delight*, 第 2 版, 2013.