P4a : Analyse de performances de différentes structures

Grille d'évaluation P4a

Problème

Lorsque l'on développe en Java, on aura souvent besoin d'utiliser des collections d'objets, sans que l'on en connaisse précisément leur fonctionnement. Chacune ayant des besoins différents, le temps d'exécution et la mémoire utilisée seront impactés par l'implémentation que l'on choisira.

On cherche donc ici à voir différentes configurations, comme par exemple:

• Quel type de collection est la plus rapide pour accéder à une donnée précise dans une collection d'objets de taille normale (~1.000 éléments) ?
• Si on se place dans une très grande collection (>100.000 éléments), quelle collection permet d'utiliser la mémoire au minimum ?

Il y a donc plusieurs paramètres qui pourront faire varier les mesures de temps d'exécution ou de mémoire en fonction du type d'opération:

• La taille de la collection
• Le nombre de répétition de l'opération choisie

Dispositif expérimental

Application

code source de l'application Java
code source du script sh
code source du script R

java -cp . main <structType> <size> <operation> <opSize>

Structures analysées

• LinkedList (listes chainées)
• ArrayList (listes non chainées)
• Set (collection sans doublon de valeurs)

Opérations analysées

• add (ajoute un nombre d'éléments x en fin de liste)
• contains (vérifie la présence de x éléments dans la liste)
• remove (retire x éléments au sein de la liste)

Environnement de test

Tous les tests ont été effectués sur mon ordinateur personnel, dont un extrait du fichier /proc/cpuinfo est le suivant:

model name	: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
cpu MHz		: 800.010
cache size	: 12288 KB
cpu cores	: 6

Description de la démarche systématique

Description de la démarche systématique et de l'espace d'exploration pour chaque paramètres.

> ./code/script.sh | tee ./data/src/dataTree.tsv
> ./code/plot.r

Le script plot.r lira par défaut le fichier dataTree.tsv présent à l'emplacement data/src/dataTree.tsv

Résultats préalables

Temps d'exécution

Opération	Plot
Add
Contains
Remove

Consommation mémoire

Opération	Plot
Add
Contains
Remove

Analyse des résultats préalables

La première chose que l'on peut remarquer est que le temps d'exécution et l'utilisation de la mémoire varient énormément selon le type de structures.

En effet, Set est bien plus long à l'exécution que les autres qui sont très proches lors de l'appel à l'opération add.

En revanche les trois structures sont très différentes sur les opérations contains et remove:

• Set est très stable et extrêmement rapide
• ArrayList reste relativement rapide même lorsque le nombre d'opérations augmente
• LinkedList a une augmentation très proportionnelle et prend donc beaucoup de temps s'il y a beaucoup d'opérations

Pour ce qui est de l'utilisation de la mémoire, on remarque que Set en utilise toujours une quantité bien supérieure à ArrayList et LinkedList quel que soit le type et nombre d'opérations. On peut également noter que ArrayList est moins gourmande en mémoire que LinkedKist.

Discussion des résultats préalables

Bien sur, ces résultats préalables ne peuvent pas démontrer efficacement la différence de temps et d'utilisation de mémoire. Pour se faire, il faudrait faire les tests sur d'autres ordinateurs aux performances différents par exemple.

Etude approfondie

Hypothèse

On a remarqué lors des résultats préalables que l'utilisation de la mémoire variait peu entre la LinkedList et l'ArrayList.
On veut donc ici observer si cette différence va augmenter ou non avec le temps, quand on rajoute des données et qu'on agrandit la structure.

Protocole expérimental de vérification de l'hypothèse

On rajoute dans le fichier script.sh les lignes suivantes:

structSize[5]=200000
structSize[6]=500000
structSize[7]=1000000

operationSize[5]=200000
operationSize[6]=500000
operationSize[7]=1000000

On relance ensuite ce script pour remplacer le contenu du fichier dataTree.tsv et enfin relancer le fichier plot.r pour générer les nouveaux graĥes.

Résultats expérimentaux

Le vilain canard a lancé les tests de son expérience trop tard, et n'est pas en mesure de fournir des graphes pour étayer son analyse, du moins pas dans la limite de temps imposée.

Analyse des résultats expérimentaux

Les valeurs affichées en terminal montrent que l'augmentation de la mémoire utilisée par la LinkedList et l'ArrayList ne varient pas de façon à s'éloigner grandement l'une de l'autre.

Discussion des résultats expérimentaux

L'utilisation d'un si grand nombre de valeurs n'était peut-être pas la solution pour mettre en évidence une différence d'utilisation de mémoire.
La durée des tests, en revanche, augmente de façon exponentielle pour la LinkedList, pouvant atteindre des durées supérieures à 20 minutes lorsque l'on doit tester de grandes quantités d'éléments.
L'ArrayList montre également une forte augmentation du temps d'exécution, mais celui-ci reste négligeable en comparaison à la LinkedList.

Conclusion et travaux futurs

On peut conclure de la manière suivante:

• Set sera une bonne solution si l'on souhaite effectuer quelque chose rapidement sans se soucier de la mémoire
• LinkedList est le choix à privilégier si l'on sait d'avance que la vitesse d'exécution va s'allonger, et que la mémoire a des limites
• ArrayList sera lui le meilleur compromis entre vitesse et utilisation de la mémoire

Bien qu'ayant des avantages, Set possède également des points faibles à connaitre:

• L'impossibilité de doublons dans la collection
• Il utilise la mémoire bien plus que les listes (ArrayList ou LinkedList)
• Set n'est rapide qu'en analyse, pas en ajout