当浮点数除法胜过整数除法

# 优化目录：当浮点除法胜过整数除法 来源：https://blog.andr2i.com/posts/2026-06-08-optimization-catalog-when-float-division-beats-integer-division 一个反直觉的热路径优化：用 DIVSD 替换 IDIVQ 来更快地执行整数除法 2026年6月8日 在开发上一个项目时，我做了不少热路径优化，其中一些确实很有意思。所以不妨写几篇相关文章。本系列从这样一个有趣案例开始：用浮点运算替代整数运算，出人意料地实现了加速。 ## 用浮点除法避免 IDIVQ 来看看这个优化（忽略文档注释中提到的 3 倍说法，我搞错了）： ```diff diff --git a/huffman.go b/huffman.go index 33f8263..180dffc 100644 --- a/huffman.go +++ b/huffman.go @@ -378,7 +378,11 @@ func optimizeHuffmanCountsForRLE(counts []uint32, goodForRLEBuf *[]bool) { if i != length { sum += int(counts[i]) if stride >= 4 { - limit = (256*sum + stride/2) / stride + // float64 除法对于可变除数大约快 3 倍，并且对于我们的输入范围（分子 < 2^25， + // 分母 < 2^9，商 < 2^17 —— 所有这些都可以在 float64 的 52 位尾数中精确表示）是精确的。 + limit = int(float64(256*sum+stride/2) / float64(stride)) } if stride == 4 { limit += 120 ``` 这里我将整数除法 `(256*sum + stride/2) / stride` 替换为浮点除法，再将结果转换回整数：`int(float64(256*sum+stride/2) / float64(stride))`。但整数运算不是天生比浮点运算快吗？嗯，是的，但实际上不是。在这个例子中就不成立。 在动手之前，我们先跑一下基准测试，确认优化是否有效（基准测试代码）： ``` goos: linux goarch: amd64 pkg: idivq cpu: 12th Gen Intel(R) Core(TM) i5-12500 │ idivq │ float │ │ sec/op │ sec/op vs base │ DivInline 3.358n ± 0% 2.414n ± 0% -28.10% (p=0.002 n=6) ``` 嗯，确实有效，微基准测试提升了 28%。再在 AMD CPU 上跑一下： ``` goos: linux goarch: amd64 pkg: idivq cpu: AMD Ryzen 5 7535HS with Radeon Graphics │ idivq │ float │ │ sec/op │ sec/op vs base │ DivInline 2.178n ± 0% 1.959n ± 0% -10.08% (p=0.002 n=6) ``` 大约提升了 10%。 那么为什么它会更快呢？我们来比较一下汇编代码： 整数（IDIVQ） | 浮点（DIVSD） --- | --- 计算 `256*sum + stride/2` | 计算 `256*sum + stride/2` ``` SHLQ $8, AX MOVQ BX, CX SHRQ $63, BX LEAQ (BX)(CX*1), DX SARQ $1, DX ADDQ DX, AX ``` ``` SHLQ $8, AX MOVQ BX, CX SHRQ $63, BX LEAQ (CX)(BX*1), DX SARQ $1, DX ADDQ AX, DX ``` ``` TESTQ CX, CX JEQ panicdivide CMPQ CX, $-1 JNE do_div NEGQ AX XORL DX, DX JMP ret ``` 浮点版本缺少除零检查，以及溢出特殊情况 `stride == -1` 的处理。 使用非常昂贵的 `IDIVQ` 指令执行实际除法： ``` CQO IDIVQ CX ``` 使用相对便宜的 `DIVSD` 指令，但增加了一些代码进行 int<-->float 转换： ``` XORPS X0, X0 CVTSQ2SD DX, X0 XORPS X1, X1 CVTSQ2SD CX, X1 DIVSD X1, X0 CVTTSD2SQ X0, AX ``` 关键在于用 `DIVSD` 替代了 `IDIVQ`。根据 uops.info 的数据，`IDIVQ` 的延迟为 14-18，吞吐量为 10 个周期（参见此链接）。而 `DIVSD` 的延迟为 13，吞吐量为 4 个周期（链接）。所以我当时关注的是吞吐量。 为什么是吞吐量而不是延迟？因为在这个微基准测试中，除法是独立的：一个结果不依赖于前一个结果。因此除法单元保持“饱和”，以最快速度接收工作。而速率受限于吞吐量而非延迟。 所以理论上吞吐量应该从 10.0 降到 4.0，这就是为什么我在上面的文档注释里写了“3 倍”（更准确地说应该是 2.5 倍，因为 10/4=2.5）。但实际加速比并不是 2.5 倍，而只有大约 1.4 倍（英特尔平台上 28% 的提升）。这是为什么呢？ 为了回答这个问题，我用 `perf stat` 收集了 `arith.divider_active` 指标。这个指标统计 CPU 除法单元忙的周期数。 | | idivq | float | |---|-------|-------| | arith.divider_active / op | 10.00 cyc | 6.35 cyc | | total cycles / op | 10.03 cyc | 7.29 cyc | perf 显示 `IDIVQ` 花费了 10 个周期，与 uops.info 预测的完全一致（看来选择吞吐量而非延迟是正确的）。注意在这个案例中，总周期只多了 0.03 个周期，说明编译器添加的除零检查和溢出检查的开销可以忽略不计（我原本想问的另一个问题是：加速是否确实是由去除那些检查导致的，而 perf 显示并非如此。加速的真正原因是使用了性能更好的 `DIVSD` 指令）。在浮点（`DIVSD`）案例中，CPU 在除法上花费了 6.35 个周期，而不是我预期的 4.0 个周期。此外，还多花了大约 1 个周期做一些额外工作，使得每操作总周期达到 7.29。难道是 uops.info 错了吗？ 我认为不是。我相当确信 `DIVSD` 的时序与操作数有关： - `6.35` 对 `4` 的差距本身就是一个迹象，因为 uops.info 测量吞吐量时使用的是固定的操作数集。不过对于具体的规则，我没有确切的解释。 ## 注意事项 整数除法和“浮点除法再取整”并不总是等价的。这是因为浮点数在硬件中的表示方式以及舍入的限制。每个不超过 2^53 的整数都可以精确表示为浮点数（超过 2^53 后也有部分整数可表示，但会出现间隙——先是只有偶数，然后只有 4 的倍数，以此类推）。如下文所述，DIVSD 的操作数必须保持在 `<= 2^53` 范围内——超过 2^53 的可表示值并不能帮你解决问题。 再说舍入限制：除法的结果（我们称商为 `q`）是 `q = floor(a/b)`。而 `a/b` 的真实值可能落在区间 `[q, q+1)` 中。问题出现在当 `a/b` 非常接近 `q+1`，以至于硬件无法确定它实际上小于 `q+1` 时。这时，会得到错误的结果 `q+1` 而非正确的 `q`。当 `ulp(q) >= 2/b`（其中 `ulp` 是最后一位的单位）时，`a/b` 就变得与 `q+1` 无法区分。这种情况发生在 `bits(q) + bits(b) > 54`，这迫使 `a ≈ q*b > 2^53`。 因此，当你用 `a` 除以 `b` 时，必须满足以下两个条件： - `a <= 2^53` - `b <= 2^53` 如果满足这些条件，你就可以安全地用 DIVSD 替代 IDIVQ。 ## 总结 所以，这是少数几个“整数运算显然更快”的直觉出错的情况之一：`IDIVQ` 是最昂贵的整数指令之一，而 `DIVSD` 加上 int<-->float 转换反而更快。当然，应用前务必进行基准测试。 哦，对了，忘了提。这种优化仅适用于运行时变量作为除数的情况。如果是编译时常量，编译器已经自动用更好的优化替换了。 ## 更新 这篇文章在 Reddit 上引发了不错的讨论（链接）。一些评论给出了不同优化思路。 u/Masztufa 写道： > 我很好奇 CPU 的超标量特性是否在这些测试中也有所体现。你总是在做整数运算（指针运算），所以自然选择整数运算会加载 CPU 的整数运算单元；而如果在实际数据上使用浮点数，你可以利用更多的硅片来完成工作。 这个评论让我豁然开朗：我意识到可以交错进行整数和浮点除法，让两个单元同时工作，受益于超标量执行（commit）。最佳组合是交错进行 5 次除法：int、int、float、float、float。 --- u/Dwedit 写道： > 整数运算的一个技巧是：预先计算倒数并用乘法来代替会快得多。编译器对常量会自动做这件事，但对变量则不会。`uint32_t reciprocal = (uint32_t)(0x100000000ULL / divisor + 1); // 除数必须大于 1; answer = (number * (uint64_t)reciprocal) >> 32;` 当除数被多次重用时，你可以用一次乘法替代除法。我在这里做了微基准测试，结果表明性能提升与浮点（divsd）优化相当。 u/vip17 提到了 C 语言库 `libdivide`。我找到了 Go 语言的对应库：`github.com/bmkessler/fastdiv`。注意我测试的是 `Uint32` 版本。为了在 64 位范围内保持正确，`Uint64` 版本必须使用 128 位数学运算，因此会执行两次乘法而不是一次。而 `Uint32` 版本只做一次乘法，更接近其他基准测试的优化（代价是将范围限制在 2^32 以下的数字）。 最后，我为每种优化都添加了 5 倍展开版本，以便与我之前提到的交错技巧进行公平比较。commit。 **数据。** 仅包含 5 倍展开的版本： | 方法 | ns / 5x ops | 与 `IDIVQ` 相比 | |------|-------------|-----------------| | `IDIVQ` | 16.81 | — | | int+float 拆分 | 8.316 | -51% | | `fastdiv` | 7.796 | -54% | | 浮点 (`DIVSD`) | 7.391 | -56% | | 倒数乘法 | 6.474 | -61% | 因此，u/Dwedit 建议的倒数乘法在 5 倍展开循环中效果最好。int+float 拆分是一个有趣的技巧，但简单展开其他版本（例如 5 倍 DIVSD）实际上更快。 **那 SIMD 呢？** 由 u/Masztufa 和 u/vip17 提出。我同意 SIMD 会胜过我的 divsd 版本。但在我优化的函数（`optimizeHuffmanCountsForRLE`）中，热循环像一个状态机，难以向量化。循环展开也不适用，所以我只能从非展开版本中挑选最优的。