机器码布局

计算机工程师习惯将CPU流水线分为两个部分:前端(front-end),从内存获取指令并进行解码;后端,对指令进行调度并最终执行。通常,性能会受到执行阶段的限制,因此,我们在本书中的大部分工作都将用于后端优化。

但有时,当前端没有以足够快的速度向后端提供指令以使其饱和时,可能会发生相反的情况。这种情况可能有很多原因,所有这些最终都与机器码在内存中的布局有关,并以奇奇怪怪的方式影响性能,例如删除未使用的代码、交换if分支,甚至更改函数声明的顺序,都可能导致性能提升或恶化。

CPU 前端

在机器码被转换为指令,并且CPU理解程序员想要做什么之前,它首先需要经历两个我们感兴趣的重要阶段:取指(fetch)和译码(decode)。

在取值阶段,CPU只需从主存中加载一个固定大小的字节块,其中包含一些指令的二进制编码。这个块大小在x86上通常是32字节,在不同的机器上可能会有所不同。一个重要的细节就是这个内存块必须对齐:内存块的地址必须是其大小的倍数(在我们的例子中是32字节)。

接下来是译码阶段:CPU查看这个字节块,丢弃指令指针之前的所有字节,并将其余字节拆分为指令。机器指令使用可变字节数进行编码:一些简单且非常常见的指令,如inc rax,需要一个字节,而一些带有编码常量(encoded constants)和行为修饰前缀(behavior-modifying prefixes)的模糊指令(obscure instruction)可能需要多达15个字节。因此,从一个32字节的内存块中,可以解码出可变数量的指令,但不超过称为解码宽度(decode width)的特定机器相关的限制。在我的CPU(Zen 2)上,解码宽度为4,这意味着每个时钟周期最多可以解码4条指令并将其传递到下一阶段。

这些阶段以流水线方式工作:如果CPU能够告诉(或预测)下一次需要哪个指令块,那么取指阶段就不用等待当前块中的最后一条指令被译码,立即加载下一条指令。

代码对齐

在其他条件相同的情况下,编译器通常更喜欢机器码更短的指令,因为这样一来,更多的指令可以放在一个32B的取指内存块中,同时也减少了编译出的二进制文件的大小。但有时情况下则不然,因为提取的指令块必须对齐。

想象一下,你需要执行一个从32字节对齐块的最后一个字节开始的指令序列。你可以在没有额外延迟的情况下执行第一条指令,但对于随后的指令,你必须等待一个额外的周期用于提取下一个指令块。如果代码块在32B边界上对齐,那么最多可以解码4条指令,然后并发执行(除非它们超长或相互依赖)。

考虑到这一点,编译器通常会进行看似有害的优化:他们有时更喜欢机器代码更长的指令,甚至插入什么都不做的伪指令[1]^{[1]},以使关键跳转位置在适当的二次方边界上对齐。

在GCC中,你可以使用-falign-labels=n标志来指定特定的对齐策略,如果你希望更具选择性,可以将-labels替换为-function-loops-jumps。在-O2-O3优化级别上,默认情况下会启用它,而不需要设置特定的对齐方式,它会使用依赖于机器的(通常是合理的)默认值。

指令缓存

指令的存储和提取采用与数据基本相同的内存系统,只是可能底层缓存被单独的指令缓存(instruction chche)取代(因为你不希望某个随机读取数据的操作会将正在处理的代码挤出缓存)。

在以下情况中,指令缓存至关重要:

  • 不知道接下来要执行什么指令,并且希望以低延迟获取下一个块;
  • 或者正在执行一段冗长但快速的指令序列,需要高带宽

因此,内存系统可能成为具有大规模机器码的程序的瓶颈。这种考虑限制了我们之前讨论过的优化技术的适用性:

  • 内联函数并不总是最优的,因为它减少了代码共享并增加了二进制大小,需要更多的指令缓存。
  • 即使在编译期间就已知循环次数,展开循环也只在一定程度上是有益的:在某个时刻,CPU将不得不从主存中获取指令和数据,在这种情况下,它可能会受到内存带宽的限制。
  • 大量的代码对齐增加了二进制大小,同样需要更多的指令缓存。与发生cache miss并等待从主存中加载指令相比,在取指上多花一个周期只是一个很小的惩罚。
  • 另一个方面是,将频繁使用的指令序列放置在相同的高速缓存行cache lines)和内存页memory pages)上提高了高速缓存局部性chche locality)。为了提高指令缓存利用率,你应该将热代码与热代码分成一组,将冷代码与冷代码分成一组,并在可能的情况下删除未使用代码。如果你想进一步探索这个想法,可以看看Facebook的 BOLT(Binary Optimization and Layout Tool),它最近被合并到了LLVM中。

不等分支

假设由于某种原因,你需要一个计算整数间隔长度的辅助函数。它需要两个参数,xy,但为了方便起见,它可以对应于[x,y][y,x],具体取决于哪个参数不为空。在纯C中,你可能会写出类似这样的代码:

int length(int x, int y) {
if (x > y)
return x - y;
else
return y - x;
}

在x86汇编中,如何实现它有很多选择,这会显著影响性能。让我们从尝试将此代码直接映射到汇编开始:

length:
cmp edi, esi
jle less
; x > y
sub edi, esi
mov eax, edi
done:
ret
less:
; x <= y
sub esi, edi
mov eax, esi
jmp done

虽然最初的C代码看起来非常对称,但汇编版本却不是。这导致了一个有趣的情况,即一个分支的执行速度可以比另一个稍快:如果x > y,那么CPU只需执行cmpret之间的5条指令,如果函数做了对齐,这些指令都可以在一个内存块中被获取到;而在x <= y的情况下,还需要额外两次跳转。

可以合理地假设x > y的情况不太可能出现(怎么会有人要计算反转区间的长度?),更像是不曾发生过的特殊情况。我们可以检查这种情况,并简单地交换xy

int length(int x, int y) {
if (x > y)
swap(x, y);
return y - x;
}

汇编代码如下所示,就像没有else分支的if模式一样:

length:
cmp edi, esi
jle normal ; if x <= y, no swap is needed, and we can skip the xchg
xchg edi, esi
normal:
sub esi, edi
mov eax, esi
ret

指令的总长度从8条减少到现在的6条。但对于我们假设的情况,它仍然没有做到极致的优化:如果我们认为x > y从不会发生,那么加载永远不会执行的xchg edi, esi指令就是在浪费。我们可以通过将其移动到正常执行路径之外来解决此问题:

length:
cmp edi, esi
jg swap
normal:
sub esi, edi
mov eax, esi
ret
swap:
xchg edi, esi
jmp normal

这种技术在处理异常情况时非常方便,在高级代码中,你可以向编译器提示某个分支比另一个分支更有可能:

int length(int x, int y) {
if (x > y) [[unlikely]] // C++20
swap(x, y);
return y - x;
}

只有当你知道很少执行该分支时,这种优化才是有益的。否则还有其他方面的问题比代码布局更重要,它会迫使编译器避免任何分支——在这种情况下,用一个特殊的“条件移动”指令代替它,大致对应于三元表达式(x > y ? y - x : x - y)或调用abs(x - y)

length:
mov edx, edi
mov eax, esi
sub edx, esi
sub eax, edi
cmp edi, esi
cmovg eax, edx ; "mov if edi > esi"
ret

消除分支是一个重要的话题,我们将在下一章的大量篇幅中更详细地讨论它。

备注

  1. 这样的指令称为no-op指令或NOP指令。在x86上,什么都不做的“官方方式”是xchg rax, rax(寄存器与自己交换):CPU能识别它,除了解码阶段之外,不需要花费额外的周期来执行它。nop简写指令映射到相同的机器码。