浅谈 O2 优化

· · 个人记录

O2 优化是什么？是自动把 O(n^2) 的算法优化为 O(n\log n)吗？

不是。你想多了。

那么 O2 优化是什么？

简单地讲，O2 优化，就是让编译器会帮助你在编译期间完成一部分计算，简化程序执行的过程，并忽略掉一些没必要的代码。下面举几个例子。，

int sum = 0;
for (int i = 1; i <= 100; ++i) 
    sum += i; 
std::cout << sum << std::endl;

这份代码用于输出 [1, 100] 的和。在没有开启 O2 优化的情况下，编译器会按照语义老老实实的编译。得出汇编代码是这样的（汇编代码不必要看懂，稍微体会一下即可）：

  mov DWORD PTR [rbp-4], 0
  mov DWORD PTR [rbp-8], 1
.L3:
  cmp DWORD PTR [rbp-8], 100
  jg .L2
  mov eax, DWORD PTR [rbp-8]
  add DWORD PTR [rbp-4], eax
  add DWORD PTR [rbp-8], 1
  jmp .L3
.L2:
  mov eax, DWORD PTR [rbp-4]
  mov esi, eax
  mov edi, OFFSET FLAT:_ZSt4cout
  call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)

代码中含有大量 jmp 命令（jmp，jump 的缩写），说明程序会老老实实地跑 100 次循环。

如果开优化，会发生什么呢？

  mov esi, 5050
  mov edi, OFFSET FLAT:_ZSt4cout
  call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)

直接输出 5050。

如果只是计算，不输出，那么无优化时，依旧要跑循环；有 O2 时，代码会被忽略了，不被编译，得到的汇编代码为空。因为编译器开优化之后变得聪明，认为不输出结果的计算是没用的。

还有其他例子吗？

当然有。比如，让我们搜一下，第 123 个质数是多少。

int cnt = 0;
for (int i = 0; ; ++i) { 
    if (is_prime(i)) ++cnt; // is_prime 假设已经在外面写好了
    if (cnt == 123) {
        std::cout << i << std::endl;
        break;
    }
}

无优化情况下，编译出的汇编代码比较长，我都没心情看。

// 此处省略 600+ 字符的汇编代码

一旦开了 O2 优化，汇编代码就变短许多：

  xor esi, esi
.L11:
  add esi, 1
.L12:
  add edi, 1
.L13:
  cmp edi, 123
  jne .L11
  mov edi, OFFSET FLAT:_ZSt4cout
  call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)

可以看到，程序根本没有调用 is_prime 函数。这说明聪明的编译器又帮你简化了运行时计算。

同理，当你使用 STL 的时候，如果开启 O2 优化，则程序将简化掉操作，不会严格按照库中的代码实现。文章后面将会举一个例子。

O2 优化在哪些方面能够发挥作用？

几乎所有暴力代码（尤其是嵌套循环的暴力代码）开启 O2 优化之后都会大幅提速。当然，还有 STL。

当然，如果只是朴素解法的 A+B，开 O2 优化不会有用。

为什么是 O2，不是 A2 / B2 / C2…… 呢？

“O”，可以理解为英文单词 optimize 的首字母，意为优化。后面的 2，可以理解为优化的等级、强度。因此，不仅有 O2 优化，还有 O、O3、Os、Ofast。其中，O 是我们平常默认的编译选项，基本没用。O3 优化，即是在 O2 优化的基础上，再次提高运行速度。Os 是用来减小生成 exe 的文件大小的。Ofast 与 O3 几乎没有区别。

既然 O2 优化这么厉害，为什么默认编译选项不包含它啊？

其实，并不是所有 O2 优化都是正优化，可能会有负优化。比如，你的代码使用了为初始化的值。编译器并不知道这个值是多少，不知道该如何为你编译。这就是传说中的 UB——未定义行为。在这种情况下，编译器给你编译出来什么东西都有可能。所以，让代码符合规范是重要的。强烈建议在本地开启 -Wall 编译选项。

在无优化情况下，一般编译器会把未初始化的变量赋值为零。但是在有优化情况下，会赋随机值。洛谷讨论区经常有人问“为什么开了 O2 优化 WA，不开 AC？”很多都是未初始化造成的。

轮子哥曾经说过：“你不开 O2，你就能感受到那些抽象带来的效果。”什么意思呢？就是说 O2 优化会对 STL 进行提速，把不必要的、浪费时间的抽象代码都去掉了。比如，你要把一个 vector 清空。如果不开优化，你怎么写，编译器就怎么办。如果开了，就会编译成内存填充的方式。所以工程上你一旦开了 O2 优化，就无法在根本层面进行 Debug。

如果你希望了解更多关于 O2 优化的内容，建议去看看 GCC 的官方文档：https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

注：本文所有汇编代码均使用 https://godbolt.org/ 中的 GCC 8.1 生成。