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

让我们分析一下该优化对 JVM 意味着什么。

可以吗

首先，假设 JVM 看到一个调用 mul0(4,8)（当然，用字节码表示，但为了讨论，让我们继续使用更具可读性的 Java 源语法）。并且假设此代码块执行得足够频繁，因此 HotSpot 引擎决定它值得优化。

现在引擎需要看到 mul0() 方法是一个纯函数，当使用相同的参数调用时总是返回相同的结果。这意味着遍历所有可从 mul0() 方法内部访问的指令，并检查它们是否访问除参数之外的任何变量。我认为 Hotspot 引擎也有类似的推理能力，所以这个应该也是可行的。

然后引擎只需要再次运行递归方法来查找结果，并用加载整数 32 替换 mul0(4,8) 调用。

值得这么痛苦吗？

我描述的推理仅适用于 mul0(4,8) 中的固定参数情况。它不适用于变量 mul0(x,y) 调用。

您发现 Java 编译器已经处理了常量参数情况（至少有时是这样），因此在 JVM 中再做一次没有用。

而且优化只会帮助那些一遍又一遍地使用相同的参数重复进行昂贵计算的程序。所以它只会帮助那些连编写高效代码的基础知识都不知道的开发人员，更糟糕的是，它不会教育他们提高他们的技能。

为什么它在 Java 编译器中有用？

如果编译器检测到表达式具有常量结果，它可以在编译时计算该结果，因此即使是 "zero-time" 中语句运行s 的第一次执行。所以在这里它投入了一点编译时间以获得更好的性能每次程序运行s.

Answer 2

简答

HotSpot JVM 能够进行这种优化，但默认的 JVM 选项阻止这样做。

长答案

首先benchmark需要稍微修正一下才能看到效果

根据设计，@State 类的字段在每次迭代时都会重新读取。 JVM 不知道它们是常量，所以它不能常量折叠它们。使 F1 和 F2 最终化，使它们成为常量并允许进一步优化。

基准方法应该 通过调用 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 returns 预先计算的值：

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

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

JVM 是否能够进行简单的递归调用预计算？

Is the JVM able to do trivial recursive call precomputation?

java

performance

jvm

microbenchmark

简答

长答案