P4a : Analyse de performances de différentes structures
Groupe
- BOCH Antoine
- MARCHAL Benjamin
Projet fait en groupe (les readmes et projet sont identiques) !
Problème
Description du Problème
En informatique, la rapidité d'exécution d'un programme est souvent recherchée et dépend de nombreux facteurs. Que ce soit l'utlisation d'une certaine structure de donnée, une liste par exemple, ou encore une opération sur ces structures, comme un ajout d'élément dans ladite liste, allant jusqu'à l'exécution répétitive du même programme. Nous utilisons régulièrement des structures de stockage de données comme les listes ou les tableaux. Cependant ces choix apportent certains avantages et inconvénients, mais surtout une différence en terme d'utilisation de mémoire et de temps d'exécution.
De ces faits, nous allons étudier plus en détail ces écarts de temps d'exécution, ainsi que les facteurs qui influent plus ou moins ces variations. Donc au travers de l'étude de différentes structures de données et d'opérations, nous allons voir dans quels cas nos choix entrainent des différences de temps d'exécution et d'utilisation de mémoire significatifs. Le but de cette analyse étant de trouver la collection la plus performante avec différents paramètres.
Notre programme nous permet donc de tester plusieurs variantes afin de déterminer quoi choisir.
Description de tous les paramètres exploratoires du problème
Pour réaliser ces observations j'ai donc choisi trois types de structure:
- ArrayList
- LinkedList
- Vector
Mais également trois opérations différentes :
- enTete : cette méthode ajoute un élément au début de la liste / du tableau
- enQueue : cette méthode ajoute un élément à la fin de la liste / du tableau
- efface : cette méthode ajoute les éléments en fin de liste / tableau, et qui les suppriment tous
De plus, le nombre d'itérations de la valeur ajoutée et la taille de la structure seront testés.
Dispositif expérimental
Application
Usage : java Program "Structure" "Test" <Occurence> <TailleStruct>Description de l'application et des arguments
L'application permet d'effectuer plusieurs tests sur différentes structures de données. Ces tests sont notamment diverses opérations effectuées un certain nombre de fois.
En ce qui concerne les arguments, on prend en compte :
- Le type de la structure utilisée
- ArrayList
- LinkedList
- Vector
- L'opération a effectuer sur cette structure
- enTete
- enQueue
- effacer
- Le nombre d'itérations de ces opérations
- La taille des structures
Environnement de test
Description de la plateforme de test
Sur troglo.iutrs.unistra.fr :
Model name : Intel(R) Xeon(R) CPU E5-2630L v3 @ 1.80GHz
Cpu MHz : 1199.115
Cache size : 20480 KB
Description de la démarche systématique
Description de la démarche systématique et de l'espace d'exploration pour chaque paramètres.
./test.sh |tee results.dat
-> le script R se lance à la fin du bash.Script sh qui met en place chaque paramètre et appel les fonctions du programme java, pour sortir le temps d'exécution, l'utilisation de la mémoire, le nombre d'itérations et les tailles de structures, dans un fichier "result.dat". Appelé avec la commande : **./Test.sh | tee results.dat ** dans le dossier P4a.
Puis, appel du script R via la commande ./cmdR.R dans le dossier graphs accessible via cd graph, pour exploiter les résultats du fichier "result.dat" graphiquement.
Résultats préalables
Temps d'exécution
Consommation mémoire
Analyse des résultats préalables
La mémoire se comporte de manière quasiment identique pour les 3 structures, avec les trois opérations, sauf pour la LinkedList qui consomme un peu plus de mémoire.
Les temps d'exécutions dépendent essentiellement de l'affichage des valeurs du tableau. Néanmoins on remarque de fortes variations entre les temps d'exécutions entre la LinkedList et les autres structures. Sauf pour l'opération d'ajout en tête, la LinkedList est nettement plus rapide que les autres structures, sur l'opération effacer aussi étant donné que l'on applique la méthode d'ajout en tête au préalable.
Donc pour l'instant, en utilisant les Integer, la LinkedList est la plus rapide mais consomme plus de mémoire.
Discussion des résultats préalables
Actuellement les résultats précédents permettent de voir graphiquement de grandes différences de temps d'exécutions et des légères différences dans les consommations de mémoires, mais si l'on ré-exécute le programme à nouveau on pourrait tomber sur d'autres résultats (changements de quelques microsecondes). De plus ces tests n'ont pas de comparatifs avec d'autres utilisations de types, on utilise que des Integer. Enfin, les méthodes sur ces structures ne sont pas si variées et n'utilisent principalement que l'ajout d'éléments. Il faudrait aussi faire des tests avec l'accès aux données et la suppression sans ajouts avant.
Ces résultats permettent néanmoins de donner une première image de ces structures, mais ne permettent pas de rééllement dire que telle structure est plus optimisée, à part pour certaines tâches.
Etude approfondie
Hypothèse
Dans l'analyse précédente on a vu comment réagissaient les différentes structures proposées par rapport au temps et à la mémoire consomée le tout sur des Integer. On se demande maintenant ce qu'il se passe au niveau du temps et de la mémoire si travaille avec deux fois plus d'Integer qu'un autre type, comme par exemple les buttons. Pour se faire les test seront réalisés uniquement sur une ArrayList.
Protocole expérimental de vérification de l'hypothèse
./testAnalyse.sh | tee resultsAnalyse.dat
cd graph
./prefAnalyse.RRemarque : Il faut penser a prendre la classe ArrayListl2
Script sh qui met en place chaque paramètre et appel les fonctions du programme java, pour sortir le temps d'exécution, l'utilisation de la mémoire, le nombre d'itérations et les tailles de structures, dans un fichier "result.dat". Appelé avec la commande : **./testAnalyse.sh | tee resultsAnalyse.dat ** dans le dossier P4a.
Puis, appel du script R via la commande ./prefAnalyse.R dans le dossier graphs accessible via cd graph, pour exploiter les résultats du fichier "result.dat" graphiquement.
Résultats expérimentaux
Temps d'exécution
Consommation mémoire
Analyse des résultats expérimentaux
En termes de temps d'exécution, l'ArrayList est plus rapide avec l'ajout en queue des éléments, que l'ArrayList. En effet, pour ajouter environ 1000000 d'Integer dans la liste, cela s'effectue en secondes, contrairement aux ajouts de Jbuttons. Plusieurs causes à ce résultat, tout d'abord le fait que les Integer ajoutés soient aléatoires, cela peut allonger le temps de remplissage. De plus, les bouttons ont toujours une "valeur" stable, donc pas de différences entre chaque ajouts.
Au niveau de la mémoire, c'est le même résultat, la mémoire consommée est moins élevée dans le cas des Jbutton, oscillant entre 50000kb et 65000kb, contre 50000kb et 85000kb pour les Integer.
On en déduit donc que l'impact du choix du type pour une certaine structure de donnée n'est pas négligeable. Aussi, on peut donc se demander pourquoi malgré tout les ArrayList restent le plus souvent utilisées, même si ce ne sont pas les plus optimisées pour certaines tâches ?
Discussion des résultats expérimentaux
Les résultats sont surprenants, notamment au niveau des différences de consommations de la mémoire. En effet, on a plus tendance à croire que, l'ajout de bouttons dans une ArrayList prend plus de mémoire de part leurs "type". Mais comme vu précedemment sur les graphes ce n'est pas le cas, pour la gestion des bouttons la plage d'utilisation de mémoire varie entre 50000 kb et 65000 kb. On peut donc dire qu'en ajoutant des Jbutton, l'ArrayList consomme moins de mémoire que pour les Integer.
Concernant l'utilisation des ArrayList en toutes circonstances, elles restent plus simple à comprendre et utiliser que les autres structures, et sont aussi plus souple en termes d'utilisation. C'est ce qui peut expliquer cette utilisation constante.
Conclusion et travaux futurs
Ce travail nous a permis de vérifier les conséquences liées aux temps d'exécutions et consommations de mémoires, qui varient selon les types de données utilisés. Pour nos travaux futurs, nous pourrons adapter notre script pour analyser nos futures choix dans nos programmes pour les optimiser.