3年前 (2022-02-09)  Java系列 |   抢沙发  391 
文章评分 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

关于
上一篇  
下一篇  

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册

繁