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)
28
demandé sur Tagir Valeev 2014-05-10 16:28:12

2 réponses

Je pense que la documentation de DoubleStream::sum est assez clair sur ce problème:

[..] La valeur d'une somme à virgule flottante est une fonction à la fois des valeurs d'entrée et de l'ordre des opérations d'addition. L'ordre des opérations d'addition de cette méthode n'est pas intentionnellement défini pour permettre une flexibilité de mise en œuvre afin d'améliorer la vitesse et la précision du résultat calculé. [..]

Cela signifie que vous ne devriez pas compter sur la stabilité, en particulier pas pour les flux parallèles.


D'autre part, il n'est pas surprenant, que vous voyez les mêmes résultats pour chaque exécution. conceptuellement , la méthodesum peut être implémentée comme suit:

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

Bien que la planification des tâches exécutées de manière asynchrone soit non déterministe, la méthode renvoie toujours le même résultat, car l'ordre des opérations d'addition est le même (c'est-à-dire que les parenthèses ne sont pas réarrangées).

Cependant, un plus une implémentation sophistiquée peut prendre en compte la charge de travail actuelle ainsi que le temps d'exécution prévu des sous-tâches (en comparaison avec les coûts des opérations asynchrones). Si cela se produit, les résultats peuvent varier.

9
répondu nosid 2014-05-10 16:48:23

J'obtiens des résultats différents de ce que vous avez posté pour la sommation parallèle, donc je peux confirmer qu'il n'est pas stable en toutes circonstances. La sommation en série semble se comporter de la même manière dans votre test et dans mon test. Ma JVM peut être différente de la vôtre, et je peux avoir un nombre de cœurs différent de celui que vous avez. Quoi qu'il en soit, voici les résultats que j'ai obtenus pour les mêmes itérations que celles pour lesquelles vous avez posté des résultats.

Oracle Corporation
Java HotSpot(TM) 64-Bit Server VM
25.51-b03
-----
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.70530e-13
-----
Min: -7.95673, Max: 7.87757, Average: 0.0658356
Serial difference:   0.00000
Parallel difference: 3.55271e-15
-----
Min: 2.53794e-09, Max: 15.8122, Average: 2.96504
Serial difference:   -4.54747e-13
Parallel difference: -4.54747e-13
1
répondu Evan VanderZee 2015-09-02 19:16:43