java 8 foreach vs stream

¿Cuándo se deben preferir los flujos sobre los bucles tradicionales para obtener el mejor rendimiento? ¿Las transmisiones aprovechan la predicción de bifurcación?

Question

Acabo de leer acerca de Branch-Prediction y quería probar cómo funciona esto con Java 8 Streams.

Sin embargo, el rendimiento con Streams siempre resulta ser peor que los bucles tradicionales.

int totalSize = 32768;
int filterValue = 1280;
int[] array = new int[totalSize];
Random rnd = new Random(0);
int loopCount = 10000;

for (int i = 0; i < totalSize; i++) {
    // array[i] = rnd.nextInt() % 2560; // Unsorted Data
    array[i] = i; // Sorted Data
}

long start = System.nanoTime();
long sum = 0;
for (int j = 0; j < loopCount; j++) {
    for (int c = 0; c < totalSize; ++c) {
        sum += array[c] >= filterValue ? array[c] : 0;
    }
}
long total = System.nanoTime() - start;
System.out.printf("Conditional Operator Time : %d ns, (%f sec) %n", total, total / Math.pow(10, 9));

start = System.nanoTime();
sum = 0;
for (int j = 0; j < loopCount; j++) {
    for (int c = 0; c < totalSize; ++c) {
        if (array[c] >= filterValue) {
            sum += array[c];
        }
    }
}
total = System.nanoTime() - start;
System.out.printf("Branch Statement Time : %d ns, (%f sec) %n", total, total / Math.pow(10, 9));

start = System.nanoTime();
sum = 0;
for (int j = 0; j < loopCount; j++) {
    sum += Arrays.stream(array).filter(value -> value >= filterValue).sum();
}
total = System.nanoTime() - start;
System.out.printf("Streams Time : %d ns, (%f sec) %n", total, total / Math.pow(10, 9));

start = System.nanoTime();
sum = 0;
for (int j = 0; j < loopCount; j++) {
    sum += Arrays.stream(array).parallel().filter(value -> value >= filterValue).sum();
}
total = System.nanoTime() - start;
System.out.printf("Parallel Streams Time : %d ns, (%f sec) %n", total, total / Math.pow(10, 9));

Salida:

1. Para Sorted-Array:

   Conditional Operator Time : 294062652 ns, (0.294063 sec) 
   Branch Statement Time : 272992442 ns, (0.272992 sec) 
   Streams Time : 806579913 ns, (0.806580 sec) 
   Parallel Streams Time : 2316150852 ns, (2.316151 sec) 

2. Para matriz no ordenada:

   Conditional Operator Time : 367304250 ns, (0.367304 sec) 
   Branch Statement Time : 906073542 ns, (0.906074 sec) 
   Streams Time : 1268648265 ns, (1.268648 sec) 
   Parallel Streams Time : 2420482313 ns, (2.420482 sec) 

Intenté el mismo código usando List :
list.stream() lugar de Arrays.stream(array)
list.get(c) lugar de array[c]

Salida:

1. Para la lista ordenada:

   Conditional Operator Time : 860514446 ns, (0.860514 sec) 
   Branch Statement Time : 663458668 ns, (0.663459 sec) 
   Streams Time : 2085657481 ns, (2.085657 sec) 
   Parallel Streams Time : 5026680680 ns, (5.026681 sec) 

2. Para la lista desordenada

   Conditional Operator Time : 704120976 ns, (0.704121 sec) 
   Branch Statement Time : 1327838248 ns, (1.327838 sec) 
   Streams Time : 1857880764 ns, (1.857881 sec) 
   Parallel Streams Time : 2504468688 ns, (2.504469 sec) 

Me referí a algunos blogs this y this que sugieren el mismo problema de rendimiento de las transmisiones de wrt.

1. Estoy de acuerdo con el hecho de que programar con streams es agradable y más fácil para algunos escenarios, pero cuando estamos perdiendo rendimiento, ¿por qué tenemos que usarlos? ¿Hay algo que me estoy perdiendo?
2. ¿Cuál es el escenario en el que las transmisiones se realizan igual a los bucles? ¿Es solo en el caso donde su función definida toma mucho tiempo, lo que resulta en un rendimiento de bucle insignificante?
3. En ninguno de los escenarios, pude ver las secuencias aprovechando la predicción de bifurcación (lo intenté con secuencias ordenadas y desordenadas, pero no sirvió de nada. Dio más del doble del impacto en el rendimiento en comparación con las transmisiones normales).

Answer 1

Estoy de acuerdo con el hecho de que programar con streams es agradable y más fácil para algunos escenarios, pero cuando estamos perdiendo rendimiento, ¿por qué tenemos que usarlos?

El rendimiento rara vez es un problema. Sería habitual que el 10% de las secuencias tuvieran que reescribirse como bucles para obtener el rendimiento que necesita.

¿Hay algo que me estoy perdiendo?

Usar parallelStream () es mucho más fácil usando streams y posiblemente más eficiente ya que es difícil escribir un código concurrente eficiente.

¿Cuál es el escenario en el que las transmisiones se realizan igual a los bucles? ¿Es solo en el caso donde su función definida toma mucho tiempo, lo que resulta en un rendimiento de bucle insignificante?

Su punto de referencia es defectuoso en el sentido de que el código no se ha compilado cuando comienza. Haría toda la prueba en un bucle como lo hace JMH, o usaría JMH.

En ninguno de los escenarios, pude ver las secuencias aprovechando la predicción de ramificación

La predicción de sucursal es una función de CPU, no una característica de JVM o secuencias.

Answer 2

¿Cómo puedo ejecutar mi programa Java rápido?

Para resumir, los programas de Java se pueden acelerar de la siguiente manera:

1. Multihilo
2. JIT

¿Las transmisiones se relacionan con la aceleración del programa Java?

¡Sí!

1. Tenga en cuenta los métodos Collection.parallelStream() y Stream.parallel() para multihilo
2. Se puede escribir for ciclo que sea lo suficientemente largo como para que salte el JIT. Las lambdas son típicamente pequeñas y JIT => puede obtenerlas para compilarlas

¿Cuál es el flujo de escenario que puede ser más rápido que for ciclo?

Echemos un vistazo a jdk/src/share/vm/runtime/globals.hpp

develop(intx, HugeMethodLimit,  8000,
        "Don''t compile methods larger than this if "
        "+DontCompileHugeMethods")

Si tiene un ciclo lo suficientemente largo, no será compilado por JIT y se ejecutará lentamente. Si reescribe dicho ciclo para transmitir, probablemente use map métodos de map , filter , map flatMap que dividen el código en pedazos y cada pieza puede ser lo suficientemente pequeña como para caber por debajo del límite. Por supuesto, escribir métodos enormes tiene otras desventajas además de la compilación JIT. Este escenario se puede considerar si, por ejemplo, tiene mucho código generado.

¿Qué hay sobre la predicción de ramas?

Por supuesto, las secuencias aprovechan la predicción de bifurcación como cualquier otro código. Sin embargo, la predicción de bifurcación no es la tecnología utilizada explícitamente para hacer que las transmisiones sean más rápidas AFAIK.

Entonces, ¿cuándo reescribo mis bucles en las transmisiones para lograr el mejor rendimiento?

Nunca.

La optimización prematura es la raíz de todo mal © Donald Knuth

Intenta optimizar el algoritmo en su lugar. Las transmisiones son la interfaz para la programación funcional, no una herramienta para acelerar los bucles.

Answer 3

Agregaré mi 0.02 $ aquí.

Acabo de leer sobre Branch-Prediction y quería probar cómo funciona esto con Java 8 Streams

Branch Prediction es una función de CPU, no tiene nada que ver con JVM. Es necesario para mantener el pipeline de la CPU lleno y listo para hacer algo. Medir o predecir la predicción de bifurcación es extremadamente difícil (a menos que realmente conozca las cosas EXACTAS que la CPU hará). Esto dependerá de al menos la carga que la CPU está teniendo en este momento (que podría ser mucho más que su programa solamente).

Sin embargo, el rendimiento con Streams siempre resulta ser peor que los bucles tradicionales

Esta declaración y la anterior no están relacionadas. Sí, las transmisiones serán más lentas para ejemplos simples como el suyo, hasta un 30% más lento, lo cual está bien. Podrías medir para un caso particular qué tan lentos son o más rápido a través de JMH como han sugerido otros, pero eso prueba solo ese caso, solo esa carga.

Al mismo tiempo, es posible que trabaje con Spring / Hibernate / Services, etc., que hace cosas en milisegundos y sus transmisiones en nano segundos y se preocupa por el rendimiento. ¿Estás cuestionando la velocidad de tu parte más rápida del código? Eso es por supuesto una cosa teórica.

Y sobre su último punto que probaste con matrices ordenadas y no ordenadas, y te da malos resultados. Esto no es en absoluto una indicación de la predicción de bifurcación o no, no tiene idea en qué punto ocurrió la predicción y si lo hizo a menos que pueda mirar dentro de las tuberías de CPU reales, lo que no hizo.

Answer 4

Java es un lenguaje de alto nivel que le permite al programador evitar la optimización del rendimiento de bajo nivel.

Nunca elija un enfoque determinado por motivos de rendimiento a menos que haya demostrado que esto es un problema en su aplicación real.

Sus medidas muestran algún efecto negativo para las corrientes, pero la diferencia está por debajo de la observabilidad. Por lo tanto, no es un problema. Además, esta prueba es una situación "sintética" y el código puede comportarse completamente diferente en un entorno de producción de trabajo pesado. Además, el código de máquina creado a partir de su código Java (byte) por el JIT puede cambiar en futuras versiones de Java (mantenimiento) y hacer que sus mediciones sean obsoletas.

En conclusión: elija la sintaxis o el enfoque que más exprese su intención (la del programador). Mantenga ese mismo enfoque o sintaxis en todo el programa a menos que tenga una buena razón para cambiar.

Answer 5

Todo está dicho, pero quiero mostrarte cómo debería ser tu código usando JMH .

@Fork(3)
@BenchmarkMode(Mode.AverageTime)
@Measurement(iterations = 10, timeUnit = TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
@Threads(1)
@Warmup(iterations = 5, timeUnit = TimeUnit.NANOSECONDS)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class MyBenchmark {

  private final int totalSize = 32_768;
  private final int filterValue = 1_280;
  private final int loopCount = 10_000;
  // private Random rnd;

  private int[] array;

  @Setup
  public void setup() {
    array = IntStream.range(0, totalSize).toArray();

    // rnd = new Random(0);
    // array = rnd.ints(totalSize).map(i -> i % 2560).toArray();
  }

  @Benchmark
  public long conditionalOperatorTime() {
    long sum = 0;
    for (int j = 0; j < loopCount; j++) {
      for (int c = 0; c < totalSize; ++c) {
        sum += array[c] >= filterValue ? array[c] : 0;
      }
    }
    return sum;
  }

  @Benchmark
  public long branchStatementTime() {
    long sum = 0;
    for (int j = 0; j < loopCount; j++) {
      for (int c = 0; c < totalSize; ++c) {
        if (array[c] >= filterValue) {
          sum += array[c];
        }
      }
    }
    return sum;
  }

  @Benchmark
  public long streamsTime() {
    long sum = 0;
    for (int j = 0; j < loopCount; j++) {
      sum += IntStream.of(array).filter(value -> value >= filterValue).sum();
    }
    return sum;
  }

  @Benchmark
  public long parallelStreamsTime() {
    long sum = 0;
    for (int j = 0; j < loopCount; j++) {
      sum += IntStream.of(array).parallel().filter(value -> value >= filterValue).sum();
    }
    return sum;
  }
}

Los resultados para una matriz ordenada:

Benchmark                            Mode  Cnt           Score           Error  Units
MyBenchmark.branchStatementTime      avgt   30   119833793,881 ±   1345228,723  ns/op
MyBenchmark.conditionalOperatorTime  avgt   30   118146194,368 ±   1748693,962  ns/op
MyBenchmark.parallelStreamsTime      avgt   30   499436897,422 ±   7344346,333  ns/op
MyBenchmark.streamsTime              avgt   30  1126768177,407 ± 198712604,716  ns/op

Resultados para datos sin clasificar:

Benchmark                            Mode  Cnt           Score           Error  Units
MyBenchmark.branchStatementTime      avgt   30   534932594,083 ±   3622551,550  ns/op
MyBenchmark.conditionalOperatorTime  avgt   30   530641033,317 ±   8849037,036  ns/op
MyBenchmark.parallelStreamsTime      avgt   30   489184423,406 ±   5716369,132  ns/op
MyBenchmark.streamsTime              avgt   30  1232020250,900 ± 185772971,366  ns/op

Solo puedo decir que hay muchas posibilidades de optimizaciones de JVM y quizás también esté involucrada la predicción de ramificación. Ahora le corresponde a usted interpretar los resultados del punto de referencia.