Est le DoubleStream de Java-8.méthode sum () stable lorsqu'il est exécuté en parallèle?

Je suis curieux de connaître la construction suivante dans Java 8:

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

Pour aller droit au but:

• la valeur de sum toujours la même, par exemple lorsqu'il est exécuté sur des ordinateurs différents?

Plus d'arrière-plan...

L'arithmétique à virgule flottante est avec perte et (contrairement à l'arithmétique à valeur réelle) n'est pas associative. Donc, à moins de prendre soin de la façon dont le travail est divisé et réassemblé, cela pourrait conduire à non déterministe résultat.

J'ai été heureux de découvrir que la méthode sum() emploiesommation Kahan sous le capot. Cela réduit considérablement l'erreur, mais ne donne toujours pas de résultats précis*.

Dans mes tests, les appels répétés semblent renvoyer le même résultat à chaque fois, mais j'aimerais savoir à quel point nous pouvons le supposer en toute sécurité. par exemple:

1. Stable en toutes circonstances?
2. Stable sur les ordinateurs avec le même nombre de cœurs?
3. Stable uniquement sur un compte tenu de l'ordinateur?
4. ne peut pas dépendre du fait qu'il soit stable du tout?

Je suis heureux d'assumer la même version de JVM sur chaque ordinateur.

Voici un test que j'ai fouetté:

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

Lorsque je lance ceci, les premières itérations sont:

-----
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

Notez que tout en sum2 & sum3 peut être supposé être plus précis que sum1 - ils pourraient ne pas être les mêmes que les autres!

Je ensemencées Random, 42, donc si quelqu'un obtient un résultat différent pour moi, ce serait immédiatement prouver quelque chose. :-)

* Pour les plus curieux...

• Voici quelques algorithmes (python) {[29] } qui donnent des résultats précis
• l'algorithme à somme précise avec les meilleures caractéristiques de performance dont j'ai entendu parler est donné ici (abonnement ACM ou frais requis). Il faut 5 flops par entrée, mais est écrit (en C) pour exploiter le parallélisme au niveau de l'instruction et ne fonctionne que 2 à 3 fois plus lentement que la sommation naïve, ce qui semble plutôt bon pour un résultat précis. (C. F. somme de Kahan à 4 flops par entrée)