java - JVM 能够进行简单的递归调用预计算吗？

Question

不久前，我运行了两种不同软件乘法算法的 Rust 基准测试:平凡递归乘法和俄罗斯农民乘法。

令我惊讶的是，编译器能够分析这个简单的递归，直接用结果替换对方法的调用(例如调用 mul0(4,8) -> 32 )。

为了查看 JVM 是否能够执行相同的优化，我通过 JMH 测量了以下 Java 实现。然而，俄罗斯农民算法更快，而且虚拟机似乎没有执行任何类似的优化。

JVM 中是否内置了类似的优化技术(用预先计算的结果替换递归调用)，或者 JVM 本身由于某种原因没有这样做？

我知道这取决于 VM，并且可能会发生变化，因此我对阻碍 VM 实现者将此类优化合并到其 VM 中的一般障碍更感兴趣。

代码片段:

@Warmup(iterations = 10)
@Fork(value = 2)
@State(Scope.Benchmark)
public class MyBenchmark {

    private int F1 = 542;
    private int F2 = 323;

    public final static int mul0(int a, int b) {
        if (a == 1) {
            return b;
        }
        return mul0(a - 1, b) + b;
    }

    //O(log n)
    public final static int mul2(int a, int b) {
        if (a == 1) {
            return b;
        }

        int sum = ((a & 1) == 1) ? b : 0;

        return mul2(a / 2, b + b) + sum;
    }

    @Benchmark
    public void test0() {
        mul0(F1, F2);
    }

    @Benchmark
    public void test2() {
        mul2(F1, F2);
    }

}

结果:

Result: 13852692,903 ▒(99.9%) 532102,125 ops/s [Average]
  Statistics: (min, avg, max) = (9899651,068, 13852692,903, 15356453,576), stdev = 945811,061
  Confidence interval (99.9%): [13320590,778, 14384795,028]


# Run complete. Total time: 00:02:22

Benchmark                   Mode  Samples         Score  Score error  Units
d.s.m.MyBenchmark.test0    thrpt       40   1453817,627    68528,256  ops/s
d.s.m.MyBenchmark.test2    thrpt       40  13852692,903   532102,125  ops/s

Answer 1

简短回答

HotSpot JVM 能够进行此类优化，但默认的 JVM 选项阻止执行此操作。

长答案

首先，需要稍微修正一下基准测试才能看到效果。

1. 按照设计，@State 类的字段会在每次迭代时重新读取。 JVM 不知道它们是常量，因此无法对它们进行常量折叠。将 F1 和 F2 最终化，使它们成为常量并允许进一步优化。

2. 基准方法应该通过调用 Blackhole.consume 或简单地从方法返回一个值来使用计算结果。

   private final int F1 = 542;
   private final int F2 = 323;
   
   public final static int mul0(int a, int b) {
       if (a == 1) {
           return b;
       }
       return mul0(a - 1, b) + b;
   }
   
   //O(log n)
   public final static int mul2(int a, int b) {
       if (a == 1) {
           return b;
       }
   
       int sum = ((a & 1) == 1) ? b : 0;
   
       return mul2(a / 2, b + b) + sum;
   }
   
   @Benchmark
   public int test0() {
       return mul0(F1, F2);
   }
   
   @Benchmark
   public int test2() {
       return mul2(F1, F2);
   }
   

现在 HotSpot 可以内联方法调用并执行常量折叠。然而，默认情况下，递归方法的内联仅限于一级。我们可以使用以下选项覆盖它:

-XX:MaxInlineLevel=20 -XX:MaxRecursiveInlineLevel=20

现在 test2 变得非常快，因为它显然执行了不到 20 个方法调用:

Benchmark               Mode  Cnt    Score    Error  Units
MyBenchmark.test0       avgt    5  675,763 ± 16,422  ns/op
MyBenchmark.test2       avgt    5    5,320 ±  0,274  ns/op

使用-prof perfasm查看生成的汇编代码，我们可以验证test2返回预先计算的值:

0x00000000038e5960: mov    %r10,0x20(%rsp)
0x00000000038e5965: mov    0x58(%rsp),%rdx
0x00000000038e596a: mov    $0x2abda,%r8d        <<<<
0x00000000038e5970: data32 xchg %ax,%ax
0x00000000038e5973: callq  0x00000000037061a0  ;*invokevirtual consume

0x2abda = 175066 = 542 * 323 = mul2(F1, F2)