如何预测递归方法的最大调用深度？ [英] How to predict the maximum call depth of a recursive method?

问题描述

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

For the purposes of estimating the maximum call depth a recursive method may achieve with a given amount of memory, what is the (approximate) formula for calculating the memory used before a stack overflow error is likely to occur?

许多人回答它依赖，这是合理的，所以让我们通过使用删除一些变量一个简单但具体的例子：

Many have responded with "it depends", which is reasonable, so let's remove some of the variables by using a trivial but concrete example:

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

很容易证明在我的Eclipse IDE中运行它会爆炸 n 低于1000（对我来说低得惊人）。
是否可以估算此调用深度限制而不执行它？

It is easy to show that running this in my Eclipse IDE explodes for n just under 1000 (surprisingly low to me). Could this call depth limit have been estimated without executing it?

编辑：我不禁认为Eclipse的最大调用深度为1000，因为我得到 998 ，但是有一个用于main，一个用于初始调用该方法，使得 1000 总之。这是一个太圆的数字恕我直言，是一个巧合。我会进一步调查。我只是Dux开销-Xss vm参数;这是最大堆栈大小，因此Eclipse运行者必须 -Xss1000 设置在某处

I can't help thinking that Eclipse has a fixed max call depth of 1000, because I got to 998, but there's one for the main, and one for the initial call to the method, making 1000 in all. This is "too round" a number IMHO to be a coincidence. I'll investigate further. I have just Dux overhead the -Xss vm parameter; it's the maximum stack size, so Eclipse runner must have -Xss1000 set somewhere

推荐答案

这显然是JVM-也可能是特定于架构的。

This is clearly JVM- and possibly also architecture-specific.

我测量了以下内容：

  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个字节，其余是其他（固定）开销。

With a 20MB Java stack (-Xss20m), the amortized cost fluctuated around 16-17 bytes per call. The lowest I've seen was 16.15 bytes/frame. I therefore conclude that the cost is 16 bytes and the rest is other (fixed) overhead.

一个函数，只需一个 int 具有基本相同的成本，16字节/帧。

A function that takes a single int has basically the same cost, 16 bytes/frame.

有趣的是，一个函数需要10个 ints 需要32字节/帧。我不确定为什么费用如此之低。

Interestingly, a function that takes ten ints requires 32 bytes/frame. I am not sure why the cost is so low.

上述结果适用于代码编译后的JIT。在编译之前，每帧成本很多，更高。我还没有想出一种可靠的估算方法。 但是，这确实意味着您无法可靠地预测最大递归深度，直到您可以可靠地预测递归函数是否已经过JIT编译。

The above results apply after the code's been JIT compiled. Prior to compilation the per-frame cost is much, much higher. I haven't yet figured out a way to estimate it reliably. However, this does mean that you have no hope of reliably predicting maximum recursion depth until you can reliably predict whether the recursive function has been JIT compiled.

所有这些都是使用 ulimit 的堆栈大小128K和8MB进行测试的。两种情况下的结果相同。

All of this was tested with a ulimit stack sizes of 128K and 8MB. The results were the same in both cases.

这篇关于如何预测递归方法的最大调用深度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！