当前位置: 首页 > 面试题库 >

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

袁亦
2023-03-14
问题内容

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

  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上具有确定性?


问题答案:

观察到的行为受到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是如何做到的,但是一种情况可能是强制执行堆栈限制的方式要求对堆栈结束地址进行一定的对齐(例如,匹配内存页面大小),而内存分配html" target="_blank">返回的内存具有一个起始地址,对齐保证较弱。将这种情况与ASLR结合使用,可能在对齐要求的大小范围内始终存在差异。



 类似资料:
  • 问题内容: Python具有最大的递归深度,但没有最大的迭代深度。为什么限制递归?像迭代一样对待递归而不限制递归调用的数量会更自然吗? 让我只说这个问题的根源在于尝试实现流。例如,假设我们要编写一个流以产生自然数: 流的递归定义非常吸引人。但是,我想更好/更多的pythonic方法是使用生成器。 问题答案: 实际上这里有一些问题。 首先,正如NPE的回答很好地说明的那样,Python不会消除尾部调

  • 问题内容: 背景:我正在使用最小构造算法构建一个Trie以表示字典。输入列表是430万个utf-8字符串,按字典顺序排序。生成的图是非循环的,最大深度为638个节点。我的脚本的第一行通过将递归限制设置为1100 。 问题:我希望能够将Trie序列化到磁盘上,因此我可以将其加载到内存中,而不必从头开始重建(大约22分钟)。我已经尝试了和,同时使用了文本和二进制协议。每次,我都会得到如下所示的堆栈跟踪

  • 问题内容: 我从星期一开始使用Python进行编程。我很喜欢学习它。但是我一直试图了解如何在tkinter菜单之间切换时避免递归!我确信这是一个非常基本的问题,感谢您宽容我对此主题的无知,但我无法在其他地方找到答案。 我现在正在做的最终是给我错误:RuntimeError:调用Python对象时超出了最大递归深度 这是我目前正在使用的模式。更新:下面的代码现在是完整的隔离副本,再现了我面临的问题!

  • 我对Python很陌生。我写了一个关于返回 x 在排序的重复元素数组 A 中的出现次数的函数: 错误是:运行时错误:超出最大递归深度。有人知道如何解决它吗?

  • 问题内容: 我正在尝试使用CASE表达式创建一个持久化的计算列: MSDN明确表示CASE是确定性的,这里 但是,我得到一个错误: 消息4936,级别16,状态1,行1表’Calendar’中的计算列’PreviousDate’无法保留,因为该列是不确定的。 当然,我可以创建一个标量UDF并将其显式声明为确定性的,但是有没有更简单的方法呢?我已经在获取最新的Service Pack中。谢谢。 问题

  • 问题内容: 我正在创建一个小型Java Jpanel游戏,其中应该有一个火箭,它通过箭头上下移动,并通过太空射击。 触发方法应按以下方式工作:按下空格键,东西触发并在屏幕上移动,然后当它碰到某个x时,它就会消失。此外,您只能发射一次,直到另一颗子弹消失为止。 我不知道我在做什么错。首先,在我的代码启动后,您会看到子弹在屏幕上飞舞。 2,子弹没有消失。 第三,即使其他子弹仍然可见,它也允许我再次开火