java - ¿Por qué lambda IntStream.anyMatch() es 10 más lento que la implementación ingenua?

performance microbenchmark

Question

Hace poco estaba perfilando mi código y encontré un cuello de botella interesante en él. Aquí está el punto de referencia:

@BenchmarkMode(Mode.Throughput)
@Fork(1)
@State(Scope.Thread)
@Warmup(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS)
public class Contains {
private int[] ar = new int[] {1,2,3,4,5,6,7};
private int val = 5;
@Benchmark
public boolean naive() {
return contains(ar, val);
}
@Benchmark
public boolean lambdaArrayStreamContains() {
return Arrays.stream(ar).anyMatch(i -> i == val);
}
@Benchmark
public boolean lambdaIntStreamContains() {
return IntStream.of(ar).anyMatch(i -> i == val);
}
private static boolean contains(int[] ar, int value) {
for (int arVal : ar) {
if (arVal == value) {
return true;
}
}
return false;
}
}

Resultado:

Benchmark Mode Cnt Score Error Units
Contains.lambdaArrayStreamContains thrpt 10 22867.962 ± 1049.649 ops/s
Contains.lambdaIntStreamContains thrpt 10 22983.800 ± 593.580 ops/s
Contains.naive thrpt 10 228002.406 ± 8591.186 ops/s

Si muestra que Array contiene una operación a través de lambda, es 10 veces más lenta que la implementación ingenua con bucle simple. Sabía que lambdas debería ser un poco más lento. Pero 10 veces? ¿Estoy haciendo mal lambda o este es un problema con java?

Answer 1

Su punto de referencia en realidad no mide el rendimiento de anyMatch , sino más bien una sobrecarga de transmisión. Esta sobrecarga puede parecer significativa cuando se compara con una operación muy simple como una búsqueda de matriz de cinco elementos.

La desaceleración no se verá tan terrible si pasamos de números relativos a números absolutos. Vamos a medir la latencia en lugar del rendimiento para obtener una imagen más clara. He omitido el benchmark lambdaIntStream ya que funciona exactamente de la misma manera que lambdaArrayStream .

Benchmark Mode Cnt Score Error Units
Contains.lambdaArrayStream avgt 5 53,242 ± 2,034 ns/op
Contains.naive avgt 5 5,876 ± 0,404 ns/op

5.8 ns es aproximadamente 14 ciclos de una CPU de 2.4 GHz. La carga de trabajo es tan pequeña que cualquier ciclo adicional será notable. Entonces, ¿cuál es la sobrecarga de las operaciones de flujo?

Asignación de objetos

Ahora vuelva a ejecutar el benchmark con -prof gc profiler. Mostrará la cantidad de asignaciones de pila:

Benchmark Mode Cnt Score Error Units
Contains.lambdaArrayStream:·gc.alloc.rate.norm avgt 5 152,000 ± 0,001 B/op
Contains.naive:·gc.alloc.rate.norm avgt 5 ≈ 10⁻⁵ B/op

lambdaArrayStream asigna 152 bytes por iteración mientras que naive benchmark naive no asigna nada. Por supuesto, la asignación no es gratuita: hay al menos 5 objetos construidos para admitir anyMatch , y cada uno toma varios nanosegundos:

• Lambda i -> i == val
• IntPipeline.Head
• Spliterators.IntArraySpliterator
• MatchOps.MatchOp
• MatchOps.MatchSink

Pila de llamadas

java.util.stream implementación de java.util.stream es un poco complicada ya que debe admitir todas las combinaciones de fuentes de flujo, operaciones intermedias y de terminal. Si miras la pila de anyMatch de anyMatch en tu benchmark, verás algo como eso:

 at bench.Contains.lambda$lambdaArrayStream$0(Contains.java:24)
at java.util.stream.MatchOps$2MatchSink.accept(MatchOps.java:119)
at java.util.Spliterators$IntArraySpliterator.tryAdvance(Spliterators.java:1041)
at java.util.stream.IntPipeline.forEachWithCancel(IntPipeline.java:162)
at java.util.stream.AbstractPipeline.copyIntoWithCancel(AbstractPipeline.java:498)
at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:485)
at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471)
at java.util.stream.MatchOps$MatchOp.evaluateSequential(MatchOps.java:230)
at java.util.stream.MatchOps$MatchOp.evaluateSequential(MatchOps.java:196)
at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
at java.util.stream.IntPipeline.anyMatch(IntPipeline.java:477)
at bench.Contains.lambdaArrayStream(Contains.java:23)

No todas estas llamadas a métodos pueden estar en línea. Además, JVM limita la creación de líneas en 9 niveles, pero aquí vemos la pila de llamadas más profunda. Si -XX:MaxInlineLevel=20 el límite con -XX:MaxInlineLevel=20 la puntuación será un poco mejor:

Benchmark Mode Cnt Score Error Units
Contains.lambdaArrayStream avgt 5 33,294 ± 0,367 ns/op (was 53,242)
Contains.naive avgt 5 5,822 ± 0,207 ns/op

Optimizaciones de bucle

for iteración sobre una matriz es un bucle contado trivial. JVM puede aplicar una amplia gama de optimizaciones de bucle aquí: peeling de bucle, desenrollado de bucles, etc. Esto no funciona por un while : el bucle de tipo forEachWithCancel método forEachWithCancel , que se utiliza para atravesar un IntStream. El efecto de las optimizaciones de bucle se puede medir con -XX:LoopUnrollLimit=0 -XX:-UseLoopPredicate :

Benchmark Mode Cnt Score Error Units
Contains.lambdaArrayStream avgt 5 33,153 ± 0,559 ns/op
Contains.naive avgt 5 9,853 ± 0,150 ns/op (was 5,876)

Conclusiones

Hay una sobrecarga para construir y atravesar una secuencia, pero esto se entiende completamente y no se puede considerar un error. No diría que la sobrecarga es grande (incluso 50 ns / op no es mucho); sin embargo, en este ejemplo particular, la sobrecarga es dominante debido a una carga de trabajo extremadamente pequeña.