并行运行时,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,所以如果有人得到不同的结果,那将立即证明一些事情.:-)

---

* 对于好奇......

• 以下是一些(python)算法,可以提供精确的结果
• 这里给出了我所听到的具有最佳声音性能特征的精确求和算法(需要ACM订阅或费用).每个输入需要5个触发器,但写入(在C中)以利用指令级并行性,并且只比初始求和运行慢2-3倍,这对于精确结果来说听起来相当不错.(参考Kahan总和每次输入4个字符串)

Answer 1

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

[..]浮点和的值是输入值以及加法运算顺序的函数.故意不定义该方法的加法运算的顺序以允许实现灵活性以提高计算结果的速度和准确性.[..]

这意味着,您不应该依赖稳定性,特别是不要依赖于并行流.

另一方面,每次运行都会看到相同的结果,这并不奇怪.从概念上讲,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;
    }
}

虽然异步执行任务的调度是非确定的,但该方法总是返回相同的结果,因为加法运算的顺序是相同的(即括号不重新排列).

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