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.