Czy metoda DoubleStream.sum() Java-8 jest stabilna, gdy działa równolegle?

Question

Jestem ciekaw następujące skonstruować w Java 8:

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

Aby przejść do sedna:

• Czy wartość sum zawsze być taka sama, na przykład kiedy działają na różnych komputerach?

---

Więcej tło ...

arytmetyka zmiennoprzecinkowa jest stratny i (w przeciwieństwie do wartości rzeczywistej arytmetyki) nie jest łączne. Więc jeśli nie zostanie podjęta troska o to, jak dzieło zostanie podzielone i ponownie złożone, może to prowadzić do niedeterministycznych rezultatów.

Z przyjemnością odkryłem, że metoda sum() zatrudnia Kahan Summation pod maską. To znacznie zmniejsza błąd, ale nadal nie daje dokładnych * wyników.

Podczas moich testów powtarzające się połączenia są wyświetlane za każdym razem, gdy zwracam ten sam wynik, ale chciałbym się dowiedzieć, jak stabilnie możemy bezpiecznie założyć, że jest. np .:

1. Stabilny we wszystkich okolicznościach?
2. Stabilny na komputerach z taką samą liczbą rdzeni?
3. Stabilna tylko na danym komputerze?
4. Nie można w ogóle polegać na tym, że jest stabilny?

Cieszę się, że mogę założyć tę samą wersję JVM na każdym komputerze.

Oto test I bita:

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

Kiedy biegnę, pierwszych kilka iteracji są:

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

Zauważ, że podczas sum2 & sum3 można założyć być bardziej dokładne niż sum1 - mogą nie być takie same!

Założyłem Random z 42, więc jeśli ktoś uzyska inny wynik, to od razu coś udowodni. :-)

---

*Dla ciekawskich ...

• Tutaj some (python) algorithms które dają dokładne wyniki
• Algorytm dokładny-sum z najlepiej brzmiących charakterystyk mam słyszy się o: given here (wymagana subskrypcja ACM). Pobiera 5 klatek na wejście, ale jest napisany (w C), aby wykorzystać paralelizm na poziomie instrukcji i działa tylko 2 - 3 razy wolniej niż naiwne sumowanie, co brzmi raczej dobrze dla dokładnego wyniku. (c.f.Kahan podsumowanie na 4 japonki na wejście)

Answer 1

myślę dokumentacja DoubleStream::sum jest całkiem jasne, o tym numerze:

[..] Wartość sumy zmiennoprzecinkowej jest zależna zarówno od wartości wejściowe, a także kolejność operacji dodawania. Kolejność operacji dodawania tej metody celowo nie jest zdefiniowana, aby umożliwić elastyczność wdrażania w celu poprawy szybkości i dokładności wyliczonego wyniku. [..]

Oznacza to, że nie należy polegać na stabilności, w szczególności nie dla równoległych strumieni.

---

Z drugiej strony, nie jest zaskakujące, że widzisz te same wyniki dla każdego biegu. Konceptualnie The suma metoda może być realizowana w następujący sposób:

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

Chociaż szeregowanie z asynchronicznie realizowanych zadań jest nondeterminstic metoda zawsze zwraca ten sam wynik, ponieważ kolejność operacji dodawania jest taka sama (nawiasy nie są uporządkowane).

Jednak bardziej zaawansowana implementacja może uwzględniać bieżące obciążenie pracą, a także przewidywany czas wykonania pod zadań (w porównaniu z kosztami operacji asynchronicznych). Jeśli tak się stanie, wyniki mogą się różnić.

Answer 2

Otrzymuję różne wyniki od tego, co napisałeś dla sumowania równoległego, więc mogę potwierdzić, że nie jest on stabilny we wszystkich okolicznościach. Wydaje się, że seryjne sumowanie zachowuje się tak samo w teście i w teście. Moja maszyna JVM może być inna od twojej i mogę mieć inną liczbę rdzeni niż ty. W każdym razie, oto wyniki uzyskane dla tych samych iteracji, dla których opublikowano wyniki.

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