StackOverflowError when scaling with fork/join architecture

Question

I trying to learn the RecursiveTask class with the classic Fibonacci-algorithm. The algorithm works fine until fibonacci number over 17000, then a StackOverflowError is thrown. I don't know if the problem is the number of threads or that I use a cache to store the calculated numbers. I know that there exist better algorithms to calculate fibonacci numbers but this is just to learn the fork/join architecture and it's limitations. The time it takes for lower numbers (for example number 17800) takes 153 ms and the cache is then of size 13 MB.

Question: how can i make this code scale better (to calculate higher numbers) using the same algorithm?

Fibonacci code:

public class FibonacciTask extends RecursiveTask<BigInteger>{
    // this theshold is used because the overhead of the architecture
    // makes the process crazy slow if we try to use it on easy problems
    private static final int EASYCALC = 10; 
    // limit of the cache
    private static final int CACHELIM = 20000; 
    private int n;

    private static Map<Integer, BigInteger> fibCache = new ConcurrentHashMap<>();

    public BigInteger result;

    public FibonacciTask(int x, Map<Integer, BigInteger> fibCache){
        n = x;
        this.fibCache = fibCache;

        // calculate the first 10 numbers without threads
        if(!fibCache.containsKey(EASYCALC)){

            fibCache.put(EASYCALC, this.fibonacci(EASYCALC));
            result = fibCache.get(x);
        }
    }

    @Override
    protected BigInteger compute() {
        if(!fibCache.containsKey(n)){

            FibonacciTask worker1 = new FibonacciTask(n-1, fibCache);
            FibonacciTask worker2 = new FibonacciTask(n-2, fibCache);
            worker1.fork(); // fork this work to new thread

            result = worker2.compute().add(worker1.join());

            if(n >= CACHELIM){
                return result;
            }
            fibCache.put(n, result);
        }
        return fibCache.get(n);
    }
    // calculate without threads
    public BigInteger fibonacci(int n){

        if(!fibCache.containsKey(n) ){
            fibCache.put(n, fibonacci(n-1).add(fibonacci(n-2)) );
        }

        return fibCache.get(n);
    }    
}

Main:

int n = 17950;
ForkJoinPool pool = new ForkJoinPool(processors);
FibonacciTask task = new FibonacciTask(n, fibCache);

pool.invoke(task);

BigInteger result = task.result;

Error output:

run:
No. of processors: 8
Exception in thread "main" java.lang.StackOverflowError
    at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
    at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:57)
    at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45)
    at java.lang.reflect.Constructor.newInstance(Constructor.java:526)
    at java.util.concurrent.ForkJoinTask.getThrowableException(ForkJoinTask.java:536)
    at java.util.concurrent.ForkJoinTask.reportResult(ForkJoinTask.java:596)
    at java.util.concurrent.ForkJoinTask.join(ForkJoinTask.java:640)
    at java.util.concurrent.ForkJoinPool.invoke(ForkJoinPool.java:1521)
    at cachedThreadedFibonacci.SmartWorker.main(SmartWorker.java:62)
Caused by: java.lang.StackOverflowError
    at cachedThreadedFibonacci.FibonacciTask.compute(FibonacciTask.java:48)
    at cachedThreadedFibonacci.FibonacciTask.compute(FibonacciTask.java:55)
    at cachedThreadedFibonacci.FibonacciTask.compute(FibonacciTask.java:55)
    ... same line repeating

Edit I'm also confused because if I in Netbeans set the stack size to 2Mb (-Xss2M) then it works fine (even though the cache can be up to 17Mb with my tests)? If I set the size to 1 Mb it doesn't work again (fails at the same point as described before), what am I missing?

It is thrown at line "result = worker2.compute().add(worker1.join());". I hope this answer the question. — Olle burman, Dec 25 '14 at 20:43
Well, you *are* using recursion, so obviously you are susceptible to stack overflows. Where's the surprise? — Marko Topolnik, Dec 25 '14 at 20:59
I was hoping that there is some way to controll how many threads that is queued to solve this. Because even if I do not use recursion the problem could be happening and then it would be harder to determined and solve it. So this is only for learning how to make safe applications without unsuspected crashes — Olle burman, Dec 25 '14 at 21:15
A stack overflow occurs on a single thread as each thread has its own stack. — William Price, Dec 25 '14 at 22:57
Aha, but isn't ForkJoinPool used to handle that not more than the number of threads specied is active at the same time (which is in my case is the number of cores in the processor)? — Olle burman, Dec 25 '14 at 23:58
... and if the stack for **one thread** exceeds the maximum size allowed, how does the _number of threads_ matter? — William Price, Dec 30 '14 at 09:04

score 2 · Accepted Answer · edited May 23 '17 at 11:51

The following (incomplete) snippet is from your FibonacciTask class.

@Override
protected BigInteger compute() {
    if(!fibCache.containsKey(n)){

        FibonacciTask worker1 = new FibonacciTask(n-1, fibCache);
        FibonacciTask worker2 = new FibonacciTask(n-2, fibCache);
        worker1.fork(); // fork this work to new thread

        result = worker2.compute().add(worker1.join());

     // ... snip ...
}

Your question is focusing too much on the number of threads used by the fork-join pool. While the call to worker1.fork() does spawn work on different threads, it is not the source of your problem. The call to worker2.compute() happens on the current thread, even though that method is called on a different (new) instance. Every such call creates its own instance of worker2 and continues to call that object's compute() method on that very same thread.

This is a recursive algorithm, not to mention your task extends RecursiveTask. There is a finite amount of memory available per thread for maintaining the method call stack. And any sufficiently deep recursive algorithm can exceed that limit; as you observed, in Java this results in a StackOverflowException.

Attempting to relate this error to the size of your Map-based cache is meaningless. Your map and its content lives on the heap, which is a completely separate area of memory from the thread call stacks.

FibonacciTask task = new FibonacciTask(n, fibCache);
pool.invoke(task);

This causes a stack depth of at least (n/2) calls to compute() on the single thread selected by pool.invoke() that is used to execute the first iteration of the task. With a large enough value of n, you can exceed the maximum allowable stack depth. As you discovered, increasing the Java stack size can prevent this error for a given value of n. However, with a recursive algorithm such as this, increasing the stack size does not "fix" the problem, it merely delays the problem until you choose a new value for n that is high enough to exceed the new per-thread stack memory region.

StackOverflowError when scaling with fork/join architecture

1 Answers1