java - 使用 fork/join 架构扩展时出现 StackOverflowError

Question

我正在尝试使用经典的斐波那契算法学习 RecursiveTask 类。该算法工作正常，直到斐波那契数超过 17000，然后抛出 StackOverflowError。我不知道问题是线程数还是我使用缓存来存储计算出的数字。我知道存在更好的算法来计算斐波那契数，但这只是为了学习 fork/join 架构及其局限性。较低的数字(例如数字 17800)花费的时间为 153 毫秒，缓存大小为 13 MB。

问题:我如何使用相同的算法使此代码规模更好(以计算更高的数字)？

斐波那契代码:

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);
    }    
}

主要内容:

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

pool.invoke(task);

BigInteger result = task.result;

错误输出:

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 

编辑我也很困惑，因为如果我在 Netbeans 中将堆栈大小设置为 2Mb (-Xss2M) 那么它工作正常(即使我的测试缓存可以达到 17Mb)？如果我将大小设置为 1 Mb，它不会再次工作(如前所述在同一点失败)，我错过了什么？

Answer 1

以下(不完整)片段来自您的 FibonacciTask类。

@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 ...
}

您的问题过于关注 fork-join 池使用的线程数。调用 worker1.fork() spawn 在不同的线程上工作，它不是问题的根源。调用worker2.compute()发生在当前线程，即使该方法是在不同的(新)实例上调用的。每个这样的调用都会创建自己的 worker2 实例并继续调用该对象的 compute()该非常相同线程上的方法。

这是一个递归算法，更不用说你的任务扩展了 RecursiveTask . 每个线程 可用于维护方法调用堆栈的内存量是有限的。并且任何足够深的递归算法都可以超过该限制；如您所见，在 Java 中这会导致 StackOverflowException .

尝试将此错误与基于 map 的缓存大小联系起来是没有意义的。您的 map 及其内容位于堆，这是一个与线程调用堆栈完全独立的内存区域。

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

这导致堆栈深度至少为 (n/2) 次调用 compute()在由pool.invoke() 选择的单线程 上用于执行任务的第一次迭代。具有足够大的值 n ，您可以超过最大允许堆栈深度。正如您所发现的，increasing the Java stack size对于 n 的给定值可以防止此错误.但是，使用这样的递归算法，增加堆栈大小并不能“解决”问题，它只会延迟问题，直到您为 n 选择一个新值为止。这足以超过新的每线程堆栈内存区域。