java - 为什么我可以达到的最大递归深度是不确定的？

Question

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

1. 当前代码在堆栈深处有多少层？
2. 当前方法在遇到 StackOverflowError 之前可以达到多少级递归？

当前执行代码的堆栈深度

这是我能想到的最好的:

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

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

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

Question:

Is there a better way of doing this that isn't so hacky and doesn't have this limitation?

对于它的值(value)，我的猜测是没有: Throwable.getStackTraceDepth() 是一个 native 调用，这表明(但不证明)它不能完成在纯 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) 会溢出。

Question:

Why is the maximum recursion depth non-deterministic on Oracle's Java 8? And why is it deterministic on 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 是如何做到的，但一种情况可能是强制堆栈限制的方式需要堆栈 end 地址的某种对齐(例如匹配内存页面大小)，而内存 < em>allocation 返回具有较弱对齐保证的起始地址的内存。将这种情况与 ASLR 结合起来并且在对齐要求的大小范围内可能总是存在差异。