P4a : Analyse de performances de différentes structures

Grille d'évaluation P4a

Problème

Lorsque que nous faisons de Java ou tout autre langage utilisant des Objets, il vient souvent l'idée d'utiliser des structures dans le but de stocker d'autres structures. De là, se pose la question de savoir quelle est la structure la plus adaptée à nos besoins, en général pour la plupart des personnes, nous utilisons des ArrayList. Mais est-ce la plus efficace ? Le but est de tester 3 structures pour voir laquelle serait la plus efficace.

Afin de mener à bien cette expérimentation, il faut effectuer des tests.

• ArrayList<>
• LinkedList<>
• Vector<>

Afin de réussir à avoir des résultats, nous pourrons essayer : p

• L'accès à un élément (Début/Milieu/Fin)
• La suppression d'un élément (Début/Milieu/Fin)
• L'ajout d'un élément (Début/Milieu/Fin)

Afin d'avoir plusieurs résultats, nous changerons le nombre d'éléments dans les structures initiales. Sachant qu'elles sont remplies aléatoirement.

Dispositif expérimental

Application

code source de l'application

    test.sh "structure" "methode"

    ---
    Java:

    arraylist
    linkedlist
    vector

    Operation:

    GetFirst
    GetMid
    GetLast
    SetFirst
    SetMid
    SetLast
    RemoveFirst
    RemoveMid
    RemoveLast

Environnement de test

Description de la plateforme de test

    model name      : Intel(R) Xeon(R) CPU E5-2630L v3 @ 1.80GHz
    cpu MHz         : 2387.888
    cache size      : 20480 KB
    siblings        : 16
    Memory          : 31986MB

Description de la démarche systématique

./test.sh

- javac src/app/Maine.java
- Lance une boucle faisant les tests

./test.sh

Résultats préalables

Temps d'exécution

Légende	ArrayList	Vector	LinkedList
Ajout
Modification
Suppression

Consommation mémoire

Légende	ArrayList	Vector	LinkedList
Ajout
Modification
Suppression

Analyse des résultats préalables

En terme de temps d'éxecution

Sur l'accès aux éléments, le Vecteur semble le plus rapide, l'ArrayList étant juste derrière, et ont des performance en termes de vitesse assez similaires, se jouant aux 0.1 s.. Si l'on s'intéresse un peu plus au temps d'exécution, on remarque un temps énorme d'accès pour la LinkedList qui semble être assez loin derrière le Vecteur et L'Arraylist, avec un maximum à 17 secondes.

Concernant la modification d'un objet, en l'occurence ici un Integer, du côté ddu Vecteur on remarque qu'au milieu, plus il y a d'éléments, plus, le temps est optimal (interprétation de R?). Elle est rejointe également par l'ArrayList concernant la vitesse, il est exponentiel, on peut remarquer juste, le fait qu'au début et au milieu sur un petit nombre d'éléments, le temps décroît avant de remonter en pic. Enfin, la LinkedList, à l'image du get, on remarque des performances par très optimales a partir d'un grand nombre d'Objets, il est assez intéressant de voir comment, d'un coup, il est possible d'atteindre les 15 secondes quelque soit l'endroit de la modification.

Finalement, concernant la suppression, le vecteur est encore une fois le plus rapide, mais cela se joue à rien avec l'ArrayList qui est assez proche des performance du Vecteur sur le premier élément. On peut remarquer que le vecteur au milieu des tailles atteintes, semble gagner de la performance que ce soit au milieu, au début ou à la fin, encore une fois peut-être une interprétation de R du fait de la courbe. L'ArrayList, est exponentielle à la manière de la modification, avec des performances semblables au Vecteur. Finalement, la LinkedList est à l'image de la modification et à l'accès d'un élément, c'est à dire, à partir d'un gros nombre d'éléments, cette dernières franchi des performances en terme de vitesse, très imprésionnant mais dans le mauvais sens.

En terme de mémoire

On peut remarquer que le vecteur ainsi que l'ArrayList sont équivalentes en terme d'usage de mémoire. Tandis que la LinkedList à un plus gros usage de mémoire.

• Lors de l'accès au début, au milieu et à la fin, 20% de plus environ dès lors que l'on atteint de grosses listes.
• Lors de la modification également, mais on constate une légère baisse(interprétation de R sûrement).
• Lors de la suppression, même constat.

Le plus impressionnant, c'est tout de même la courbe du Vecteur et de l'ArrayList qui semblent être presque identique sur les 3*3 opérations.

Discussion des résultats préalables

On peut remarquer tout le long que le Vecteur et l'ArrayList sont assez similaires, on pourrait remplacer un Vecteur par une ArrayList dans un code sans réellement voir la différence et inversement. Par contre concernant la LinkedList, on a du mal à comprendre, elle hérite également de List<>, on se demande pourquoi les performances de cette dernière sont si mauvaises à partir d'un gros nombre d'éléments. Le seul endroit où les résultats pourraient être faussés serait lors de la modification, en effet, c'est un nombre aléatoire qui est tiré, mais je ne pense pas que cela affecte vraiment les performances de cette dernière.

Nous avons donc bien constaté que le Vecteur est le plus rapide des trois structures, que l'ArrayList pourrait bien le remplacer. Néanmoins, une liste chaînée tel qu'une LinkedList est assez lourd pour un code et se ferait ressentir, d'où les courbes.

Etude approfondie

Hypothèse

Nous avons pu voir tout au long de ces tests, que les Vecteurs et les ArrayList sont à des performances à peu près équivalente, ce qu'il serait intéressant de voir, c'est quelle est la limite à cette équivalence ? Pour ce faire, nous utiliserons des structures remplies de plus de 10 millions d'objets le tout en intérant 100 fois dans le bout de voir également si cette performance reste équivalente entre les deux. De plus, on peut se demander, si finalement à tort d'user d'ArrayList, pourrions-nous pas les remplacer par des Vecteurs ? En effet, si finalement, cela est plus rapide, il serait bon de faire la transition.

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

Nous allons refaire un script shell conçu spécialement pour tester cette hypothèse

./testH.sh

Résultats expérimentaux

Vitesse

Légende	ArrayList	Vector
Ajout
Modification
Suppression

Mémoire

Vitesse

Légende	ArrayList	Vector
Ajout
Modification
Suppression

Analyse des résultats expérimentaux

Vitesse

Premièrement, on peut constater que le vecteur est bien plus rapide sur de plus grosses valeurs, les premières sont de l'ordre de 10 millions allant jusqu'à 40 millions peut-être. On peut donc constater sur l'accès du premier élément que le Vecteur est plus rapide, pour un premier à moins de 4 secondes et plus l'on avance et plus ces dernières sont proches de 4,5 ou 5. C'est assez contrasté par rapport à l'ArrayList qui elle début sous la barre des 7 secondes pour le premier élément. Puis cela est exponentiel des deux côtés, peut-être tout de même plus droit du côté de l'ArrayList augmentant plus rapidement, on fera le même constat au niveau du dernier élément et de celui du milieu.

On observe également, concernant la vitesse, que le vecteur est plus rapide que l'ArrayList, toujours dans les mêmes circonstances exactement comme l'accessibilité, et il est de même pour la moditification

Mémoire

Ici, malgré l'échelle au niveau de la mémoire, on voit tout de suite, qu'elle n'est pas la même, avec 1 million pour le vecteur en tant que plus grosse graduation et 600 000 également pour la plus faible. On peut remarquer que, au début, le même nombre de mémoires est utilisé, cela se suit au niveau de l'accès au premier élément, à celui du milieu et à celui de la fin. Cela se gâte à partir du moment où les structures vont contenir de très gros nombres d'objets tel que 30 millions, on voit alors les limites de l'ArrayList, laissant au vecteur son avantage de mémoire au niveau de l'accès. On peut également observer pour la modification et la suppression, que le Vecteur de manière générale utilise moins de mémoire que l'ArrayList.

Discussion des résultats expérimentaux

On a donc pu voir que finalement, par ces tests qu'un Vecteur prends moins de mémoire qu'une ArrayList, les opérations fondamentales sont également plus rapides sur un vecteur. Aussi les résultats n'étant pas faits sur exactement les mêmes valeurs s'ils n'ont pas une marge d'erreur à prendre en compte. En plus, du fait du nombre de personne sur un serveur à distance, que serait-il de ces tests sur un autre ordinateur?

Conclusion et travaux futurs

On peut désormais se dire qu'à outre mesure, il serait peut-être préférable de privilégier un Vecteur plutôt qu'une ArrayList. Comme futurs travaux, il serait possible de regarder également à l'inverse, jusqu'à quand est il le plus utile d'utiliser une ArrayList? Cela est plutôt un cadre non traité ici, puisque j'ai privilégié la quantité élevé et non-basse, mais cela aurait pu être une bonne piste également puisque peu de personne n'utilisent 40M de données tous les jours.