Il metodo DoubleStream.sum() di Java-8 è stabile quando viene eseguito in parallelo?

Question

Sono curioso di sapere il seguente costrutto in Java 8:

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

Per al sodo:

• Sarà il valore di sum essere sempre lo stesso, ad esempio, quando viene eseguito su computer diversi?

---

più di fondo ...

virgola mobile aritmetica è lossy e (a differenza aritmetica a valori reali) non è associativa. Quindi, se non si presta attenzione a come il lavoro viene diviso e ricomposto, potrebbe portare a risultati non deterministici.

Sono stato felice di scoprire che il metodo sum() utilizza Kahan Summation sotto il cofano. Questo riduce significativamente l'errore, ma non dà ancora risultati precisi *.

Nel mio test le chiamate ripetute sembrano restituire lo stesso risultato ogni volta, ma mi piacerebbe sapere quanto stabile possiamo tranquillamente supporre che lo sia. ad esempio:

1. Stabile in tutte le circostanze?
2. Stabile su computer con lo stesso numero di core?
3. Stabile solo su un determinato computer?
4. Non si può dipendere dal fatto che sia stabile?

Sono felice di assumere la stessa versione JVM su ciascun computer.

Ecco una prova che ho scatenato:

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

Quando eseguo questo, le prime iterazioni sono:

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

Si noti che mentre sum2 & sum3 può essere assunto per essere più precisi di sum1 - potrebbero non essere uguali tra loro!

Ho seminato Random con 42, quindi se qualcuno ottiene un risultato diverso per me, ciò proverebbe immediatamente qualcosa. :-)

---

*Per i curiosi ...

• Ecco some (python) algorithms che danno risultati precisi
• L'algoritmo preciso somma con le caratteristiche di prestazione miglior suono che abbia sentito parlare di è given here (abbonamento ACM o tassa richiesta). Occorrono 5 flop per input, ma sono scritti (in C) per sfruttare il parallelismo a livello di istruzioni e funzionano solo 2 - 3 volte più lentamente della sommatoria naïve, che suona piuttosto bene per un risultato preciso. (C.f.Kahan somma alle 4 del flop per ingresso)

Answer 1

Credo che la documentazione di DoubleStream::sum è abbastanza chiaro su questo problema:

[..] Il valore di una somma in virgola mobile è funzione sia di i valori di input e l'ordine delle operazioni di aggiunta. L'ordine delle operazioni di aggiunta di questo metodo non è intenzionalmente definito per consentire flessibilità di implementazione per migliorare la velocità e la precisione del risultato calcolato. [..]

Ciò significa che non si deve fare affidamento sulla stabilità, in particolare non per i flussi paralleli.

---

D'altra parte, non è sorprendente, che si vedano gli stessi risultati per ogni corsa. Concettualmente, il metodo somma potrebbe essere implementata come segue:

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

Anche se la programmazione dei compiti in modo asincrono eseguiti è nondeterminstic, il metodo restituisce sempre lo stesso risultato, perché l'ordine delle operazioni di addizione è lo stesso (ovvero le parentesi non vengono ridisposte).

Tuttavia, un'implementazione più sofisticata potrebbe considerare il carico di lavoro corrente nonché il tempo di esecuzione previsto delle sotto-attività (rispetto ai costi delle operazioni asincrone). Se ciò accade, i risultati potrebbero variare.

Answer 2

Ottengo risultati diversi da quello che hai inviato per la sommatoria parallela, quindi posso confermare che non è stabile in tutte le circostanze. La somma seriale sembra comportarsi allo stesso modo nel test e nel mio test. La mia JVM potrebbe essere diversa dalla tua e potrei avere un numero diverso di core di quello che hai. Ad ogni modo, ecco i risultati che ho ottenuto per le stesse iterazioni per cui hai pubblicato i risultati.

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