49

为了估计递归方法在给定内存量下可以实现的最大调用深度，计算在可能发生堆栈溢出错误之前使用的内存的（近似）公式是什么？

编辑：

许多人用“它取决于”来回应，这是合理的，所以让我们通过一个微不足道但具体的例子来删除一些变量：

public static int sumOneToN(int n) {
    return n < 2 ? 1 : n + sumOneToN(n - 1);
}

很容易证明，在我的 Eclipse IDE 中运行它会爆炸n不到 1000（对我来说太低了）。是否可以在不执行的情况下估计此调用深度限制？

编辑：我不禁想到 Eclipse 有一个固定的最大调用深度 1000，因为我得到了998，但是有一个用于主要的，一个用于对方法的初始调用，1000总而言之。这是一个“太圆”的数字恕我直言，不是巧合。我会进一步调查。我刚刚 Dux 开销了 -Xss vm 参数；这是最大堆栈大小，所以 Eclipse 运行器必须-Xss1000设置在某个地方

4

6 回答 6

25

这显然是 JVM 特定的，也可能是特定于体系结构的。

我测量了以下内容：

  static int i = 0;
  public static void rec0() {
      i++;
      rec0();
  }

  public static void main(String[] args) {
      ...
      try {
          i = 0; rec0();
      } catch (StackOverflowError e) {
          System.out.println(i);
      }
      ...
  }

使用

Java(TM) SE Runtime Environment (build 1.7.0_09-b05)
Java HotSpot(TM) 64-Bit Server VM (build 23.5-b02, mixed mode)

在 x86 上运行。

使用 20MB 的 Java 堆栈 ( -Xss20m)，每次调用的摊销成本在 16-17 字节左右波动。我见过的最低的是 16.15 字节/帧。因此，我得出结论，成本为 16 个字节，其余为其他（固定）开销。

一个函数int的开销基本相同，16 字节/帧。

有趣的是，一个需要 10 个字节的函数ints需要 32 个字节/帧。我不知道为什么成本这么低。

以上结果适用于代码经过 JIT 编译后。在编译之前，每帧的成本要高得多。我还没有找到可靠估计它的方法。但是，这确实意味着您没有希望可靠地预测最大递归深度，直到您能够可靠地预测递归函数是否已被 JIT 编译。

所有这些都使用ulimit128K 和 8MB 的堆栈大小进行了测试。两种情况下的结果都是一样的。

于 2012-12-21T19:24:12.270 回答
10

只是部分答案：从JVM Spec 7, 2.5.2开始，可以在堆上分配堆栈帧，并且堆栈大小可能是动态的。我不能肯定地说，但似乎应该可以让您的堆栈大小仅受您的堆大小限制：

因为除了推送和弹出帧外，Java 虚拟机堆栈永远不会被直接操作，因此帧可能是堆分配的。

和

该规范允许 Java 虚拟机堆栈具有固定大小或根据计算需要动态扩展和收缩。如果 Java 虚拟机堆栈具有固定大小，则可以在创建堆栈时独立选择每个 Java 虚拟机堆栈的大小。

Java 虚拟机实现可以为程序员或用户提供对 Java 虚拟机堆栈的初始大小的控制，以及在动态扩展或收缩 Java 虚拟机堆栈的情况下，对最大和最小大小的控制。

所以这将取决于JVM的实现。

于 2012-12-21T19:20:37.043 回答
4

添加到 NPE 答案：

最大堆栈深度似乎是灵活的。以下测试程序打印出截然不同的数字：

public class StackDepthTest {
    static int i = 0;

    public static void main(String[] args) throws Throwable {
        for(int i=0; i<10; ++i){
            testInstance();
        }
    }

    public static void testInstance() {
        StackDepthTest sdt = new StackDepthTest();
        try {
            i=0;
            sdt.instanceCall();
        } catch(StackOverflowError e){}
        System.out.println(i);
    }

    public void instanceCall(){
        ++i;
        instanceCall();
    }
}

输出是：

10825
10825
59538
59538
59538
59538
59538
59538
59538
59538

我使用了这个 JRE 的默认值：

java version "1.7.0_09"
OpenJDK Runtime Environment (IcedTea7 2.3.3) (7u9-2.3.3-0ubuntu1~12.04.1)
OpenJDK 64-Bit Server VM (build 23.2-b09, mixed mode)

所以结论是：如果你的脓够了（即超过两次），你就有第二次机会；-)

于 2012-12-21T20:14:38.297 回答
3

答案是，这一切都取决于。

首先，Java Stack 的大小是可以改变的。

其次，给定方法的堆栈帧大小可以根据不同的变量而变化。您可以查看调用堆栈的调用堆栈帧大小部分- 维基百科了解更多详细信息。

于 2012-12-21T19:21:10.030 回答
2

取决于您的系统架构（32 位或 64 位地址）、局部变量的数量和方法的参数。如果是 尾递归则没有开销，如果编译器将其优化为循环。

你看，没有简单的答案。

于 2012-12-21T19:21:35.870 回答
2

您可以走经验主义道路并试验您的代码和-Xss设置。有关更多信息，请参见此处：JVM 选项 -Xss - 它究竟做了什么？

于 2012-12-21T19:29:10.140 回答