以下 Java 程序平均需要 0.50 秒到 0.55 秒才能运行:
public static void main(String[] args) { long startTime = System.nanoTime(); int n = 0; for (int i = 0; i < 1000000000; i++) { n += 2 * (i * i); } System.out.println((double) (System.nanoTime() - startTime) / 1000000000 + " s"); System.out.println("n = " + n); }
如果我替换2 * (i * i)为2 * i * i,则运行需要 0.60 到 0.65 秒。怎么会?
2 * (i * i)
2 * i * i
我运行程序的每个版本 15 次,在两者之间交替运行。结果如下:
2*(i*i) | 2*i*i ----------+---------- 0.5183738 | 0.6246434 0.5298337 | 0.6049722 0.5308647 | 0.6603363 0.5133458 | 0.6243328 0.5003011 | 0.6541802 0.5366181 | 0.6312638 0.515149 | 0.6241105 0.5237389 | 0.627815 0.5249942 | 0.6114252 0.5641624 | 0.6781033 0.538412 | 0.6393969 0.5466744 | 0.6608845 0.531159 | 0.6201077 0.5048032 | 0.6511559 0.5232789 | 0.6544526
最快的运行2 * i * i时间比最慢的运行时间更长2 * (i * i)。如果它们具有相同的效率,那么发生这种情况的概率将小于1/2^15 * 100% = 0.00305%。
1/2^15 * 100% = 0.00305%
字节码的顺序略有不同。
2 * (i * i):
iconst_2 iload0 iload0 imul imul iadd
与2 * i * i:
iconst_2 iload0 imul iload0 imul iadd
乍一看,这应该没什么区别。如果有的话,第二个版本会更优化,因为它少用了一个插槽。
所以我们需要深入挖掘底层(JIT)1。
请记住,JIT 倾向于非常积极地展开小循环。事实上,我们观察到该案例的 16 倍展开2 * (i * i):
030 B2: # B2 B3 <- B1 B2 Loop: B2-B2 inner main of N18 Freq: 1e+006 030 addl R11, RBP # int 033 movl RBP, R13 # spill 036 addl RBP, #14 # int 039 imull RBP, RBP # int 03c movl R9, R13 # spill 03f addl R9, #13 # int 043 imull R9, R9 # int 047 sall RBP, #1 049 sall R9, #1 04c movl R8, R13 # spill 04f addl R8, #15 # int 053 movl R10, R8 # spill 056 movdl XMM1, R8 # spill 05b imull R10, R8 # int 05f movl R8, R13 # spill 062 addl R8, #12 # int 066 imull R8, R8 # int 06a sall R10, #1 06d movl [rsp + #32], R10 # spill 072 sall R8, #1 075 movl RBX, R13 # spill 078 addl RBX, #11 # int 07b imull RBX, RBX # int 07e movl RCX, R13 # spill 081 addl RCX, #10 # int 084 imull RCX, RCX # int 087 sall RBX, #1 089 sall RCX, #1 08b movl RDX, R13 # spill 08e addl RDX, #8 # int 091 imull RDX, RDX # int 094 movl RDI, R13 # spill 097 addl RDI, #7 # int 09a imull RDI, RDI # int 09d sall RDX, #1 09f sall RDI, #1 0a1 movl RAX, R13 # spill 0a4 addl RAX, #6 # int 0a7 imull RAX, RAX # int 0aa movl RSI, R13 # spill 0ad addl RSI, #4 # int 0b0 imull RSI, RSI # int 0b3 sall RAX, #1 0b5 sall RSI, #1 0b7 movl R10, R13 # spill 0ba addl R10, #2 # int 0be imull R10, R10 # int 0c2 movl R14, R13 # spill 0c5 incl R14 # int 0c8 imull R14, R14 # int 0cc sall R10, #1 0cf sall R14, #1 0d2 addl R14, R11 # int 0d5 addl R14, R10 # int 0d8 movl R10, R13 # spill 0db addl R10, #3 # int 0df imull R10, R10 # int 0e3 movl R11, R13 # spill 0e6 addl R11, #5 # int 0ea imull R11, R11 # int 0ee sall R10, #1 0f1 addl R10, R14 # int 0f4 addl R10, RSI # int 0f7 sall R11, #1 0fa addl R11, R10 # int 0fd addl R11, RAX # int 100 addl R11, RDI # int 103 addl R11, RDX # int 106 movl R10, R13 # spill 109 addl R10, #9 # int 10d imull R10, R10 # int 111 sall R10, #1 114 addl R10, R11 # int 117 addl R10, RCX # int 11a addl R10, RBX # int 11d addl R10, R8 # int 120 addl R9, R10 # int 123 addl RBP, R9 # int 126 addl RBP, [RSP + #32 (32-bit)] # int 12a addl R13, #16 # int 12e movl R11, R13 # spill 131 imull R11, R13 # int 135 sall R11, #1 138 cmpl R13, #999999985 13f jl B2 # loop end P=1.000000 C=6554623.000000
我们看到有 1 个寄存器“溢出”到堆栈上。
对于2 * i * i版本:
05a B3: # B2 B4 <- B1 B2 Loop: B3-B2 inner main of N18 Freq: 1e+006 05a addl RBX, R11 # int 05d movl [rsp + #32], RBX # spill 061 movl R11, R8 # spill 064 addl R11, #15 # int 068 movl [rsp + #36], R11 # spill 06d movl R11, R8 # spill 070 addl R11, #14 # int 074 movl R10, R9 # spill 077 addl R10, #16 # int 07b movdl XMM2, R10 # spill 080 movl RCX, R9 # spill 083 addl RCX, #14 # int 086 movdl XMM1, RCX # spill 08a movl R10, R9 # spill 08d addl R10, #12 # int 091 movdl XMM4, R10 # spill 096 movl RCX, R9 # spill 099 addl RCX, #10 # int 09c movdl XMM6, RCX # spill 0a0 movl RBX, R9 # spill 0a3 addl RBX, #8 # int 0a6 movl RCX, R9 # spill 0a9 addl RCX, #6 # int 0ac movl RDX, R9 # spill 0af addl RDX, #4 # int 0b2 addl R9, #2 # int 0b6 movl R10, R14 # spill 0b9 addl R10, #22 # int 0bd movdl XMM3, R10 # spill 0c2 movl RDI, R14 # spill 0c5 addl RDI, #20 # int 0c8 movl RAX, R14 # spill 0cb addl RAX, #32 # int 0ce movl RSI, R14 # spill 0d1 addl RSI, #18 # int 0d4 movl R13, R14 # spill 0d7 addl R13, #24 # int 0db movl R10, R14 # spill 0de addl R10, #26 # int 0e2 movl [rsp + #40], R10 # spill 0e7 movl RBP, R14 # spill 0ea addl RBP, #28 # int 0ed imull RBP, R11 # int 0f1 addl R14, #30 # int 0f5 imull R14, [RSP + #36 (32-bit)] # int 0fb movl R10, R8 # spill 0fe addl R10, #11 # int 102 movdl R11, XMM3 # spill 107 imull R11, R10 # int 10b movl [rsp + #44], R11 # spill 110 movl R10, R8 # spill 113 addl R10, #10 # int 117 imull RDI, R10 # int 11b movl R11, R8 # spill 11e addl R11, #8 # int 122 movdl R10, XMM2 # spill 127 imull R10, R11 # int 12b movl [rsp + #48], R10 # spill 130 movl R10, R8 # spill 133 addl R10, #7 # int 137 movdl R11, XMM1 # spill 13c imull R11, R10 # int 140 movl [rsp + #52], R11 # spill 145 movl R11, R8 # spill 148 addl R11, #6 # int 14c movdl R10, XMM4 # spill 151 imull R10, R11 # int 155 movl [rsp + #56], R10 # spill 15a movl R10, R8 # spill 15d addl R10, #5 # int 161 movdl R11, XMM6 # spill 166 imull R11, R10 # int 16a movl [rsp + #60], R11 # spill 16f movl R11, R8 # spill 172 addl R11, #4 # int 176 imull RBX, R11 # int 17a movl R11, R8 # spill 17d addl R11, #3 # int 181 imull RCX, R11 # int 185 movl R10, R8 # spill 188 addl R10, #2 # int 18c imull RDX, R10 # int 190 movl R11, R8 # spill 193 incl R11 # int 196 imull R9, R11 # int 19a addl R9, [RSP + #32 (32-bit)] # int 19f addl R9, RDX # int 1a2 addl R9, RCX # int 1a5 addl R9, RBX # int 1a8 addl R9, [RSP + #60 (32-bit)] # int 1ad addl R9, [RSP + #56 (32-bit)] # int 1b2 addl R9, [RSP + #52 (32-bit)] # int 1b7 addl R9, [RSP + #48 (32-bit)] # int 1bc movl R10, R8 # spill 1bf addl R10, #9 # int 1c3 imull R10, RSI # int 1c7 addl R10, R9 # int 1ca addl R10, RDI # int 1cd addl R10, [RSP + #44 (32-bit)] # int 1d2 movl R11, R8 # spill 1d5 addl R11, #12 # int 1d9 imull R13, R11 # int 1dd addl R13, R10 # int 1e0 movl R10, R8 # spill 1e3 addl R10, #13 # int 1e7 imull R10, [RSP + #40 (32-bit)] # int 1ed addl R10, R13 # int 1f0 addl RBP, R10 # int 1f3 addl R14, RBP # int 1f6 movl R10, R8 # spill 1f9 addl R10, #16 # int 1fd cmpl R10, #999999985 204 jl B2 # loop end P=1.000000 C=7419903.000000
在这里,我们观察到更多的“溢出”和对堆栈的更多访问[RSP + ...],因为需要保留更多的中间结果。
[RSP + ...]
因此,问题的答案很简单:2 * (i * i)比2 * i * i因为 JIT 为第一种情况生成更优化的汇编代码而更快。
但当然很明显,第一版和第二版都不好。循环确实可以从矢量化中受益,因为任何 x86-64 CPU 都至少支持 SSE2。
所以这是优化器的问题;通常情况下,它过于激进地展开并射中自己的脚,同时错过了各种其他机会。
事实上,现代 x86-64 CPU 将指令进一步分解为微操作 (μops),并具有寄存器重命名、μop 缓存和循环缓冲区等功能,循环优化比简单展开以获得最佳性能需要更多的技巧。根据 Agner Fog 的优化指南:
如果平均指令长度超过 4 个字节,那么由于 yop 缓存带来的性能提升可能相当可观。可以考虑以下优化 yop 缓存使用的方法: 确保关键循环足够小以适合 ?op 缓存。 将最关键的循环条目和函数条目对齐 32。 避免不必要的循环展开。 避免有额外加载时间的指令 。. .
如果平均指令长度超过 4 个字节,那么由于 yop 缓存带来的性能提升可能相当可观。可以考虑以下优化 yop 缓存使用的方法:
关于那些加载时间——即使是最快的 L1D 命中也要花费 4 个周期、一个额外的寄存器和 oop,所以是的,即使是对内存的几次访问也会损害紧密循环中的性能。
但是回到向量化的机会——看看它有多快,我们可以用 GCC 编译一个类似的 C 应用程序,它完全向量化它(显示了 AVX2,SSE2 类似)2:
vmovdqa ymm0, YMMWORD PTR .LC0[rip] vmovdqa ymm3, YMMWORD PTR .LC1[rip] xor eax, eax vpxor xmm2, xmm2, xmm2 .L2: vpmulld ymm1, ymm0, ymm0 inc eax vpaddd ymm0, ymm0, ymm3 vpslld ymm1, ymm1, 1 vpaddd ymm2, ymm2, ymm1 cmp eax, 125000000 ; 8 calculations per iteration jne .L2 vmovdqa xmm0, xmm2 vextracti128 xmm2, ymm2, 1 vpaddd xmm2, xmm0, xmm2 vpsrldq xmm0, xmm2, 8 vpaddd xmm0, xmm2, xmm0 vpsrldq xmm1, xmm0, 4 vpaddd xmm0, xmm0, xmm1 vmovd eax, xmm0 vzeroupper
随着运行时间:
1 要获取 JIT 生成的程序集输出,请获取调试 JVM并运行-XX:+PrintOptoAssembly
-XX:+PrintOptoAssembly
2 C 版本是使用-fwrapv标志编译的,它使 GCC 能够将有符号整数溢出视为二进制补码环绕。
-fwrapv