How to predict the maximum call depth of a recursive method?

Question

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?

Edit:

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);
}

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?

Edit: 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

(It seems like this would depend on the JVM and possibly architecture.) — , Dec 21 '12 at 19:16
I _guess_ it's just the local variables + frame pointer + return address. — John Dvorak, Dec 21 '12 at 19:17
http://stackoverflow.com/questions/4734108/what-is-the-maximum-depth-of-the-java-call-stack — P.P, Dec 21 '12 at 19:18
Recursion really has nothing to do with this (except it's the most common way to generate a really deep call stack). For the purposes of determining call depth limit, recursive calls are no different than any other type of call. (Of course, a compiler might eliminate tail recursion, in which case recursion is an active distraction from your question.) — Ted Hopp, Dec 21 '12 at 19:24
Any. `List a = new ArrayList();` will use up more memory than `List a;`. The OP asks for total memory usage. — SJuan76, Dec 21 '12 at 19:26
@JanDvorak Does Java have a separate memory space for stack and heap? I really do not know, if it is yes then object creation is irrelevant for recursion (at least until it runs of space itself), if not they both count. — SJuan76, Dec 21 '12 at 19:29
@SJuan76 there are two different exceptions, `OutOfMemoryError` and `StackOverflowError`, so I'm assuming Java has the notion of a stack size / heap size :-) — John Dvorak, Dec 21 '12 at 19:32
Java certainly has separate stack and heap spaces, but as referenced in [my answer](http://stackoverflow.com/a/13995940/839646), stack size may be variable and/or dynamic, and stack frames may be allocated on the heap, so all of this depends on the JVM in use and how it's configured. — Ryan Stewart, Dec 21 '12 at 20:07
@RyanStewart Is it possible that the possibility of stack = heap is intended primarily for devices that don't have a separate stack memory, never to be used on x86/x64? — John Dvorak, Dec 22 '12 at 09:28
@Jan: Anything's possible :) I haven't found anything on google indicating how any real JVMs behave in this area, so it may be that this feature just isn't used. I suppose in the end, regardless of where things are allocated, you'll be bounded by the overall system memory available, but you can't really derive a formula from that, as the OP asked. — Ryan Stewart, Dec 22 '12 at 15:15

NPE · Accepted Answer · 2012-12-22T10:03:50.643

25

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

I've measured the following:

  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);
      }
      ...
  }

using

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

running on x86.

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.

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

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

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.

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

edited Dec 22 '12 at 10:03

answered Dec 21 '12 at 19:24

NPE

486,780
108
951
1,012

6

How are you measuring the recursion depth? – John Dvorak Dec 21 '12 at 19:25
3

He/She can easily measure the recursive depth with a static member field that is incremented on each call – Amir Afghani Dec 22 '12 at 02:29
About 16 bytes per stack frame on a 64-bit system looks like a return address + one extra address (frame pointer? `this` pointer (which is technically `null`, not absent)?) – John Dvorak Dec 22 '12 at 09:25
@Bohemian: I've expanded the answer (didn't have time to do it last night). – NPE Dec 22 '12 at 09:42
@JanDvorak: I would expect there to be no `this` at all. I can only guess what the second 8 bytes are for. Could well be a pointer of some sort. – NPE Dec 22 '12 at 09:59
Does anyone know if there's a way to make HotSpot print out the assembly it produces when JIT compiling? That would answer a lot of these questions... – NPE Dec 22 '12 at 10:00
@NPE You could try a classic disassembler like CheatEngine. Not sure how to find the compiled piece of code then, though. I will try to, though. – John Dvorak Dec 22 '12 at 12:31

score 10 · Answer 2 · answered Dec 21 '12 at 19:20

Only a partial answer: from JVM Spec 7, 2.5.2, stack frames can be allocated on the heap, and the stack size may be dynamic. I couldn't say for certain, but it seems it should be possible to have your stack size bounded only by your heap size:

Because the Java virtual machine stack is never manipulated directly except to push and pop frames, frames may be heap allocated.

and

This specification permits Java virtual machine stacks either to be of a fixed size or to dynamically expand and contract as required by the computation. If the Java virtual machine stacks are of a fixed size, the size of each Java virtual machine stack may be chosen independently when that stack is created.

A Java virtual machine implementation may provide the programmer or the user control over the initial size of Java virtual machine stacks, as well as, in the case of dynamically expanding or contracting Java virtual machine stacks, control over the maximum and minimum sizes.

So it'll be up to the JVM implementation.

score 4 · Answer 3 · answered Dec 21 '12 at 20:14

4

Addig to NPEs answer:

The maximum stack depth seems to be flexible. The following test program prints vastly different numbers:

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();
    }
}

The output is:

I've used the default of this 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)

So the conclusion is: If you pus had enough (i.e. more than twice) you get a second chance ;-)

answered Dec 21 '12 at 20:14

A.H.

63,967
15
92
126

Really interesting but I'm not completely sure I'd trust my VM after catching a StackOverflow... I guess it would be safe but it's still a little scary. – Bill K Dec 22 '12 at 00:17
The whole question is about stuff on the edge. My hope is that someone can shed some light on the condition when the JVM switches the gears (from 10k to 60k). – A.H. Dec 22 '12 at 09:06
If you change the -Xss setting, it changes how many times you get the "low" vs the "high" output. My guess would be that the JVM just gets into a corrupted state, which is why you don't try to recover from Errors. – Ryan Stewart Dec 22 '12 at 15:54
1

@RyanStewart: OR (already mentioned in some other answer): The JIT compiler kicks in and uses a second, more compact stack frame format. Also I don't believe, that the JVM is in a corrupt state since this way out of the JVM sandbox would be just to easy. And after all the error is detected by the JVM. – A.H. Dec 22 '12 at 16:56
1

@A.H. I agree. It's the compiler. I changed your code to run ten times but cut off at about 10k recursions, thereby avoiding the overflow. Then after that ran one more time until overflow, and it had bumped up to the ~60k. – Ryan Stewart Dec 22 '12 at 17:57

score 3 · Answer 4 · answered Dec 21 '12 at 19:21

3

The answer is, it all depends.

First of all, the Java Stack size can be changed.

Second of all, the stack frame size of a given method can vary based on different variables. You can look at the Call Stack Frame Size section of Call stack - Wikipedia for more details.

answered Dec 21 '12 at 19:21

Justin Niessner

242,243
40
408
536

Stack frames may be heap-allocated, so frame size may be irrelevant, depending. – Ryan Stewart Dec 21 '12 at 19:22

score 2 · Answer 5 · answered Dec 21 '12 at 19:21

2

depends on your system-architecture (32 or 64 bit addresses), the amount of local variables and parameters of the method. If it is tail-recursive no overhead, if the compiler optimize it to a loop.

You see, no simple answer.

answered Dec 21 '12 at 19:21

MrSmith42

9,961
6
38
49

This is tagged "java", so we're assuming we're talking about a JVM here. – Ryan Stewart Dec 21 '12 at 19:22
@RyanStewart There are 32 and 64bit JVMs – MrSmith42 Dec 21 '12 at 19:58
2

There are, but memory in the JVM works the same regardless. There also is no tail recursion in the JVM, nor do I know of any java compiler that will do any such optimization. Therefore, it seemed to me you must be talking about something else. – Ryan Stewart Dec 21 '12 at 20:03
@Ryan Stewart: I just made a google search and was shocked that there is no tail recursion optimization for java yet. But might be in the future. – MrSmith42 Dec 26 '12 at 16:42

score 2 · Answer 6 · edited May 23 '17 at 12:17

2

You can take the empirical road and experiment with your code and the -Xss setting. See here for more: JVM option -Xss - What does it do exactly?

edited May 23 '17 at 12:17

Community

1
1

answered Dec 21 '12 at 19:29

David Soroko

8,521
2
39
51

How to predict the maximum call depth of a recursive method?

Edit:

6 Answers6

Linked

Related