整数溢出检查成本揭秘开销几何编译器表现如何启用整数溢出检查会带来多少额外开销呢通过编译器标志或内置函数可利用基于 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 美元所以选择对 bzip2SPECint 的一个组件进行基准测试而不是花 800 美元购买 SPECint。使用 clang -O3、clang -O3 -fsanitizesigned-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 架构上使用 -fsanitizesigned-integer-overflow,unsigned-integer-overflow 编译时速度大约慢 6 倍。查看反汇编代码正常版本使用 SSE 加法而启用检查的版本使用普通加法。对于未检查的 SSE 加法和检查后的加法慢 6 倍是合理的。但如果尝试不同的循环排列方式使编译器无法为未检查版本生成 SSE 指令使用 fsanitize 编译的版本仍然会有 4 - 6 倍的性能损失。由于涉及多种优化包括循环展开来看一个简单的只做一次加法的函数以更好地了解情况。下面是一个将两个整数相加的函数的反汇编代码分别使用 -O3 和 -O3 -fsanitizesigned-integer-overflow,unsigned-integer-overflow 编译asm0000000000400530 :400530: 01 f7 add %esi,%edi400532: 89 f8 mov %edi,%eax400534: c3 retq编译器在 -O3 版本上表现不错。根据标准的 AMD64 调用约定参数通过 esi 和 edi 寄存器传入结果通过 eax 寄存器传出。与内联 add 指令相比这里有一些开销因为需要将结果移动到 eax 寄存器并从函数调用返回但考虑到这是一个函数调用这个实现是完全合理的。asm000000000041df90 :41df90: 53 push %rbx41df91: 89 fb mov %edi,%ebx41df93: 01 f3 add %esi,%ebx41df95: 70 04 jo 41df9b41df97: 89 d8 mov %ebx,%eax41df99: 5b pop %rbx41df9a: c3 retq41df9b: 89 f8 mov %edi,%eax41df9d: 89 f1 mov %esi,%ecx41df9f: bf a0 89 62 00 mov $0x6289a0,%edi41dfa4: 48 89 c6 mov %rax,%rsi41dfa7: 48 89 ca mov %rcx,%rdx41dfaa: e8 91 13 00 00 callq 41f340 __ubsan_handle_add_overflow41dfaf: eb e6 jmp 41df97编译器在 -O3 -fsanitizesigned-integer-overflow,unsigned-integer-overflow 版本上的表现不佳。优化专家 Nathan Kurz 对 clang 的输出评价如下 这是糟糕但并非罕见的编译器生成代码。出于某种原因编译器决定使用 %ebx 作为加法的目标寄存器。一旦这样做就不得不进行后续操作。问题在于为什么它不使用临时寄存器为什么觉得有必要进行移动操作以及未来如何避免这种情况。如你所知%ebx 是一个 “被调用者保存” 寄存器这意味着函数返回时它的值必须保持不变因此需要进行压栈和出栈操作。如果编译器直接进行加法操作不进行额外的移动操作让输入保持在传入时的 %edi/%esi 寄存器中就像未检查版本那样就不需要这些操作了。我猜测这是早期优化阶段的遗留问题但不知为何 %ebx 的影响仍然存在。然而添加 -fsanitize-undefined-trap-on-error 后代码变为asm0000000000400530 :400530: 01 f7 add %esi,%edi400532: 70 03 jo 400537400534: 89 f8 mov %edi,%eax400536: c3 retq400537: 0f 0b ud2虽然这是一个简单的示例但可以在使用允许 fsanitize 打印诊断信息的选项编译的其他代码中看到各种优化问题。理论上更好的 C 编译器可以做得更好但在这里gcc 4.82 并不比 clang 3.4 好。一方面gcc 的 -ftrapv 只检查有符号溢出更糟糕的是它不起作用[自 2008 年以来关于 -ftrapv 的这个 bug 一直未修复](https://gcc.gnu.org/bugzilla/show_bug.cgi?id35412)。尽管检查更少且检查不正确但在 bzip2 上gcc 的 -ftrapv 与 clang 的 -fsanitizesigned-integer-overflow,unsigned-integer-overflow 导致的性能下降程度相当比 -fsanitizesigned-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)