整数溢出检查成本揭秘：开销几何？编译器表现如何？
整数溢出检查成本揭秘：开销几何？编译器表现如何？
启用整数溢出检查会带来多少额外开销呢？通过编译器标志或内置函数，可利用基于 `add` 和 `sub` 指令设置的溢出标志进行条件分支检查。原本类似 “`add %esi, %edi`” 的代码，会变成 “`add %esi, %edi`” 与 “`jo `”。
假设分支预测总是准确（大多数代码能做到），分支成本包括执行预测正确且未跳转分支的开销、分支在分支历史表中造成的污染，以及解码分支的成本（在 x86 架构中，`jo` 和 `jno` 不会与 `add` 或 `sub` 融合，意味着在快速路径下，分支会占用每个周期从解码指令缓存中取出的 4 个操作码之一）。在前端受限的最坏情况下（可能出现在高度优化的循环中，但总体少见），每个 `add` 或 `sub` 操作的开销可能不到 2 倍，再加上分支历史污染带来的难以在微基准测试中衡量的模糊开销。总体可悲观估计总开销为 2 倍。
2 倍听起来多，但应用程序在加法和减法操作上花费的时间有多少呢？以最常用的 “工作站” 整数工作负载基准测试 [SPECint](http://www.spec.org/cpu2006/) 为例，其操作组成大概是 40% 的加载/存储操作、10% 的分支操作和 50% 的其他操作。在这 50% 的 “其他” 操作中，约 30% 是整数加法/减法操作。假设加载/存储操作的开销是加法/减法操作的 10 倍，其他操作的开销与加法/减法操作相同，那么加法/减法操作开销增加 2 倍会导致整体性能下降 `(40*10 + 10 + 50 + 12) / (40*10 + 10 + 50) = 3%`。这里假设分支开销为 2 倍、加法/减法操作仅比加载/存储操作快 10 倍，以及加法/减法操作不比其他 “其他” 操作快，这些都是比较悲观的假设，所以对于大多数工作负载来说，这个估计应该是偏高的。
John Regehr 对整数溢出检查进行了深入分析，他估计性能下降约为 [5%](http://blog.regehr.org/archives/1154)，这与我们的粗略估算大致相符。
SPEC 许可证售价 800 美元，所以选择对 bzip2（SPECint 的一个组件）进行基准测试，而不是花 800 美元购买 SPECint。使用 `clang -O3`、`clang -O3 -fsanitize=signed-integer-overflow,unsigned-integer-overflow`（溢出时打印警告）和 `-fsanitize-undefined-trap-on-error`（未定义溢出时导致崩溃）这三种方式编译 bzip2，对机器上的 1GB 代码和二进制文件进行压缩和解压缩，得到以下结果：
| 选项 | 压缩时间 (s) | 解压缩时间 (s) | 压缩时间比例 | 解压缩时间比例 |
| --- | --- | --- | --- | --- |
| 正常 | 93 | 45 | 1.0 | 1.0 |
| fsan | 119 | 49 | 1.28 | 1.09 |
| fsan ud | 94 | 45 | 1.01 | 1.00 |
表中的比例是运行时间的相对比例，而非压缩比。`fsan ud` 解压缩和正常解压缩的差异实际上并非为 0，但以整秒为单位测量时会四舍五入为 0。如果启用详细的错误信息，解压缩速度不会减慢太多（从 45 秒变为 49 秒），但压缩速度会明显变慢（从 93 秒变为 119 秒）。如果打印详细诊断信息，整数溢出检查会使压缩性能下降 28%，解压缩性能下降 9%；如果不打印，则几乎没有影响。这是为什么呢？bzip2 通常会有一些无符号整数溢出情况。如果修改代码以消除这些溢出，即使不执行诊断打印代码路径，仍然会导致较大的性能损失。
看看执行类似 “`for (int i = 0; i < n; ++i) { sum += a[i]; }`” 这样的加法操作时的开销。在机器（3.4 GHz 的 Sandy Bridge 架构）上，使用 `-fsanitize=signed-integer-overflow,unsigned-integer-overflow` 编译时，速度大约慢 6 倍。查看反汇编代码，正常版本使用 SSE 加法，而启用检查的版本使用普通加法。对于未检查的 SSE 加法和检查后的加法，慢 6 倍是合理的。
但如果尝试不同的循环排列方式，使编译器无法为未检查版本生成 SSE 指令，使用 fsanitize 编译的版本仍然会有 4 - 6 倍的性能损失。由于涉及多种优化，包括循环展开，来看一个简单的只做一次加法的函数，以更好地了解情况。
下面是一个将两个整数相加的函数的反汇编代码，分别使用 `-O3` 和 `-O3 -fsanitize=signed-integer-overflow,unsigned-integer-overflow` 编译：
```asm
0000000000400530 :
400530: 01 f7 add %esi,%edi
400532: 89 f8 mov %edi,%eax
400534: c3 retq
```
编译器在 `-O3` 版本上表现不错。根据标准的 AMD64 调用约定，参数通过 `esi` 和 `edi` 寄存器传入，结果通过 `eax` 寄存器传出。与内联 `add` 指令相比，这里有一些开销，因为需要将结果移动到 `eax` 寄存器并从函数调用返回，但考虑到这是一个函数调用，这个实现是完全合理的。
```asm
000000000041df90 :
41df90: 53 push %rbx
41df91: 89 fb mov %edi,%ebx
41df93: 01 f3 add %esi,%ebx
41df95: 70 04 jo 41df9b
41df97: 89 d8 mov %ebx,%eax
41df99: 5b pop %rbx
41df9a: c3 retq
41df9b: 89 f8 mov %edi,%eax
41df9d: 89 f1 mov %esi,%ecx
41df9f: bf a0 89 62 00 mov $0x6289a0,%edi
41dfa4: 48 89 c6 mov %rax,%rsi
41dfa7: 48 89 ca mov %rcx,%rdx
41dfaa: e8 91 13 00 00 callq 41f340 <__ubsan_handle_add_overflow>
41dfaf: eb e6 jmp 41df97
```
编译器在 `-O3 -fsanitize=signed-integer-overflow,unsigned-integer-overflow` 版本上的表现不佳。优化专家 Nathan Kurz 对 clang 的输出评价如下：
> 这是糟糕（但并非罕见）的编译器生成代码。出于某种原因，编译器决定使用 %ebx 作为加法的目标寄存器。一旦这样做，就不得不进行后续操作。问题在于为什么它不使用临时寄存器，为什么觉得有必要进行移动操作，以及未来如何避免这种情况。如你所知，%ebx 是一个 “被调用者保存” 寄存器，这意味着函数返回时它的值必须保持不变，因此需要进行压栈和出栈操作。如果编译器直接进行加法操作，不进行额外的移动操作，让输入保持在传入时的 %edi/%esi 寄存器中（就像未检查版本那样），就不需要这些操作了。我猜测这是早期优化阶段的遗留问题，但不知为何 %ebx 的影响仍然存在。
然而，添加 `-fsanitize-undefined-trap-on-error` 后，代码变为：
```asm
0000000000400530 :
400530: 01 f7 add %esi,%edi
400532: 70 03 jo 400537
400534: 89 f8 mov %edi,%eax
400536: c3 retq
400537: 0f 0b ud2
```
虽然这是一个简单的示例，但可以在使用允许 fsanitize 打印诊断信息的选项编译的其他代码中看到各种优化问题。
理论上，更好的 C 编译器可以做得更好，但在这里，gcc 4.82 并不比 clang 3.4 好。一方面，gcc 的 `-ftrapv` 只检查有符号溢出；更糟糕的是，它不起作用，[自 2008 年以来，关于 `-ftrapv` 的这个 bug 一直未修复](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35412)。尽管检查更少且检查不正确，但在 bzip2 上，gcc 的 `-ftrapv` 与 clang 的 `-fsanitize=signed-integer-overflow,unsigned-integer-overflow` 导致的性能下降程度相当，比 `-fsanitize=signed-integer-overflow` 导致的下降程度更大。
综上所述，对于典型的整数密集型工作负载，整数溢出检查应该只会导致百分之几的性能下降，前提是不需要详细的错误信息。目前生成详细错误信息的机制在很多情况下会导致优化出现问题。
更新
在 clang 3.8.0 及更高版本，以及 gcc 5 及更高版本中，寄存器分配似乎能按预期工作（可能需要传递 `-fno-sanitize-recover`）。还没有重新对不同版本的 clang 和 gcc 进行基准测试，但有时间的话会去做。
CPU 内部机制系列
- [分支预测简史](//danluu.com/branch-prediction/)
- [80 年代以来的新 CPU 特性](//danluu.com/new-cpu-features/)
- [实际代码中分支和整数溢出检查的成本](//danluu.com/integer-overflow/)
- [CPU 漏洞](https://danluu.com/cpu-bugs/)
- [CPU 开发为何困难](//danluu.com/hardware-unforgiving/)
- [Verilog 很糟糕，第一部分](//danluu.com/why-hardware-development-is-hard/)
- [Verilog 很糟糕，第二部分](//danluu.com/pl-troll/)
感谢 Nathan Kurz 对本文主题的评论，包括文中引用他的话；感谢 Stan Schwertly、Nick Bergson-Shilcock、Scott Feeney、Marek Majkowski、Adrian 和 Juan Carlos Borras 纠正错别字并提出澄清建议。还要特别感谢 Richard Smith，他向我指出了 `-fsanitize-undefined-trap-on-error` 选项。在 Richard 评论后，本文更新了该选项的测试结果。此外，感谢 Filipe Cabecinhas 指出 clang 在 3.8 版本（本文发布约 1.5 年后发布）修复了这个问题。
John Regehr 在 [这里](https://plus.google.com/105487075784331805819/posts/dyKKLrW8jXb) 对 clang 整数溢出检查实现速度不够快（目前）的原因有更多评论。
注释
1. 人们经常 [呼吁](http://yosefk.com/blog/the-high-level-cpu-challenge.html) 在现有溢出标志的基础上增加硬件对整数溢出检查的支持。这会增加每个芯片的成本和复杂度，在最佳情况下，对于优化后的代码，最多能提高百分之几的性能。这可能是值得的，因为英特尔添加了很多只对部分应用程序有百分之几性能提升的特性。
这通常被描述为一个鸡和蛋的问题：如果检查速度不那么慢，人们会使用溢出检查；而要使检查速度变快，需要硬件支持。但实际上，对于绝大多数应用程序来说，现有的硬件支持已经足以提供足够好的性能。只是因为人们实际上并不关心这个问题，所以没有充分利用这些支持。
[返回]
[← Julia 语言评测](https://danluu.com/julialang/) [Malloc 教程 →](https://danluu.com/malloc-tutorial/)
[存档](https://danluu.com/) [Patreon](https://www.patreon.com/danluu) [Mastodon](https://mastodon.social/@danluu)
[领英](https://www.linkedin.com/in/danluu/) [推特](https://twitter.com/danluu/) [RSS](https://danluu.com/atom.xml)