为什么我能达到的最大递归深度是非确定性的?当前正在执行的代码的堆栈深度确定我们还剩下多少递归深度

我决定尝试一些实验,看看我能发现什么关于堆栈帧的大小,以及当前正在执行的代码在堆栈中走了多远。我们可以在这里研究两个有趣的问题:

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

当前正在执行的代码的堆栈深度

这是我能想到的最好的:

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

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

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

问题:

有没有更好的方法来做到这一点,不是那么笨拙,也没有这个限制?

就其价值而言,我的猜测是没有:是一个本机调用,这表明(但没有证明)它不能在纯Java中完成。Throwable.getStackTraceDepth()

确定我们还剩下多少递归深度

我们可以达到的级别数量将由(a)堆栈帧的大小和(b)剩余的堆栈数量决定。让我们不要担心堆栈帧的大小,只需看看在达到.StackOverflowError

以下是我执行此操作的代码:

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

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

那么,为什么它会是非确定性的呢?应该有一个固定的堆栈大小,不是吗?对我来说,所有的代码看起来都是确定性的。

我想知道这是否是错误捕获的奇怪之处,所以我尝试了这个:

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

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

同样,我得到的结果在Java 8上是非确定性的。如果我打电话,它会给我大约一半的时间,并返回14500的另一半。但是在Java 7 OpenJDK上,它是一致的:完成良好,溢出。badSum(14500)StackOverflowErrorbadSum(9160)badSum(9161)

问题:

为什么在Oracle的Java 8上,最大递归深度是非确定性的?为什么它在OpenJDK 7上是确定性的?

答案 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 结合使用,在对齐要求的大小范围内可能始终存在差异。


答案 2
Why is the maximum recursion depth non-deterministic on Oracle's Java 8? And why is it deterministic on OpenJDK 7?

关于这一点,可能与垃圾回收的变化有关。Java 每次都可以为 gc 选择不同的模式。http://vaskoz.wordpress.com/2013/08/23/java-8-garbage-collectors/


推荐