Re: Recursion Depth in Java

On Thu, 23 Feb 2006 17:26:14 -0500, George Karabotsos wrote:
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

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
.

Relevant Pages

  • Re: forth and virtual memory
    ... too, maybe even the same order, so ordering the blocks by allocation ... on systems with too little memory ... What Java is known for, and what it actually does, are two distinct ... My measurements indicate that some of the benchmarks (from SpecJVM98, ...
    (comp.lang.forth)
  • Re: function "&" for strings type cause memory problem.
    ... > and I allocate the large object in heap memory in previous case. ... Memory allocation is always a risk. ... There is no difference between stack and heap here. ...
    (comp.lang.ada)
  • Re: function "&" for strings type cause memory problem.
    ... > its execution state i. Si/|Si| is an average object size. ... >> and I allocate the large object in heap memory in previous case. ... One can ignore allocation issues as long as ... > the heap can be enlarged on demand while the stack not, ...
    (comp.lang.ada)
  • Re: ten thousand small processes
    ... them roughly in the middle you take space away from heap and stack ... identical across two processes as is the case with large shared memory ... There is no special allocation for virtual address space that is ... the standard libc or at least not the standard malloc implementation. ...
    (freebsd-performance)
  • Re: C++ vs Java "new" (no flame war please!)
    ... of such objects that would fit in available memory. ... memory and much more time than would the JVM for the equivalent Java ... The "allocation" ... If you have a small object with a string, ...
    (comp.lang.java)