Background:
在使用嵌入式汇编语言优化某些Pascal代码时,我注意到了一条不必要的 MOV
指令,并将其删除了 .
令我惊讶的是,删除不必要的指令导致我的程序变慢 .
我发现 adding arbitrary, useless MOV instructions increased performance 更进一步 .
效果不稳定,并根据执行顺序进行更改: the same junk instructions transposed 向上或向下一行 produce a slowdown .
我知道CPU会进行各种优化和精简,但这看起来更像是黑魔法 .
The data:
我的代码版本有条件地在运行 2**20==1048576
次的循环中编译 three junk operations . (周围的程序只计算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次,每次运行顺序随机变化 .
Excerpt:
{$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;
Try it yourself:
如果您想自己试用,代码在线at GitHub .
My questions:
-
为什么无用地将寄存器的内容复制到RAM会不会提高性能?
-
为什么同样无用的指令会在某些线路上提供加速,而在其他线路上则会减速?
-
这种行为是否可以被编译器可预测地利用?
4 回答
速度提升的最可能原因是:
插入MOV会将后续指令移至不同的存储器地址
其中一个移动的指令是一个重要的条件分支
由于分支预测表中的别名而错误地预测了该分支
移动分支消除了别名并允许正确预测分支
您的Core2没有为每个条件跳转保留单独的历史记录 . 相反,它保留了所有条件跳转的共享历史记录 . global branch prediction的一个缺点是,如果不同的条件跳跃是不相关的,则历史被无关信息稀释 .
这个小branch prediction tutorial显示了分支预测缓冲区如何工作 . 缓存缓冲区由分支指令的地址的下部索引 . 除非两个重要的不相关分支共享相同的低位,否则这很有效 . 在这种情况下,您最终会出现别名,这会导致许多错误预测的分支(这会拖延指令管道并减慢程序速度) .
如果您想了解分支错误预测如何影响性能,请看一下这个优秀的答案:https://stackoverflow.com/a/11227902/1001643
编译器通常没有足够的信息来知道哪些分支将是别名,以及这些别名是否重要 . 但是,可以使用Cachegrind和VTune等工具在运行时确定该信息 .
你可能想看http://research.google.com/pubs/pub37077.html
TL; DR:在程序中随机插入nop指令可以轻松地将性能提高5%或更多,不,编译器不能轻易利用它 . 它通常是分支预测器和缓存行为的组合,但它也可以是例如保留站停止(即使在没有任何依赖链被破坏或明显的资源超额预订的情况下) .
我相信现代CPU中的汇编指令虽然是程序员向CPU提供执行指令的最后一个可见层,但实际上是CPU实际执行的几个层 .
现代CPU是RISC / CISC混合体,它们将CISC x86指令转换为更符合RISC行为的内部指令 . 此外,还有无序执行分析器,分支预测器,英特尔"micro-ops fusion"试图将指令分组到更大批量的同时工作(有点像VLIW / Itanium泰坦尼克号) . 甚至有缓存边界可以使代码运行得更快,因为上帝知道 - 为什么如果它更大(可能是缓存控制器更智能地插槽,或保持更长时间) .
CISC一直有一个汇编到微代码转换层,但重点是现代CPU的事情要复杂得多 . 利用现代半导体制造工厂中所有额外的晶体管空间,CPU可以并行应用多种优化方法,然后在最后选择提供最佳加速的方法 . 额外的指令可能偏向CPU以使用一个比其他更好的优化路径 .
额外指令的效果可能取决于CPU型号/生成/制造商,并且不太可能是可预测的 . 以这种方式优化汇编语言需要针对许多CPU架构生成执行,可能使用特定于CPU的执行路径,并且仅对于非常重要的代码段而言是理想的,尽管如果您正在进行汇编,您可能已经知道了 .
准备缓存
将操作移动到内存可以准备缓存并使后续的移动操作更快 . CPU通常有两个加载单元和一个存储单元 . 加载单元可以从存储器读入寄存器(每个周期读取一个),存储单元从寄存器存储到存储器 . 还有其他单元在寄存器之间进行操作 . 所有单位并行工作 . 因此,在每个循环中,我们可以同时执行多个操作,但不超过两个加载,一个存储和多个寄存器操作 . 通常,使用普通寄存器最多可进行4次简单操作,使用XMM / YMM寄存器最多可进行3次简单操作,使用任何类型的寄存器进行1-2次复杂操作 . 您的代码对寄存器进行了大量操作,因此一个虚拟内存存储操作是免费的(因为无论如何都有超过4个寄存器操作),但它为后续存储操作准备了内存高速缓存 . 要了解内存存储的工作原理,请参阅Intel 64 and IA-32 Architectures Optimization Reference Manual .
打破错误的依赖关系
虽然这并不完全是指你的情况,但有时在64位处理器下使用32位mov操作(如你的情况)用于清除高位(32-63)并打破依赖链 .
众所周知,在x86-64下,使用32位操作数清除64位寄存器的高位 . 请阅读Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 1的相关章节 - 3.4.1.1 - :
因此,第一眼看上去似乎毫无用处的mov指令清除了适当寄存器的高位 . 它给我们的是什么?它打破了依赖链并允许指令以随机顺序并行执行,自1995年Pentium Pro以来由CPU内部实现的Out-of-Order algorithm .
来自Intel® 64 and IA-32 Architectures Optimization Reference Manual的报价,第3.5.1.8节:
具有32位x64操作数的MOVZX和MOV是等效的 - 它们都会破坏依赖链 .
这就是你的代码执行速度更快的原因 . 如果没有依赖关系,CPU可以在内部重命名寄存器,即使初看起来第二条指令似乎修改了第一条指令使用的寄存器,并且两条指令不能并行执行 . 但由于注册重命名,他们可以 .
Register renaming是一种由CPU内部使用的技术,它消除了由连续指令重用寄存器引起的错误数据依赖性,这些指令之间没有任何实际数据依赖性 .
我想你现在看到它太明显了 .