为什么最大递归深度我可以达到非确定性？

Question

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

1. 当前代码的堆栈深度是多少？
2. 当前方法在到达之前可以达到多少级别的递归StackOverflowError？

堆栈当前执行代码的深度

这是我能想到的最好的:

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

这看起来有点黑客.它生成并捕获异常,然后查看堆栈跟踪的长度.

不幸的是,它似乎也有一个致命的限制,即返回的堆栈跟踪的最大长度为1024.除此之外的任何内容都被削减,因此此方法可以返回的最大值为1024.

题:

有没有更好的方法做到这一点,不是那么hacky并没有这个限制？

对于它的价值,我的猜测是没有: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)上,结果完全一致: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上是非确定性的.如果我打电话badSum(14500),它会给我StackOverflowError一半的时间,而另一半则返回14500.但是在Java 7 OpenJDK上,它是一致的:badSum(9160)完成正常,并badSum(9161)溢出.

题:

为什么Oracle Java 8上的最大递归深度不确定？为什么OpenJDK 7确定性？

Answer 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结合起来可能总是存在差异,在对齐要求的大小范围内.