4个月前 (02-09)  Java系列 |   抢沙发  75 
文章评分 0 次,平均分 0.0

Joshua Bloch 在推特上发了一个链接(http://igoro.com/archive/gallery-of-processor-cache-effects/),使用高级编程语言(如C#)演示了CPU缓存的效果。强烈推荐!

Java演示CPU级的缓存效果

那我们能否在Java中演示同样的效果呢?乍一看,这种可能性对我们不利:Java不是编译成本机代码,而是编译成中间字节码,而中间字节码可能会编译成本机代码,也可能不会编译成本机代码(取决于具体情况,例如JIT)。那么,我们能在Java程序中显示缓存效果吗?

是的,可以!

当心局部优化

在继续之前,我想提醒大家关于局部优化的问题。这篇文章向你展示了如何在一个非常初级的层次上优化你的程序。这很有趣,也很有启发性,但大多数情况下,将知识应用到实际应用中是浪费时间。首先,现实世界中的应用程序通常可以通过全局优化得到更好的优化。大多数情况下,你可以用更好的算法来代替算法。其次,局部优化是一种可以由编译器自动完成的优化。让他们去做吧。

然而,本文让您更好地了解Java是如何在处理器上运行的。

一个简单的问题

Igor Ostrovsky以一个简单的问题开始他的文章:以下哪种方法运行得更快?

public class CacheLines {
  private static int[] array = new int[64 * 1024 * 10];

  private static void loop1() {
    int length = array.length;
    for (int i = 0; i < length; i=i+1)
      array[i] --;
  }

  private static void loop2() {
    int length = array.length;
    for (int i = 0; i < length; i += 2)
      array[i] --;
  }
}

令我惊讶的是,第一种方法是快速的。它的工作量是原来的两倍,但速度更快。

我还用更大的增量步骤实现了这个方法,一直到loop128,它的增量是128。以下是我的台式电脑的结果:

Step   1/10000 took 1250.627 ms  that's  100% of the expected time
Step   2/10000 took 1668.458 ms  that's  266% of the expected time
Step   4/10000 took 1159.842 ms  that's  370% of the expected time
Step   8/10000 took 1039.095 ms  that's  664% of the expected time
Step  16/10000 took 1022.674 ms  that's 1308% of the expected time
Step  32/10000 took  530.95  ms  that's 1358% of the expected time
Step  64/10000 took  272.518 ms  that's 1394% of the expected time
Step 128/10000 took  138.968 ms  that's 1422% of the expected time
Step 256/10000 took  100.921 ms  that's 2065% of the expected time

在第16步之前,程序的运行速度或多或少与第1步版本相同。这就是缓存线的效果。我建议读一下原文的解释(http://igoro.com/archive/gallery-of-processor-cache-effects/)。相反,我想把重点放在JVM的特性上。

检查汇编代码

JVM的一个更有趣、也是相当未知的特性是,您可以看到优化器在工作,一直到机器代码。添加JVM选项-XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly会输出您该方法的源代码:

0x00000000027f0f69: dec     dword ptr [r10+r13*4+10h]
                                                ;*iastore
                                                ; - CacheLines::loop1@18 (line 199)
  0x00000000027f0f6e: inc     r13d              ;*iinc
                                                ; - CacheLines::loop1@19 (line 198)
  0x00000000027f0f71: cmp     r13d,r9d
  0x00000000027f0f74: jl      27f0f69h          ;*if_icmplt
                                                ; - CacheLines::loop1@24 (line 198)

说实话,编译器发出的代码要多得多——总共有72条指令(从JDK 1.7.0 U55开始)。有代码可以同步多个线程,有代码可以在JVM的假设被证明是错误的情况下对机器代码进行去优化,而且可能会更糟。然而,这四条指令才是最重要的。它们是for循环:

for (int i = 0; i < length; i += 2)
      array[i] --;

让我们逐行分析代码。有些准备工作我没有展示。当CPU到达代码段时,它的寄存器[1]r10指向整数数组的开头。r13是计数器,即Java代码中的变量i。它的初始值是0。r9d包含数组的长度。

1. dec dword ptr [r10+r13*4+10h]这是最复杂的线路,也是最让我惊讶的线路。整个行数组[i]——可以用一个操作码来表示。r10+10h是指向字节数组的指针,r13*4是数组内的偏移量。按照惯例,方括号指的是由括号内的数字指示的存储单元。所以dec[r10+r13+10h]取整数数组的一个值,将其递减,并将其写回内存。

2. inc r13d递增循环计数器(变量i)。

3. cmp r13d、r9d检查是否已到达回路末端。

4. jl 27f0f69h是一个有条件的转到。根据之前的检查,指令指针被设置回四条指令,再次运行循环。

loop2()的运行速度比loop1()慢了一点,所以我们也应该检查机器代码。也许有一个奇怪的优化?

0x00000000027f1508: dec     dword ptr [r11+rbx*4+10h]
                                              ;*iastore
                                              ; - CacheLines::loop2@18 (line 205)
0x00000000027f150d: add     ebx,2h            ;*iinc
                                              ; - CacheLines::loop2@19 (line 204)
0x00000000027f1510: cmp     ebx,r10d
0x00000000027f1513: jl      27f1508h          ;*if_icmplt
                                              ; - CacheLines::loop2@24 (line 204)

代码几乎相同。唯一的区别是循环计数器不是递增的,而是增加的。这需要我们使用不同的操作码add,它的效率比inc稍低,因为它需要一个参数。

所以我们可以断定生成的代码没有问题。恰恰相反,这是最好的。也许一个努力计算CPU周期的机器代码程序员可以更好地优化代码,但它已经相当不错了。

step 计数

当我们不使用固定的step步长,而是将它们放在一个变量中时,我们会感到惊讶:

private static void testVariableStep(final int step) {
    long start3 = System.nanoTime();
    loopVariableStep(step);
    long time3 = System.nanoTime() - start3;
    cumulated3 += time3;
  }
  private static void loopVariableStep(final int step) {
    int length = array.length;
    for (int i = 0; i < length; i += step)
      array[i]--;
}

程序的运行速度大大降低,至少对于低阶数来说是如此。第一个循环比静态循环慢四倍。另外,前三个循环占用的时间并不相同,但它们可以线性扩展。在那之后,在时间再次线性扩展之前,似乎存在缓存效应:

Step   1/10000 took 5363.778 ms  that's 100% of the expected time
Step   2/10000 took 2703.319 ms  that's 100% of the expected time
Step   4/10000 took 1428.127 ms  that's 106% of the expected time
Step   8/10000 took 1024.124 ms  that's 152% of the expected time
Step  16/10000 took  985.169 ms  that's 293% of the expected time
Step  32/10000 took  492.46  ms  that's 293% of the expected time
Step  64/10000 took  250.679 ms  that's 299% of the expected time
Step 128/10000 took  122.265 ms  that's 291% of the expected time
Step 256/10000 took   69.627 ms  that's 332% of the expected time

所以我的第一个猜测是step参数有问题。显然,step变量需要从主存中反复读取。

错误的step变量存储在CPU寄存器(edx)中,因此算法仍然非常快速。问题完全出乎意料:

0x00000000027404b0: cmp     r9d,r10d
0x00000000027404b3: jnb     27404d4h          ;*iaload
                                              ; - CacheLines::loopVariableStep@15 (line 295)
0x00000000027404b5: dec     dword ptr [r11+r9*4+10h]
                                              ;*if_icmplt
                                              ; - CacheLines::loopVariableStep@25 (line 294)
0x00000000027404ba: add     r9d,edx           ; OopMap{r11=Oop rbp=NarrowOop off=61}
                                              ;*if_icmplt
                                              ; - CacheLines::loopVariableStep@25 (line 294)
0x00000000027404bd: test    dword ptr [120000h],eax  ;   {poll}
0x00000000027404c3: cmp     r9d,r10d
0x00000000027404c6: jl      27404b0h          ;*synchronization entry
                                              ; - CacheLines::loopVariableStep@-1 (line 293)

有两件事很奇怪:

  • 比较i < length执行两次(cmp r9、r10d,然后在第1-2行和第11-12行进行条件跳转)。如果需要,第一次检查会引发IndexOutOfBoundsException。重复的支票并不能解释差异。它只增加了几个CPU周期。先进的CPU技术,如无序执行和分支预测,可以几乎完全消除性能损失。[2]
  • 有一个测试似乎什么都没做。

测试比较参数,并设置条件分支可以使用的许多CPU标志。但是,这些标志会在下一行中被覆盖:cmp r9, r10d (aka i < length)

测试说明的目的是添加所谓的safe-point(安全点)。safe-point允许JVM执行垃圾收集之类的任务。因此,JVM每隔一段时间就会添加指令来调用负责垃圾收集的VM线程。Oracle的JVM以一种巧妙的方式实现了这一点:测试指令访问虚拟内存页中的一个内存单元,JVM可以取消该单元的映射。当JVM认为是时候进行同样的垃圾收集时,它会取消映射虚拟内存页,并等待每个线程都遇到异常。阅读Alexey Ragozin关于HotSpot JVM中safe-point的文章中的全部细节(http://blog.ragozin.info/2012/10/safepoints-in-hotspot-jvm.html)。

如果缓存了内存单元,则检查安全点标志没有太大意义。因此,每个循环都会导致缓存未命中,即访问真实内存,这反过来会降低性能。

循环展开

循环展开是你永远不应该自己实现的想法之一。这是一个典型的JVM任务。然而,在这种情况下,JVM不会自行展开循环,所以如果我们自己展开循环,看看会发生什么可能会很有趣。

private static void loopVariableStepWithLoopUnrolling(final int step) {
  int length = array.length;
  for (int i = 0; i < length;) {
    array[i]--;
    i += step;
    array[i]--;
    i += step;
  }
}

结果并不那么令人信服:

Step 1/10000 took 3216.271 ms  that's 100% of the expected time
Step 2/10000 took 1828.833 ms  that's 113% of the expected time
Step 4/10000 took 1234.583 ms  that's 153% of the expected time
Step 8/10000 took 992.342 ms  that's 246% of the expected time
Step 16/10000 took 982.522 ms  that's 488% of the expected time
Step 32/10000 took 495.244 ms  that's 492% of the expected time
Step 64/10000 took 251.165 ms  that's 499% of the expected time
Step 128/10000 took 122.601 ms  that's 487% of the expected time
Step 256/10000 took 86.526 ms  that's 688% of the expected time

安全点(safe-point)测试较少,因此对于较小的步数,循环运行得更快,但对于较高的增量,方法运行得更慢。这可能是由于内部的CPU架构:它可以优化小循环,而不是更大的循环。另外,JIT不知道你的意图。看看代码,我很确定一个汇编程序员可以对其进行大量优化,从而使循环展开变得有利可图。但Java程序员几乎从未成功过。

那么优化编译器呢?

令我惊讶的是,SUN和Oracle都没有实现过优化字节码编译器。他们把它留给JIT。JIT进行了一些优化——例如方法内联、逃逸分析、循环展开等等。JIT非常好地优化了代码。不幸的是,它受到必须在运行时进行分析的限制。人类程序员直觉地注意到,循环永远不会引发ArrayIndexOutOfBoundsException。所以他们可以省略检查cmp r9,r10d。我想实现一个优化字节码编译器也是可能的。使用循环展开的手动优化版本看起来与JIT生成的版本有很大不同:

              mov     r12, 100h
START_OF_LOOP: dec     dword ptr [r11+r9*4+10h]
               add     r9d,edx           
               ; we know there's no array bounds check needed!
               dec     dword ptr [r11+r9*4+10h]
               add     r9d,edx  
               dec     r12
               jnz     CHECK_END_OF_LOOP         
               test    dword ptr [120000h],eax  ;   {poll}
               mov     r12, 100h
CHECK_END_OF_LOOP:
               cmp     r9d,r10d
               jl      START_OF_LOOP

你能把这些知识应用到日常编程中吗?几乎不

我上面展示的示例是一个非常特殊的情况,很少出现在业务代码中。这个例子不适用于对象数组:Java对对象数组使用了一个有点奇怪的内存模型。

整数数组只是包含该数组的内存块。第一个整数使用第一个可用内存单元(字节16-19),第二个整数使用第二个可用内存单元(字节20-23),依此类推。

对象数组看起来很相似。区别在于数组不包含实际对象,而是指向对象的指针。当程序员调用新语句时,对象本身被分配。换句话说:对象没有可预测的内存布局。更有可能的是,对象在堆内存中随机分布。换句话说:接触数组中每个对象的循环最有可能遭受大量缓存未命中。

顺便说一句,这就是Brian Goetz和他的团队希望向Java添加值类型的原因之一。值类型的数组具有缓存友好的线性内存布局。

其他缓存效果

你注意到我只讨论了一个缓存效果了吗?这是一个有趣的效果,因为缓存线是广为人知的,但还有很多需要发现。Igor Ostrovsky还演示了缓存大小和缓存关联性的影响。我还不能用Java重现他的例子,所以我没有把它们包括在本文中。

Java的一个关键点是让程序员远离硬件(或者反过来说?)。它在虚拟机上运行,编译成字节码,曾经它只作为解释器语言运行。

时代变了!如今,可以一直跟踪处理器,直到机器编程级别。虽然这并不能让你成为一名更好的程序员,但它会给你一些未来可能有用的背景信息。

  
 

除特别注明外,本站所有文章均为老K的Java博客原创,转载请注明出处来自https://javakk.com/2573.html

关于

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册