为什么引入无用的MOV指令会加速x86_64汇编中的紧凑循环？

Question

背景:

在使用嵌入式汇编语言优化某些Pascal代码时,我注意到了一条不必要的MOV指令,并将其删除.

令我惊讶的是,删除不必要的指令会导致我的程序变慢.

我发现添加任意无用的MOV指令可以进一步提高性能.

效果不稳定,并且基于执行顺序进行更改:相同的垃圾指令向上或向下移动一行会产生减速.

我知道CPU会进行各种优化和精简,但这看起来更像是黑魔法.

数据:

我的代码版本有条件地在运行时间的循环中编译三个垃圾操作2**20==1048576.(周围的程序只计算SHA-256哈希值).

在我相当老的机器(英特尔(R)Core(TM)2 CPU 6400 @ 2.13 GHz)上的结果:

avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without:        1836.44 ms

程序在循环中运行25次,每次运行顺序随机变化.

摘抄:

{$asmmode intel}
procedure example_junkop_in_sha256;
  var s1, t2 : uint32;
  begin
    // Here are parts of the SHA-256 algorithm, in Pascal:
    // s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
    // s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
    // Here is how I translated them (side by side to show symmetry):
  asm
    MOV r8d, a                 ; MOV r9d, e
    ROR r8d, 2                 ; ROR r9d, 6
    MOV r10d, r8d              ; MOV r11d, r9d
    ROR r8d, 11    {13 total}  ; ROR r9d, 5     {11 total}
    XOR r10d, r8d              ; XOR r11d, r9d
    ROR r8d, 9     {22 total}  ; ROR r9d, 14    {25 total}
    XOR r10d, r8d              ; XOR r11d, r9d

    // Here is the extraneous operation that I removed, causing a speedup
    // s1 is the uint32 variable declared at the start of the Pascal code.
    //
    // I had cleaned up the code, so I no longer needed this variable, and 
    // could just leave the value sitting in the r11d register until I needed
    // it again later.
    //
    // Since copying to RAM seemed like a waste, I removed the instruction, 
    // only to discover that the code ran slower without it.
    {$IFDEF JUNKOPS}
    MOV s1,  r11d
    {$ENDIF}

    // The next part of the code just moves on to another part of SHA-256,
    // maj { r12d } := (a and b) xor (a and c) xor (b and c)
    mov r8d,  a
    mov r9d,  b
    mov r13d, r9d // Set aside a copy of b
    and r9d,  r8d

    mov r12d, c
    and r8d, r12d  { a and c }
    xor r9d, r8d

    and r12d, r13d { c and b }
    xor r12d, r9d

    // Copying the calculated value to the same s1 variable is another speedup.
    // As far as I can tell, it doesn't actually matter what register is copied,
    // but moving this line up or down makes a huge difference.
    {$IFDEF JUNKOPS}
    MOV s1,  r9d // after mov r12d, c
    {$ENDIF}

    // And here is where the two calculated values above are actually used:
    // T2 {r12d} := S0 {r10d} + Maj {r12d};
    ADD r12d, r10d
    MOV T2, r12d

  end
end;

亲自尝试一下:

如果您想自己试用,代码在GitHub上在线.

我的问题:

• 为什么无用地将寄存器的内容复制到RAM会不会提高性能？
• 为什么同样无用的指令会在某些线路上提供加速,而在其他线路上则会减速？
• 这种行为是否可以被编译器可预测地利用？

Answer 1

速度提升的最可能原因是:

• 插入MOV会将后续指令移到不同的存储器地址
• 其中一个移动指令是一个重要的条件分支
• 由于分支预测表中的混叠,该分支被错误预测
• 移动分支消除了别名并允许正确预测分支

您的Core2没有为每个条件跳转保留单独的历史记录.相反,它保留了所有条件跳转的共享历史记录.全局分支预测的一个缺点是,如果不同的条件跳转是不相关的,则历史被无关信息稀释.

这个小分支预测教程展示了分支预测缓冲区如何工作.缓存缓冲区由分支指令的地址的下部索引.除非两个重要的不相关分支共享相同的低位,否则这很有效.在这种情况下,您最终会出现别名,这会导致许多错误预测的分支(这会拖延指令管道并减慢程序速度).

如果您想了解分支机构误预测会如何影响性能,请查看以下优秀答案:https: //stackoverflow.com/a/11227902/1001643

编译器通常没有足够的信息来知道哪些分支将是别名,以及这些别名是否重要.但是,可以使用Cachegrind和VTune等工具在运行时确定该信息.

Answer 2

您可能需要阅读http://research.google.com/pubs/pub37077.html

TL; DR:在程序中随机插入nop指令可以轻松地将性能提高5%或更多,不然,编译器不能轻易利用它.它通常是分支预测器和缓存行为的组合,但它也可以是例如保留站停顿(即使在没有任何依赖链被破坏或明显的资源超额预订的情况下).

Answer 3

我相信现代CPU中的汇编指令虽然是程序员向CPU提供执行指令的最后一个可见层,但实际上是CPU实际执行的几个层.

现代CPU是RISC/CISC混合,它将CISC x86指令转换为更符合RISC行为的内部指令.此外,还有无序执行分析器,分支预测器,英特尔的"微操作融合",试图将指令分组到更大批量的同步工作中(有点像VLIW/Itanium泰坦尼克号).甚至有缓存边界可以使代码运行得更快,因为上帝知道 - 为什么如果它更大(可能是缓存控制器更智能地插槽,或保持更长时间).

CISC总是有一个汇编到微码的转换层,但重点是现代CPU的事情要复杂得多.利用现代半导体制造工厂中所有额外的晶体管空间,CPU可以并行应用多种优化方法,然后在最后选择提供最佳加速的方法.额外的指令可能会偏向CPU以使用一个比其他更好的优化路径.

额外指令的效果可能取决于CPU型号/生成/制造商,并且不太可能是可预测的.以这种方式优化汇编语言需要针对许多CPU架构生成执行,可能使用特定于CPU的执行路径,并且仅对于真正非常重要的代码段才是可取的,尽管如果您正在进行汇编,您可能已经知道了.