背景:

在用嵌入式汇编语言优化一些Pascal代码时,我注意到一个不必要的MOV指令,并删除了它。

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

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

效果是不稳定的,并且根据执行顺序而变化:相同的垃圾指令向上或向下转置一行会产生减速。

我知道CPU做了各种各样的优化和精简,但是,这看起来更像是黑魔法。

数据:

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

在我相当旧的机器(英特尔(R)酷睿(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会提高性能? 为什么同样无用的指令会在某些行上加速,而在其他行上减慢? 这种行为可以被编译器预测地利用吗?


当前回答

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

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

Core2不会为每个条件跳转保存单独的历史记录。相反,它保留了所有条件跳转的共享历史。全局分支预测的一个缺点是,如果不同的条件跳跃不相关,历史会被不相关的信息冲淡。

这个分支预测教程展示了分支预测缓冲区是如何工作的。缓存缓冲区是根据分支指令地址的下半部分建立索引的。这工作得很好,除非两个重要的不相关分支共享相同的下位。在这种情况下,您最终会得到别名,这会导致许多错误预测的分支(这会使指令管道停滞并降低程序速度)。

如果您想了解分支的错误预测是如何影响性能的,请查看这个优秀的答案:https://stackoverflow.com/a/11227902/1001643

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

其他回答

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

TL;DR:在程序中随机插入nop指令可以很容易地将性能提高5%或更多,不,编译器不能轻易利用这一点。这通常是分支预测器和缓存行为的结合,但也可能是预留站失速(即使没有依赖链断裂或明显的资源过度订阅)。

准备缓存

Move operations to memory can prepare the cache and make subsequent move operations faster. A CPU usually have two load units and one store units. A load unit can read from memory into a register (one read per cycle), a store unit stores from register to memory. There are also other units that do operations between registers. All the units work in parallel. So, on each cycle, we may do several operations at once, but no more than two loads, one store, and several register operations. Usually it is up to 4 simple operations with plain registers, up to 3 simple operations with XMM/YMM registers and a 1-2 complex operations with any kind of registers. Your code has lots of operations with registers, so one dummy memory store operation is free (since there are more than 4 register operations anyway), but it prepares memory cache for the subsequent store operation. To find out how memory stores work, please refer to the Intel 64 and IA-32 Architectures Optimization Reference Manual.

打破错误的依赖

虽然这并不完全适用于您的情况,但有时在64位处理器下使用32位mov操作(如您的情况)用于清除较高的位(32-63)并打破依赖链。

众所周知,在x86-64下,使用32位操作数将清除64位寄存器的高位。请阅读Intel®64 and IA-32架构软件开发人员手册第1卷的相关章节- 3.4.1.1:

32位操作数生成一个32位的结果,在目标通用寄存器中由0扩展为64位的结果

因此,mov指令,乍一看可能毫无用处,清除相应寄存器的较高位。它给了我们什么?它打破了依赖链,允许指令以随机顺序并行执行,这是自1995年Pentium Pro以来由cpu内部实现的失序算法。

摘自Intel®64和IA-32架构优化参考手册第3.5.1.8节:

Code sequences that modifies partial register can experience some delay in its dependency chain, but can be avoided by using dependency breaking idioms. In processors based on Intel Core micro-architecture, a number of instructions can help clear execution dependency when software uses these instruction to clear register content to zero. Break dependencies on portions of registers between instructions by operating on 32-bit registers instead of partial registers. For moves, this can be accomplished with 32-bit moves or by using MOVZX. Assembly/Compiler Coding Rule 37. (M impact, MH generality): Break dependencies on portions of registers between instructions by operating on 32-bit registers instead of partial registers. For moves, this can be accomplished with 32-bit moves or by using MOVZX.

对于x64来说,带有32位操作数的MOVZX和MOV是等价的——它们都打破了依赖链。

这就是为什么你的代码执行得更快。如果没有依赖关系,CPU可以在内部重命名寄存器,即使第一眼看起来第二条指令修改了第一条指令使用的寄存器,而且这两条指令不能并行执行。但由于注册重命名,他们可以。

寄存器重命名是CPU内部使用的一种技术,它可以消除由于连续指令重用寄存器而产生的虚假数据依赖关系,这些指令之间没有任何真正的数据依赖关系。

我想你现在明白了,这太明显了。

我相信在现代CPU中,虽然汇编指令是程序员向CPU提供执行指令的最后可见层,但实际上它与CPU的实际执行有好几层。

Modern CPUs are RISC/CISC hybrids that translate CISC x86 instructions into internal instructions that are more RISC in behavior. Additionally there are out-of-order execution analyzers, branch predictors, Intel's "micro-ops fusion" that try to group instructions into larger batches of simultaneous work (kind of like the VLIW/Itanium titanic). There are even cache boundaries that could make the code run faster for god-knows-why if it's bigger (maybe the cache controller slots it more intelligently, or keeps it around longer).

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

额外指令的效果可能取决于CPU型号/代/制造商,而且不太可能是可预测的。以这种方式优化汇编语言将需要针对许多CPU体系结构代执行,可能使用特定于CPU的执行路径,并且只适用于非常非常重要的代码段,尽管如果您正在进行汇编,您可能已经知道这一点。

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

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

Core2不会为每个条件跳转保存单独的历史记录。相反,它保留了所有条件跳转的共享历史。全局分支预测的一个缺点是,如果不同的条件跳跃不相关,历史会被不相关的信息冲淡。

这个分支预测教程展示了分支预测缓冲区是如何工作的。缓存缓冲区是根据分支指令地址的下半部分建立索引的。这工作得很好,除非两个重要的不相关分支共享相同的下位。在这种情况下,您最终会得到别名,这会导致许多错误预测的分支(这会使指令管道停滞并降低程序速度)。

如果您想了解分支的错误预测是如何影响性能的,请查看这个优秀的答案:https://stackoverflow.com/a/11227902/1001643

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