Il y a peu, je suis tombé sur ce bout de code qui concatène deux listes en utilisant la classe utilitaire Lists de Guava puis l’API Stream :

Lists.newArrayList(collectionOriginal,collectionValue)
        .stream()
        .flatMap(Collection::stream)
        .toList();

Comme ce bout de code est dans le chemin critique de l’application et donc appelé très fréquemment, je me suis demandé si c’était la meilleure manière de concaténer deux listes.

On peut concaténer deux listes de beaucoup de manières différentes :

• Avec le code ci-dessus
• Avec Stream.concat()
• Avec Stream.of()
• Avec ListUtils d’Apache Commons Collection
• Avec ArrayList.addAll()

Il y a certainement d’autre manière, mais je voulais déjà comparer ces cinq là !

Pour comparer ces cinq solutions, rien de mieux que JMH – The Java Microbenchmark Harness. Cet outil nous permet d’écrire des micro-benchmarks pertinents en tenant compte des caractéristiques internes de la JVM. Il offre aussi des outils intégrés pour analyser les performances de nos tests (profiler, disassembler, …). Si vous ne connaissez pas JMH, vous pouvez vous référer à cet article : INTRODUCTION À JMH – JAVA MICROBENCHMARK HARNESS.

Le benchmark

Pour pouvoir comparer sur plusieurs tailles de liste, j’utilise @Param pour paramétriser la taille des listes à concaténer. Voici le setup que j’ai utilisé :

@Param({"10", "1000", "10000"})
int size;

List<String> list1;
List<String> list2;

@Setup
public void setup() {
    list1 = new ArrayList<>(size);
    list2 = new ArrayList<>(size);
    for (int i = 0; i < size; i++) {
        list1.add("list1-" + i);
        list2.add("list2-" + i);
    }
}

Voici ensuite l'implémentation des cinq benchmarks

@Benchmark
public List<String> concatWithStreamConcat() {
    return Stream.concat(list1.stream(), list2.stream())
            .toList();
}

@Benchmark
public List<String> concatWithStreamOf() {
    return Stream.of(list1, list2)
            .flatMap(List::stream)
            .toList();
}

@Benchmark
public List<String> concatWithGuava() {
    return Lists.newArrayList(list1, list2)
            .stream()
            .flatMap(Collection::stream)
            .toList();
}

@Benchmark
public List<String> concatWithCommonsCollection() {
    return ListUtils.union(list1, list2);
}

@Benchmark
public List<String> concatWithNewArrayList() {
    List<String> newList = new ArrayList<>(list1.size() + list2.size());
    newList.addAll(list1);
    newList.addAll(list2);
    return newList;
}

Les résultats

Tous les tests ont été exécutés sur mon laptop : Intel(R) Core(TM) i7-1260P 8 coeurs (16 avec hyperthreading) – Ubuntu 24.10.

La version de Java utilisé est openjdk version "21.0.5" 2024-10-15 LTS.

 Benchmark                               (size)  Mode  Cnt       Score        Error  Units
 ConcatList.concatWithCommonsCollection      10  avgt    5      57,706 ±     27,376  ns/op
 ConcatList.concatWithCommonsCollection    1000  avgt    5    1631,110 ±    472,323  ns/op
 ConcatList.concatWithCommonsCollection   10000  avgt    5   15434,192 ±   2164,191  ns/op
 ConcatList.concatWithGuava                  10  avgt    5     225,249 ±     83,069  ns/op
 ConcatList.concatWithGuava                1000  avgt    5    7967,360 ±   8693,234  ns/op
 ConcatList.concatWithGuava               10000  avgt    5  108601,706 ± 104439,847  ns/op
 ConcatList.concatWithNewArrayList           10  avgt    5      54,327 ±     10,894  ns/op
 ConcatList.concatWithNewArrayList         1000  avgt    5    1515,667 ±    595,135  ns/op
 ConcatList.concatWithNewArrayList        10000  avgt    5   14827,026 ±   1253,715  ns/op
 ConcatList.concatWithStreamConcat           10  avgt    5     111,837 ±     26,451  ns/op
 ConcatList.concatWithStreamConcat         1000  avgt    5    7104,415 ±   4030,866  ns/op
 ConcatList.concatWithStreamConcat        10000  avgt    5   57587,144 ±  13994,551  ns/op
 ConcatList.concatWithStreamOf               10  avgt    5     157,634 ±     55,757  ns/op
 ConcatList.concatWithStreamOf             1000  avgt    5    5915,797 ±   1692,437  ns/op
 ConcatList.concatWithStreamOf            10000  avgt    5   58156,102 ±   1655,090  ns/op

Ce qui saute directement aux yeux, c'est que la version utilisée aujourd'hui est la pire :(.
Si on la laisse de côté, on constate que concatWithStreamOf et concatWithStreamConcat ont quasiment la même performance, ainsi que concatWithNewArrayList et concatWithCommonsCollection. En regardant le code de ListUtils.union(list1, list2) on s’aperçoit qu'il fait exactement ce qui est fait dans concatWithNewArrayList.

Analyse plus poussée

Pour aller plus loin dans l'analyse, relançons le benchmark avec le profiler GC intégré à JMH via l'option ligne de commande -prof gc, c'est souvent un bon début ;). Ce qui m’intéresse tout particulièrement, c'est le débit d'allocation mémoire (allocation rate).

ConcatList.concatWithCommonsCollection:·gc.alloc.rate.norm                   10  avgt    5     232,012 ±     0,002    B/op
ConcatList.concatWithCommonsCollection:·gc.alloc.rate.norm                 1000  avgt    5   16072,479 ±     0,036    B/op
ConcatList.concatWithCommonsCollection:·gc.alloc.rate.norm                10000  avgt    5  160077,107 ±     0,434    B/op
ConcatList.concatWithGuava:·gc.alloc.rate.norm                               10  avgt    5     888,058 ±     0,009    B/op
ConcatList.concatWithGuava:·gc.alloc.rate.norm                             1000  avgt    5   16969,104 ±     0,221    B/op
ConcatList.concatWithGuava:·gc.alloc.rate.norm                            10000  avgt    5  212148,835 ±     2,822    B/op
ConcatList.concatWithNewArrayList:·gc.alloc.rate.norm                        10  avgt    5     232,011 ±     0,003    B/op
ConcatList.concatWithNewArrayList:·gc.alloc.rate.norm                      1000  avgt    5   16072,511 ±     0,040    B/op
ConcatList.concatWithNewArrayList:·gc.alloc.rate.norm                     10000  avgt    5  160076,834 ±     0,366    B/op
ConcatList.concatWithStreamConcat:·gc.alloc.rate.norm                        10  avgt    5     424,023 ±     0,006    B/op
ConcatList.concatWithStreamConcat:·gc.alloc.rate.norm                      1000  avgt    5    8344,716 ±     0,173    B/op
ConcatList.concatWithStreamConcat:·gc.alloc.rate.norm                     10000  avgt    5   80350,980 ±     1,306    B/op
ConcatList.concatWithStreamOf:·gc.alloc.rate.norm                            10  avgt    5     824,037 ±     0,007    B/op
ConcatList.concatWithStreamOf:·gc.alloc.rate.norm                          1000  avgt    5   16905,076 ±     0,208    B/op
ConcatList.concatWithStreamOf:·gc.alloc.rate.norm                         10000  avgt    5  212083,533 ±     2,497    B/op

Ici, on va s’intéresse à la valeur de gc.alloc.rate.norm c'est le débit d'allocation mémoire normalisé par opération, et on voit tout de suite une grande différence. Si on prend comme référence ConcatList.concatWithNewArrayList :

• concatWithCommonsCollection : allocation identique.
• concatWithGuava : 4x plus d'allocation.
• concatWithStreamConcat : 2x plus d'allocation.
• concatWithStreamOf : 4x plus d'allocation.

Cela explique une partie des différences de performance, mais pas tout.

Relançons le test avec le profiler stack qui est un profiler simple et naïf intégré à JMH.

# Benchmark: fr.loicmathieu.jmh.ConcatList.concatWithCommonsCollection
# Parameters: (size = 10)

....[Thread state: RUNNABLE]........................................................................
 33,3%  50,0% $lt;stack is empty, everything is filtered?>
 31,6%  47,4% fr.loicmathieu.jmh.ConcatList.concatWithCommonsCollection
  1,5%   2,3% fr.loicmathieu.jmh.jmh_generated.ConcatList_concatWithCommonsCollection_jmhTest.concatWithCommonsCollection_avgt_jmhStub
  0,1%   0,1% java.util.ArrayList.<init>
  0,1%   0,1% java.util.Arrays.copyOf
  0,0%   0,0% org.apache.commons.collections4.ListUtils.union
  0,0%   0,0% java.lang.invoke.MethodHandle.maybeCustomize

# Benchmark: fr.loicmathieu.jmh.ConcatList.concatWithGuava
# Parameters: (size = 10)

....[Thread state: RUNNABLE]........................................................................
 33,3%  50,0% $lt;stack is empty, everything is filtered?>
 19,2%  28,8% java.util.stream.SpinedBuffer.ensureCapacity
  5,3%   8,0% java.util.stream.AbstractPipeline.wrapSink
  3,4%   5,1% java.util.stream.ReferencePipeline.toArray
  3,2%   4,8% java.util.stream.SpinedBuffer.copyInto
  2,1%   3,1% fr.loicmathieu.jmh.jmh_generated.ConcatList_concatWithGuava_jmhTest.concatWithGuava_avgt_jmhStub
  0,1%   0,1% java.util.stream.StreamSupport.stream
  0,0%   0,0% java.util.stream.ReferencePipeline.lambda$toArray$0
  0,0%   0,0% java.util.ArrayList.spliterator
  0,0%   0,0% java.util.stream.SpinedBuffer.inflateSpine

# Benchmark: fr.loicmathieu.jmh.ConcatList.concatWithNewArrayList
# Parameters: (size = 10)

....[Thread state: RUNNABLE]........................................................................
 33,3%  50,0% $lt;stack is empty, everything is filtered?>
 24,4%  36,6% java.util.ArrayList.addAll
  8,7%  13,1% fr.loicmathieu.jmh.jmh_generated.ConcatList_concatWithNewArrayList_jmhTest.concatWithNewArrayList_avgt_jmhStub
  0,1%   0,2% java.util.Arrays.copyOf
  0,0%   0,1% java.util.ArrayList.<init>
  0,0%   0,0% fr.loicmathieu.jmh.ConcatList.concatWithNewArrayList


# Benchmark: fr.loicmathieu.jmh.ConcatList.concatWithStreamConcat
# Parameters: (size = 10)

....[Thread state: RUNNABLE]........................................................................
 33,3%  50,0% $lt;stack is empty, everything is filtered?>
 22,5%  33,8% java.util.ArrayList$ArrayListSpliterator.forEachRemaining
  5,8%   8,7% fr.loicmathieu.jmh.ConcatList.concatWithStreamConcat
  3,7%   5,6% java.util.stream.ReferencePipeline.toArray
  1,1%   1,7% fr.loicmathieu.jmh.jmh_generated.ConcatList_concatWithStreamConcat_jmhTest.concatWithStreamConcat_avgt_jmhStub
  0,0%   0,1% java.util.ImmutableCollections.listFromTrustedArrayNullsAllowed
  0,0%   0,1% java.util.stream.ReferencePipeline.lambda$toArray$0
  0,0%   0,1% java.util.stream.StreamSupport.stream
  0,0%   0,0% java.util.ArrayList.spliterator



# Benchmark: fr.loicmathieu.jmh.ConcatList.concatWithStreamOf
# Parameters: (size = 10)

....[Thread state: RUNNABLE]........................................................................
 33,3%  50,0% $lt;stack is empty, everything is filtered?>
 16,9%  25,4% java.util.ArrayList$ArrayListSpliterator.forEachRemaining
  4,5%   6,8% java.util.stream.SpinedBuffer.copyInto
  4,5%   6,7% java.util.stream.AbstractPipeline.wrapSink
  3,4%   5,2% java.util.stream.SpinedBuffer.ensureCapacity
  3,4%   5,0% fr.loicmathieu.jmh.jmh_generated.ConcatList_concatWithStreamOf_jmhTest.concatWithStreamOf_avgt_jmhStub
  0,3%   0,5% java.util.stream.ReferencePipeline.toArray
  0,1%   0,2% java.util.stream.ReferencePipeline$Head.forEach
  0,0%   0,0% java.util.ArrayList.spliterator
  0,0%   0,0% java.util.stream.SpinedBuffer.inflateSpine

concatWithCommonsCollection et concatWithNewArrayList utilisent tous les deux java.util.Arrays.copyOf, cette méthode est annotée par @IntrinsicCandidate ce qui veut dire qu'il y a un intrinsic qui permet de l'optimiser directement au sein de la JVM. À ma connaissance, même si l'annotation contient Candidate dans le nom, au sein de la JVM OpenJDK d'Oracle il y a toujours au moins un intrinsic pour une des architectures supportées (ce qui peut ne pas être le cas pour d'autres fournisseurs de JVM). Cet intrinsic permet une copie efficiente en mémoire des tableaux des éléments de la liste sans nécessiter de parcours de la liste et copie un à un des éléments.

concatWithStreamConcat et concatWithStreamOf tous les deux parcourent tous les éléments de la liste via java.util.ArrayList$ArrayListSpliterator.forEachRemaining ce qui est moins efficace.

concatWithGuava parcours aussi tous les éléments de la liste, mais en plus va créer une liste avec les deux premières listes ce qui va doubler le nombre de fois où les éléments sont copiés !

Conclusion

Le code le plus simple est souvent le plus performant même s'il n'est pas forcément le plus élégant.

La JVM contient de nombreux intrinsics qui permettent des opérations de copie en mémoire de tableaux, ceux-ci sont primordiaux quand on travaille avec de grande liste de données.

Bien sûr, cette optimisation n'a du sens que si le code appelé est dans le chemin critique de l’application, ici, la concaténation est potentiellement réalisée des milliers de fois par seconde dans Kestra, c'est donc important qu'elle soit réalisée de la manière la plus performante.

Pour rappel, cet article contient des nombres qui ne sont que ça, des nombres, ils peuvent être très différents d'un contexte à l'autre. Il est toujours mieux de réaliser vous-même vos benchmarks, dans votre contexte puis de les valider dans un environnement réel pour en déduire la pertinence.

Pour les curieux, voici la PR dans le repo Kestra: https://github.com/kestra-io/kestra/pull/7160 et voici le benchmark complet : ConcatList.java.