java - Java-8 的 DoubleStream.sum() 方法在并行运行时是否稳定？

Question

我很好奇 Java 8 中的以下构造:

double[] doubles = //...
double sum = DoubleStream.of(doubles).parallel().sum();

切入正题:

• sum 的值是否始终相同，例如什么时候在不同的计算机上运行？

---

更多背景...

浮点算术是有损的并且(与实值算术不同)不是关联的。因此，除非注意工作的划分和重组方式，否则可能会导致不确定的结果。

我很高兴地发现 sum() 方法使用了 Kahan Summation在引擎盖下。这显着减少了错误，但仍然不能给出精确的*结果。

在我的测试中，重复调用似乎每次都返回相同的结果，但我想知道我们可以安全地假设它有多稳定。例如:

1. 在所有情况下都稳定吗？
2. 在具有相同内核数的计算机上是否稳定？
3. 仅在给定的计算机上稳定？
4. 不能完全依赖它稳定吗？

我很高兴假设每台计算机上的 JVM 版本相同。

这是我做的一个测试:

public static void main(String[] args) {
    Random random = new Random(42L);
    for (int j = 1; j < 20; j++) {

        // Stream increases in size and the magnitude of the values at each iteration.
        double[] doubles = generate(random, j*100, j);

        // Like a simple for loop
        double sum1 = DoubleStream.of(doubles).reduce(0, Double::sum); 

        double sum2 = DoubleStream.of(doubles).sum();
        double sum3 = DoubleStream.of(doubles).parallel().sum();

        System.out.println(printStats(doubles, sum1, sum2, sum3));

        // Is the parallel computation stable?
        for (int i = 0; i < 1000; i++) {
            double sum4 = DoubleStream.of(doubles).parallel().sum();
            assert sum4 == sum3;
        }
        Arrays.sort(doubles);
    }
}

/**
 * @param spread When odd, returns a mix of +ve and -ve numbers.
 *               When even, returns only +ve numbers.
 *               Higher values cause a wider spread of magnitudes in the returned values.
 *               Must not be negative.  
 */
private static double[] generate(Random random, int count, int spread) {
    return random.doubles(count).map(x -> Math.pow(4*x-2, spread)).toArray();
}

private static String printStats(double[] doubles, double sum1, double sum2, double sum3) {
    DoubleSummaryStatistics stats = DoubleStream.of(doubles).summaryStatistics();

    return String.format("-----%nMin: %g, Max: %g, Average: %g%n"
            + "Serial difference:   %g%n"
            + "Parallel difference: %g",
            stats.getMin(), stats.getMax(), stats.getAverage(), sum2-sum1, sum3-sum1);
}

当我运行它时，前几次迭代是:

-----
Min: -1.89188, Max: 1.90414, Average: 0.0541140
Serial difference:   -2.66454e-15
Parallel difference: -2.66454e-15
-----
Min: 0.000113827, Max: 3.99513, Average: 1.17402
Serial difference:   1.70530e-13
Parallel difference: 1.42109e-13
-----
Min: -7.95673, Max: 7.87757, Average: 0.0658356
Serial difference:   0.00000
Parallel difference: -7.10543e-15
-----
Min: 2.53794e-09, Max: 15.8122, Average: 2.96504
Serial difference:   -4.54747e-13
Parallel difference: -6.82121e-13

请注意，虽然可以假设 sum2 和 sum3 比 sum1 更准确 - 它们可能彼此不同!

我将 Random 播种为 42，所以如果有人得到与我不同的结果，那将立即证明一些事情。 :-)

---

* 对于好奇的人......

• 这里有 some (python) algorithms给出精确的结果
• 我听说过的具有最佳性能特征的精确求和算法是 given here (需要 ACM 订阅或费用)。每个输入需要 5 次触发器，但是(用 C 语言)编写是为了利用指令级并行性，并且只比简单求和慢 2 到 3 倍，这对于精确的结果来说听起来相当不错。 (c.f. Kahan summation at 4 flops per input)

Answer 1

我认为 DoubleStream::sum 的文档很清楚这个问题:

[..] The value of a floating-point sum is a function both of the input values as well as the order of addition operations. The order of addition operations of this method is intentionally not defined to allow for implementation flexibility to improve the speed and accuracy of the computed result. [..]

这意味着，您不应该依赖稳定性，尤其是并行流。

---

另一方面，每次运行都看到相同的结果也就不足为奇了。 从概念上来说，sum方法可能实现如下:

double sum(double[] array, int startInclusive, int endExclusive) {
    int distance = endExclusive - startInclusive;
    if (distance < 1000) {
        double total = 0;
        for (int i = startInclusive; i < endExclusive; ++i) {
            total += array[i];
        }
        return total;
    } else {
        int middle = startInclusive + distance / 2;
        var left = async sum(array, startInclusive, middle);
        var right = async sum(array, middle, endExclusive);
        return await left + await right;
    }
}

虽然异步执行任务的调度是不确定的，但该方法总是返回相同的结果，因为加法操作的顺序是相同的(即括号没有重新排列)。

但是，更复杂的实现可能会考虑当前的工作负载以及子任务的预期执行时间(与异步操作的成本相比)。如果发生这种情况，结果可能会有所不同。