在分析最近一个问题的结果时,我遇到了一个非常奇特的现象:显然,HotSpot的JIT优化的额外层实际上减慢了我机器上的执行速度。
这是我用于测量的代码:
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(Measure.ARRAY_SIZE)
@Warmup(iterations = 2, time = 1)
@Measurement(iterations = 5, time = 1)
@State(Scope.Thread)
@Threads(1)
@Fork(2)
public class Measure
{
public static final int ARRAY_SIZE = 1024;
private final int[] array = new int[ARRAY_SIZE];
@Setup public void setup() {
final Random random = new Random();
for (int i = 0; i < ARRAY_SIZE; ++i) {
final int x = random.nextInt();
array[i] = x == 0? 1 : x;
}
}
@GenerateMicroBenchmark public int normalIndex() {
final int[] array = this.array;
int result = 0;
for (int i = 0; i < array.length; i++) {
final int j = i & array.length-1;
final int entry = array[i];
result ^= entry + j;
}
return result;
}
@GenerateMicroBenchmark public int maskedIndex() {
final int[] array = this.array;
int result = 0;
for (int i = 0; i < array.length; i++) {
final int j = i & array.length-1;
final int entry = array[j];
result ^= entry + i;
}
return result;
}
@GenerateMicroBenchmark public int normalWithExitPoint() {
final int[] array = this.array;
int result = 0;
for (int i = 0; i < array.length; i++) {
final int j = i & array.length-1;
final int entry = array[i];
result ^= entry + j;
if (entry == 0) break;
}
return result;
}
@GenerateMicroBenchmark public int maskedWithExitPoint() {
final int[] array = this.array;
int result = 0;
for (int i = 0; i < array.length; i++) {
final int j = i & array.length-1;
final int entry = array[j];
result ^= entry + i;
if (entry == 0) break;
}
return result;
}
}
代码非常微妙,所以让我指出重要的部分:
- "正常索引"变体使用数组索引的直接变量
i
。HotSpot可以轻松确定整个循环中的i
范围,并消除数组边界检查; - "掩蔽索引"变体按
j
索引,实际上等于i
,但这一事实通过 AND 掩蔽操作对热点"隐藏">
; - "带出口点"变体引入了显式循环出口点。下面将解释这一点的重要性。
循环展开和重新排序
请注意,边界检查数字有两个重要方式:
- 它具有与之关联的运行时开销(比较后跟条件分支);
- 它构成了一个循环出口点,可以在任何步骤中断循环。事实证明,这对适用的 JIT 优化具有重要影响。
通过检查上述四种方法发出的机器代码,我注意到以下几点:
- 在所有情况下,循环都是展开的;
- 在
normalIndex
的情况下,它被区分为唯一没有过早循环退出点的,所有展开步骤的操作被重新排序,以便首先执行所有数组提取,然后将所有值异或到累加器中。
预期和实际测量结果
现在我们可以根据讨论的特征对四种方法进行分类:
normalIndex
没有边界检查,也没有循环出口点;normalWithExitPoint
没有边界检查和 1 个退出点;maskedIndex
有 1 个边界检查和 1 个退出点;maskedWithExitPoint
有 1 个边界检查和 2 个退出点。
显而易见的期望是,上面的列表应该按性能降序呈现方法;但是,这些是我的实际结果:
Benchmark Mode Samples Mean Mean error Units
normalIndex avgt 20 0.946 0.010 ns/op
normalWithExitPoint avgt 20 0.807 0.010 ns/op
maskedIndex avgt 20 0.803 0.007 ns/op
maskedWithExitPoint avgt 20 1.007 0.009 ns/op
normalWithExitPoint
和maskedIndex
是相同的模测量误差,即使只有后者具有边界检查;- 最大的异常是在
normalIndex
上观察到的,这应该是最快的,但明显比normalWithExitPoint
慢,除了多了一行代码,即引入退出点的代码之外,在各个方面都与它相同。
由于normalIndex
是唯一应用了额外重新排序"优化"的方法,因此结论是这是导致速度变慢的原因。
我正在测试:
Java HotSpot(TM) 64-Bit Server VM (build 24.0-b56, mixed mode)
(Java 7 更新 40)- OS X 版本 10.9.1
- 2.66 GHz 英特尔酷睿 i7
我也成功地在Java 8 EA b118上重现了结果。
我的问题:
上述现象是否可以在其他类似的机器上重现?从开头提到的问题中,我已经暗示至少某些机器不会重现它,因此来自同一CPU的另一个结果将非常有趣。
更新1:更多受maaartinus发现启发的测量
我收集了下表,该表将执行时间与-XX:LoopUnrollLimit
命令行参数相关联。在这里,我只关注两个变体,带和不带if (entry == 0) break;
行:
LoopUnrollLimit: 14 15 18 19 22 23 60
withExitPoint: 96 95 95 79 80 80 69 1/100 ns
withoutExitPoint: 94 64 64 63 64 77 75 1/100 ns
可以观察到以下突然变化:
在从 14 到 15 的过渡中,
withoutExitPoint
变体获得了有益的 LCM1转换并显着加快了速度。由于循环展开限制,所有加载的值都适合寄存器;在 18->19 上,
withExitPoint
变体获得加速比,小于上述;在 22->23 上,
withoutExitPoint
变体减速。在这一点上,我看到溢出到堆栈位置,正如maaartinus的回答中所描述的那样,开始发生。
我的设置的默认loopUnrollLimit
是 60,因此我在最后一列中显示其结果。
1LCM = 本地代码运动。正是这种转换导致所有数组访问都在顶部发生,然后处理加载的值。
更新 2:这实际上是一个已知的、报告的问题
https://bugs.openjdk.java.net/browse/JDK-7101232
附录:机器代码中normalIndex
的展开和重新排序循环
0x00000001044a37c0: mov ecx,eax
0x00000001044a37c2: and ecx,esi ;*iand
; - org.sample.Measure::normalIndex@20 (line 44)
0x00000001044a37c4: mov rbp,QWORD PTR [rsp+0x28] ;*iload_3
; - org.sample.Measure::normalIndex@15 (line 44)
0x00000001044a37c9: add ecx,DWORD PTR [rbp+rsi*4+0x10]
0x00000001044a37cd: xor ecx,r8d
0x00000001044a37d0: mov DWORD PTR [rsp],ecx
0x00000001044a37d3: mov r10d,esi
0x00000001044a37d6: add r10d,0xf
0x00000001044a37da: and r10d,eax
0x00000001044a37dd: mov r8d,esi
0x00000001044a37e0: add r8d,0x7
0x00000001044a37e4: and r8d,eax
0x00000001044a37e7: mov DWORD PTR [rsp+0x4],r8d
0x00000001044a37ec: mov r11d,esi
0x00000001044a37ef: add r11d,0x6
0x00000001044a37f3: and r11d,eax
0x00000001044a37f6: mov DWORD PTR [rsp+0x8],r11d
0x00000001044a37fb: mov r8d,esi
0x00000001044a37fe: add r8d,0x5
0x00000001044a3802: and r8d,eax
0x00000001044a3805: mov DWORD PTR [rsp+0xc],r8d
0x00000001044a380a: mov r11d,esi
0x00000001044a380d: inc r11d
0x00000001044a3810: and r11d,eax
0x00000001044a3813: mov DWORD PTR [rsp+0x10],r11d
0x00000001044a3818: mov r8d,esi
0x00000001044a381b: add r8d,0x2
0x00000001044a381f: and r8d,eax
0x00000001044a3822: mov DWORD PTR [rsp+0x14],r8d
0x00000001044a3827: mov r11d,esi
0x00000001044a382a: add r11d,0x3
0x00000001044a382e: and r11d,eax
0x00000001044a3831: mov r9d,esi
0x00000001044a3834: add r9d,0x4
0x00000001044a3838: and r9d,eax
0x00000001044a383b: mov r8d,esi
0x00000001044a383e: add r8d,0x8
0x00000001044a3842: and r8d,eax
0x00000001044a3845: mov DWORD PTR [rsp+0x18],r8d
0x00000001044a384a: mov r8d,esi
0x00000001044a384d: add r8d,0x9
0x00000001044a3851: and r8d,eax
0x00000001044a3854: mov ebx,esi
0x00000001044a3856: add ebx,0xa
0x00000001044a3859: and ebx,eax
0x00000001044a385b: mov ecx,esi
0x00000001044a385d: add ecx,0xb
0x00000001044a3860: and ecx,eax
0x00000001044a3862: mov edx,esi
0x00000001044a3864: add edx,0xc
0x00000001044a3867: and edx,eax
0x00000001044a3869: mov edi,esi
0x00000001044a386b: add edi,0xd
0x00000001044a386e: and edi,eax
0x00000001044a3870: mov r13d,esi
0x00000001044a3873: add r13d,0xe
0x00000001044a3877: and r13d,eax
0x00000001044a387a: movsxd r14,esi
0x00000001044a387d: add r10d,DWORD PTR [rbp+r14*4+0x4c]
0x00000001044a3882: mov DWORD PTR [rsp+0x24],r10d
0x00000001044a3887: mov QWORD PTR [rsp+0x28],rbp
0x00000001044a388c: mov ebp,DWORD PTR [rsp+0x4]
0x00000001044a3890: mov r10,QWORD PTR [rsp+0x28]
0x00000001044a3895: add ebp,DWORD PTR [r10+r14*4+0x2c]
0x00000001044a389a: mov DWORD PTR [rsp+0x4],ebp
0x00000001044a389e: mov r10d,DWORD PTR [rsp+0x8]
0x00000001044a38a3: mov rbp,QWORD PTR [rsp+0x28]
0x00000001044a38a8: add r10d,DWORD PTR [rbp+r14*4+0x28]
0x00000001044a38ad: mov DWORD PTR [rsp+0x8],r10d
0x00000001044a38b2: mov r10d,DWORD PTR [rsp+0xc]
0x00000001044a38b7: add r10d,DWORD PTR [rbp+r14*4+0x24]
0x00000001044a38bc: mov DWORD PTR [rsp+0xc],r10d
0x00000001044a38c1: mov r10d,DWORD PTR [rsp+0x10]
0x00000001044a38c6: add r10d,DWORD PTR [rbp+r14*4+0x14]
0x00000001044a38cb: mov DWORD PTR [rsp+0x10],r10d
0x00000001044a38d0: mov r10d,DWORD PTR [rsp+0x14]
0x00000001044a38d5: add r10d,DWORD PTR [rbp+r14*4+0x18]
0x00000001044a38da: mov DWORD PTR [rsp+0x14],r10d
0x00000001044a38df: add r13d,DWORD PTR [rbp+r14*4+0x48]
0x00000001044a38e4: add r11d,DWORD PTR [rbp+r14*4+0x1c]
0x00000001044a38e9: add r9d,DWORD PTR [rbp+r14*4+0x20]
0x00000001044a38ee: mov r10d,DWORD PTR [rsp+0x18]
0x00000001044a38f3: add r10d,DWORD PTR [rbp+r14*4+0x30]
0x00000001044a38f8: mov DWORD PTR [rsp+0x18],r10d
0x00000001044a38fd: add r8d,DWORD PTR [rbp+r14*4+0x34]
0x00000001044a3902: add ebx,DWORD PTR [rbp+r14*4+0x38]
0x00000001044a3907: add ecx,DWORD PTR [rbp+r14*4+0x3c]
0x00000001044a390c: add edx,DWORD PTR [rbp+r14*4+0x40]
0x00000001044a3911: add edi,DWORD PTR [rbp+r14*4+0x44]
0x00000001044a3916: mov r10d,DWORD PTR [rsp+0x10]
0x00000001044a391b: xor r10d,DWORD PTR [rsp]
0x00000001044a391f: mov ebp,DWORD PTR [rsp+0x14]
0x00000001044a3923: xor ebp,r10d
0x00000001044a3926: xor r11d,ebp
0x00000001044a3929: xor r9d,r11d
0x00000001044a392c: xor r9d,DWORD PTR [rsp+0xc]
0x00000001044a3931: xor r9d,DWORD PTR [rsp+0x8]
0x00000001044a3936: xor r9d,DWORD PTR [rsp+0x4]
0x00000001044a393b: mov r10d,DWORD PTR [rsp+0x18]
0x00000001044a3940: xor r10d,r9d
0x00000001044a3943: xor r8d,r10d
0x00000001044a3946: xor ebx,r8d
0x00000001044a3949: xor ecx,ebx
0x00000001044a394b: xor edx,ecx
0x00000001044a394d: xor edi,edx
0x00000001044a394f: xor r13d,edi
0x00000001044a3952: mov r8d,DWORD PTR [rsp+0x24]
0x00000001044a3957: xor r8d,r13d ;*ixor
; - org.sample.Measure::normalIndex@34 (line 46)
0x00000001044a395a: add esi,0x10 ;*iinc
; - org.sample.Measure::normalIndex@36 (line 43)
0x00000001044a395d: cmp esi,DWORD PTR [rsp+0x20]
0x00000001044a3961: jl 0x00000001044a37c0 ;*if_icmpge
; - org.sample.Measure::normalIndex@12 (line 43)
JITC 试图将所有内容组合在一起的原因对我来说相当不清楚。AFAIK 有一些(曾经?)架构,其中两个负载的分组会带来更好的性能(我认为是一些早期的奔腾)。
由于 JITC 知道热点,因此它可以比提前编译器更积极地内联,因此在这种情况下它会执行 16 次。我在这里看不到任何明显的优势,除了使循环相对便宜。我也怀疑是否有任何架构可以从将 16 个负载组合在一起中获利。
该代码计算 16 个临时值,每次迭代一个
int j = i & array.length-1;
int entry = array[i];
int tmp = entry + j;
result ^= tmp;
每个计算都非常简单,一个 AND,一个 LOAD,一个 ADD。这些值将映射到寄存器,但数量还不够。因此,这些值必须在以后存储和加载。
16个寄存器中有7个会发生这种情况,并大大增加了成本。
更新
我不太确定是否使用-XX:LoopUnrollLimit
来验证这一点:
LoopUnrollLimit Benchmark Mean Mean error Units
8 ..normalIndex 0.902 0.004 ns/op
8 ..normalWithExitPoint 0.913 0.005 ns/op
8 ..maskedIndex 0.918 0.006 ns/op
8 ..maskedWithExitPoint 0.996 0.008 ns/op
16 ..normalIndex 0.769 0.003 ns/op
16 ..normalWithExitPoint 0.930 0.004 ns/op
16 ..maskedIndex 0.937 0.004 ns/op
16 ..maskedWithExitPoint 1.012 0.003 ns/op
32 ..normalIndex 0.814 0.003 ns/op
32 ..normalWithExitPoint 0.816 0.005 ns/op
32 ..maskedIndex 0.838 0.003 ns/op
32 ..maskedWithExitPoint 0.978 0.002 ns/op
- ..normalIndex 0.830 0.002 ns/op
- ..normalWithExitPoint 0.683 0.002 ns/op
- ..maskedIndex 0.791 0.005 ns/op
- ..maskedWithExitPoint 0.908 0.003 ns/op
16 的限制使normalIndex
成为最快的变体,这表明我对"过度分配惩罚"是正确的。Bur 根据 Marko 的说法,生成的组件在其他方面也随着展开限制而变化,因此事情更加复杂。