Java Fork/Join 计算 0 到 Integer.MAX_VALUE 之间的整数和导致 StackOverflow 错误

Question

我将使用一个示例来利用多核 CPU 架构，该示例计算所有整数 0 到 Integer.MAX_VALUE 的总和。我的门槛是 5000000 个整数。所以我递归地拆分它直到它达到阈值。然后当它达到阈值时，我计算总和。最后将所有的和累加在一起计算最终结果。该问题本质上是递归的，并且非常适合 Fork/join 框架。但是当我运行它时，我收到了错误。有时它是 Whosebug 错误。其他时候是这样。

Exception in thread "ForkJoinPool.commonPool-worker-7" java.lang.NoClassDefFoundError: Could not initialize class java.util.concurrent.locks.AbstractQueuedSynchronizer$Node
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1198)

这是我的代码：

public class ParallelSum extends RecursiveTask<Long> {
    private static final int THRESHOLD = 5000000;

    private final int start;
    private final int end;

    public ParallelSum(int start, int end) {
        super();
        this.start = start;
        this.end = end;
    }

    @Override
    protected Long compute() {
        // System.out.println("Start: " + start + " End: " + end);
        if (end - start > THRESHOLD) {
            return ForkJoinTask.invokeAll(createSubtasks()).stream().mapToLong(ForkJoinTask::join).sum();
        }
        return LongStream.rangeClosed(start, end).sum();
    }

    private Collection<RecursiveTask<Long>> createSubtasks() {
        final List<RecursiveTask<Long>> dividedTasks = new ArrayList<>();
        dividedTasks.add(new ParallelSum(start, end / 2));
        dividedTasks.add(new ParallelSum(end / 2 + 1, end));
        return dividedTasks;
    }
}

主要方法就是这样，

public class ParallelSumTest {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        final long sum = new ParallelSum(0, Integer.MAX_VALUE).compute();
        long endTime = System.currentTimeMillis();
        final long elapsedTime = endTime - startTime;
        System.out.println(sum + " was computed in " + elapsedTime + " milliseconds.");
    }
}

这里缺少什么？我做错了什么？感谢任何帮助。

Answer 1

最有可能引发异常 NoClassDefFoundError，因为 JVM 运行超出永久代 space。和WhosebugException一样，这是因为你的算法产生的递归层次太深了。

创建任务并将工作分成两部分时出现了一个小错误。您应该使用中间索引作为 (start + end) / 2 而不是 end / 2:

dividedTasks.add(new ParallelSum(start, (start + end) / 2));
dividedTasks.add(new ParallelSum((start + end) / 2 + 1, end));

在我的机器上进行了上述调整，我得到了以下输出：

2738188572099084288 was computed in 1636 milliseconds.

Java Fork/Join 计算 0 到 Integer.MAX_VALUE 之间的整数和导致 StackOverflow 错误

Java Fork/Join computing sum of integers between 0 through Integer.MAX_VALUE leads to StackOverflow error

java

concurrency

recursion

fork-join