JVM优化之循环展开

在JVM内部实现系列的前几篇文章中，我们已经看到了Java的HotSpot虚拟机的just-in-time (JIT)编译技术，包括逃逸分析和锁消除。本文我们将要讨论另一种自动优化，叫作循环展开。JIT编译器使用这项技术来让循环（比如Java的for或者while循环）执行得更加高效。

由于我们要对JVM的内部机制进行深入分析，所以你会时不时看到用于讲解介绍的各种C的代码甚至是汇编语言，扶稳了！

我们先从下面这段C代码开始，它会去分配100万个long类型的空间，然后用100万个随机的long值来填充。

int main(int argv, char** argc) {
    int MAX = 1000000;
    long* data = (long*)calloc(MAX, sizeof(long));
    for (int i = 0; i < MAX; i++) {
        data[i] = randomLong();
    } 
}

C被认为是一门高级语言，不过事实真的是这样的吗？在苹果Mac电脑上，用Clang编译器（开启—S选项来打印Intel格式的汇编语言）来编译前面的代码会得到如下的输出结果：

_main:                       ## @main
## BB#0:
    pushq   %rbp
    movq    %rsp, %rbp
    subq    $48, %rsp
    movl    $8, %eax
    movl    %eax, %ecx
    movl    $0, -4(%rbp)
    movl    %edi, -8(%rbp)
    movq    %rsi, -16(%rbp)
    movl    $1000000, -20(%rbp)   ## imm = 0xF4240
    movslq  -20(%rbp), %rdi
    movq    %rcx, %rsi
    callq   _calloc
    movq    %rax, -32(%rbp)
    movl    $0, -36(%rbp)
LBB1_1:                       ##   LBB1_1是内部循环的Header Depth=1
    movl    -36(%rbp), %eax
    cmpl    -20(%rbp), %eax
    jge LBB1_4
## BB#2:                      ##   循环体内部: Header=BB1_1 Depth=1   
    callq   _randomLong
    movslq  -36(%rbp), %rcx
    movq    -32(%rbp), %rdx
    movq    %rax, (%rdx,%rcx,8)
## BB#3:                      ##   循环体内部: Header=BB1_1 Depth=1
    movl    -36(%rbp), %eax
    addl    $1, %eax
    movl    %eax, -36(%rbp)
    jmp LBB1_1
LBB1_4:
    movl    -4(%rbp), %eax
    addq    $48, %rsp
    popq    %rbp
    retq

看下这个代码，你会发现开始处有一次calloc函数的调用，并且仅存在一次randomLong()函数的调用（在循环中）。里面有两次跳转，它和下面变种的C代码所生成的机器代码本质上是一样的：

int main(int argv, char** argc) {
    int MAX = 1_000_000;
    long* data = (long*)calloc(MAX, sizeof(long));
    int i = 0;
    LOOP: if (i >= MAX)
        goto END;
    data[i] = randomLong();
    ++i;
    goto LOOP;
    END: return 0;
}

Java里面同样的代码应该是这样的：

public class LoopUnroll {
    public static void main(String[] args) {
        int MAX = 1000000;
        long[] data = new long[MAX];
        java.util.Random random = new java.util.Random();
            for (int i = 0; i < MAX; i++) {
            data[i] = random.nextLong();
        } 
    }
}

编译成字节码的话，就成了这样：

public static void main(java.lang.String[]);
    Code:
 0: ldc                        #2       // int 1000000
 2: istore_1
 3: iload_1
 4: newarray       long
 6: astore_2
 7: new                       #3       // class java/util/Random
10: dup
11: invokespecial             #4       // 方法 java/util/Random."<init>:()V
14: astore_3
15: iconst_0
16: istore        4
18: iload         4
20: iload_1
21: if_icmpge     38
24: aload_2
25: iload         4
27: aload_3
28: invokevirtual             #5.      // 方法 java/util/Random.nextLong:()J
31: lastore
32: iinc          4, 1
35: goto          18
38: return

这些程序在代码结构来看都非常相似。它们都在循环中对数组data进行了一次操作。真实的处理器会有指令流水线（instruction pipeline），如果程序一直向下线性执行的话，就能够充分地引用流水线，因为下一条执行的指令马上就会就绪。

不过，一旦碰到跳转指令，指令流水线的优势通常就消失了，因为流水线的内容需要丢弃掉并重新从主内存中跳转地址处开始加载新的操作码。这里所产生的性能损耗和缓存未命中是类似的————都要额外从主存中加载一次。

对于前向跳转（注：原文是back branch，从代码执行顺序来看，是指要跳转回前面所执行过的分支上，这里姑且称为前向跳转）————跳转回前面的执行点————正如前面for循环中那样，对性能的影响取决于CPU提供的分支预测算法的准确程度。Intel 64和IA-32架构优化参考手册[PDF]第3.4.1节对里面所提到的特定芯片的分支预测算法有详细的介绍。

不过由于有HotSpot的JIT编译器的存在，Java程序还有着更多的可能。JIT编译器进行了很多优化，不同的情况下所编译出来的代码会很不一样。

尤其是在使用int, short, 或者char变量作为计数器的计数循环（counted loops）当中，JIT进行了不少优化。它会把循环体展开，并用一个个排列好的原循环体的拷贝来替代。对循环的重构减少了所需的前向跳转。而且和C代码编译后所生成的汇编代码相比，性能上有很大的提升，因为指令流水线的缓存被丢弃的次数要少得多了。

我们用几个简单的方法来测试下不同的循环执行方式的区别。你可以看下循环展开后的汇编代码，原先的多个循环操作是如何在一次循环内完成的。

在开始汇编代码之旅前，我们还需要对前面的Java代码作一些简单的修改，以便让JIT编译器发挥作用，因为HotSpot虚拟机只会对整个方法体进行编译。不光如此，这个方法还需要在解释模式下执行过一定次数后，编译器才会考虑对它进行编译（通常是执行了1万次后才会进入完全优化的编译模式）。如果只是前面那样的一个单独的main方法，JIT编译器是永远不会被唤起的，也就没有任何优化可言了。

下面这个Java方法基本上是和原先的例子类似的，你可以用它来进行测试：

private long intStride1()
{
    long sum = 0;
    for (int i = 0; i < MAX; i += 1)
    {
        sum += data[i];
    }
    return sum; 
}

这个方法会顺序地从数组中取值，并累加起来，然后将结果返回。这和前面的例子是类似的，但我们选择把结果返回，这是为了确保JIT编译器不会把循环展开和逃逸分析结合起来进行更进一步的优化，那样就不容易确定循环展开的实际效果了。

我们可以从汇编语言中识别出一个关键的访问模式，这样更容易帮助我们理解代码在干什么。这就是由寄存器和偏移量组成的三元组[base, index, offset]，这里面

base寄存器存储的是数组的起始地址
index寄存器存储的是计数器(这个要乘上数据类型的大小)
offset用来记录展开循环内的偏移量

实际的汇编语言看起来会类似这样：

add rbx, QWORD PTR [base register + index register * size + offset]

假设数组类型是long的，我们来看下什么条件下会触发循环展开。需要注意的是，循环展开的行为在不同的HotSpot虚拟机版本间是不太一样的，同时也取决于具体的CPU架构，不过整体的概念是一样的。

要想得到JIT编译器生成的反汇编后的本地代码，你还需要一个反汇编库（一般是hsdis，HotSpot Disassembler），这个要安装到你的Java安装地址下面的jre/lib目录中。

hsdis可以从OpenJDK源码中编译得到，具体的操作文档可以看下JITWatch wiki。还有个方法，Oracle的GraalVM项目将hsdis作为可下载的二进制文件一起分发出来了———你可以从GraalVM的安装目录里把它拷贝到Java的安装位置下面。

装好了hsdis之后，还需要配置下让虚拟机把方法的编译后的汇编代码输出出来。要这么做你还得额外加上一些VM启动参数，包括-XX:+PrintAssembly。

需要注意的是JIT线程编译完方法后就会直接将对应的本地代码反汇编成可读的汇编语言。这是一个很昂贵的操作，会影响到应用程序的性能，所以在生产环境中不要使用。

用如下的VM选项来执行程序，你便能看到指定方法的反汇编后的汇编语言了：

java -XX:+UnlockDiagnosticVMOptions \
     -XX:-UseCompressedOops         \
     -XX:PrintAssemblyOptions=intel \
     -XX:CompileCommand=print,javamag.lu.LoopUnrolling::intStride1 \
     javamag.lu.LoopUnrolling

这个命令会生成一个步进固定为1的int计数循环所对应的汇编代码。

值得注意的是，这里我们用到了-XX:-UseCompressedOops，这只是为了把指针地址压缩的优化给关掉，来简化生成的汇编代码。在64位的JVM上这会节省一定的内存占用，不过我们不建议你在普通的虚拟机使用场景中这么做。你可以在OpenJDK的wiki中了解到更多关于普通对象指针（ordinary object pointers, oops）压缩的知识。

不断累加的long类型的求和结果存储在64位的寄存器rbx中。每个add指令都会从data数组中取出下一个值，并将它加到rbx上。每次加载后，偏移量的常量会增加8（这正是Java中long基础类型的大小）。

当展开的部分前向跳转回主循环的起始处时，offset寄存器会进行自增，加上这次循环迭代所处理的数据量：

//==============================
// 初始化代码
//==============================

// 将data数组的地址赋值给 rcx
0x00007f475d1109f7: mov rcx,QWORD PTR [rbp+0x18]  ;*getfield data

// 将数组大小赋值给  edx
0x00007f475d1109fb: mov edx,DWORD PTR [rcx+0x10]

// 将MAX赋值给  r8d
0x00007f475d1109fe: mov r8d,DWORD PTR [rbp+0x10]  ;*getfield MAX

// 循环计数器是 r13d, 将它和MAX进行比较
0x00007f475d110a02: cmp r13d,r8d

// 如果COUNTER >= MAX，跳转到exit处
0x00007f475d110a05: jge L0006

0x00007f475d110a0b: mov r11d,r13d
0x00007f475d110a0e: inc r11d
0x00007f475d110a11: xor r9d,r9d
0x00007f475d110a14: cmp r11d,r9d
0x00007f475d110a17: cmovl r11d,r9d
0x00007f475d110a1b: cmp r11d,r8d
0x00007f475d110a1e: cmovg r11d,r8d

//==============================
// 前置循环
//==============================

// 数组边界检查
             L0000: cmp r13d,edx
0x00007f475d110a25: jae L0007

// 执行加法
0x00007f475d110a2b: add rbx,QWORD PTR [rcx+r13*8+0x18]  ;*ladd

// 计数器自增
0x00007f475d110a30: mov r9d,r13d
0x00007f475d110a33: inc r9d  ;*iinc

// 如果已经完成PRE-LOOP，跳转至MAIN LOOP 
0x00007f475d110a36: cmp r9d,r11d
0x00007f475d110a39: jge L0001

// 检查循环计数器，如果未完成，则前向跳转（L0000处）
0x00007f475d110a3b: mov r13d,r9d
0x00007f475d110a3e: jmp L0000

//==============================
// 主循环初始化
//==============================

             L0001: cmp r8d,edx
0x00007f475d110a43: mov r10d,r8d
0x00007f475d110a46: cmovg r10d,edx
0x00007f475d110a4a: mov esi,r10d
0x00007f475d110a4d: add esi,0xfffffff9
0x00007f475d110a50: mov edi,0x80000000
0x00007f475d110a55: cmp r10d,esi
0x00007f475d110a58: cmovl esi,edi
0x00007f475d110a5b: cmp r9d,esi
0x00007f475d110a5e: jge L000a
0x00007f475d110a64: jmp L0003
0x00007f475d110a66: data16 nop WORD PTR [rax+rax*1+0x0]

//==============================
// 开始主循环 (展开的部分)
// 每次迭代执行8次加法
//==============================
             L0002: mov r9d,r13d
             L0003: add rbx,QWORD PTR [rcx+r9*8+0x18]   ;*ladd
0x00007f475d110a78: movsxd r10,r9d
0x00007f475d110a7b: add rbx,QWORD PTR [rcx+r10*8+0x20]  ;*ladd
0x00007f475d110a80: add rbx,QWORD PTR [rcx+r10*8+0x28]  ;*ladd
0x00007f475d110a85: add rbx,QWORD PTR [rcx+r10*8+0x30]  ;*ladd
0x00007f475d110a8a: add rbx,QWORD PTR [rcx+r10*8+0x38]  ;*ladd
0x00007f475d110a8f: add rbx,QWORD PTR [rcx+r10*8+0x40]  ;*ladd
0x00007f475d110a94: add rbx,QWORD PTR [rcx+r10*8+0x48]  ;*ladd
0x00007f475d110a99: add rbx,QWORD PTR [rcx+r10*8+0x50]  ;*ladd

// 循环计数器自增8
0x00007f475d110a9e: mov r13d,r9d
0x00007f475d110aa1: add r13d,0x8  ;*iinc

// 检查循环计数器，如果未完成，则前向跳转（L0002处）
0x00007f475d110aa5: cmp r13d,esi
0x00007f475d110aa8: jl L0002
//==============================

0x00007f475d110aaa: add r9d,0x7  ;*iinc

// 如果 循环计数器 >= MAX 跳转至退出处
             L0004: cmp r13d,r8d
0x00007f475d110ab1: jge L0009
0x00007f475d110ab3: nop

//==============================
// 后置循环
//==============================

// 数组边界检查
             L0005: cmp r13d,edx
0x00007f475d110ab7: jae L0007

// 执行一次加法
0x00007f475d110ab9: add rbx,QWORD PTR [rcx+r13*8+0x18];*ladd

// 循环计数器自增
0x00007f475d110abe: inc r13d  ;*iinc

// 检查循环计数器，如果未完成，则前向跳转（L0005处）
0x00007f475d110ac1: cmp r13d,r8d
0x00007f475d110ac4: jl L0005
//==============================

（为了让大家更容易理解，我们在汇编代码中加入了一些注释，这样每个独立的部分更加清晰了。为了简洁起见，我们只保留了一个退出方法的块，不过在汇编语言中通常会有多个退出块，来处理方法结束可能的各种情况。设置部分的代码也包含进来了，本文稍后会将它和其它操作来进行比较。）

当在循环里访问数组的时候，HotSpot虚拟机会将循环拆分成三个部分，来消除数组的边界检查：

前置循环：执行初始迭代，并且进行边界检查。
主循环：通过循环步长（就是每次迭代时计数器增加的大小）来计算在不需要边界检查情况下可以执行的最大迭代次数。
后置循环：执行剩余的迭代，并且进行边界检查。

计算一下add操作和jump操作的比例，你就能知道这个方法的实际优化效果是怎样的了。在我们前面测试的未优化的C语言的版本上，这个比例是1:1，而Java的HotSpot虚拟机的JIT编译器把这个数字提高到了8:1，在这一部分上减少了87%的跳转次数。而一次跳转的影响一般来说是会消耗2到300个CPU周期，用来等待从主存中重新加载代码，因此这个提升效果就非常明显了。（如果想了解HotSpot虚拟机是如何消除数组循环过程中的边界检查的，可以看下这个线上文档。）

HotSpot虚拟机也可以展开int计数，步长为常量2或4的循环。比方说步长为4的话，它可以将循环展开成8次，每次循环地址偏移量会增加0x20(32）。编译器还可以支持展开short，byte或者char来计数的循环体，但是long类型的不支持，这个在下一节我们马上会讲到。

安全点(Safepoints)

用long类型进行循环计数的Java方法的代码，看起来和int类型的是非常类似的：

private long longStride1()
{
    long sum = 0;
    for (long l = 0; l < MAX; l++)
    {
        sum += data[(int) l];
    }
    return sum; 
}

不过使用了long类型来计数之后，它所生成的汇编代码中的初始化的部分，就和前面所列出的汇编代码中的完全不一样了————哪怕步长是常量1，也不会出现循环展开：

  // 将数组长度赋值给 r9d
  0x00007fefb0a4bb7b: mov    r9d,DWORD PTR [r11+0x10]

  // 跳转到循环结束处，检查计数器是否超上限
  0x00007fefb0a4bb7f: jmp    0x00007fefb0a4bb90

  //（这里是前向跳转的目标地址） - 通过r14来求和
  0x00007fefb0a4bb81: add    r14,QWORD PTR [r11+r10*8+0x18]

  // 循环计数器rbx自增
  0x00007fefb0a4bb86: add    rbx,0x1

  // 安全点检查
  0x00007fefb0a4bb8a: test   DWORD PTR [rip+0x9f39470],eax

  // 如果 循环计数器 >= 1_000_000 则跳转到退出处
  0x00007fefb0a4bb90: cmp    rbx,0xf4240
  0x00007fefb0a4bb97: jge    0x00007fefb0a4bbc9

  // 将循环计数器的低32位赋值给r10d
  0x00007fefb0a4bb99: mov    r10d,ebx

  // 数组边界检查并前向跳转回循环起始处
  0x00007fefb0a4bb9c: cmp    r10d,r9d
  0x00007fefb0a4bb9f: jb     0x00007fefb0a4bb81

现在在循环体内就只有一个加的指令了——加法和跳转指令的比例又变回了1:1，循环展开的好处没有了。不光如此，循环中还多了一次安全点检查。

安全点是代码中的一些特殊位置，当执行线程执行到这个地方的时候，它便知道自己已经完成了对内部数据结构的所有修改（比如堆中的对象）。这个时候适合来检查并确认JVM是否需要暂停执行Java代码的所有线程。应用线程通过检查安全点并挂起执行，给JVM提供了一个机会来执行一些可能会修改内存布局或内部数据结构的操作，比如stop-the-world (STW)垃圾回收。

在代码解释执行的时候，有一个很适合进行安全点检查的时机：一个字节码刚执行完，下一个字节码还未执行的时候。

在“字节码间”进行安全点检查对解释执行来说非常有用，但对JIT编译过的方法来说，这个检查就必须要整合插入到编译器生成的代码里面才行。

如果缺少这些检查，就会出现其它线程都已经在它们的安全点上暂停但有的线程还在继续执行的情况。这会导致虚拟机进入到混乱的状态，几乎所有应用线程都停止运行了，却还有一些在不停地执行中。

HotSpot使用了几种启发法（heuristics）来往编译后的代码中插入安全点检查。最常用的两个就是在前向跳转之前（就像这个例子中这样），还有就是在方法即将退出但控制流还没回到调用方的时候。

不过，long计数的例子中安全点检查的出现也暴露了int计数循环中另一个特点：它们没有安全点检查。也就是说在整个int计数循环（步长为常量）的执行过程中不会出现任何安全点检查，在极端情下这可能会占用相当长的时间。

然而，如果是int计数但步长不固定的循环体，比如说每次方法调用时步长都可能发生变化：

private long intStrideVariable(int stride)
{
    long sum = 0;
    for (int i = 0; i < MAX; i += stride)
    {
        sum += data[i];
    }
return sum; 
}

这段代码便会强制要求JIT编译器在前向跳转处生成安全点检查。

长时间运行的int计数循环会导致其它线程一直在安全点等待，直到它执行结束，如果你对这个所导致的延迟暂停时间比较敏感的话，可以使用启动参数-XX:+UseCountedLoopSafepoints来解决这个问题。这个选项会在未展开的循环体的前向跳转处加入一个安全点检查。这样在刚才前面的例子中所生成的长长的汇编代码中，每进行8次加法运算，便会出现一次安全点检查。

除非你已经在性能测试中明确证实加上这个参数后会对性能有明显的提高，不然不要激活这个选项，其它会对性能产生影响的命令行参数也是同样的处理原则。很少有程序能从启用该选项中受益，因此不要盲目地开启这一选项。Java 10引入了一项更高级的叫循环切分（loop strip mining）的技术来更进一步地平衡安全点检查对吞吐量和延迟所产生的影响。

我们用JMH来测试下同样的数组使用int计数和使用long计数的性能差异，来做一下总结。正如前面所解释的，使用long计数的循环是不会被展开的，同时每次循环也会包含一次安全点检查。

package optjava.jmh;
import org.openjdk.jmh.annotations.*;
import java.util.concurrent.TimeUnit;


@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@State(Scope.Thread)
public class LoopUnrollingCounter
{
    private static final int MAX = 1_000_000;
    private long[] data = new long[MAX];
    @Setup
    public void createData()
    {
        java.util.Random random = new java.util.Random();
        for (int i = 0; i < MAX; i++)
        {
            data[i] = random.nextLong();
        }
    }

    @Benchmark
    public long intStride1()
    {
        long sum = 0;
        for (int i = 0; i < MAX; i++)
        {
            sum += data[i];
        }
        return sum; 
    }

    @Benchmark
    public long longStride1()
    {
        long sum = 0;
        for (long l = 0; l < MAX; l++)
        {
            sum += data[(int) l];
        }
        return sum; 
    }
}

最后的输出结果如下：

Benchmark                          Mode  Cnt     Score   Error  Units
LoopUnrollingCounter.intStride1   thrpt  200  2423.818 ± 2.547  ops/s
LoopUnrollingCounter.longStride1  thrpt  200  1469.833 ± 0.721  ops/s

也就是说使用int计数的循环每秒执行的操作能高出64%。

结论

HotSpot虚拟机可以执行更复杂的循环展开优化——比如说，当循环包含多个退出点时。这种情况下，循环会被展开，且每个展开的迭代都会进行一次终止条件的检查。

作为一个虚拟机，HotSpot利用循环展开的能力来减少或消除了前向跳转所带来的性能损耗。不过对大多数的Java开发人员来说，他们并不需要知道这个能力——这只不过又是一项运行时所提供的对他们透明的性能优化罢了。

原文链接

原创文章，转载请注明： 转载自并发编程网 – ifeve.com本文链接地址: JVM优化之循环展开

并发编程网 - ifeve.com

让天下没有难学的技术