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

在前面的代码中,我之前应该使用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

当然,它并不像对齐每个分支目标那么简单.如果我这样做,表演通常会变得更糟,除非上面有一些特殊情况.

Answer 1

对齐优化

1.使用.p2align <abs-expr> <abs-expr> <abs-expr>而不是align.

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

• param1 - 与什么边界对齐.
• param2 - 用什么(零或NOPs)填充填充.
• param3 - 如果填充超过指定的字节数,请不要对齐.

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

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

3.使用多字节NOPs进行填充以减少执行NOPs所花费的时间.

  /* 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.来源binutils-2.2.3.)

分支预测优化

_{x86_64微架构/代之间有很多变化.但是,适用于所有这些指南的一套通用指南可归纳如下.参考:Agner Fog的x86微架构手册第3节.}

1.坚持短跳.

• 远距离跳跃没有被预测,即管道总是在有条件的远距离跳跃时停止.

2.展开大型循环.

• 保证循环检测逻辑仅适用于<64次迭代的循环.这是因为分支指令被识别为具有循环行为,如果它以单向n-1次然后以另一种方式进行1次,对于任何n高达64.

Answer 2

为了扩展TheCodeArtist的答案,谁提出了一些好处,这里有一些额外的东西和细节,因为我实际上能够解决问题.

1 - 代码对齐

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

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

虽然这通常是一个很好的建议,但应该仔细进行.
盲目地16字节对齐一切都可能导致性能损失,因此应在应用之前在每个分支目标上进行测试.

正如TheCodeArtist指出的那样,使用多字节NOP可能会有所帮助,因为简单地使用标准的单字节NOP可能无法带来预期的代码对齐性能增益.

作为旁注,该.p2align指令在NASM或YASM中不可用.
但它们确实支持使用标准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

下面的说明.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

所以,以防万一,要记住好事.

Answer 3

为了更好地理解对齐的重要性和原因，请查看Agner Fog 的微体系结构文档，尤其是。关于各种 CPU 设计的取指令前端的部分。Sandybridge 引入了 uop 缓存，这与吞吐量有很大不同，尤其是。在 SSE 代码中，指令长度通常太长，每个周期 16B 无法覆盖 4 条指令。

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

循环缓冲区也有帮助，但采用的分支会破坏每个周期的 4 uop。例如，3 个 uops 的循环执行如abc, abc, 不abca, bcda。所以一个 5-uop 循环每 2 个周期进行一次迭代，而不是每 1.25 次迭代。这使得展开更有价值。