224

背景:

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

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

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

效果是不稳定的,并且会根据执行顺序进行更改:由单行向上或向下转置的相同垃圾指令会产生减速

我知道 CPU 做了各种优化和精简,但是,这似乎更像是黑魔法。

数据:

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

在我相当旧的机器(Intel(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会提高性能?
  • 为什么相同的无用指令会在某些线路上提供加速,而在其他线路上提供减速?
  • 这种行为是否可以被编译器可预测地利用?
4

4 回答 4

146

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

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

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

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

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

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

于 2013-07-28T08:52:41.047 回答
80

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

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

于 2013-07-27T11:33:03.123 回答
15

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

现代 CPU 是RISC / CISC混合体,可将 CISC x86 指令转换为行为更符合 RISC 的内部指令。此外,还有乱序执行分析器、分支预测器、英特尔的“微操作融合”,它们试图将指令分组为更大批量的同时工作(有点像VLIW / Itanium Titanic)。甚至有缓存边界可以使代码运行得更快,因为上帝知道为什么如果它更大(也许缓存控制器更智能地插入它,或者让它保持更长时间)。

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

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

于 2013-07-27T17:59:25.663 回答
0

准备缓存

将操作移动到内存可以准备缓存并使后续的移动操作更快。一个 CPU 通常有两个加载单元和一个存储单元。加载单元可以从内存读取到寄存器(每个周期读取一次),存储单元从寄存器存储到内存。还有其他单元在寄存器之间进行操作。所有单元并行工作。因此,在每个循环中,我们可能一次执行多个操作,但最多不能超过两次加载、一次存储和多次寄存器操作。通常使用普通寄存器最多可以进行 4 次简单操作,使用 XMM/YMM 寄存器最多可以进行 3 次简单操作,使用任何类型的寄存器最多可以进行 1-2 次复杂操作。您的代码有很多寄存器操作,所以一个虚拟内存存储操作是免费的(因为无论如何有超过 4 个寄存器操作),但它会为后续的存储操作准备内存缓存。要了解内存存储的工作原理,请参阅Intel 64 和 IA-32 架构优化参考手册

打破虚假的依赖关系

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

众所周知,在 x86-64 下,使用 32 位操作数会清除 64 位寄存器的高位。请阅读英特尔® 64 和 IA-32 架构软件开发人员手册第 1 卷的相关部分 - 3.4.1.1 :

32 位操作数生成 32 位结果,在目标通用寄存器中零扩展为 64 位结果

因此,初看起来似乎无用的 mov 指令会清除相应寄存器的较高位。它给了我们什么?自 1995 年 Pentium Pro 以来,它通过 CPU 内部实现的乱序算法打破了依赖链并允许指令以随机顺序并行执行。

引自英特尔® 64 和 IA-32 架构优化参考手册,第 3.5.1.8 节:

修改部分寄存器的代码序列可能会在其依赖链中遇到一些延迟,但可以通过使用依赖破坏惯用语来避免。在基于 Intel Core 微架构的处理器中,当软件使用这些指令将寄存器内容清零时,许多指令可以帮助清除执行依赖性。通过对 32 位寄存器而不是部分寄存器进行操作,打破指令之间对部分寄存器的依赖关系。对于移动,这可以通过 32 位移动或使用 MOVZX 来完成。

汇编/编译器编码规则 37。(M 影响,MH 通用性):通过对 32 位寄存器而不是部分寄存器进行操作,打破指令之间对寄存器部分的依赖关系。对于移动,这可以通过 32 位移动或使用 MOVZX 来完成。

x64 的 MOVZX 和具有 32 位操作数的 MOV 是等效的——它们都破坏了依赖链。

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

寄存器重命名是 CPU 内部使用的一种技术,它消除了由连续指令重用寄存器引起的错误数据依赖性,这些指令之间没有任何实际数据依赖性。

我想你现在看到它太明显了。

于 2017-05-14T14:41:01.583 回答