Intermittent Stack Overflow for Recursion Method

Question

I have a simple method I've written for a class homework assignment that uses recursion (yes, it must use recursion) to calculate the number of triangles in a fractal pattern:

public static BigInteger triangleFract(int layer) {
    if(layer < 0) {
        throw new IllegalArgumentException("Input must be >= 0");
    } else if(layer == 0) {
        return new BigInteger("0");
    } else if (layer == 1) {
        return new BigInteger("1");
    } else {
        return triangleFract(layer - 1)
              .multiply(new BigInteger("3"))
              .add(new BigInteger("2"));
    }
}

What I've been trying to do is understand how big the int layer can be so as to limit user input. After some tests I get a stack overflow at around 6700+, which is fine.

What is troubling me is that if layer is in the thousands, the method usually runs, but it can still randomly encounter a StackOverflowError.

For instance, I chose to limit layer to 4444, and it seems to be able to handle that almost always, but every once in a while it still seems to overflow.

Why does it do this? And is there anything that I can do about it?

Answer 1

Perhaps the JVM has determined (through escape analysis) that the BigInteger can be allocated on the stack rather than the heap. Depending on when it implements this optimization, the required stack size would vary.

That said, there could be many other causes, and the behaviour is likely to depend on the JVM you use.

Answer 2

Consider to move to iterated version. That what I think if you developing a recursion algorithm you must control the level depth or don't use recursion at all.

Answer 3

There is actually something you can do: increase the maximum stack size. This is done at JVM startup with the option -Xss like this:

java -Xss40m MainClass

Be careful not to set an excessively high value. If you have to go over 60M - 70M, then a redesign of your code is recommended.

Answer 4

I couldn't reproduce your 'fluctuation' effect. This is pretty deterministic code, so you should get the same result every time (including the stack overflow error).

How did you test it? Did you run a new jvm for each try of your 4444 test? (or was it just the triangleFrac(4444); called in a loop?).

What's your OS, java version etc...

I'm asking because I don't really like unsolved problems like this --- something like this could bite you where (and when) it hurts ;).

oh... BTW, for all it's worth, you should be using the ONE and ZERO constants from BigInteger (and create your own for 2 and 3, for that matter. This should save you quite a bit of memory (yes, I know, this wasn't your question).

Answer 5

Allowing recursion to that depth is a design smell.

Try this iterative version:

public static BigInteger triangleFract(int layer) {
    if (layer < 0) {
        throw new IllegalArgumentException("Input must be >= 0");
    }
    if (layer == 0) {
        return BigInteger.ZERO;
    }
    BigInteger result = BigInteger.ONE;
    BigInteger two = new BigInteger("2");
    BigInteger three = new BigInteger("3");
    for (int i = 1; i < layer; i++) {
        result = result.multiply(three).add(two);
    }
    return result;
}

Notes:

• Using BigInteger.ZERO and BigInteger.ONE instead of creating new instances for these values
• Removed redundant else - there is no else after a terminating statement (eg return)
• Re-using new BigInteger("2") and new BigInteger("3") rather than creating new instances every iteration

Answer 6

For those who can't reproduce this fluctuation. Find the layer value starting from which method will reliably throw StackOverflowError. The closer this value to the real threshold the better. Now call this method from inside the loop (on my machine maxLayer = 11500):

int i = 11500;
while (true) {
    System.out.println(i);
    triangleFract(i++);
}

It will throw StackOverflowError. Now decrease this value a little bit (looks like 5-10% should be enough):

int i = 10500;
while (true) {
    System.out.println(i);
    triangleFract(i++);
}

Well on my machine this doesn't throw any error and successfully jumps over 11500. Actually it works fine up until 16000.

So whatever it is it probably involves JVM optimisations. I tried to run a program with -XX:+PrintCompilation. I saw how JIT does its job while looping:

117   1       java.lang.String::hashCode (64 bytes)
183   2       java.lang.String::charAt (33 bytes)
189   3       sun.nio.cs.UTF_8$Decoder::decodeArrayLoop (553 bytes)
201   4       java.math.BigInteger::mulAdd (81 bytes)
205   5       java.math.BigInteger::multiplyToLen (219 bytes)
211   6       java.math.BigInteger::addOne (77 bytes)
215   7       java.math.BigInteger::squareToLen (172 bytes)
219   8       java.math.BigInteger::primitiveLeftShift (79 bytes)
224   9       java.math.BigInteger::montReduce (99 bytes)
244  10       sun.security.provider.SHA::implCompress (491 bytes)
280  11       sun.nio.cs.UTF_8$Encoder::encodeArrayLoop (490 bytes)
282  12       java.lang.String::equals (88 bytes) 11400
289  13       java.lang.String::indexOf (151 bytes)
293  14       java.io.UnixFileSystem::normalize (75 bytes)
298  15       java.lang.Object::<init> (1 bytes)
298  16       java.util.jar.Manifest$FastInputStream::readLine (167 bytes)
299  17       java.lang.CharacterDataLatin1::getProperties (11 bytes)
300  18       NormalState::triangleFract (74 bytes)
308  19       java.math.BigInteger::add (178 bytes)
336  20       java.lang.String::lastIndexOf (151 bytes)
337  21       java.lang.Number::<init> (5 bytes)
338  22       java.lang.Character::digit (6 bytes)
340  23       java.lang.Character::digit (168 bytes)
342  24       java.lang.CharacterDataLatin1::digit (85 bytes)
343  25       java.math.BigInteger::trustedStripLeadingZeroInts (37 bytes)
357  26       java.lang.String::substring (83 bytes)
360  27       java.lang.String::lastIndexOf (10 bytes)
360  28       java.lang.String::lastIndexOf (29 bytes)
361  29       java.math.BigInteger::<init> (24 bytes)
361  30       java.lang.Integer::parseInt (269 bytes)
361  31       java.math.BigInteger::<init> (8 bytes)
362  32       java.math.BigInteger::<init> (347 bytes)
404  33       java.math.BigInteger::multiply (72 bytes)
404  34       java.math.BigInteger::add (123 bytes)

May it be compilation? Let's try to delay compilation so it affects us as late as possible. I tried to play with -XX:CompileThreshold flag and pretty soon found a value (-XX:CompileThreshold=1000000) which doesn't let my loop jump over 11500.

UPDATE

I finally reproduced it without any tweaking of compilation threshold. For me it looks like it only happens when I run program in my IDE (IntelliJ IDEA). So it may have something to do with IDEA's launcher. I copied its command line and used it in a small script:

for I in `seq 1 100`; do 
        java ... com.intellij.rt.execution.application.AppMain \
        Triangle 2>&1| grep Stack; done | wc -l

And what I found out it usually prints out something less than 100 (95-98). Which is consistent to what I saw when did it manually. When I skip the launcher:

for I in `seq 1 100`; do 
        java \
        Triangle 2>&1| grep Stack; done | wc -l

it always prints out 100.