Tutoriel sur les bibliothèques de substitution pour les collections Java

Nous nous sommes limités aux opérations d'ajout, de suppression et de recherche dans une liste. Les tests ont été effectués sur un grand nombre de données en itérations successives. Une moyenne a été établie sur plusieurs itérations pour éviter les perturbations périphériques (initialisation de la JVM, charge CPU).

Bien que l'occupation de la mémoire soit un élément prépondérant, il ne sera pas abordé ici, car il est hors du scope que nous nous sommes fixé, et il nécessite à lui seul un article complet. Toutefois, certains frameworks proposent une stratégie de compression des données, nous verrons cela en annexe.

Pour les insertions nous avons étudié deux cas : un conteneur d'une taille initiale de 10 et un autre d'une taille initiale de 1 000 000.

Nous nous sommes également limité aux données entières qui, même si elles ne sont pas représentatives d'un système complet, permettent de simplifier les tests et de fixer les idées. L'ossature des tests est la suivante :

• Ajout

Collection liste = …
Start timer
for (int i = 0; i < 1000000; i++)
liste.add(i);
Stop timer

• Recherche (un entier au hasard entre 0 et999 999)

Collection liste = …
Start timer
collection.indexOf(element);
Stop timer

• Suppression

Start timer
// indexes est la liste en désordre des éléments à supprimer.
int[] indexes;
for (int i = 0; i < 20000; i++)
collection.remove(indexes[i]);
Stop timer

Les tests ont été faits avec la JVM de Oracle version 1.7.0_21-b11 paramétrée à Xmx :1024m et Xms :1024m. Toutes les durées sont exprimées en millisecondes.

Java fournit plusieurs implémentations de listes, nous avons choisi de tester ArrayList (dont la structure interne est un tableau) et les LinkedList (dont la structure interne est une liste doublement chaînée).

II-A. Linkedlist Java▲

II-B. ArrayList Java▲

GsCollection est un framework de collections qui peut se substituer à l'API Collections. Il propose des collections optimisées pour réduire le temps de traitement et l'utilisation mémoire. Pour plus d'informations :https://github.com/goldmansachs/gs-collections. Nous allons faire les tests avec la classe IntArrayList.

Ajoutons 1 000 000 entiers dans une liste.

Recherchons d'un élément dans une liste de 1 000 000 entiers (méthode indexOf).

Supprimons 20 000 éléments d'une liste dans un ordre aléatoire.

PCJ (Primitive Collections for Java) est un framework de collections pour les types primitifs. Il propose des collections pour les types primitifs tels que boolean, char, byte, short, int, long, float, et double. Ces collections sont optimisées pour de grandes performances. Pour plus d'informations http://pcj.sourceforge.net/. Nous allons faire des tests avec la classe IntCollection.

Ajoutons 1 000 000 entiers dans une liste.

Recherchons d'un élément dans une liste de 1 000 000 entiers (méthode indexOf).

Supprimons 20 000 éléments d'une liste dans un ordre aléatoire.

Javolution est un framework de collections qui propose un ensemble minimal de classes. Il fournit des classes performantes et optimisées. Le site officiel annonce une complexité pour les insertions et les suppressions en O[log(n)] !!! Cette API peut remplacer les Collections du JDK. Pour plus d'informations http://javolution.org/.

Nous allons faire les tests avec la classe FastTable qui est une implémentation de la classe abstraite FastCollection.

Ajoutons 1 000 000 entiers dans une liste.

Recherchons un élément dans une liste de 1 000 000 entiers (méthode indexOf).

Supprimons 20 000 éléments d'une liste dans un ordre aléatoire.

Trove propose une extension légère et rapide du framework Collections. Ces collections sont spécialisées pour les types natifs (TIntCollection, TFloatCollection, TDoubleCollection, etc). Le site officiel affirme qu‘avec Trove nous construirons les meilleures applications client ou serveur qui fonctionneront plus rapidement en consommant le moins de mémoire ! Néanmoins Trove ne semble pas exposer les mêmes interfaces que l'API Collections : la classe que nous avons utilisée (TIntArrayList) étend une interface propre au framework TIntCollection. Pour plus d'informations : http://trove.starlight-systems.com/.

Nous allons faire les tests avec la classe TIntArrayList qui est une implémentation de TIntCollection.

Ajoutons 1 000 000 entiers dans une liste.

Recherchons un élément dans une liste de 1 000 000 entiers (méthode indexOf).

Supprimons 20 000 éléments d'une liste dans un ordre aléatoire.

Ajout de 1 000 000 dans un tableau de taille 10.

Ajout de 1 000 000 dans un tableau de taille 1 000 000

Recherche d'un élément dans la liste de 1 000 000 éléments avec la méthode indexOf

Suppression dans une liste de 20 000 éléments dans un ordre aléatoire.

Les frameworks PCJ, GsCollections et Trove 4j affichent des performances intéressantes en comparaison des performances des LinkedList ou des ArrayList. PCJ et Trove4j affichent des performances intéressantes en recherche et en recherche-suppression, mais restent en dessous pour les opérations d'insertion. GsCollections affiche des performances intéressantes en insertion, quant à Javolution, il affiche des performances assez comparables à celles de l'API Collections.

Quel framework de collections Java choisir ?

Pour faire un choix, il est primordial de savoir comment vont être utilisées les collections. Est-ce qu'elles vont être modifiées (suite à beaucoup de suppressions par exemple) : il faudra alors choisir des bibliothèques ou des classes efficaces pour les opérations de suppression, d'insertion et de recherche - par exemple celles qui proposent une complexité en O(log(n)) peuvent faire la différence avec celles dont la complexité est en O(n). Vont-elles être peu modifiées, il faudra prendre en compte la complexité sur les opérations d'insertion.

Nous nous sommes limité ici aux List qui ne sont pas nécessairement la structure la plus adaptée. Un mauvais choix peut induire de très mauvaises performances. Certains algorithmes ont besoin de structures de données spécifiques : il sera préférable d'utiliser une Map pour accéder aux données de référence via leur clé : l'opération get est en o(1). De même on pourra préférer les Set aux List si les données n'ont pas besoin d'un ordre naturel, car la complexité de l'opération get est aussi en o(1).

Enfin certaines structures du JDK sont conçues pour être efficaces : la Javadoc de l'API souligne que les classes TreeMap et TreeSet ont une complexité garantie en O(log(n)) pour les opérations d'ajout, de suppression ou de recherche d'un élément.

Les aspects non techniques suivants peuvent être importants pour le choix du framework :

1. Un minimum d'impacts sur le code
   Dans le cas où l'on veut remplacer le framework Collections de Java sur un applicatif existant, il est indispensable que l'impact soit minimal. Pour cela, il faut que l'API s'intègre aux interfaces exposées par l'API Collections. Or Trove4J et PCJ exposent leurs propres interfaces et ne peuvent donc pas remplir cette condition, quant à GSCollection et Javolution, ils répondent à cette exigence.
2. Pas de conflits avec les bibliothèques tierces
   Si le développement démarre depuis zéro, il faut que le framework expose les mêmes interfaces que l'API Collections. Ainsi, si l'on veut modifier le framework, ce changement aura le moins d'impacts possible. Il est aussi très gênant de découvrir a posteriori que notre framework ne cohabite pas avec des bibliothèques tierces, très populaires et très utilisées comme Hibernate ou Spring.
3. La simplicité d'utilisation de l'API

La popularité du framework de Collections du JDK réside non seulement dans sa richesse ou sa robustesse, mais aussi dans son utilisation intuitive. Il serait bon qu'un autre framework conserve cette simplicité.

Au regard de ces éléments, il semble que le framework GSCollection se démarque du lot : il est simple à utiliser, efficace et repose sur les interfaces communes de l'API Collections. On pourra également se pencher sur Javolution qui affiche des complexités en O(log(n)) pour les opérations d'insertion et de suppression et qui par ailleurs présente des performances comparables à celles de l'API Collections.

Le monde Java propose beaucoup de frameworks de collection qui ont pour certains des performances très intéressantes. Le choix d'un substitut au framework Collections du JDK se fera par une réflexion globale et approfondie. Il sera nécessaire de prendre en compte non seulement les aspects performances, mais aussi ceux de modularité, de simplicité ou encore la capacité du framework de s'intégrer à un écosystème existant ou à exposer une interface générique.

Pour élargir l'horizon à des problématiques assez récurrentes, nous allons discuter des réponses des API aux points suivants.

1. Occupation de la mémoire
   Les collections étudiées ci-dessus ne proposent pas toutes un mécanisme pour garantir une moindre occupation de la mémoire. Pour gérer des collections volumineuses, on pourra utiliser l'API Vanilla qui propose des optimisations spécifiques afin de préserver la consommation des ressources, avec notamment une compression des données des collections qui en garantit une consommation linéaire. Par ailleurs, cette API s'intègre aux interfaces de l'API Collections. Voici ci-dessous un exemple simple de son utilisation :

    

   Sélectionnez

   1.
   2.
   3.
   4.
   5.
   6.
   7.
   8.
   9.
   10.
   11.
   12.
   13.
   14.
   15.
   16.
   17.
   18.
   19.
   

   interface MutableInteger {
   public void setInt(int value);
   public int getInt();
   };
    
   HugeArrayBuilder<MutableInteger> builderFull = new
   HugeArrayBuilder<MutableInteger>() {
   {
   allocationSize = ELEMENTS;
   capacity = ELEMENTS;
   }
   };
    
   HugeArrayList<MutableInteger> list = builderDefault.create();
    
   // Ajout d'un element
   MutableInteger type = builderDefault.createBean();
   type.setInt(i);
   list.add(type);
   

   Cette API semble moins facile d'utilisation, toutefois le site officiel affiche des métriques intéressantes qui peuvent nous aider à apporter une réponse aux projets traitant un ensemble de données important. Pour plus d'informations http://code.google.com/p/vanilla-java/wiki/HugeCollections.

2. Collections non modifiables

L'API de collections du JDK fournit un utilitaire Collections.unmodifiableList qui crée une Collection non modifiable, malheureusement rien ne garantit la non-modification du contenu de l'objet sous-jacent (par sa référence) : la collection « non modifiable » est une vue de la collection originale. Guava propose un mécanisme fiable pour créer des collections non modifiables. À l'aide de la classe utilitaire ImmutableList.copyOf nous créons une nouvelle collection non modifiable par copie de celle passée en paramètre.

ImmutableList<String> list2 = ImmutableList.copyOf(list);

Toutefois la modification de la collection lève une UnsupportedOperationException qui peut être problématique dans un applicatif, car il faut assurer une gestion particulière de cette exception.

Pour plus d'informations : http://code.google.com/p/guava-libraries/wiki/GuavaExplained.

Cet article a été publié avec l'aimable autorisation de SQLI qui est le partenaire de référence des entreprises dans la définition, la mise en œuvre et le pilotage de leur transformation digitale.

Nous tenons à remercier Claude Leloup pour la relecture de cet article et milkoseck pour la mise au gabarit.