29

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

到目前为止，我已经在性能方面取得了出色的成绩，但是当我尝试进行更多优化时，有时会出现奇怪的行为。

例如，添加甚至删除一些简单的指令，或者只是重新组织一些与跳转一起使用的本地标签，会完全降低整体性能。就代码而言，绝对没有理由。

所以我的猜测是代码对齐和/或错误预测的分支存在一些问题。

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

但是，在 x86-64 上开发高性能时，是否有一些关于代码对齐和分支预测的一般建议？

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

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

在前面的代码中，我是否应该在之前使用 align 指令.label:，例如：

align 4
.label:

如果是这样，在使用 SSE-2 时对齐 DWORD 是否足够？

关于分支预测，是否有一种“首选”方式来组织跳转指令使用的标签，以帮助 CPU，或者今天的 CPU 是否足够聪明，可以在运行时通过计算分支的次数来确定这一点？

编辑

好的，这是一个具体的例子 - 这是strlen()SSE-2 的开始：

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

使用 1000 个字符的字符串运行 10'000'000 次大约需要 0.48 秒，这很好。
但它不检查 NULL 字符串输入。很明显，我将添加一个简单的检查：

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

同样的测试，它现在在 0.59 秒内运行。但是，如果我在此检查后对齐代码：

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

原来的表演又回来了。我使用 8 进行对齐，因为 4 不会改变任何东西。
谁能解释一下，并就何时对齐或不对齐代码段提供一些建议？

编辑 2

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

4

4 回答 4

27

对齐优化

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

使用其 3 个参数授予细粒度控制

  • param1 - 对齐到什么边界。
  • param2NOP - 用什么（零或s）填充填充。
  • param3 - 如果填充将超过指定的字节数，则不对齐。

2. 将经常使用的代码块的开始与高速缓存行大小边界对齐。

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

3.使用多字节NOPs进行填充，减少执行s的时间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最多 10byte NOP s。源binutils-2.2.3。）

分支预测优化

x86_64 微架构/代之间有很多变化。然而，一套适用于所有这些的通用指南可以总结如下。参考：Agner Fog 的 x86 微架构手册第 3 节。

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

  • 循环检测逻辑保证仅适用于小于 64次迭代的循环。这是因为一个分支指令被识别为具有循环行为，如果它单向n-1次，然后向另一个方向运行1次，对于任何n最多 64。

    这并不真正适用于 Haswell 和以后使用 TAGE 预测器并且没有针对特定分支的专用循环检测逻辑的预测器。在 Skylake 上，对于没有其他分支的紧外循环内部的内循环来说，迭代计数约为 23 可能是最坏的情况：从内循环的退出大多数时候会出现错误预测，但行程计数非常低，以至于它经常发生。展开可以通过缩短模式来提供帮助，但是对于非常高的循环行程计数，最后的单个错误预测会在很多行程中摊销，并且需要进行不合理的展开才能对此进行任何处理。

2. 坚持近跳/短跳。

  • 无法预测远跳转，即管道总是在远跳转到新代码段 (CS:RIP) 时停止。无论如何，基本上没有理由使用远跳，所以这几乎不相关。

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

    但是 Silvermont（英特尔的低功耗 CPU）在预测目标距离超过 4GB 时的间接跳转方面存在一些限制，因此通过在低 32 位虚拟地址空间中加载/映射可执行文件和共享库来避免这种情况可能是一个胜利. 例如在 GNU/Linux 上通过设置环境变量LD_PREFER_MAP_32BIT_EXEC。有关更多信息，请参阅英特尔的优化手册。

于 2013-08-16T18:10:37.260 回答
24

为了扩展TheCodeArtist 的回答，他提出了一些好的观点，这里有一些额外的东西和细节，因为我实际上能够解决这个问题。

1 - 代码对齐

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

3.4.1.5 - 汇编/编译器编码规则 12。（M 影响，H 通用性）
所有分支目标应为 16 字节对齐。

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

正如TheCodeArtist指出的那样，在这里使用多字节 NOP可能会有所帮助，因为简单地使用标准的单字节 NOP 可能不会带来代码对齐的预期性能增益。

作为旁注，该.p2align指令在 NASM 或 YASM 中不可用。
但它们确实支持与标准指令的 NOP 以外的其他指令对齐align：

align 16, xor rax, rax

2. 分支预测

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

CPU 尝试在 BTB（分支目标缓冲区）中保留分支历史记录。
但是当 BTB 中没有分支信息时，CPU 将使用他们所谓的静态预测，它遵循简单的规则，如 Intel 手册中所述：

  1. 预测不采用前向条件分支。
  2. 预测要采用的后向条件分支。

这是第一种情况的示例：

test rax, rax
jz   .label

; Fallthrough - Most likely

.label:

    ; Forward branch - Most unlikely

下指令.label是不太可能的情况，因为.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

因此，以防万一，请记住这一点。

于 2013-08-17T10:41:28.370 回答
5

要更好地理解对齐的重要性和方式，请查看Agner Fog 的微架构文档，尤其是。关于各种 CPU 设计的指令提取前端的部分。Sandybridge 引入了 uop 缓存，这对吞吐量产生了巨大的影响，尤其是。在 SSE 代码中，指令长度通常太长，以至于每个周期 16B 无法覆盖 4 条指令。

填充 uop 缓存行的规则很复杂，但是一个新的 32B 指令块总是会启动一个新的缓存行 IIRC。所以将热函数入口点对齐到 32B 是一个好主意。在其他情况下，这么多的填充可能会损害 I$ 密度而不是帮助。（不过，L1 I$ 仍然有 64B 高速缓存行，因此在帮助 uop 高速缓存密度的同时，有些事情可能会损害 L1 I$ 密度。）

循环缓冲区也有帮助，但采用的分支会破坏每个循环的 4 微指令，尤其是在 Haswell 之前。例如，在 SnB/IvB 上执行 3 条微指令的循环，如abc, abc, not 。因此，5-uop 循环每 2 个周期进行一次迭代，而不是每 1.25 次迭代。这使得展开更有价值。（Haswell 和后来似乎在 LSD 中展开了微小的循环，使 5-uop 循环不那么糟糕：执行 uop 计数不是处理器宽度倍数的循环时性能会降低吗？）abcabcda

于 2015-07-27T00:18:36.737 回答
3

“分支目标应该是 16 字节对齐规则”不是绝对的。该规则的原因是，在 16 字节对齐的情况下，可以在一个周期内读取 16 个字节的指令，然后在下一个周期内再读取 16 个字节。如果您的目标位于偏移量 16n + 2，那么处理器仍然可以在一个周期内读取 14 字节的指令（缓存行的其余部分），这通常已经足够了。然而，在偏移量 16n + 15 处开始循环是一个坏主意，因为一次只能读取一个指令字节。更有用的是将整个循环保持在尽可能少的高速缓存行中。

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

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

于 2015-07-26T23:28:02.730 回答