Skip to content
Posts🇬🇧 Read in English

Le coût d'allocation caché des opérations de stream eager

•10 min read

Les opérations terminales eager des streams allouent des objets à chaque appel, même sur une entrée vide

javastreamsperformanceallocationjmheclipse-collections

Les streams sont la manière par défaut d’exprimer la logique de collection en Java moderne. anyMatch, allMatch, noneMatch, filter(...).findFirst() et filter(...).count() se lisent presque comme la phrase qu’ils implémentent et font le travail en une seule passe. Mais cette lisibilité cache un coût : chacun de ces appels construit un petit graphe d’objets avant de toucher le moindre élément et il construit ce graphe que la collection contienne 100 000 éléments ou aucun.

Don Raab a décrit le problème dans son article Medium “Allocation Hungry Any/All/None, FindFirst, and Count Methods on Java Stream”[1]. L’affirmation est simple : la machinerie des streams alloue à chaque appel, alors qu’une boucle for équivalente ou une utilisation de la librairie eclipse-collections[2] reste libre de toute allocation.

Cet article pose des chiffres sur cette affirmation.

Ce qui est mesuré

Chaque appel est mesuré face à quatre cas :

  • un appel de stream
  • un appel de stream derrière une garde isEmpty()
  • une simple boucle for issue de com.hogwai.util.Iterables
  • l’utilitaire eager d’Eclipse Collections sur Iterate
@Benchmark
public boolean jdkStream() {
    return values.stream().anyMatch(predicate);
}

@Benchmark
public boolean jdkStreamGuarded() {
    if (values.isEmpty()) {
        return false;
    }
    return values.stream().anyMatch(predicate);
}

@Benchmark
public boolean helperLoop() {
    return Iterables.anyMatch(values, predicate);
}

@Benchmark
public boolean eclipseCollections() {
    return Iterate.anySatisfy(values, predicate);
}

La garde est là parce qu’elle supprime le travail du stream quand il n’y a rien à parcourir, un cas que Heinz Kabutz a déjà signalé pour les pipelines de stream[2].

Iterables.anyMatch est la base sans allocation et ce n’est rien de plus qu’une boucle :

public static <T> boolean anyMatch(Iterable<T> items, Predicate<? super T> predicate) {
    for (T item : items) {
        if (predicate.test(item)) {
            return true;
        }
    }
    return false;
}

Les quatre autres benchmarks remplacent l’appel :

  • allMatch avec Iterables.allMatch et Iterate.allSatisfy
  • noneMatch avec Iterables.noneMatch et Iterate.noneSatisfy
  • filter(...).findFirst() avec Iterables.findFirst, Iterables.detect et Iterate.detect
  • filter(...).count() avec Iterables.count et Iterate.count

Résultats

Tous les chiffres ci-dessous proviennent de l’exécution décrite plus haut et plus la valeur est basse, mieux c’est. Un score de ~0 dans les tableaux d’allocation marque le seuil de détection du profileur, pas exactement zéro (mais presque).

AnyMatch

values.stream().anyMatch(predicate);

Temps (ns/op)

Methodemptyfirstmidlastabsent
Stream.anyMatch12.0813.5765022.22124726.69115280.56
guarded Stream.anyMatch0.36113.8166031.29128021.76130399.62
Iterables.anyMatch0.4230.74315479.4731096.3530234.64
Iterate.anySatisfy0.3830.74016612.2840736.5246140.81

Allocation (B/op)

Methodemptyfirstmidlastabsent
Stream.anyMatch144.00144.00143.59131.3998.33
guarded Stream.anyMatch~0144.00143.58132.3182.81
Iterables.anyMatch~0~00.0980.1970.192
Iterate.anySatisfy~0~00.1050.2580.311

Sur une liste vide, la garde fait passer l’appel de 12 ns et 144 octets à 0,36 ns et rien. Sur une liste non vide, elle ne change rien à l’allocation ni au temps. Sur un parcours complet, la boucle et Eclipse Collections se situent toutes les deux entre 30 000 et 46 000 ns selon l’endroit où se trouve le match, contre 115 000 à 130 000 ns pour le stream et elles n’allouent rien.

AllMatch

values.stream().allMatch(predicate);

Temps (ns/op)

Methodemptyfirstmidlastabsent
Stream.allMatch13.1713.9967382.91124991.24116349.65
guarded Stream.allMatch0.35714.1368351.66125698.54130865.15
Iterables.allMatch0.3930.69414811.4730099.5331289.08
Iterate.allSatisfy0.3820.74216042.1144003.7444389.83

Allocation (B/op)

Methodemptyfirstmidlastabsent
Stream.allMatch144.00144.00136.30130.9198.42
guarded Stream.allMatch~0144.00136.47131.4282.62
Iterables.allMatch~0~00.0940.1910.198
Iterate.allSatisfy~0~00.1010.2790.281

allMatch est l’image miroir de anyMatch et les chiffres disent la même chose : les trois opérations de matching partagent une implémentation, donc elles partagent un profil d’allocation. Le scénario first est le seul endroit où le stream ne coûte presque rien, 14 ns et 144 octets, parce que le tout premier élément décide de la réponse.

NoneMatch

values.stream().noneMatch(predicate);

Temps (ns/op)

Methodemptyfirstmidlastabsent
Stream.noneMatch12.2013.6567547.33124416.94115951.16
guarded Stream.noneMatch0.36013.9668346.99128971.91129895.88
Iterables.noneMatch0.3960.68814718.2130191.9731304.02
Iterate.noneSatisfy0.3790.73516413.2142259.2246026.17

Allocation (B/op)

Methodemptyfirstmidlastabsent
Stream.noneMatch144.00144.00136.48131.7298.22
guarded Stream.noneMatch~0144.00136.63132.3783.50
Iterables.noneMatch~0~00.0930.1910.198
Iterate.noneSatisfy~0~00.1040.2680.292

Sans surprise et c’est tout l’intérêt. Trois méthodes aux noms différents, un coût identique.

FindFirst

values.stream().filter(predicate).findFirst();

Temps (ns/op)

Methodemptyfirstmidlastabsent
Stream.filter().findFirst()14.9717.6160210.32125820.39118251.70
guarded Stream.filter().findFirst()0.35917.6060745.89125174.22117942.84
Iterables.findFirst0.4081.7418398.3845708.3830994.93
Iterables.detect0.4140.70615398.2130989.7431010.92
Iterate.detect0.3810.73916741.8240767.4345399.61

Allocation (B/op)

Methodemptyfirstmidlastabsent
Stream.filter().findFirst()168.00184.00184.38184.80168.75
guarded Stream.filter().findFirst()~0184.00184.39184.79168.75
Iterables.findFirst~016.0016.1216.290.196
Iterables.detect~0~00.0970.1960.196
Iterate.detect~0~00.1060.2580.288

Le stage filter supplémentaire se voit dans l’allocation : 168 à 184 octets par appel au lieu de 144. Il se voit aussi dans le scénario first, où le stream coûte désormais 17,6 ns au lieu de 13,6 ns. Même quand le filter retient le premier élément, le stage doit quand même être construit.

La ligne Iterables.findFirst rappelle utilement qu’envelopper un match dans un Optional coûte aussi 16 octets, alors que detect renvoie null et reste au seuil de détection. Le confort du Optional n’est pas gratuit, mais il coûte peu.

Count

values.stream().filter(predicate).count();

Temps (ns/op)

Methodemptynonehalfall
Stream.filter().count()14.3458871.7572139.1175908.07
guarded Stream.filter().count()0.35461915.4076259.4679184.47
Iterables.count0.41131062.4440120.1729900.15
Iterate.count0.37846491.2461630.7345381.66

Allocation (B/op)

Methodemptynonehalfall
Stream.filter().count()176.00192.18207.99208.00
guarded Stream.filter().count()~0192.19206.97208.00
Iterables.count~00.1970.2540.189
Iterate.count~00.3510.4660.287

count ne peut pas court-circuiter, c’est donc le pire cas pour le stream dans chaque scénario non vide. La boucle est environ 2 fois plus rapide que le stream et son allocation reste au seuil de détection du profileur.

D’où viennent ces octets ?

Un appel de stream n’est pas juste une boucle avec une plus jolie syntaxe, c’est un pipeline qui doit être assemblé avant de pouvoir s’exécuter et cet assemblage nécessite l’allocation de structures intermédiaires.

La source

list.stream() est la méthode par défaut de Collection et elle démarre le pipeline :

default Stream<E> stream() {
    return StreamSupport.stream(spliterator(), false);
}

spliterator() est une autre méthode par défaut, parce que les listes immuables renvoyées par List.copyOf ne la redéfinissent pas :

default Spliterator<E> spliterator() {
    return Spliterators.spliterator(this, 0);
}

Donc stream() seul alloue déjà deux objets :

  • le Spliterators.IteratorSpliterator adossé à un itérateur[3]
  • le ReferencePipeline.Head[4] que StreamSupport.stream construit autour.

L’opération terminale

anyMatch tient en une ligne et confie le predicate à MatchOps :

@Override
public final boolean anyMatch(Predicate<? super P_OUT> predicate) {
    return evaluate(MatchOps.makeRef(predicate, MatchOps.MatchKind.ANY));
}

C’est dans makeRef que les objets apparaissent. Elle déclare la classe du sink puis renvoie un nouveau MatchOp qui porte un supplier MatchSink::new[5] :

public static <T> TerminalOp<T, Boolean> makeRef(Predicate<? super T> predicate,
        MatchKind matchKind) {
    Objects.requireNonNull(predicate);
    Objects.requireNonNull(matchKind);
    class MatchSink extends BooleanTerminalSink<T> {
        MatchSink() {
            super(matchKind);
        }

        @Override
        public void accept(T t) {
            if (!stop && predicate.test(t) == matchKind.stopOnPredicateMatches) {
                stop = true;
                value = matchKind.shortCircuitResult;
            }
        }
    }

    return new MatchOp<>(StreamShape.REFERENCE, matchKind, MatchSink::new);
}

Le MatchOp et le supplier sont tous les deux nouveaux à chaque appel et l’évaluation appelle ensuite sinkSupplier.get() pour créer le MatchSink lui-même. Cela fait cinq objets pour une simple opération de matching, ce qui explique pourquoi anyMatch atterrit autour de 144 octets. allMatch et noneMatch sont le même code avec un MatchKind différent.

Le cas du count

count() est routé vers ReduceOps.makeRefCounting()[6] :

public static <T> TerminalOp<T, Long>
makeRefCounting() {
    return new ReduceOp<T, Long, CountingSink<T>>(StreamShape.REFERENCE) {
        @Override
        public CountingSink<T> makeSink() { return new CountingSink.OfRef<>(); }

        @Override
        public <P_IN> Long evaluateSequential(PipelineHelper<T> helper,
                                              Spliterator<P_IN> spliterator) {
            long size = helper.exactOutputSizeIfKnown(spliterator);
            if (size != -1)
                return size;
            return super.evaluateSequential(helper, spliterator);
        }

        @Override
        public <P_IN> Long evaluateParallel(PipelineHelper<T> helper,
                                            Spliterator<P_IN> spliterator) {
            long size = helper.exactOutputSizeIfKnown(spliterator);
            if (size != -1)
                return size;
            return super.evaluateParallel(helper, spliterator);
        }

        @Override
        public int getOpFlags() {
            return StreamOpFlag.NOT_ORDERED;
        }
    };
}

La sous-classe anonyme de ReduceOp est créée à chaque appel, contrairement à l’opération mise en cache ci-dessous. Le comptage ne peut pas non plus court-circuiter, donc chaque élément doit passer par le CountingSink, ce qui explique pourquoi count est le plus lourd des cinq sur un parcours complet.

Le cas du find

findFirst() est l’exception : elle n’alloue pas du tout d’opération terminale, parce que FindOps les met en cache dans des champs statiques[7].

public static <T> TerminalOp<T, Optional<T>> makeRef(boolean mustFindFirst) {
    return (TerminalOp<T, Optional<T>>)
            (mustFindFirst ? FindSink.OfRef.OP_FIND_FIRST : FindSink.OfRef.OP_FIND_ANY);
}
static final TerminalOp<?, ?> OP_FIND_FIRST, OP_FIND_ANY;
static {
    Predicate<Optional<Object>> isPresent = Optional::isPresent;
    Supplier<TerminalSink<Object, Optional<Object>>> newSink
            = FindSink.OfRef::new;
    OP_FIND_FIRST = new FindOp<>(true, StreamShape.REFERENCE,
            Optional.empty(), isPresent, newSink);
    OP_FIND_ANY = new FindOp<>(false, StreamShape.REFERENCE,
            Optional.empty(), isPresent, newSink);
}

Les deux opérations sont construites une fois au chargement de la classe et réutilisées indéfiniment, donc les octets de filter().findFirst() viennent du stage filter et du sink qu’il enveloppe, pas de l’opération terminale.

Le stage filter

filter() renvoie un nouveau StatelessOp anonyme, donc chaque appel à filter(...) alloue un stage avant même que le pipeline s’exécute[8] :

@Override
public final Stream<P_OUT> filter(Predicate<? super P_OUT> predicate) {
    Objects.requireNonNull(predicate);
    return new StatelessOp<>(this, StreamShape.REFERENCE,
            StreamOpFlag.NOT_SIZED) {
        @Override
        Sink<P_OUT> opWrapSink(int flags, Sink<P_OUT> sink) {
            return new Sink.ChainedReference<>(sink) {
                @Override
                public void begin(long size) {
                    downstream.begin(-1);
                }

                @Override
                public void accept(P_OUT u) {
                    if (predicate.test(u))
                        downstream.accept(u);
                }
            };
        }
    };
}

L’assemblage des sinks

Avant qu’un seul élément ne circule, wrapSink parcourt les stages à l’envers et enveloppe le sink terminal une fois par stage intermédiaire[9] :

@Override
@SuppressWarnings("unchecked")
final <P_IN> Sink<P_IN> wrapSink(Sink<E_OUT> sink) {
    Objects.requireNonNull(sink);

    for ( @SuppressWarnings("rawtypes") AbstractPipeline p=AbstractPipeline.this; p.depth > 0; p=p.previousStage) {
        sink = p.opWrapSink(p.previousStage.combinedFlags, sink);
    }
    return (Sink<P_IN>) sink;
}

Un matching brut n’a pas de stage intermédiaire, donc le corps de la boucle ne s’exécute jamais. Un filter ajoute un stage, donc un Sink.ChainedReference est créé ici. C’est pourquoi filter().findFirst() se situe entre 168 et 184 octets et filter().count() entre 176 et 208, contre 144 pour les appels de matching bruts.

Pourquoi les chiffres restent stables

Rien de tout cela ne dépend de la taille de la collection ni de l’endroit où le match est trouvé. Le pipeline est assemblé une fois par appel, avant la lecture du premier élément et les sinks sont ensuite réutilisés au fil des éléments qui les traversent. Le court-circuit arrête simplement la boucle plus tôt, il ne change pas ce qui a été alloué. C’est pourquoi les chiffres d’allocation restent stables d’un scénario à l’autre et pourquoi un parcours complet de 100 000 éléments n’alloue pas plus qu’une liste vide.

Une garde supprime tout le graphe dans le cas vide parce que la méthode retourne avant que stream() ne soit évalué. Sur une collection non vide, la garde n’ajoute rien.

Une nuance à propos des lambdas. Une référence de méthode non capturante comme String::isEmpty se résout en une seule instance mise en cache par site d’appel, donc la passer à anyMatch ou filter n’alloue rien. Une lambda capturante comme le value -> value.equals(target) du benchmark est une autre histoire : elle a besoin d’un champ pour la valeur capturée et finit stockée à l’intérieur d’un stage du pipeline. Le JIT ne peut pas décomposer en scalaires un objet qui atteint le tas. En pratique, elle est allouée à chaque appel. Le benchmark hisse son predicate dans un champ créé une fois dans @Setup, ce qui isole le coût du stream et garde la comparaison équitable.

Ce que ces chiffres signifient

Le JDK alloue à chaque appel

Environ 144 octets pour les opérations de matching, 168 à 184 octets pour filter().findFirst() et 176 à 208 octets pour filter().count(). Le montant est déterminé par la forme du pipeline, pas par les données. Un appel sur une liste vide alloue autant qu’un appel sur un parcours complet.

La garde isEmpty() n’est pas une solution générale

Elle supprime entièrement le stream sur une entrée vide, ce qui transforme un appel de 12 ns en un appel de 0,36 ns et ramène l’allocation à zéro. Sur une entrée non vide, c’est une vérification de taille suivie exactement du même stream, avec exactement la même allocation.

La boucle et Eclipse Collections restent à zéro

Sur les longs parcours, elles sont 2 à 4 fois plus rapides et n’allouent pratiquement rien, parce qu’il n’y a aucun pipeline à construire. La seule allocation du groupe est le Optional de 16 octets de Iterables.findFirst.

La règle pratique est la règle habituelle pour les hot paths : un stream est un outil de lisibilité et la lisibilité vaut quelques centaines d’octets quand le code s’exécute une fois par requête, pas un million de fois par seconde. Dans une boucle serrée, dans un callback par élément ou sur une grande collection parcourue souvent, la simple boucle est à la fois l’option la plus rapide et la moins coûteuse et Eclipse Collections arrive juste derrière quand vous en dépendez déjà.

Références

Démonstration

Une démonstration des concepts illustrés dans cet article est disponible ici : stream-allocation-benchmark