Where is variablilty in stack consumption coming from?

Question

Whilst running test code from this question and fiddling with the JVM's thread stack size, I found that results were not necessarily repeatable: there were values of stack size for which the program would sometimes throw java.lang.StackOverflowError, but sometimes not.

My question is: "What is causing the variation in stack space consumption?"

Also, can an interrupt's stack be put on this program's main thread? Will results be similarly non-deterministic for other JVM implementations and/or operating systems?

Test Code

public class PointlessRecursion {

    private static final long N = 1 << 15;

    private static long addOne(long n) {
        return (n < 2) ? n : 1 + (addOne(n - 1));
    }

    public static void main(String[] args) {
        try {
            long x = addOne(N);
            System.out.println(x);
            assert(x == N);
            System.exit(0);
        } catch (StackOverflowError e) {
            System.exit(1);
        } catch (Throwable t) {
            System.err.println(t.toString());
            System.exit(2);
        }
    }
}

Silly bash script for running test program multiple times for each stack size setting

#! /bin/bash
s=2000
while [ $s -lt 4100 ] ; do
    i=0
    pass=0
    fail=0
    while [ $i -lt 10 ] ; do
        java -Xss${s}k -cp ~/bin/classes PointlessRecursion > /dev/null
        if [ $? -eq 0 ] ; then
            pass=$((pass+1))
        elif [ $? -eq 1 ] ; then
            fail=$((fail+1))
        fi
        i=$((i+1))
    done
    echo ss=$s pass=$pass fail=$fail
    s=$(($s+100))
done

Results

$ java -version
java version "1.6.0_20"
Java(TM) SE Runtime Environment (build 1.6.0_20-b02)
Java HotSpot(TM) 64-Bit Server VM (build 16.3-b01, mixed mode)
$ ~/bin/stack-test.sh
ss=2000 pass=0 fail=10
ss=2100 pass=1 fail=9
ss=2200 pass=0 fail=10
ss=2300 pass=2 fail=8
ss=2400 pass=1 fail=9
ss=2500 pass=1 fail=9
ss=2600 pass=2 fail=8
ss=2700 pass=6 fail=4
ss=2800 pass=3 fail=7
ss=2900 pass=1 fail=9
ss=3000 pass=3 fail=7
ss=3100 pass=3 fail=7
ss=3200 pass=6 fail=4
ss=3300 pass=2 fail=8
ss=3400 pass=4 fail=6
ss=3500 pass=10 fail=0
ss=3600 pass=9 fail=1
ss=3700 pass=10 fail=0
ss=3800 pass=10 fail=0
ss=3900 pass=10 fail=0
ss=4000 pass=10 fail=0

Answer 1

I don't observe this behaviour. In my environment (Windows 7 x64, 1.6.0_19 x86 JDK) they fail consistently up to a certain point and then start passing at ss=1400 (I bumped it down since they were all passing with your parameters).

The only thing I changed was to not specify a classpath (I ran the script from the same directory as the class file). But even when specifying a classpath I got the same results.

Are you sure it's actually StackOverflowError that you're catching? I would catch that error solely instead of the generic Throwable to make sure it isn't something else, like an OutOfMemoryError.

//...
} catch (StackOverflowError e) {
    System.exit(1);
}

That way it'll print a stacktrace if it's not actually a StackOverflowError you're getting.

Answer 2

I would not be surprised if it had something to do with the timing the HotSpot compiler kicks in, specially if you are running on a multicore system.

EDIT: To check this you can launch your test with -Xint. IF you start getting reproducible results, then the nondeterministic behavior is probably caused by the HotSpot compiler.