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

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

...

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

On Thu, 23 Feb 2006 17:26:14 -0500, George Karabotsos
<karabot@vif.com> wrote, quoted or indirectly quoted someone who said

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

On Thu, 23 Feb 2006 17:26:14 -0500, George Karabotsos
<karabot@vif.com> wrote, quoted or indirectly quoted someone who said

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.

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.