Java Collection Performance

Le temps de [ ] est révolu ; celui de < > est venu. La liste a remplacé le tableau et type ses éléments — comme son prédécesseur — depuis java 1.5. Mais est-elle efficace ? À quel prix s’entoure-t-on d’un de ses cadets, LinkedList, HashSet, TreeMap ? La JavaDoc détaille leurs complexités, pourtant aucun site ni ouvrage semblent n’en faire l’écho. Quelques indices glanés dans « Java in a Nutshell » quelques autres dans « Java Generics and Collections » pas beaucoup plus sur la toile à ma connaissance. Les Collections, utilisées si généreusement, seraient méconnues ? Petite revue des troupes.

Complexité(s)

Deux complexités sont couramment exprimées dans le domaine informatique, complexité en temps et en mémoire. Dans ce but, des symboles portant une indication chiffrée entre parenthèses sont utilisés (en savoir plus). Cet article traite de la complexité en temps et utilise le symbole O — limite supérieure — pour ce faire.

  • O(n) — temps linéaire — indique la nécessité de parcourir chacun des n éléments d’une collection (dans le pire des cas) pour y réaliser une opération ;
  • O(log n) — temps logarithmique — indique que, plus le nombre d’éléments est élevé, plus la complexité d’une opération se tasse ;
  • O(1) — temps constant — indique que, quel que soit son nombre d’éléments, l’opération aura toujours un coup similaire.

Collections classiques

Commençons par la star de ces dames : ArrayList. Comme toute List qui se respecte, cette implémentation est une séquence d’objets autorisant les doublons, la valeur null et l’ajout à un index donné. Elle est bâtie sur un tableau dont la taille est gérée en interne.

add(e) get(i) remove(e) / remove(i) contains(e) size() iteration
ArrayList O(1) O(1) O(n) O(n) O(1) O(n)

légende : e = élément, i = index, n = nombre d’éléments

Cette liste est donc toute désignée lorsqu’il s’agit d’itérer sur des éléments ou d’y accéder par index. Mais, dès lors qu’une suppression ou une recherche est nécessaire, il faudra s’en remettre à une autre collection ; pourquoi pas au matheux de la bande : HashSet. Cet ensemble ne tolère ni doublons, ni valeur null ni accès à un élément donné. Il permet, cependant, de vérifier la présence d’un élément en son sein ou de l’en retirer en temps constant.

add(e) remove(e) contains(e) size(e) iteration
HashSet O(1) O(1) O(1) O(1) O(c)

légende : c = capacité (c > n)

Cet ensemble serait la collection idéale si il offrait la possibilité d’accéder à un élément par index. Il n’en demeure pas moins un alié de choix lorsque l’appartenance d’un élément prime sur la valeur de ses attributs. Si ces deux informations comptent, c’est à sa soeur ainée qu’il faut s’adresser : HashMap. Ce dictionnaire référence ses objets par clé (à l’image du rangement d’une définition par mot dans un dictionnaire classique). L’ajout d’un objet pour une clé existante remplace l’ancien objet.

put(k, e) get (k) remove(k) containsKey(k) containsValue(e) size() iteration
HashMap O(1) O(1) O(1) O(1) O(n) O(1) O(c)

légende : k = clé (de type objet)

Attention toutefois, les objets clés sont transformés en entier à l’aide d’un algorithme de hash (la structure sous-jacente peut être vue ainsi Map<int, Objet>). Ce calcul est effectué à partir de la référence java de l’objet ; deux objets aux attributs égaux ne correspondent pas à la même clé. Il est possible de modifier cet état de fait via la surcharge des méthodes hashCode() et equals() (« Effective Java » souligne que les deux méthodes doivent toujours être implémentées de paire). Les wraps de type primitifs les surchargent par défaut (deux Integer de même valeur représentent la même clé).

Comme le souligne la JavaDoc, la complexité des types à base de hash est garantie à condition que la fonction de hash répartisse correctement leurs valeurs. Les collisions sont prises en charge ; lorsque deux objets aux attributs différents obtiennent le même hash, ils sont tous deux conservés. Si la fonction de hash est correcte, n opérations s’effectuent en O(n), les erreurs étant amorties par le nombre d’éléments, une opération est bien en O(1).

En Java les hash sont couramment calculés ainsi, pour n attributs a : ((17 * 31 + a1) * 31 + a2) * ... * 31 + an 31 offre les qualités d’être un nombre premier, impair et de permettre une multiplication optimisée 31 * i == (i << 5) - i Et, toujours selon « Effective Java », ce nombre offre une bonne distribution (HashCodeBuilder de commons-lang s'appuie lui, par défaut, sur 37). La valeur initiale 17 diminue le nombre de collisions qu'aurait occasionné un premier attribut de valeur 0. Sa valeur est arbitraire.

Respect de l'ordre d'insertion

Certaines implémentations des collections sont dédiées au maintient des éléments dans leur ordre d'insertion.

add(e) / ... / size(e) iteration
LinkedHashSet idem HashSet O(n)

À l'instar du HashSet, les opérations du LinkedHashSet sont en temps constant. Ses performances sont légèrement moins bonnes (à cause du coût de maintient du tri), à une exception : itérer sur ses éléments sera moins coûteux (relatif à son nombre d'éléments et non à sa capacité).

Ces mêmes remarques s'appliquent à LinkedHashMap, respectant elle aussi l'ordre d'insertion.

put(k, e) / ... / size() iteration
LinkedHashMap idem HashMap O(n)

En ce qui concerne les listes, ArrayList maintient déjà les éléments dans leur ordre d'insertion, mais des compères peuvent lui prêter main forte dans certains cas particuliers.

add(e) get(i) remove(e) remove(i) contains(e) size() iteration
LinkedList O(1) O(n) O(1) O(n) O(n) O(1) O(n)

légende : ajout en queue, retrait en tête

Comme ses paires, la liste doublement chainée LinkedList n'est pas allouée d'un bloc ; ses éléments se référencent les uns les autres. Récupérer un élément à un index donné peut être coûteux si l'on ignore son prédécesseur ou son successeur (LinkedHashSet et LinkedHashMap ont recours à ce procédé pour garantir l'itération ; chaque élément connait le suivant).

push(e) peek() pop() contains(e) size() iteration
ArrayDeque O(1) O(1) O(1) O(n) O(1) O(n)

Une ArrayDeque peut être utilisée comme une file d'attente ; premier arrivé, premier servi (FIFO). Elle peut également l'être comme une pile d'assiettes ; dernière arrivée, première utilisée (LIFO). Cette implémentation est à préférer à celle de Stack, basée sur Vector. Comme elle n'accède qu'aux premier et dernier éléments, cette implémentation offre une suppression en temps constant.

Respect de l'ordre naturel

Certaines implémentations des collections sont dédiées au maintient des éléments dans leur ordre naturel (les chiffres et les chaines de caractères par ordre croissant, les objets selon leur implémentation de l'interface Comparable) évitant d'avoir recours à un tri.

add(e) remove(e) contains(e) size(e) iteration
TreeSet O(log n) O(log n) O(log n) O(1) O(c)

Un TreeSet peut remplacer avantageusement un ensemble classique lorsque des éléments y sont ajoutés à différentes reprises et que leur ordre importe.

put(k, e) get (k) remove(k) containsKey(k) containsValue(e) size() iteration
TreeMap O(log n) O(log n) O(log n) O(log n) O(n) O(1) O(c)

Une TreeMap permet de s'assurer de l'ordre d'itération sur ses clés.

add(e) get(i) remove(e) / remove(i) contains(e) size() iteration
TreeList O(log n) O(1) O(log n) O(log n) O(1) O(n)

Une TreeList, proposée dans commons-collections car absente du langage natif, améliore suppression et vérification d'appartenance d'un élément au détriment d'une insertion plus coûteuse. Sa documentation souligne que LinkedList est rarement un bon choix (via des statistiques que l'on aimerait voir plus souvent ; TreeList vs ArrayList vs LinkedList).

Limite des collections du JDK

Malgré sa richesse, certains cas de figure ne sont pas adressés par les collections du JDK. C'est là qu'Apache avec ses commons-collections et Google avec guava-collections (anciennement google-collections) prennent le relais. Contrairement aux secondes, et malgré leur popularité, les premières ne supportent pas les génériques (un portage de la version 3.1 par une entreprise externe les y ajoute ; mais ne semble plus maintenu). Voici leurs dépendances maven : guava-collections, commons-collection (et de son port en collections-generic).

Retenir une collection pour sa complexité en temps n'a pas que des vertus d'optimisation, elle est porteuse de sens pour l'algorithme qu'elle accompagne ; elle porte plus que l'opération elle-même la logique des traitements attendus.

Ce billet est dédié à Denis Lapoire

Publié par

Publié par Yves Amsellem

Développeur depuis 5 ans — les 2 derniers chez Xebia — Yves tire de son expérience sur des sites à fort trafic une culture de la qualité, de l'effort commun et de l'innovation. Spécialisé du style d'architecture ReST, il intervient sur des projets web à forte composante JavaScript et NoSQL. Avec Benoît Guérout, il développe la librairie open source Jongo — Query in Java as in Mongo shell

Commentaire

24 réponses pour " Java Collection Performance "

  1. Publié par , Il y a 9 ans

    Merci pour cet article Yves.
    Les mots-clefs qui permettent de trouver les bouquins et sites qui traitent du sujet sont : « java data structures algorithms ».
    Il y en a quelques uns tout de même :-)

  2. Publié par , Il y a 9 ans

    Article très interessant. Merci

  3. Publié par , Il y a 9 ans

    Très intéressant !
    Dommage qu’il manque LinkedList.

    Sinon pour générer le hashCode() dans Java 7 on pourra utiliser Objects.hash(), et actuellement on peut utiliser Arrays.hashCode() :

    @Override
    public int hashCode() {
    // return Objects.hash(attr1, attr2, attr3);
    return Arrays.hashCode(new Object[]{attr1, attr2, attr3});
    }

    a++

  4. Publié par , Il y a 9 ans

    L’absence de LinkedList est due à son ambiguïté. Ce croisement entre ArrayList et ArrayDeque n’affiche pas clairement ses intentions. Sa complexité, illustrée dans un comparatif de la JavaDoc de TreeList, est en net retrait. Je déconseille cette collection.

  5. Publié par , Il y a 9 ans

    LinkedList n’est pas très efficace lorsqu’on la manipule par index. D’où les statistiques pas très belle du get/insert/remove « from anywhere ».

    Par contre elle offre de belle performance globale pour si on la manipule via un Iterator/ListIterator, que ce soit en ajout/suppression.

    C’est très efficace par exemple si on doit traiter la liste en plusieurs passes, en la modifiant pendant son parcours.

    a++

  6. Publié par , Il y a 9 ans

    Bonjour,

    Je suis tout à fait d’accord avec la conclusion de cet article, à savoir, utiliser la bonne collection pour le bon usage (et bien connaître les collections).

    Cela dit, je ne suis pas d’accord avec votre point de vue sur LinkedList. Il y a des usages pour lesquels c’est de loin de meilleur choix. Par exemple, si on veut faire des ajouts successifs dans une collection modifiable avant d’itérer pour créer une collection immuable, la javadoc de TreeList montre que le choix de LinkedList est meilleur avec un rapport de performance x5.

    Je trouve un peu dommage de ne pas mentionner les problématiques de concurrences. Dans la plupart des cas, c’est une problématique dont il faut tenir compte dans le choix des collections avant de privilégier la performance.

    Benoît

  7. Publié par , Il y a 9 ans

    J’ai du mal à voir quels cas particuliers gagnent à l’usage de LinkedList (le comparatif des trois types est tout de même assez édifiant). Sa JavaDoc ne présente malheureusement pas ses complexités ; elle est donc fournie sans garantie (si ce n’est celle de l’expérimentation, ce qu’Apache illustre clairement).

    J’ai hésité à glisser un mot à propos de la concurrence, mais je ne connais pas assez le domaine et pense qu’il s’agit là d’un sujet assez différent. Un domaine ou une relecture de chacune des collections semble nécessaire.

  8. Publié par , Il y a 9 ans

    Merci pour cet article qui résume bien le sujet.

    La dédicace à Denis Lapoire m’interpelle… S’agit-il du Denis Lapoire de l’ENSEIRB ? Pourrais tu éclairer cette dédicace ?

  9. Publié par , Il y a 9 ans

    Il s’agit bien de l’enseignant chercheur Denis Lapoire. Lui qui fournit des algorithmes et exhibe des preuves.
    Ces humbles complexités sont l’occasion de saluer un des hommes sans lequel le goût de mon travail ne serait pas le même. Merci à eux. Merci à vous, monsieur Hanin.

  10. Publié par , Il y a 9 ans

    [quote author=’Yves’] le comparatif des trois types est tout de même assez édifiant [/quote]

    Oui, mais il est faux :-)

    La comparaison sur le ‘add’ de LinkedList et ArrayList, par exemple est grossièrement fausse.

    En effet, LinkedList est, comme son nom l’indique, une liste chaînée. Donc l’ajout d’un élément coûte toujours la même chose. En gros, l’instanciation d’une structure maillon, et la mise à jour des pointeurs (pardon, des références).

    ArrayList encapsule un tableau. Donc l’ajout d’un élément ne nécessite, en général que la mise à jour d’une référence dans le tableau et de l’index de taille de la liste.

    Sauf que quand le tableau atteint sa taille maximale, il faut réallouer un tableau, de taille deux fois plus grande, et recopier tous les éléments du tableau précédent.

    Visiblement, les benchs de la javadoc de TreeList utilisent le cas où l’on sait à l’avance l’allocation finale de l’ArrayList. Cela rejoint la conclusion de l’article : il faut analysez les cas d’utilisation et choisir la bonne collection en connaissance de cause.

    De plus, le bench n’est pas pertinent.

    Il montre que les performances d’une liste chaînée sont mauvaises pour un randomAccess. Bon OK: c’est pas une nouveauté. On va pas utiliser une liste chaînée pour ça.

    Je ne suis pas un spécialiste des collections, mais la plupart des cas où j’ai trouvé pertinent d’utiliser une LinkedList, c’est justement pour des constructions intermédiaires (dans un builder par exemple).

    Pour information, les implémentations des List immuables en Scala ne sont pas basées sur les LinkedList natif Java, mais sur des listes chaînées encapsulées.

  11. Publié par , Il y a 9 ans

    @Benoit : oui, comme toi j’ai d’abord été étonnné par ces stats. Mais j’ai trouvé quelques explications de Stephen Colebourne dans les commentaires d’un blog :

    http://chaoticjava.com/posts/linkedlist-vs-arraylist/#comment-175
    http://chaoticjava.com/posts/linkedlist-vs-arraylist/#comment-182

    Je ne pense pas qu’il ait oublié le redimensionnement des tableaux. Il explique la différence par le fait qu’une LinkedList instancie un objet pour chaque nouveau noeud (objet qui devra aussi être traité par le garbage collector quand la liste diminue).
    Instancier et détruire des objets coûte cher, alors que recopier des tableaux est très rapide (System.arrayCopy fait un appel natif).

    Dommage qu’il ne donne pas plus de détails sur son benchmark.

    Autre commentaire intéressant : « You should only worry about the type of the list if it is long lived, large and performance is important ». Pas la peine de se prendre la tête quand n = 10.

  12. Publié par , Il y a 9 ans

    Salut Yves,

    Ca me rappelle les bancs de la FAC ou on abordait ces histoires de complexité.

    Pour information sans parler de concurrence, la ConcurrentHashMap est nettement plus performante qu’une HashMap non synchronisé et donc dans un environnement mono-threadé.

    @Benoit, tu nous fait un article sur les perfs des collections Scala pour nous éduquer :)

  13. Publié par , Il y a 9 ans

    Bonjour,

    Un petit commentaire qui peut sembler trivial, sur les TreeMap et autres collections triées utilisant un Comparator : Le fait de changer un attribut d’un objet de la liste, qui entre en jeu dans le calcul de la comparaison rend l’ordre des éléments de cette liste caduque, l’ordre des éléments n’est pas recalculé. Ca parait bête et évident, mais je me suis déjà fait avoir… Ce problème n’est pas facilement identifiable, car quand on tente d’accéder à un objet de la collection, le contains(e) peut alors renvoyer false bien que l’objet soit présent dans la collection (l’algorithme de recherche s’arrête quand il trouve un objet hors bornes, sans parcourir le reste de la collection).

    Sinon, merci pour ce très bon article qui résume bien les avantages et inconvénients de chaque implémentation, même s’il est parfois difficile de bien comprendre ces différences.

  14. Publié par , Il y a 9 ans

    L’article aborde un problème souvent négligé des développeurs.

    Mais l’auteur n’a visiblement pas compris la notation Théta. Sinon, il n’aurait pas écrit que Θ est la « limite supérieure ». En notation de Landau, théta désigne l’équivalent asymptotique. C’est « grand O » qui désigne la borne supérieure. Mais rien n’empêche d’étudier la complexité algorithmique maximale (plutôt que la complexité algorithmique moyenne ; ou encore la complexité algorithmique minimale). Ensuite, il n’aurait pas écrit que la complexité est un « Θ(c) où c>n ». J’imagine que la capacité est c=n+k ou bien c=a*n (selon les implémentations), et dans ce cas c’est tout simplement un Θ(n).

    Enfin, avec l’explosion des téléphones mobiles, il me paraît difficile de faire l’impasse sur la complexité mémoire.

  15. Publié par , Il y a 9 ans

    Régis,

    Je me suis en effet mépris sur la notation Théta. En relisant plus attentivement l’article wikipedia sur le sujet, j’ai trouvé de quoi éclairer mon erreur :

    T(n) = O(n3), which is identical to T(n) ∈ O(n3) — T(n) grows asymptotically no faster than n3.

    T(n) = Θ(n3), which is identical to T(n) ∈ Θ(n3) — T(n) grows asymptotically as fast as n3.

    Voilà qui est corrigé. Merci.

  16. Publié par , Il y a 9 ans

    Et en parlant de développement mobile, il est à noter aussi qu’Android propose des types spécifiques, tels que le SparseArray, SparseBooleanArray, SparseIntArray, SparseSet.

  17. Publié par , Il y a 9 ans

    Bonjour,

    Il faudrait un autre article sur les Collections car celles-ci sont à 99% mal exploitées notamment des itérations au niveau des performances :

    1) Le « for(String item :lstItem) » de Java5 est traduit en un Iterator parcourant la collection qui est moins rapide qu’une bonne vieille boucle for (int i=0; i Vérifier soit-même le
    2) En général, on fait des recherches sur une collection en la parcourant séquentiellement :
    List lstItem = new ArrayList(10);
    ….
    for(String item :lstItem) { .. parcours la Collection … }
    ==> Ce genre de code ne consomme que 1 Thread et ne sera pas plus rapide sur un mono-core ou sur un Hexa-Core…

    Il est temps de savoir utiliser les Callable et Executor de Java5 pour découper le problème et utiliser le maximum de ressources disponibles.
    Il est dommage que Java7 n’intègre pas de façon transparente des mécanismes tel que ceux préconisés par Doug LEA sur les ParallelArray (http://gee.cs.oswego.edu/dl/jsr166/dist/extra166ydocs/extra166y/ParallelArray.html)

    3) Même si tout n’est pas hautement parallélisable, il existe l’api APARAPI d’AMD qui permet d’accélérer certains traitements entièrement par le GPU des cartes graphiques avec OpenCL (ou par un parallèlisme 100% Java). J’ai essayé et ça marche plutôt bien. (http://developer.amd.com/zones/java/aparapi/pages/default.aspx) NB: Le SDK d’AMD marche même sans carte graphique puissante, il bascule sur OpenCL en mode CPU voire avec que des Threads 100% Java si nécessaire.

    Autre article intéressant : http://groups.csail.mit.edu/mac/users/gjs/6.945/readings/MITApril2009Steele.pdf
    ==> J’aime trop leur remarque « JavaTM-style iterators are so last millennium! »
    Et pourtant c’est ce que fera n’importe quel développeur avec les collections, il fera un « beau » FOR séquentiel alors que les CPU+GPU fusionnent déjà et que l’on arrive bientôt à 12 coeurs dans un CPU…

  18. Publié par , Il y a 9 ans

    @Olivier : le parcours d’une collection via index n’est valide que sur une ArrayList.

    L’Iterator garantie un parcours rapide et sûr dans TOUS les cas ;)

    a++

  19. Publié par , Il y a 8 ans

    Pour prolonger ce billet, une bonne comparaison des Collections et de leurs performances dans différents scénarios peut se trouver dans Implementation Patterns de Kent Beck. Je vous le recommande.

  20. Publié par , Il y a 7 ans

    Salut Yves,

    Merci pour l’article et surtout pour la dédicace ;)

  21. Publié par , Il y a 5 ans

    Bien compliqué pour pas grand chose et bien incomplet.
    valeur ajoutée zéro….
    ….à part se faire plaisir, et se caresser l’ego sur le ventre du net…

  22. Publié par , Il y a 5 ans

    @croute

    Que voilà un commentaire constructif !

    Et surtout grossièrement erroné : la compréhension des mécanismes et des performances des collections est une des plus importantes et souvent négligée pour un développeur Java (et en général pour tout développeur, quelque soit le langage).

  23. Publié par , Il y a 4 ans

    Plus de commentaire que de ligne d’article….
    Comment pourrais-on calculer la limite d’un Algorithme
    Par exemple pour un algorithme d’une complexité de n! on sait qu’à partir de n = 13 ça prend beaucoup de temps plus d’une minute pour un processeur d’1Ghz…
    La question est : c’est quoi la limite d’un algo de complexité linéaire ?

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Nous recrutons

Être un Xebian, c'est faire partie d'un groupe de passionnés ; C'est l'opportunité de travailler et de partager avec des pairs parmi les plus talentueux.