一尘不染

为什么我能达到的最大递归深度是不确定的?

java

我决定尝试一些实验,以了解关于堆栈帧大小以及当前执行的代码在堆栈中的距离的发现。我们可能在这里调查两个有趣的问题:

  1. 当前代码有多少层深入堆栈?
  2. 当前方法在达到a之前可以达到多少级别的递归StackOverflowError

当前执行代码的堆栈深度

这是我为此能想到的最好的方法:

public static int levelsDeep() {
    try {
        throw new SomeKindOfException();
    } catch (SomeKindOfException e) {
        return e.getStackTrace().length;
    }
}

这似乎有点骇人听闻。它生成并捕获异常,然后查看堆栈跟踪的长度。

不幸的是,它似乎也有一个致命的限制,那就是返回的堆栈跟踪的最大长度为1024。超出此范围的任何内容都会被削减,因此此方法可以返回的最大长度为1024。

题:
有没有更好的方法来做到这一点,而且又没有此限制?
对于它的价值,我的猜测是没有:Throwable.getStackTraceDepth()一个本机调用,这表明(但没有证明)它不能用纯Java完成。

确定我们还剩下多少递归深度
我们可以达到的级别数将由(a)堆栈框架的大小和(b)剩余堆栈数决定。让我们不必担心堆栈框架的大小,而只需在达到之前查看可以达到多少级StackOverflowError。

这是我执行此操作的代码:

public static int stackLeft() {
    try {
        return 1+stackLeft();
    } catch (StackOverflowError e) {
        return 0;
    }
}

即使堆栈数量是线性的,它的工作也令人钦佩。但是,这是非常非常奇怪的部分。在64位Java 7(OpenJDK 1.7.0_65)上,结果是完全一致的:在我的机器上(64位Ubuntu 14.04)是9,923。但是Oracle的Java 8(1.8.0_25)给了我不确定的结果:记录下来的深度大约在18500到20700之间。

现在为什么在地球上将是不确定的?应该有固定的堆栈大小,不是吗?而且所有代码对我来说都是确定性的。

我想知道错误陷阱是否有点怪异,所以我尝试了一下:

public static long badSum(int n) {
    if (n==0)
        return 0;
    else
        return 1+badSum(n-1);
}

显然,这将返回给定的输入或溢出。

同样,我得到的结果在Java 8上是不确定的。如果调用badSum(14500),它将给我StackOverflowError大约一半的时间,而另一半则返回14500。但是在Java 7 OpenJDK上,它是一致的:badSum(9160)正常运行并badSum(9161)溢出。

题:
为什么在Oracle Java 8上不确定最大递归深度?为什么在OpenJDK 7上具有确定性?


阅读 369

收藏
2020-03-22

共1个答案

一尘不染

观察到的行为受到HotSpot优化器的影响,但这不是唯一的原因。当我运行以下代码

public static void main(String[] argv) {
    System.out.println(System.getProperty("java.version"));
    System.out.println(countDepth());
    System.out.println(countDepth());
    System.out.println(countDepth());
    System.out.println(countDepth());
    System.out.println(countDepth());
    System.out.println(countDepth());
    System.out.println(countDepth());
}
static int countDepth() {
    try { return 1+countDepth(); }
    catch(StackOverflowError err) { return 0; }
}

启用JIT后,我得到如下结果:

> f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -cp build\classes X
1.8.0_40-ea
2097
4195
4195
4195
12587
12587
12587

> f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -cp build\classes X
1.8.0_40-ea
2095
4193
4193
4193
12579
12579
12579

> f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -cp build\classes X
1.8.0_40-ea
2087
4177
4177
12529
12529
12529
12529

在这里,JIT的效果清晰可见,显然优化后的代码需要更少的堆栈空间,并且它表明启用了分层编译(实际上,-XX:-TieredCompilation如果程序运行时间足够长,则使用一次跳转)。

相反,在禁用JIT的情况下,我得到以下结果:

> f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -Xint -cp build\classes X
1.8.0_40-ea
2104
2104
2104
2104
2104
2104
2104

> f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -Xint -cp build\classes X
1.8.0_40-ea
2076
2076
2076
2076
2076
2076
2076

> f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -Xint -cp build\classes X
1.8.0_40-ea
2105
2105
2105
2105
2105
2105
2105

这些值仍会变化,但不会在单个运行时线程内变化,并且幅度较小。

因此,如果优化程序可以减少每次方法调用所需的堆栈空间(例如由于内联),则存在一个(相当小的)差异,该差异会变得更大。

是什么导致这种差异?我不知道这个JVM是如何做到的,但是一种情况可能是强制执行堆栈限制的方式要求对堆栈结束地址进行一定的对齐(例如,匹配内存页面大小),而内存分配返回的内存具有一个起始地址,对齐保证较弱。将这种情况与ASLR结合使用,可能在对齐要求的大小范围内始终存在差异。

2020-03-22