x86-64汇编的性能优化 - 对齐和分支预测

Question

我目前正在编写一些C99标准库字符串函数的高度优化版本，例如strlen()，memset()等，使用x86-64汇编和SSE-2指令。

到目前为止，我的表现在性能方面非常优秀，但是当我尝试进行更多优化时，有时会出现奇怪的行为。

例如，添加甚至删除一些简单的指令，或者仅仅是重新组织一些与跳转一起使用的本地标签，就会完全降低整体性能。而且从代码角度来看没有任何原因。

所以我猜测代码对齐存在问题，或者分支被错误预测了。

我知道，即使是相同的架构（x86-64），不同的CPU也具有不同的分支预测算法。

但是，在开发x86-64高性能应用程序时，有关代码对齐和分支预测方面是否有一些通用建议呢？

特别是关于对齐，我应该确保所有用于跳转指令的标签都对齐在DWORD上吗？

_func:
    ; ... Some code ...
    test rax, rax
    jz   .label
    ; ... Some code ...
    ret
    .label:
        ; ... Some code ...
        ret

在之前的代码中，我应该在.label:之前使用一个align指令，像这样：

align 4
.label:

如果使用SSE-2，对齐到DWORD是否已足够？

关于分支预测，是否有优选的方式来组织跳转指令中使用的标签以帮助CPU，或者现今的CPU是否聪明到足以在运行时通过计算分支被执行的次数来确定呢？

编辑

好的，这里有一个具体的例子 - 这是使用SSE-2的 strlen()函数的开头：

_strlen64_sse2:
    mov         rsi,    rdi
    and         rdi,    -16
    pxor        xmm0,   xmm0
    pcmpeqb     xmm0,   [ rdi ]
    pmovmskb    rdx,    xmm0
    ; ...

用一个1000个字符的字符串运行10000000次大约需要0.48秒，这非常好。
但它并没有检查空字符串输入。所以显然，我会添加一个简单的检查：

_strlen64_sse2:
    test       rdi,    rdi
    jz          .null
    ; ...

同样的测试，现在运行时间为0.59秒。但是如果我在这个检查之后对代码进行对齐：

_strlen64_sse2:
    test       rdi,    rdi
    jz          .null
    align      8
    ; ...

原始的表现已经回来了。我使用8来对齐，因为4不会改变任何东西。
有人能解释一下这是什么意思，并给出一些关于何时对齐或不对齐代码段的建议吗？

编辑2

当然，对齐每个分支目标并不像简单。如果这样做，性能通常会变得更糟，除非像上面那样的特定情况。

- Macmade

---

SSE2 拥有分支提示前缀 (2E 和 3E)。 - Kerrek SB

除了 P4 处理器外，所有处理器都会忽略分支提示。 - harold

就现代x86 CPU上的分支预测而言，请查看本手册的第3节。 - TheCodeArtist

我想知道这种优化水平在更现实的环境中有多有用，因为整个字符串并不像你使用的基准测试那样存在于L1缓存中。你所担心的20%性能差异可能与内存获取成本相比完全微不足道。 - Gene

投票关闭，原因是过于宽泛。 - Ciro Santilli OurBigBook.com

Answer 1

对齐优化

1. 使用.p2align <abs-expr> <abs-expr> <abs-expr>代替align。

使用其三个参数可以实现精细控制。

• param1 - 对齐到哪个边界。
• param2 - 使用什么填充空隙（零或NOP）。
• param3 - 如果填充会超过指定的字节数，则不进行对齐。

2. 将频繁使用的代码块的开头对齐到缓存行大小的边界。

• 这将增加整个代码块位于单个缓存行的可能性。一旦加载到L1高速缓存中，就可以完全运行而无需访问RAM以进行指令获取。这对于具有大量迭代的循环非常有益。

3. 使用多字节NOP作为空隙填充，以减少执行NOP的时间。

  /* nop */
  static const char nop_1[] = { 0x90 };

  /* xchg %ax,%ax */
  static const char nop_2[] = { 0x66, 0x90 };

  /* nopl (%[re]ax) */
  static const char nop_3[] = { 0x0f, 0x1f, 0x00 };

  /* nopl 0(%[re]ax) */
  static const char nop_4[] = { 0x0f, 0x1f, 0x40, 0x00 };

  /* nopl 0(%[re]ax,%[re]ax,1) */
  static const char nop_5[] = { 0x0f, 0x1f, 0x44, 0x00, 0x00 };

  /* nopw 0(%[re]ax,%[re]ax,1) */
  static const char nop_6[] = { 0x66, 0x0f, 0x1f, 0x44, 0x00, 0x00 };

  /* nopl 0L(%[re]ax) */
  static const char nop_7[] = { 0x0f, 0x1f, 0x80, 0x00, 0x00, 0x00, 0x00 };

  /* nopl 0L(%[re]ax,%[re]ax,1) */
  static const char nop_8[] =
    { 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00};

  /* nopw 0L(%[re]ax,%[re]ax,1) */
  static const char nop_9[] =
    { 0x66, 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 };

  /* nopw %cs:0L(%[re]ax,%[re]ax,1) */
  static const char nop_10[] =
    { 0x66, 0x2e, 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 };

(对于x86来说，最多使用10字节的NOP。参考资料：binutils-2.2.3。)

---

分支预测优化

_{x86_64微架构/代际之间存在许多变化。然而，适用于所有这些微架构的一组常见指南可以总结如下。参考资料：Agner Fog x86微架构手册第3节。}

1. 展开循环以避免迭代次数略高。

• 仅对具有< 64次迭代的循环保证循环检测逻辑有效。这是因为如果一个分支指令在任何n（n最大到64）内向一个方向走了n-1次，然后向另一个方向走了1次，则该分支指令将被识别为具有循环行为。

  这对Haswell和更高版本中的预测器实际上并不适用，因为它们使用TAGE预测器，并且没有专门的循环检测逻辑来针对特定分支。在Skylake上，没有其他分支的紧密外部循环中的内部循环的迭代次数约为23，从中退出的时机大多数情况下都会出现错误预测，但是由于迭代次数非常低，所以经常发生。展开可以通过缩短模式来帮助解决问题，但对于非常高的循环迭代次数，最后的一次错误预测会被摊销到许多迭代中，并且需要大量的展开才能解决这个问题。

2. 保持近/短跳转。

• 远跳转未被预测，即流水线总是在远跳转到新代码段（CS：RIP）上停顿。基本上没有理由使用远跳转，因此这基本上不相关。

  具有任意64位绝对地址的间接跳转在大多数CPU上通常都是常规预测的。

  但是Silvermont（Intel的低功耗CPU）在目标距离超过4GB时有一些限制，因此通过将可执行文件和共享库加载/映射到虚拟地址空间的低32位中来避免这种情况可能是一个好选择。例如，在GNU / Linux上，通过设置环境变量LD_PREFER_MAP_32BIT_EXEC。请参见英特尔的优化手册以了解更多信息。

- TheCodeArtist

---

谢谢你的回答，特别是关于多字节NOP的部分。我会在另一个回答中添加更多细节，因为这也可能有助于其他人。同时，我授予你赏金，感谢你花时间撰写详细的答案，即使它并没有回答所有问题：） - Macmade

谢谢。:-)期待您的答案，带上您在研究中发现的细节。 - TheCodeArtist

在x86中，FAR跳转是指到不同代码段的跳转，即它会改变CS。这基本上只与16位有关。对于优化普通用户空间代码，甚至没有必要提及它。短（rel8）和近（rel32）跳转都是被预测和推测执行的。我不知道你是否认为Far意味着rel32或其他什么。 - Peter Cordes

@TheCodeArtist 关于“在一个紧密的外部循环内部的迭代次数可能是最坏情况下的23”，这不是因为分支预测器。这是因为内部循环将在大约23次迭代后开始耗尽LSD，而LSD的唯一停止条件是分支失误。 - Noah

Answer 2

延续TheCodeArtist的回答，他提出了一些好点子。在此我补充一些额外的内容和细节，因为我实际上已经成功解决了这个问题。

1 - 代码对齐

英特尔建议将代码和分支目标对齐到16字节边界：

  

3.4.1.5-汇编/编译器编码规则12.(M影响，H一般性)
  所有分支目标都应该对齐到16字节。

虽然这通常是一个很好的建议，但是应该小心谨慎地进行。
盲目地对齐所有东西可能会导致性能损失，因此在应用之前应该在每个分支目标上进行测试。

如同TheCodeArtist所指出的那样，使用多字节NOP可以帮助解决这个问题，因为仅使用标准的一字节NOP可能无法带来代码对齐的预期性能提升。

顺便说一下，在NASM或YASM中，.p2align指令不可用。
但是它们支持使用标准的align指令将其他指令对齐，而不仅仅是NOP。

align 16, xor rax, rax

2. 分支预测

这被证明是最重要的部分。
虽然每一代的x86-64 CPU都有不同的分支预测算法，但通常可以应用一些简单的规则来帮助CPU预测哪个分支可能会被执行。

CPU试图在BTB（分支目标缓存）中保留分支历史记录。
但当BTB中没有可用的分支信息时，CPU将使用所谓的静态预测，遵循简单的规则，如英特尔手册中所述：

1. 预测前向条件分支不会被执行。
2. 预测后向条件分支将被执行。

以下是第一种情况的一个示例：

test rax, rax
jz   .label

; Fallthrough - Most likely

.label:

    ; Forward branch - Most unlikely

< p > 在实际分支之后声明 < code > .label ，因此在 < code > .label 下的指令是不太可能的情况。

对于第二种情况：

.label:

    ; Backward branch - Most likely

test rax, rax
jz   .label

; Fallthrough - Most unlikely

在这里，.label 下的指令是可能的条件，因为 .label 在实际分支之前被声明。

所以每个条件分支应该始终遵循这个简单的模式。
当然，这也适用于循环。

正如我之前提到的，这是最重要的部分。

当我添加一些本应该合理提高整体性能的简单测试时，我会经历不可预测的性能增益或损失。
盲目遵循这些规则解决了这些问题。
如果没有，为优化目的添加分支可能会产生相反的结果。

TheCodeArtist 在他的回答中还提到了 循环展开。
虽然这不是问题所在，因为我的循环已经展开，但我在这里提到它，因为这确实是 非常重要 的，并且会带来实质性的性能提升。

最后对读者说一句，虽然这似乎是显而易见的，但在不必要的情况下不要分支。

从 Pentium Pro 开始，x86 处理器拥有 条件 移动指令，这可能有助于消除分支并抑制错误预测的风险：

test   rax, rax
cmovz  rbx, rcx

以防万一，记住这个好东西。

- Macmade

---

虽然您和TCA的答案是很好的一般原则，但更深层次的问题是这些规则实际上何时适用。一般来说，这不能回答，除非（大量）参考目标CPU的细节。虽然避免分支错误预测至关重要，但是每次迭代都应该正确预测此循环，但无论您跳转的方式如何，退出都是如此。我认为您在对齐方面真正的问题在于指令解码和微操作循环缓冲区。您可能正在旧处理器上测试这个？您能发布您的完整代码吗？我认为更多的探索可能会很有趣。 - Nathan Kurz

所有分支目标应该是16字节对齐的。这个编码规则似乎已经在2020年5月的Intel® 64和IA-32架构优化参考手册中被删除，或者更早之前就已经删除了。 - Olsonist

有人知道为什么吗？ - Olsonist

@Olsonist: 因为现代CPU具有uop缓存，关心32字节边界，但这对于填充来说太宽了不值得。更好的是在函数内部实现紧密排列，通常包括循环的顶部。还有实现"if"/"else"逻辑的分支，只有在每次调用函数时才跳转。 - Peter Cordes

顺便提一下，对齐代码和将分支目标对齐到16字节边界是两回事。我记得英特尔曾经建议不要让指令重叠16字节的边界。也许这是错误的记忆，但现在他们说“前端每个周期可以获取16个字节的指令。”注意，这不是16个对齐字节。因此，英特尔正在显着放宽他们的建议。至于LCP，他们提到在LSD中没有问题，因为“没有LCP惩罚，因为已经通过了预解码阶段。”所以对于循环，它们不是问题。它们是优势吗？只有测试才能说明。 - Olsonist

Answer 3

为了更好地了解为什么对齐很重要以及如何进行对齐，请查看Agner Fog的微架构文档，特别是有关各种CPU设计的指令获取前端的部分。 Sandybridge引入了uop缓存，这对吞吐量有很大影响，特别是在SSE代码中，指令长度通常太长，16B每个周期无法覆盖4条指令。

填充uop缓存行的规则很复杂，但是新的32B指令块始终会启动新的缓存行，如果我没记错的话。 因此，将热函数入口点对齐到32B是一个好主意。 在其他情况下，那么多的填充可能会损害I $密度而不是帮助它。（L1 I$仍然具有64B缓存行，因此某些事物可能会损害L1 I $密度，同时帮助uop缓存密度。）

循环缓冲区也有帮助，但分支会破坏每个周期的4个uops，特别是在Haswell之前。例如，一个由3个uops组成的循环执行方式为abc，abc，而不是abca，bcda在SnB/IvB上。因此，一个由5个uop组成的循环需要2个周期才能完成一次迭代，而不是1.25个周期。这使得展开循环更加有价值。（Haswell及以后版本似乎在LSD中展开微小循环，使得一个由5个uop组成的循环不那么糟糕：Is performance reduced when executing loops whose uop count is not a multiple of processor width?）

- Peter Cordes

---

我现在遇到了一些问题。比我想象的要复杂得多。我将不得不提出一个有关它的问题。 - Z boson

Answer 4

“分支目标应该按16字节对齐的规则”并不是绝对的。这个规则的原因是，使用16字节对齐，可以在一个周期内读取16字节的指令，然后在下一个周期中读取另外16字节。如果你的目标偏移量为16n+2，则处理器仍然可以在一个周期内读取14字节的指令（缓存行的余数），通常足够好。但是，从偏移量16n+15开始循环是一个坏主意，因为一次只能读取一个指令字节。更有用的是将整个循环保留在尽可能少的缓存行中。

在某些处理器上，分支预测具有奇怪的行为，即所有在8或4字节内的分支使用相同的分支预测器。将分支移动，以使得每个条件分支使用自己的分支预测器。

这两条建议的共同点是插入一些代码可以改变行为并使其更快或更慢。

- gnasher729