Recursion Depth in Java

[George Karabotsos]

Hey guys,

I have a question pertinent to how deep I can go with Java as compared
with C and whether there is any way to match or at least closely
approximate the C depth.

For illustration purposes I have written 2 small programs, which are
attached, one is java the other one is in C.

The environment I run these two programs is as follows:

uname -a

Linux xxxxxxx 2.6.14-1.1644_FC4smp #1 SMP Sun Nov 27 03:39:31 EST 2005
i686 i686 i386 GNU/Linux

limit

cputime unlimited
filesize unlimited
datasize unlimited
stacksize unlimited
coredumpsize 0 kbytes
memoryuse unlimited
vmemoryuse unlimited
descriptors 1024
memorylocked 32 kbytes
maxproc 16360

gcc -v

Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man
--infodir=/usr/share/info --enable-shared --enable-threads=posix
--enable-checking=release --with-system-zlib --enable-__cxa_atexit
--disable-libunwind-exceptions --enable-libgcj-multifile
--enable-languages=c,c++,objc,java,f95,ada --enable-java-awt=gtk
--with-java-home=/usr/lib/jvm/java-1.4.2-gcj-1.4.2.0/jre
--host=i386-redhat-linux
Thread model: posix
gcc version 4.0.2 20051125 (Red Hat 4.0.2-8)

/pkg/jdk1.5/bin/java -version

java version "1.5.0_06"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_06-b05)
Java HotSpot(TM) Client VM (build 1.5.0_06-b05, mixed mode)


Ok now to the actual results and question.

With C I am able to go throught the program with no issues. On the
other hand Java throws StackOverflowError at after DoIt is been called
recursively 84K times or so.

82000
83000
84000
Exception in thread "main" java.lang.StackOverflowError

Is there any way I can get java to come close to C's results?

I tried using the -Xms, -Xmx, and -Xss flags but the results did not
changed by much. When tried the same program in SunOS things improved
but I had to allocate a huge stack to make it work.

Thank you in advance,

George

 

[George Karabotsos]

I tried using the -Xms, -Xmx, and -Xss flags but the results did not

changed by much. When tried the same program in SunOS things improved
but I had to allocate a huge stack to make it work.

Ohh one more thing the linux machine has 1Gb of RAM. In the SunOS one I
was able to use the -X options to increase the memory of the java
thread, in the linux one they seem to have no effect.

Thanks again,

George

 

[Adam Warner]

I have a question pertinent to how deep I can go with Java as compared
with C and whether there is any way to match or at least closely
approximate the C depth.

For illustration purposes I have written 2 small programs, which are
attached, one is java the other one is in C.

The environment I run these two programs is as follows:

Linux xxxxxxx 2.6.14-1.1644_FC4smp #1 SMP Sun Nov 27 03:39:31 EST 2005
i686 i686 i386 GNU/Linux

cputime unlimited
filesize unlimited
datasize unlimited
stacksize unlimited
coredumpsize 0 kbytes
memoryuse unlimited
vmemoryuse unlimited
descriptors 1024
memorylocked 32 kbytes
maxproc 16360

These days it is somewhat unusual for the main stack in Linux userspace
to be unlimited. Mine isn't:

$ ulimit -a
core file size (blocks, -c) 0
data seg size (kbytes, -d) unlimited
file size (blocks, -f) unlimited
pending signals (-i) unlimited
max locked memory (kbytes, -l) unlimited
max memory size (kbytes, -m) unlimited
open files (-n) 1024
pipe size (512 bytes, -p) 8
POSIX message queues (bytes, -q) unlimited
stack size (kbytes, -s) 8192
cpu time (seconds, -t) unlimited
max user processes (-u) unlimited
virtual memory (kbytes, -v) unlimited
file locks (-x) unlimited

Here a program is restricted to 8MB of stack space. You are fortunate
your program ran with an "unlimited" size default stack. What is more
likely to be comparable is Java and a multithreaded C application. In a
JVM implementation with native threads running on Linux a Java thread will
have comparable resource limitations to a native POSIX thread.

Here's a Java program to test some startup tradeoffs:

public final class MaxThreads implements Runnable {
static int threads=0;

public void run() {
do {
Thread.yield();
} while(true);
}

public static void main(String[] args) {
try {
do {
new Thread(new MaxThreads()).start();
System.out.print("Scheduled thread number ");
System.out.println(++threads);
System.out.flush();
} while (true);
} catch (OutOfMemoryError e) {
System.out.println("Out of memory. Exiting.");
System.out.flush();
System.exit(1);
}
}
}

Some outcomes with a Sun JVM on Debian IA32:
$ java -Xms1000M -Xmx1000M -Xss2M MaxThreads
....
Scheduled thread number 952
Out of memory. Exiting.

$ java -Xms1000M -Xmx1000M -Xss8M MaxThreads
....
Scheduled thread number 233
Out of memory. Exiting.

$ java -Xms2000M -Xmx2000M -Xss8M MaxThreads
....
Scheduled thread number 108
Out of memory. Exiting.

The number of threads is limited by the address space available for
allocation to threads. Increasing the heap size decreases the address
space available for thread allocation and hence the number of threads that
can be created.

As you comment: "I tried using the -Xms, -Xmx, and -Xss flags but the
results did not changed by much. When tried the same program in SunOS
things improved but I had to allocate a huge stack to make it work."

That's the tradeoff: If you need at least one huge stack you will limit
the number of threads you can create. The point where you can't even
create one additional thread is similar to your single threaded C
situation.

Because address space is the primary issue you may be able to resolve this
by moving to a 64-bit platform and 64-bit JVM.

The alternatives are, if feasible, to rewrite your code to eliminate the
deep recursion or even to implement a language on top of Java with
dynamically heap allocated stacks. People often make do with broken
abstractions because doing the right thing is slower. Dynamic stacks
will require reallocation as they grow which imposes an extra level of
indirection upon access to stack items.

Regards,
Adam

 

[lewmania942]

George Karabotsos wrote:
....

I tried using the -Xms, -Xmx, and -Xss flags but the results did not
changed by much.

What about the -server flag ?

Changes from around 84 000 to about 217 000 here (Pentium 4, 768 Mb
of Ram, also running Fedora Core 4).

 

[George Karabotsos]

Hi Adam,

thanks a lot for the reply quite enlightening

These days it is somewhat unusual for the main stack in Linux userspace
to be unlimited. Mine isn't:

hehe, mine wasn't either, I had to set it to unlimited in my efforts to
make it this work.

The alternatives are, if feasible, to rewrite your code to eliminate the
deep recursion or even to implement a language on top of Java with
dynamically heap allocated stacks. People often make do with broken
abstractions because doing the right thing is slower. Dynamic stacks
will require reallocation as they grow which imposes an extra level of
indirection upon access to stack items.

Its unfortunate but there is no alternative to using deep recursion. I
guess I better freshen up on my C programming again .

Well thanks again for your very helpful comments Adam, much appreciated.

George

 

[George Karabotsos]

Hi,

George Karabotsos wrote:
...



What about the -server flag ?

Changes from around 84 000 to about 217 000 here (Pentium 4, 768 Mb
of Ram, also running Fedora Core 4).

Thanks for pointing out this flag, I was not aware that has this effect.
However, I need to go deeper than that. Its in the millions, which C
seems to be working.

Thanks again,

George

 

[Adam Warner]

Hi,



Thanks for pointing out this flag, I was not aware that has this effect.
However, I need to go deeper than that. Its in the millions, which C
seems to be working.

Debian IA32. 1GB RAM and plentiful swap.

$ java -version
java version "1.6.0-beta2"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.6.0-beta2-b72)
Java HotSpot(TM) Client VM (build 1.6.0-beta2-b72, mixed mode, sharing)

$ java -Xss300M Recursion
....
4967000
4968000
4969000
4970000
4971000
Exception in thread "main" java.lang.StackOverflowError
at Recursion.DoIt(Recursion.java:23)
at Recursion.DoIt(Recursion.java:23)
....

Regards,
Adam

 

[Roedy Green]

Is there any way I can get java to come close to C's results?

you can do two things. Expand the size of the stack with a run time
option. see http://mindprod.com/jgloss/javaexe.html

In a single thread language you can allocate all of the remainder of
your virtual RAM to a single giant stack. In Java every thread needs
it own fixed size stack allocation. Even simple applications may have
a dozen threads or so.

Second you can use an optimising compiler to reduce the stack overhead
at each layer. See http://mindprod.com/jgloss/jet.html

or try the -server option on the JDK version of Java.exe

 

[Jaakko Kangasharju]

Thanks for pointing out this flag, I was not aware that has this
effect. However, I need to go deeper than that. Its in the millions,
which C seems to be working.

I'm curious: what are you writing that requires that many nested
calls? If you cannot simply rewrite your program iteratively, do you
think you could maintain the call stack yourself? This way would
transfer your memory requirements from the stack to the heap.

 

[Roedy Green]

Is there any way I can get java to come close to C's results?

You could probably beat them, but it would a chunk of work.

Back in the olden days I used to code in FORTRAN. The Journal of the
ACM would publish these elegant algorithms in an much more advanced
language called Algol, which supported recursion, e.g. QuickSort.

If you wanted to use them in FORTRAN you had to convert them to use
iteration instead. Granted, the code is quite a bit more complicated,
but it can be more memory efficient since, if you are clever you don't
need to store every last local variable and hidden temporary variables
as part of your state the way recursion does.

Let's say you had a program that called itself in only one place in
the program. What are the crucial local variables you have to
remember? Define an object to hold them. Instead of recursively
calling yourself, push your current state onto a stack (an ArrayList
would do in a pinch), and LOOP back to process the new state.
Eventually you will stop adding states and when you loop back you can
process the top of stack and get rid of it.

 

[Ben Caradoc-Davies]

I have a question pertinent to how deep I can go with Java as compared
with C and whether there is any way to match or at least closely
approximate the C depth.

You have a problem with your C test program. With a sufficiently high
level of optimisation, gcc is "properly tail recursive" for tail calls
in the same translation unit (source file). This means that, if a
function returns the result of a call to itself (or for a void function,
calls itself as its last statement), the compiler can optimise away the
function call and replace it with a jump (passing parameters by
rewriting the stack frame, if needed). This means that, if you turned on
optimisation, you are not using any stack space for each recursive call
to DoIt(). You can recurse infinitely and never run out of stack space.
Try it.

Tail recursion is only optimised for -O2 or better, so for a better
test, use gcc -O0 or gcc -O1. If you do this, the C implementation will
run out of space after less than one million recursions or so, because
Linux i386 stack space is typically limited to around 1 MB per process
(regardless of how much RAM you have).

On Fedora Core 4 x86_64 (gcc-4.0.2), compiled with -O3, your program
completes all 10000000 recursions (as it uses no stack space for each
call after the first), but compiled with -O0 it segfaults after 261000
recursions (it runs out of stack space). I expect similar results on
i386 (x86_64 likely differs as it has a different ABI). Not that much
more than the 84000 for Java.

 

[Boris Gorjan]

Hi Adam,

thanks a lot for the reply quite enlightening


hehe, mine wasn't either, I had to set it to unlimited in my efforts to
make it this work.

Its unfortunate but there is no alternative to using deep recursion. I

What do you mean, there's no alternative? Of course there is: you don't rely on
system stack, you keep your own. It's slower, but it works. As long as there's
any _heap_ left.

 

[Jeffrey Schwab]

Its unfortunate but there is no alternative to using deep recursion. I
guess I better freshen up on my C programming again .

Sorry to butt in, but it would be very strange if your recursion could
not be replaced by a while-loop and a simple stack. Could you provide
some details?

 

[Thomas Hawtin]

Ohh one more thing the linux machine has 1Gb of RAM. In the SunOS one I
was able to use the -X options to increase the memory of the java
thread, in the linux one they seem to have no effect.

IIRC: There is a little problem with Linux and stack sizes. The native
thread that the Java program is launched from will have a limited size.
To work around this create a new thread straight away and discard the
main thread.

In recent builds of Mustang, the java launch program does that for you.
I don't believe beta 1 is sufficiently recent.

Tom Hawtin

 

[George Karabotsos]

Debian IA32. 1GB RAM and plentiful swap.

$ java -version
java version "1.6.0-beta2"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.6.0-beta2-b72)
Java HotSpot(TM) Client VM (build 1.6.0-beta2-b72, mixed mode, sharing)

$ java -Xss300M Recursion
...
4967000
4968000
4969000
4970000
4971000
Exception in thread "main" java.lang.StackOverflowError
at Recursion.DoIt(Recursion.java:23)
at Recursion.DoIt(Recursion.java:23)
...

Regards,
Adam

Thanks again Adam for pointing this out for me!

FYI, one colleague of mine told me the following:
"I sometimes compile java bytecode to native executable using
Excelsior's JET compiler. There are versions for both Win32 and Linux.
(An evaluation version can be had here). With it and marking the
method as final, I was able to get it to run to completion. Attached is
the output."
So I will give that one a try

George

 

[George Karabotsos]

IIRC: There is a little problem with Linux and stack sizes. The native
thread that the Java program is launched from will have a limited size.
To work around this create a new thread straight away and discard the
main thread.

In recent builds of Mustang, the java launch program does that for you.
I don't believe beta 1 is sufficiently recent.

Tom Hawtin

Hi Tom,

thanks for letting me know about this!
Would it be possible to provide me with a small example or point me to
one to see how I can replace the main thread with one created in the
program?

Thanks again,

George

 

[Boris Gorjan]

(An evaluation version can be had here).

Kinky!

 

[Thomas Hawtin]

Would it be possible to provide me with a small example or point me to
one to see how I can replace the main thread with one created in the
program?

Yup. Replace your main with this:


public static void main(String[] args) {
Thread thread = new Thread(new Runnable() { public void run() {
Recursion r=new Recursion();
r.DoIt();
}});
thread.start();
}

Tom Hawtin

 

[George Karabotsos]

You have a problem with your C test program. With a sufficiently high
level of optimisation, gcc is "properly tail recursive" for tail calls
in the same translation unit (source file). This means that, if a
function returns the result of a call to itself (or for a void function,
calls itself as its last statement), the compiler can optimise away the
function call and replace it with a jump (passing parameters by
rewriting the stack frame, if needed). This means that, if you turned on
optimisation, you are not using any stack space for each recursive call
to DoIt(). You can recurse infinitely and never run out of stack space.
Try it.

Tail recursion is only optimised for -O2 or better, so for a better
test, use gcc -O0 or gcc -O1. If you do this, the C implementation will
run out of space after less than one million recursions or so, because
Linux i386 stack space is typically limited to around 1 MB per process
(regardless of how much RAM you have).

On Fedora Core 4 x86_64 (gcc-4.0.2), compiled with -O3, your program
completes all 10000000 recursions (as it uses no stack space for each
call after the first), but compiled with -O0 it segfaults after 261000
recursions (it runs out of stack space). I expect similar results on
i386 (x86_64 likely differs as it has a different ABI). Not that much
more than the 84000 for Java.

Thanks Ben!!
This is another excellent point!!
Much appreciated!!

Actually all of your comments and suggestions have been really helpful!!

Thanks a lot you guys!!

George

 

[Roedy Green]

FYI, one colleague of mine told me the following:
"I sometimes compile java bytecode to native executable using
Excelsior's JET compiler. There are versions for both Win32 and Linux.
(An evaluation version can be had here).

for links to the download and other information see
http://mindprod.com/jgloss/jet.html