javanetbeans's blog

Available stack size in Java vs. C++?
By javanetbeans, 12 years ago, In English

Today I was going through SRM-556 DIV-2 500 question.

I tried to implement the solution in Java. It didn't work. Then implemented in C++. It worked. In Java I got stackoverflow error. While in C++, it ran perfectly.

Please refer this post

For the last test cases, the number of recursive calls made is 25600. Doesn't Java have enough space to accomodate this much instances (copies) of program.

Please help me why I am getting such strange behavior in Java????

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

There is no "stack size in C++" or "stack size in Java" — these values could be configured at compilation / runtime (though at TopCoder you, perhaps, could not control it).

You wrote:

Stack size for last test cases is roughly 25600. Is it that Java's available stack size is less than this?

But stack size is not measured in stack frames. Stack size is defined in bytes (and sometimes you can change this setting, for example from command line) — and it depends on your implementation how much each stack frame takes. For example you could try and make the method static, or use arguments of smaller size (shorts, for example). However, I do not believe such monkeying is a good approach.

I think when you see that recursion could be too deep, you need to use external stack (and iteration) or something like it. It would never do to write programs which are at the edge of failing by design.

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Try this

new Thread(null, new Runnable() {
            public void run() {
                new Main().run();
            }
        }, "1", 1 << 23).start();

Executes .run() method with 8Mb stacksize. (Last parametr == (1 << 23) )

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    In your case:

    new Thread (null, new Runnable() {
	public void run() {
		dfs(0, ans);				
	}
}, "1", 1 << 23);
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Since this is competitive problem, I am not allowed to use threads.... :)

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is not cheating, it is quite old recipe found in old submission of Petr Mitrichev, for example. The idea is that newly created threads could use larger stack. However I do not remember whether it makes sense for nowadays versions of java.

        Read the post thoroughly and perform some experiments if you want.

        → Reply