数据类型与算术:整数/浮点、除法瓶颈与跳转表

这一类优化编译器替不了你

ch04-02 讲循环优化时,你会发现一大半是「编译器 -O2 替你做了」。这一篇换个角度看算术:有些运算的快慢,取决于你选了什么数据类型、写了什么运算,而选择权在你手里,编译器无能为力,最典型的就是除法。

除法是 x86 上最「贵」的基本整数运算:它的执行延迟相对长(Zen 3 上 idiv 32 位约 9-12 周期、64 位可达 9-17 周期,对比 imul/lea 的 1-3 周期,数据见 Agner《Instruction tables》Zen 3 节;注意是「十几周期」而不是「几十周期」,旧教材里「几十周期」是 Pentium 漫长除法器时代的数字)、吞吐低(每 6-12 周期才能发射一条,除法器稀缺,一条接一条排队),是典型的 ch02-03 讲的结构冒险(structural hazard),多个除法抢同一个除法端口。乘法相反,imul 1 周期、全流水线。能避开除法就避开,是这一篇的核心。

除法瓶颈:5 倍于乘法

我们直接测(本机 Zen 3,taskset -c 0,每元素平均耗时):

===== A. 整数算术成本 =====
  x/8   (除数=2 的幂,编译器换位移): 0.33 ns
  x>>3  (手写位移)                 : 0.38 ns
  x/7   (除数=运行期变量)           : 1.64 ns  ← 除法瓶颈
  x*3   (乘法)                      : 0.33 ns
  除法(变量)/乘法 = 5.0x

三件事读出来:

1. 除数是 2 的幂,编译器替你换位移。x/8 和 x>>3 一样快(都 0.33-0.38 ns),因为 GCC 看出 8 = 2^3,自动编译成 >>3。所以你写 x/8 不用觉得「不优雅」,编译器替你优化了。这条对常量除数也成立,x/10 这种常量除法,编译器会换成「乘以 10 的逆元」(一种用乘法+位移近似除法的技术),不真的做除法。

2. 除数是运行期变量,除法躲不掉,5 倍于乘法。x/d(d 是变量)时编译器没法换成位移或逆元,只能真的执行 idiv 指令。1.64 ns vs 乘法 0.33 ns,5 倍。这就是「除法瓶颈」的硬数字。

3. 实战推论:热路径上,把变量除法换成乘法或位移。常见手法:

• 除数是 2 的幂 → 用位移(或干脆写 /8 让编译器换)。
• 除数虽不是 2 的幂但是常量 → 信任编译器换逆元。
• x % m(取模)和 x / m 一样贵(底层都是除法),取模瓶颈同理。
• 哈希表用「& (size-1)」替代「% size」(前提 size 是 2 的幂),这正是 absl::flat_hash_map、folly::F14 这类现代哈希表把桶数取 2 的幂的原因,省掉一次除法。注意 std::unordered_map 反其道:libstdc++ 实现把桶数取素数(本机实测 reserve(100) 给 103、reserve(1000) 给 1031、reserve(10000) 给 10273,都非 2 的幂),为散列质量宁可付一次真除法,是「散列质量 vs 除法成本」另一面的权衡。

整数 vs 浮点:别凭直觉

很多人以为「浮点比整数慢」,这条在现代 CPU 上基本不成立。Zen 3 有独立的浮点/vector 执行单元,FP 加法和乘法都是全流水线、3-4 周期延迟,和整数加法吞吐相当(甚至 FMA 一条指令做乘加两条的活)。所以:

• 「为了快点把 double 换成 int」通常没用,甚至更慢(精度损失、额外转换)。
• 真正慢的浮点运算是除法、平方根、超越函数(sin/exp):这些延迟几十周期、吞吐低,是浮点里的「除法瓶颈」。
• **subnormal(次正规数)**浮点运算有额外惩罚(Agner 微架构手册有载);-ffast-math 能开 flush-to-zero 关掉这个惩罚,但同样改 FP 语义。

一句话:普通 FP 加乘不慢,慢的是 FP 除法和超越函数。优化重点放在后者。

switch vs if-else:跳转表什么时候真快

最后一个常被误讲的话题。教科书常说 switch 在分支多时会生成跳转表(jump table),O(1) 的查表跳转,比一长串 if-else(平均要走一半分支)快。我们测:

===== B. switch vs if-else 链 =====
  switch:  0.48 ns
  if-else: 0.43 ns
  if-else/switch = 0.90x

if-else 反而略快?先别急着用「跳转表的间接跳转预测器拖后腿」去解释,这正好是 ch00-01 警告的「听起来像解释」的伪因果陷阱。 看 -O2 汇编才知道真发生了什么:配套代码里 switch (x % 8) 的 case 是 0..7(连续)、return 值是 100..107(也连续),GCC 发现这等价于 return 100 + (x & 7),直接折成了几条算术指令,既没生成跳转表、也没保留 if-else 链(g++ -O2 -S 输出里间接跳转 jmp * 数 = 0,跳转表数据也为 0);if-else 版被同样折叠。两段 codegen 几乎逐行相同,所以 0.90× 是测量噪声,不是跳转表的预测代价。

真正的教训正是 ch02-03 那条纪律:分支的开销不取决于语法(switch/if),取决于编译器实际生成了什么、那东西在硬件上好不好预测。想当然地用「跳转表 vs 分支树」解释,正好掉进伪因果。

跳转表什么时候才真出现? 当 case 标号稀疏不连续时(例如 case 1: case 23: case 199: ...),编译器没法折成算术,才会真上跳转表,一张地址表 + 一次间接跳转(jmp *)。间接跳转的目标地址动态,分支预测器确实更难猜;case 数量又多时,跳转表 O(1) 才大胜 if-else 链的 O(n)。所以结论仍是「switch 不一定比 if-else 快」,但原因要落到汇编上看:case 少且连续(本例)折成算术,两者一样;case 多且密集时跳转表大胜;case 稀疏时跳转表仍 O(1) 但间接跳转有预测代价。判断前先 g++ -O2 -S 看一眼。

把这一篇压成几句口诀:除法是 5 倍于乘法的瓶颈(运行期变量除法),除数 2 的幂走位移(编译器常替你做),常量除法编译器换乘法逆元,热路径的变量除法/取模要重写掉;整数和浮点的普通加乘差不多,慢的是 FP 除法/平方根/超越函数;switch 不一定比 if-else 快,本例 case 少且连续被编译器折成算术/branchless,差异是噪声,判断前 -S 看一眼实际 codegen。这一类优化编译器替不了你,选什么数据类型、写什么运算,是你手里的牌。

参考资源

• Agner Fog《Optimizing software in C++》§14 *Optimizing arithmetic》(整数/浮点、乘除、跳转表的指令级成本)。本地
• Agner Fog《Instruction tables》——各指令的延迟/吞吐/µop 分解,案头查证用。本地
• ch02-03 流水线、ILP 与分支预测(本卷,结构冒险与分支预测器)
• 本篇实测代码:code/volumn_codes/vol6-performance/ch04/arithmetic_cost.cpp