threads - java util concurrent forkjoinpool common parallelism

¿Es estable el método DoubleStream.sum() de Java-8 cuando se ejecuta en paralelo?

Question

Tengo curiosidad por la siguiente construcción en Java 8:

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

Para cortar a la persecución:

• ¿El valor de la sum siempre será el mismo, por ejemplo, cuando se ejecute en equipos diferentes?

Más antecedentes ...

La aritmética de punto flotante tiene pérdidas y (a diferencia de la aritmética de valores reales) no es asociativa. Entonces, a menos que se tenga cuidado en la forma en que se divide y se vuelve a montar el trabajo, podría llevar a resultados no deterministas.

Me alegró descubrir que el método sum() emplea la suma Kahan bajo el capó. Esto reduce significativamente el error, pero aún no da resultados * precisos.

En mis pruebas, las llamadas repetidas parecen devolver el mismo resultado cada vez, pero me gustaría saber qué tan estable podemos asumir con seguridad que es. p.ej:

1. ¿Estable en todas las circunstancias?
2. ¿Estable en todas las computadoras con el mismo número de núcleos?
3. ¿Estable solo en una computadora dada?
4. ¿No puedes depender de que sea estable?

Estoy feliz de asumir la misma versión de JVM en cada computadora.

Aquí hay una prueba que preparé:

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

Cuando ejecuto esto, las primeras iteraciones son:

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

Tenga en cuenta que, si sum2 se puede suponer que sum2 y sum3 son más precisos que sum1 , ¡es posible que no sum1 entre sí!

Sembré Random con 42, así que si alguien me da un resultado diferente, eso probaría algo de inmediato. :-)

* Para los curiosos ...

• Aquí hay algunos algoritmos (python) que dan resultados precisos.
• El algoritmo de suma precisa con las características de rendimiento con mejor sonido que he escuchado se da aquí (se requiere suscripción a ACM o tarifa). Se necesitan 5 fracasos por entrada, pero se escribe (en C) para explotar el paralelismo a nivel de instrucción y solo se ejecuta 2 - 3 veces más lento que la suma ingenua, lo que parece bastante bueno para un resultado preciso. (cf suma Kahan en 4 fracasos por entrada)

Answer 1

Creo que la documentación de DoubleStream::sum es bastante clara sobre este problema:

[..] El valor de una suma de punto flotante es una función tanto de los valores de entrada como del orden de las operaciones de suma. El orden de las operaciones de adición de este método no está definido intencionalmente para permitir la flexibilidad de implementación para mejorar la velocidad y la precisión del resultado calculado. [..]

Eso significa que no debe confiar en la estabilidad, en particular no para flujos paralelos.

Por otro lado, no es sorprendente que vea los mismos resultados para cada ejecución. Conceptualmente , el método de suma podría implementarse de la siguiente manera:

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

Aunque la programación de las tareas ejecutadas de forma asíncrona no es determinante, el método siempre devuelve el mismo resultado, porque el orden de las operaciones de adición es el mismo (es decir, los paréntesis no se reorganizan ).

Sin embargo, una implementación más sofisticada podría considerar la carga de trabajo actual así como el tiempo de ejecución esperado de las tareas secundarias (en comparación con los costos de las operaciones asíncronas). Si eso sucede, los resultados pueden variar.

Answer 2

Obtengo resultados diferentes de lo que publicó para la suma paralela, por lo que puedo confirmar que no es estable en todas las circunstancias. La suma en serie parece comportarse igual en su prueba y en mi prueba. Mi JVM puede ser diferente a la suya y es posible que tenga un número de núcleos diferente al que usted tiene. De todos modos, aquí están los resultados que obtuve para las mismas iteraciones para las que publicaste los resultados.

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