代码之家  ›  专栏  ›  技术社区  ›  Ravindra Ranwala

Java Fork/Join计算0到Integer之间的整数之和。MAX\u值导致StackOverflow错误

  •  0
  • Ravindra Ranwala  · 技术社区  · 7 年前

    我将使用一个示例来利用多核CPU体系结构,该示例计算0到n的所有整数之和 Integer.MAX_VALUE . 我的阈值是5000000个整数。所以我递归地拆分它,直到它达到阈值。然后当它达到阈值时,我计算总和。最后,将所有总和累加在一起,以计算最终结果。这个问题本质上是递归的,很好地符合Fork/join框架。但当我运行它时,我会出错。有时是Stackoverflow错误。其他时候是这样的。

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

    这里缺少什么?我做错了什么?非常感谢您的帮助。

    1 回复  |  直到 7 年前
        1
  •  0
  •   Alexandre Dupriez    7 年前

    例外情况 NoClassDefFoundError 很可能是因为JVM的永久生成空间不足而引发的。就像 StackOverflowException ,这是因为算法生成的递归级别太深。

    创建任务并将工作分成两部分时,会出现一个小错误。您应该使用中间索引作为 (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.