3年前 (2022-03-02)  jvm |   抢沙发  863 
文章评分 0 次,平均分 0.0
[收起] 文章目录

在本文中,我们将讨论一种自动优化,称为循环展开。JIT编译器使用这种技术使循环(例如Java的forwhile循环)执行得更快。

因为我们将在这里深入研究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可以被认为是一种高级语言,但真的是这样吗?在Apple Macintosh上,Clang编译器(使用-S开关以英特尔格式转储汇编语言)为前面的代码生成以下输出:

_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:                         ## =>This Inner Loop Header: Depth=1
    movl    -36(%rbp), %eax
    cmpl    -20(%rbp), %eax
    jge LBB1_4
## BB#2:                        ##   in Loop: Header=BB1_1 Depth=1
    callq   _randomLong
    movslq  -36(%rbp), %rcx
    movq    -32(%rbp), %rdx
    movq    %rax, (%rdx,%rcx,8)
## BB#3:                        ##   in Loop: 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    // Method 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    // Method java/util/Random.nextLong:()J
      31: lastore
      32: iinc          4, 1
      35: goto          18
      38: return
</init>

这些程序在代码的整体形状上非常相似。它们都对每个循环的数据数组执行一个操作。然而,真正的处理器有即将到来的指令的管道,因此如果程序继续线性前进,管道可以有效地使用,因为下一条要执行的指令总是在手边。

但是,如果遇到跳转指令,指令管道的好处通常会丢失,因为管道内容需要从主内存转储并重新加载,新的操作码从跳转到的地址开始。在这种情况下,性能损失将类似于缓存未命中从主内存进行的额外提取。

JIT线程发出编译后的方法后,直接将本机代码反汇编成可读的汇编语言。这是一种昂贵的操作,不应用于生产过程。

对于后分支(如for循环中所示,跳到前一点),对性能的影响取决于CPU提供的分支预测算法的精确形式。《英特尔64和IA-32体系结构优化参考手册》[PDF]第3.4.1节详细介绍了它所涵盖的特定芯片的分支预测优化。

然而,在Java程序的情况下,由于HotSpot的JIT编译器,这个故事还有更多内容。JIT编译器包含几个优化,在有利的情况下可以生成非常不同的编译代码。

特别是,对使用intshortchar变量作为循环计数器的计数循环(例如for循环)进行了优化。循环体展开,并由循环体的多个副本替换,一个接一个地排列。这种对循环的返工减少了所需的反向分支的数量。此外,与编译后的C代码生成的汇编语言相比,它可以显著提高性能,因为指令管道缓存需要较少丢弃。

让我们研究一些以不同方式执行循环的简单方法。您可以查看汇编语言来确定循环何时展开,以便在单个循环迭代中执行多个循环体操作。

在深入研究汇编语言之前,我们应该注意,为了使JIT编译生效,需要稍微修改前面的Java代码,因为HotSpot VM只编译整个方法。不仅如此,在编译器考虑方法之前,方法在解释模式下执行一定次数(对于完全优化的编译,通常为10000次)后才会被编译。如图所示,只使用一个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],其中

  • 基址寄存器包含数组中数据的起始地址
  • 索引寄存器包含循环计数器(与数据类型大小相乘)
  • 偏移用于偏移每个展开的访问

实际的汇编语言如下所示:

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

考虑long类型的数组,让我们看看循环展开的条件。请注意,循环展开行为在HotSpot VM版本之间可能有所不同,并且取决于CPU体系结构的细节,但总体概念保持不变。

要获得JIT编译器生成的反汇编本机代码,需要一个反汇编库(标准选择是hsdis,热点反汇编程序),需要将其安装在Java安装的jre/lib目录中。

hsdis可以从OpenJDK源代码构建,相关说明可以在JITWatch wiki中找到。或者,Oracle的GraalVM项目将hsdis作为可下载二进制文件的一部分提供,该文件可以简单地从GraalVM安装复制到主Java安装位置。

安装hsdis后,需要指示VM输出方法的汇编语言。要实现这一点,您需要添加一些额外的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中节省了一些内存使用,但我们不建议您在正常的VM使用中这样做。您可以在OpenJDK wiki中了解所有关于压缩普通对象指针(OOP)的信息。

累加的长和存储在64位寄存器rbx中。每条add指令从数据数组加载下一个值,并将其添加到rbx。每次加载时,数组中的常量偏移量增加8字节(相当于Java long原语的大小)。

当展开的部分分支回到主循环开始时,偏移寄存器将按循环迭代中处理的数据量递增:

//==============================
// SETUP CODE
//==============================

// MOVE ADDRESS OF data ARRAY INTO rcx
0x00007f475d1109f7: mov rcx,QWORD PTR [rbp+0x18]  ;*getfield data

// MOVE SIZE OF data ARRAY INTO edx
0x00007f475d1109fb: mov edx,DWORD PTR [rcx+0x10]

// MOVE MAX INTO r8d
0x00007f475d1109fe: mov r8d,DWORD PTR [rbp+0x10]  ;*getfield MAX

// LOOP COUNTER IN r13d, COMPARE WITH MAX
0x00007f475d110a02: cmp r13d,r8d

// JUMP TO EXIT IF COUNTER >= MAX
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

//==============================
// PRE-LOOP
//==============================

// ARRAY BOUNDS CHECK
             L0000: cmp r13d,edx
0x00007f475d110a25: jae L0007

// PERFORM A SINGLE ADDITION
0x00007f475d110a2b: add rbx,QWORD PTR [rcx+r13*8+0x18]  ;*ladd

// INCREMENT THE LOOP COUNTER
0x00007f475d110a30: mov r9d,r13d
0x00007f475d110a33: inc r9d  ;*iinc

// JUMP TO MAIN LOOP IF FINISHED PRE-LOOP
0x00007f475d110a36: cmp r9d,r11d
0x00007f475d110a39: jge L0001

// CHECK LOOP COUNTER AND BACK BRANCH IF NOT FINISHED
0x00007f475d110a3b: mov r13d,r9d
0x00007f475d110a3e: jmp L0000

//==============================
// MAIN LOOP SETUP
//==============================
             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]

//==============================
// MAIN LOOP START (UNROLLED SECTION)
// PERFORMS 8 ADDITIONS PER LOOP ITERATION
//==============================
             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

// INCREMENT LOOP COUNTER BY 8
0x00007f475d110a9e: mov r13d,r9d
0x00007f475d110aa1: add r13d,0x8  ;*iinc

// CHECK LOOP COUNTER AND BACK BRANCH IF NOT FINISHED
0x00007f475d110aa5: cmp r13d,esi
0x00007f475d110aa8: jl L0002
//==============================

0x00007f475d110aaa: add r9d,0x7  ;*iinc

// IF LOOP COUNTER >= MAX JUMP TO EXIT
             L0004: cmp r13d,r8d
0x00007f475d110ab1: jge L0009
0x00007f475d110ab3: nop

//==============================
// POST-LOOP
//==============================

// ARRAY BOUNDS CHECK
             L0005: cmp r13d,edx
0x00007f475d110ab7: jae L0007

// PERFORM A SINGLE ADDITION
0x00007f475d110ab9: add rbx,QWORD PTR [rcx+r13*8+0x18];*ladd

// INCREMENT THE LOOP COUNTER
0x00007f475d110abe: inc r13d  ;*iinc

// CHECK LOOP COUNTER AND BACK BRANCH IF NOT FINISHED
0x00007f475d110ac1: cmp r13d,r8d
0x00007f475d110ac4: jl L0005
//==============================

(为了使事情更简单,我们在汇编代码中加入了一些注释,以便清楚地显示单独的部分。为简洁起见,我们只显示一个出口块,但在汇编语言中通常会有多个出口块来处理方法结束的不同方式。包括设置部分是为了与后面的其他操作进行比较。)(在本文中为r。)

当循环访问阵列时,HotSpot VM通过将循环分为三个部分来消除阵列边界检查:

在Java10中,引入了一种更先进的技术,称为循环条带挖掘,以进一步平衡安全点对吞吐量和延迟的影响。

  • 预循环:通过边界检查执行初始迭代。
  • 主循环:循环步长(每次迭代时循环计数器增加的量)用于计算无需边界检查即可执行的最大迭代次数。
  • Post循环:通过边界检查执行剩余的迭代。

通过查看加法运算与跳转的比率,可以看到这种方法的实际效果。在我们前面研究的未优化的C案例中,这个比率是1:1,但是Java HotSpot VM的JIT编译器将这个比率增加到了8:1,这一部分的跳转次数减少了87%。因为跳转的效果通常是在等待从主内存重新填充代码时消耗2到300个周期,所以这种改进可能是显著的。(要了解HotSpot VM在迭代循环不变数组时如何消除边界检查的更多信息,请参阅在线文档。)

HotSpot VM还可以使用int计数器和2或4的常规步幅展开循环。例如,步幅为4时,主体展开8次,每次访问的地址偏移量增加0x20(32)字节。编译器还可以使用short、byte或char类型的计数器展开循环,但不能使用long类型的计数器,我们将在下一节中进行解释。

Safepoints 安全点

对于一个非常长的计数器,Java方法的int似乎与case类似:

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

但是,对于long类型的循环计数器,生成的汇编语言与前一个汇编语言中的设置部分完全不同。列表中列出,即使步幅恒定为1,也不会发生循环展开:

// ARRAY LENGTH INTO r9d
  0x00007fefb0a4bb7b: mov    r9d,DWORD PTR [r11+0x10]

  // JUMP TO END OF LOOP TO CHECK COUNTER AGAINST LIMIT
  0x00007fefb0a4bb7f: jmp    0x00007fefb0a4bb90

  // BACK BRANCH TARGET - SUM ACCUMULATES IN r14
  0x00007fefb0a4bb81: add    r14,QWORD PTR [r11+r10*8+0x18]

  // INCREMENT LOOP COUNTER IN rbx
  0x00007fefb0a4bb86: add    rbx,0x1

  // SAFEPOINT POLL
  0x00007fefb0a4bb8a: test   DWORD PTR [rip+0x9f39470],eax

  // IF LOOP COUNTER >= 1_000_000 THEN JUMP TO EXIT CODE
  0x00007fefb0a4bb90: cmp    rbx,0xf4240
  0x00007fefb0a4bb97: jge    0x00007fefb0a4bbc9

  // MOVE LOW 32 BITS OF LOOP COUNTER INTO r10d
  0x00007fefb0a4bb99: mov    r10d,ebx

  // ARRAY BOUNDS CHECK AND BRANCH BACK TO LOOP START
  0x00007fefb0a4bb9c: cmp    r10d,r9d
  0x00007fefb0a4bb9f: jb     0x00007fefb0a4bb81

现在,每个循环体迭代只有一条add指令。add指令与跳转指令的比率回到1:1,循环展开的好处已经消失。不仅如此,循环中还添加了一个safepoint poll。

安全点是代码中的一个位置,在这个位置执行线程知道它已经完成了对内部数据结构(例如堆中的对象)的所有修改。这是检查JVM是否需要停止所有执行Java代码的线程的理想时机。通过在安全点进行检查并安全地暂停执行,应用程序线程为JVM提供了执行操作的机会,这些操作可能会改变内存布局并修改内部数据结构,例如停止世界(STW)垃圾收集。

在解释代码的情况下,安全点检查的一个非常自然的位置已经存在:一个字节码执行完毕之后,下一个字节码执行之前。

解释代码的“字节码之间”安全点检查非常有用,但在JIT编译方法的情况下,必须合成额外的检查,并将其插入编译器发出的代码中。

如果没有这些检查,一个线程可以继续运行,而其他线程已经在其安全点停止。这可能会导致病态的VM状态,在这种状态下,几乎所有应用程序线程都会暂停,但有些线程会继续运行相当长的时间。

作为一个虚拟机,Java HotSpot VM具有高级循环展开功能,可以减少或消除后分支的开销。

HotSpot提供了几种将安全点检查插入已编译代码的启发式方法。最常见的两种情况是在后分支之前(如本例中),以及在方法退出之后和控件返回给调用方之前。

然而,在长计数器示例中出现的safepoint检查也指出了int计数循环的另一个特点:它们不包含safepoint检查。这意味着一个整数计数的循环(以恒定的步幅)将在不遇到任何安全点检查的情况下运行,在极端情况下,这可能需要相当长的时间。

但是,考虑一个带有int计数器和一个不是常数的步长的循环,例如在每个方法调用中步长可以不同的一个循环:

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

这段代码确实会迫使JIT编译器在每个后分支上发出一个安全点检查。

如果您担心长时间运行的counted int循环会导致延迟暂停,在循环完成之前,它会将其他线程保持在安全点,那么可以使用VM开关-XX:+UseCountedLoopSafepoints。此选项在展开循环的后分支之前添加安全点检查。因此,在冗长的汇编代码清单中,测试将每隔八次进行一次。

与每个与性能相关的命令行开关一样,在性能测试中证明它将提供显著的好处之前,不应激活它。很少有应用程序会从激活此开关中看到任何好处,因此不应该盲目地打开它。在Java10中,引入了一种更先进的技术,称为loop strip mining,以进一步平衡安全点对吞吐量和延迟的影响。

最后,我们来看一个JMH基准测试,比较使用int计数器或long计数器迭代同一数组的性能。如前所述,带有长计数器的循环体不会展开,循环还将包含一个safepoint轮询。

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 VM可以执行更复杂的循环展开优化,例如,在包含多个出口点的循环上。在这种情况下,循环被展开,每个展开的迭代都包含一个退出条件测试。

作为一个虚拟机,HotSpot VM具有高级循环展开功能,可以减少或消除后分支的开销。然而,大多数Java程序员不需要知道这种功能——它只是运行时提供的一种更透明的性能优化。

原文地址:https://blogs.oracle.com/javamagazine/post/loop-unrolling

 

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

关于

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册