Participants: CHAUVIN Ewan, EHLES Ivan
P4a : Analyse de performances de différentes structures
Problème
Description du Problème:
C’est la comparaison des performances de différentes structures de données et différentes implantations, pour différentes opérations, en termes de consommation CPU et de consommation mémoire. Dans notre cas, l'objectif sera donc de comparer les performances de différentes opérations pour différentes implémentations de l'interface List.
Description de tous les paramètres exploratoires du problème:
Les paramètres modifiables seront:
- Le choix de la structure
- Le choix de l'opération à éxecuter
- Le nombre de répétion de l'opération choisi
- La taille de la structure
Dispositif expérimental
Plan de travail:
Tout d'abord, l'objectif sera de faire de simples comparaisons sur les temps d'exécutions (et ressources utilisées) des opérations entre deux implémentations de l'interface List. Nous prendrons ici les classes ArrayList et LinkedList et travaillerons en Java. Suite à cela, nous créerons notre propre implémentation de List, nottament une classe qui reprendra le concept de tableau. L'implémentation de l'interface List pour une classe utilisant un tableau peut, à première vue, sembler étrange, mais cela nous permettra de tester cette classe de la même manière que toutes les autres, et ce, de manière simplifiée.
Organisation objet
Description de l'organisation des classes et interfaces, ou diagramme de classes:
Application
L'application permet de faire des opérations sur different type de structure: Lorsqu'on lance l'application, on passe en paramètre:
- la taille de la structure (le nombre d'élément present par defaut dans la structure)
- le nom de la structure (array, ArrayList ou OurLinkedList (une liste chainée crée par nous même))
- le nombre de répétition
- l'action a effectuer (les actions sont get, inserthead, insertqueue, insertrandom, remove)
Note importante:
- remove supprime un élément au hasard dans la structure, si le nombre d'element à supprimer est suppérieur à la taille de la liste, on passe l'opération.
- get récupère un élément au hasard de la liste.Environnement de test
Description de la plateforme de test
La plateforme utilisé pour générer nos données est le bureau à distance (sous Unix)
Extrait pertinent de /proc/cpuinfo:
Nom de modèle : Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz
Vitesse du processeur en MHz : 1468.843
Vitesse maximale du processeur en MHz : 3100,0000
Cache L1d :32K
Cache L1i : 32K
Cache L2 : 256K
Cache L3 : 25600KDescription de la démarche systématique
Description de la démarche systématique et de l'espace d'exploration pour chaque paramètres:
Afin d'obtenir les données nécessaires à la génération des graphiques, il est nécessaire de generer un fichier de valeur (.csv), que l'on obtient en éxecutant un scrpit, prenant en paramètre simplement le nombre de répétitions des opérations
Script utilisé:
[ $# -eq 1 ] || { echo "Usage: $(basename $0) <amount of repetition>" 1>&2
exit 1
}
NTEST=50
size=10000
repetition=$1
echo -e "Test\tTaille\tRep\tType\tOpe\tCPU\tMem"
for structType in "array" "ourlinkedlist" "arraylist"
do
for structOp in "get" "remove" "inserthead" "insertrandom" "insertqueue"
do
for i in `seq $NTEST`
do
res=`(/usr/bin/time -f "%U\t%M" java -jar P4a.jar $size $structType $repetition $structOp > /dev/null) 2>&1`
echo -e "$i\t$size\t$repetition\t$structType\t$structOp\t$res"
repetition=$((repetition + 1000))
done
repetition=$1
done
doneRésultats préalables
Temps d'exécution
Consommation mémoire
Analyse des résultats préalables
Au niveau de la consomation de mémoire ainsi que du temps d'éxecution, on constate que plus le nombre d'opération augmente, plus le temps d'éxecution ainsi que la consomation mémoire augmente de facon expodentielle. On peut expliquer cela par le fait que nous avons fait le choix de recreer une array pour chaque élément ajouté / inséré. Par exemple, si l'on décide d'ajouter une valeur à un tableau de 50 élements, on va creer un tableau de 51 élément vide auquel on rajoute les 50 éléments du tableau précedent ainsi que la valeur souhaité. On constate également que le temps d'éxecution est fortement lié à la génération de nombre aléatoire. On observe une croissance logarithmique en fonction du nombre de répétition
//Extrait du code pour la fonction insertHead() de Array
int[] tempArray = array;
array = new int[size];
//Insertion des valeurs dans le nouveau tableau
array[0] = elem;
for(int i = 1; i < size; i++) {
array[i] = tempArray[i-1];
}En ce qui concerne les autres structures, on remarque que les insertions en tête pour la structure ArrayList sont plus lente que pour la structure linkedlist car une insertion dans une arraylist necessite de modifier l'index de chacun des éléments alors qu'une liste doublement chainée (dans notre cas) ne nécessite de modifier que 2 valeurs.
Discussion des résultats préalables
Explications précises et succinctes sur ce que les limites des résultats préalables et ce qu'ils ne permettent pas de vérifier. Une des limite concernant les resultats obtenu sur nos graphiques sont lié au type array: En effet, lors des insertions de valeurs, on ne parvient pas à déterminer réelement le temps écoulé / la consomation de mémoire pour effectuer l'action d'insertion, puisque cette opération nécessite la recréation du tableau, ainsi que son insertion.
Etude approfondie
Hypothèse
Expression précise et succincte d'une hypothèse.
Protocole expérimental de vérification de l'hypothèse
Expression précise et succincte du protocole.
Suite des commandes, ou script, à exécuter pour produire les données.