P4z : Analyse de performances de différents tris

• Grille d'évaluation P4z
• Grille de pré-évaluation

Problème

Il existe des dizaines d'algorithme de tri et aucun n'est pour l'instant "le meilleur".
Ils ont tous des caractéristiques propres, et des cas d'utilisation bien précis.

Nous analysons ici un ensemble de paramètres (variables exploratoires) pour déterminer ces cas d'usages et caractéristiques.

Les variables exploratoires que nous possédons sont les suivantes :

• Temps
• Consommation mémoire
• Nombre d'itérations
• Nombre de copies de variable
• Nombre de comparaisons entre entier
• Nombre de calculs effectués (+,-,...)
• Nombre d'instanciations de variables
• Nombre d'instanciations de tableaux
• Nombre d'initialisation de variables (a = 5, b ='a'...)

Le temps et la consommation mémoire sont évalués en dehors du programme (via /bin/time)
Les autres variables sont récupérées par le programme lui même pendant son exécution à condition
d'avoir été compilé avec le flag DEBUG. La classe complexityTest se charge de récupérer ses variables dans les algorithmes et de les afficher.

Pour afficher ces variables exploratoires, il faut lancer le programme en mode "perfplot", voir section "Application".

Dispositif expérimental

Application

Code source de l'application

Usage: ./main {mode} [maxTabSize, maxValTab, algo, iterations, tab_type]

L'executable possède deux {modes}, perfplot et autotest.  
Si on lance en "autotest", aucun autre paramètre n'est nécessaire. Le programme va démarrer une série de tests automatiques (aléatoires et prédéfinis pour tester les 'edge-cases') sur l'intégralité des algorithmes implémentés. Il retourne dans la sortie standard un ensemble d'informations de debug au cours de la réalisation des tests.

Le deuxième mode est le mode "perfplot".
Ce mode permet d'obtenir (si l'application a été compilée avec le flag DEBUG) un ensemble d'information sur les tâches réalisées par les algorithmes (nombre d'itérations, nombre de variables instanciées, nombre de valeurs copiées) sous forme normalisée pour les analyser avec un outil comme R.

Ce mode analyse un algorithme en particulier, passé en paramètre par "algo", avec un entier qui désigne le numéro de l'algorithme dans le code.

"maxTabSize" et "maxValTab" permettent de définir la taille des tableaux passés en entrée de l'algorithme, mais aussi la valeur maximale des valeurs aléatoires générées dans ces tableaux.

"iterations" permet de définir combien de fois l'algorithme doit se lancer. En général on y passe 1 pour mesurer de manière extérieure (par exemple via /bin/time) le temps d'execution de l'algorithme.

"tab_type" est un caractère définit dans la nomenclature de la section "Résultats préalables". Ce paramètre permet de choisir quel type de jeu de donnée va être mis en entrée de notre algorithme (tableau trié, trié inverse, aléatoire..)

Environnement de test

Architecture :                          x86_64
Mode(s) opératoire(s) des processeurs : 32-bit, 64-bit
Processeur(s) :                         32
Nom de modèle :                         Intel(R) Xeon(R) CPU E5-2630L v3 @ 1.80GHz
Vitesse du processeur en MHz :          1198.575
Vitesse maximale du processeur en MHz : 2900,0000
Vitesse minimale du processeur en MHz : 1200,0000
Cache L1d :                             32K
Cache L1i :                             32K
Cache L2 :                              256K
Cache L3 :                              20480K

Le processeur en question possède de nombreux coeurs (parfait pour le parallélisme, mais pas utilisé dans notre cas).
La fréquence est relativement bonne et permet donc normalement de réaliser nos tris rapidement.

Le processeur possède beaucoup de cache, essentiel pour éviter les "cache miss" qui peuvent ralentir le tri en raison du besoin d'aller chercher des valeurs à trier en RAM.

Description de la démarche systématique

Pour réaliser les graphes de l'utilisation de la mémoire et du temps de calcul d'un algorithme,
il suffit de lancer le script pipeline.sh avec le numéro de l'algorithme à analyser en paramètre.
La correspondance numéro/algorithme est écrite dans le script.

#  0 INSERTION;  1 FUSION;  2 RAPIDE; 4 TRI PAR TAS

Le script réalise les deux graphes pour l'algorithme avec 4 courbes par graphe.
Ces courbes décrivent les jeux de données utilisés (aléatoire, trié, trié inversé, unique...) On peut ainsi observer comment ce comporte l'algorithme suivant les données en entrée.

Ces graphes sont générés avec des tableaux de plusieurs milliers de valeurs, ce qui peut prendre du temps
sur certains algorithmes (insertion).

Résultats préalables

Nomenclature

Les courbes présentées pour chaque algorithme de tri sont aux nombres de quatres.
On teste le temps d'éxecution/consommation mémoire avec des tableaux de valeur en entrée différents (jeux de données).
Les tableaux aléatoires sont remplis avec des valeurs aléatoires.
Les tableaux ordonnés croissants sont déjà triés par ordre croissant (les algorithmes n'ont théoriquement donc rien à faire).
Les tableaux ordonnés décroissants sont triés mais à l'envers, l'algorithme doit donc retourner le tableau. Les tableaux à valeur uniques sont remplis avec la même valeur de bout en bout (ex: [5,5,5,5,...,5]).

Le tableau ci-dessous donne les noms des jeux de données dans les graphiques générés par R

Temps d'exécution

Tri par Insertion	Tri Fusion	Tri Rapide	Tri par tas

Consommation mémoire

Tri par Insertion	Tri Fusion	Tri Rapide	Tri par tas

Analyse des résultats préalables

Tri par insertion

Il est évident que le tri par insertion est peu efficace. Son temps d'exécution explose rapidement et
générer des résultats pour cet algorithme est rapidement lassant en raison du temps pris.

L'avantage de cet algorithme est que les données déjà triées ou une répétition de X fois la même valeur
dans le tableau en entrée est instantanément considérée comme trié.

On observe par contre des mauvaises performances sur les données aléatoires et encore plus sur les données triées en ordre inverse.
L'usage mémoire est fonction de la taille des données en entrée, et ceci même si elles sont déjà classées.
Pour faire simple, l'algorithme consomme de la mémoire même quand il n'y a techniquement rien à faire pour trier.
L'usage est cependant ératique et ne semble pas suivre une droite bien dessinée.

Tri par fusion

L'algorithme semble réagir de manière semblable que les données en entrée soient triées/triées inverses/uniques. Il n'est donc pas forcément adapté pour des valeurs de ce type, même si son déroulement prend toujours moins de 0.5s
même sur des tableaux de plus de 1 million de valeurs, la ou le tri par insertion prendrait des heures.

C'est un algorithme très rapide sur les valeurs aléatoires en comparaison aux autres, et la consommation temps est linéaire. Cet algorithme semble donc polyvalent.

La consommation mémoire est linéaire et fonction de la taille des données en entrée, et ce quelque soit le jeu de données.
Il est donc facile de prédire combien de mémoire le programme va consommer. EN revanche cet algorithme consomme énormément
de mémoire et entraine rapidement un crash pour cette raison si le tableau en entrée est trop grand.

Tri rapide

Cet algorithme est visiblement lent sur les données triées/triées inverse/uniques mais rapide sur les données aléatoires,
qui est le type de donnée le plus "réaliste".

Sur les jeux de données non-aléatoires, l'algorithme ralentit très rapidement avec un temps d'exécution >5s pour un tableau
de seulement 50 000 éléments.

Il faut donc éviter d'utiliser cet algorithme sur des données qui pourraient être déjà structurées, au risque de voir le temps exploser.

En terme de consommation mémoire on notera que contrairement aux deux autres algorithmes, si on réalise peu d'opérations
pour trier un tableau, on utilise aussi peu de mémoire. Plus la complexité de résolution est haute, plus l'utilisation mémoire est
haute et inversement. L'augmentation de la taille des données en entrée semble aussi jouer sur la quantité de mémoire utilisée.

L'usage mémoire de cet algorithme est donc fonction du nombre d'opérations effectuées pour trier le tableau, contrairement aux autres
qui étaient fonction de la taille de l'entrée.

Tri par tas

L'algorithme de tris par tas est rapide sur la plus part des jeux de données. On remarque que les tableaux avec des valeurs
triées ou aléatoires sont les plus lents à traiter, avec des temps de calcul quasiment égaux.

Les valeurs uniques sont les plus rapides à trier, suivis de près par les valeurs triées de manière décroissantes. Cet algorithme présente donc des comportements bien différents suivant le jeu de données en entrée.

Il est intéressant de voir que la mémoire utilisée par l'algorithme est tout à fait linéaire et ne dépend que
du volume de données en entrée. Peut-importe le jeu de données en entrée, on sait exactement combien de mémoire va consommer
notre processus en fonction de la taille du tableau à trier.

Ce comportement est causé par le fait que l'algorithme effectue toutes ses permutations dans le tableau à trier lui même (In-place algorithm),
sans instancier d'autres tableaux ou variables qui allourdiraient l'usage mémoire.

Cette particularité permet à l'algorithme de traiter plus de données que les autres que nous avons implémenté avant de faire planter
le programme en raison d'un manque de mémoire.

Discussion des résultats préalables

Notre étude présente des limites :

• On réalise l'étude sur 4 jeux de données différents, il existe un nombre illimité de jeux particuliers (taille qui est un nombre premier et valeurs décroissantes..)
  et nous ne testons pas sur ces jeux. Il se peut que un tri polyvalent comme fusion ne l'est en réalité pas du tout sur certains jeux spécifiques.

• Le tri fusion ne peut pas être testé (en l'état) sur des tableaux avec une taille supérieure à ~2,500,000 valeurs. En effet cet algorithme
  utilise beaucoup de mémoire et les tableaux trop grands le font crash. Il faudrait optimiser l'algorithme pour utiliser des allocations dynamiques au lieu
  d'utiliser la pile qui possède une taille limitée. On peut quand même imaginer la courbe au dela de ces tailles de tableau, elle semble en effet linéaire.

• Nos tests sont dépendants d'une plateforme précise. Pour être rigoureux il faudrait refaire tous nos tests (avec les mêmes valeurs dans les tableaux) sur des machines
  différentes. Il se peut que des programmes qui tournent sur le serveur, des configurations ou limitations (cgroup...) entrainent des ralentissements.

• Avec les mesures/temps mémoires on ne voit pas l'effort réel fournit par l'algorithme. Un algorithme qui prend du temps ne réalise pas forcément énormément de calculs.
  Il se peut qu'il attendre pour des entrées/sorties entre le cache/RAM en raison d'une faible optimisation.

Etude approfondie

Hypothèse

On constate sur les graphiques précédents un problème avec le quicksort (tri rapide). Il n'est pas du tout rapide sur les tableaux classés
par ordre croissant (triés), et sur les tableaux triés à l'envers. Le même phénomène est visible sur les tableaux remplis avec la même valeur.

En étudiant nos résultats, nous nous sommes rendus compte que ces jeux de données entrainaient une explosion du nombre
d'instanciation de variable, de copies et de comparaisons.

Note hypothèse est donc que ces accès mémoires abusifs sont la source des problèmes de l'algorithme.
Notre but va donc être d'analyser des résultats, de les confronter au code et d'évaluer des possibles solutions.

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

On effectue au début une mesure repère du temps et de la mémoire utilisée en utilisant le pipeline.sh dans le dossier TP2/rapideApprofondi/. Il génère les graphes qui correspondent.

Pour les autres variables exploratoires (itérations, copies, instanciations de variables), il faut utiliser le script pipelineExploration.sh. On peut ensuite modifier plotExplo.r pour afficher les variables que l'on veut.

La procédure que nous avons suivis est la suivante :

A chaque modification de code, on recompile et on test avec nos autotests pour vérifier que nos améliorations n'aient pas cassé le trie : make && ./main autotest

Si le tri fonctionne, on lance ./pipelineExploration.sh pour obtenir les variables exploratoires qui nous intéressent et observer des changements.

On lance ensuite ./pipeline.sh pour voir le temps et la mémoire utilisée.

Les .png sont ensuite classés :

• dans le dossier after pour les données obtenues après modification
• dans le dossier before pour les données avant modification

Résultats expérimentaux

Voici les graphes du temps/mémoire utilisé par notre algorithme de tri rapide avant toute optimisation :

Temps d'exécution	Mémoire utilisée

On prendra ces graphes comme référence pour déterminer si on améliore ou non notre algorithme au fil des essais.

En étudiant nos variables exploratoires on notes des taux élevés de copies et d'instanciations de variables :

Copies	Instanciations de variables

125 millions de copies pour les valeurs uniques. On ne sait pas à ce moment la ce qui cause le problème,
mais on identifie très vite en regardant le code exactement ou il se manifeste :

long tmp = array[i];
array[i] = array[j];
array[j] = tmp;

Ce bout de code effectue l'inversion de deux espaces dans la mémoire. La mémoire cache d'un CPU
est assez optimisée pour faire rapidement ces inversions, mais pour des valeurs uniques, on va réaliser
cette opération inutile (inverser 1 et 1 ? 2 et 2 ?) autant de fois qu'il y a de valeurs n'est pas nécessaire.

On va donc remplacer ces couteuses opérations mémoires (1 instanciation de variable + 3 copies) par une comparaison. Si les valeurs sont identiques, on ne réalise pas la permutation.

Voici le résultat sur les copies et instanciations après le changement dans le code :

Copies	Instanciations de variables

L'amélioration est significative: 50 000 copies au maximum pour les valeurs uniques contre 125 millions ! C'est 2500x moins d'opérations inutiles.

Etonnement, une amélioration énorme s'est aussi faite sur les autres jeux de données (trié/trié inverse). A ce stade, nous ne comprenons
pas réellement la source de cette amélioration. Probablement du à la manière de découper les données dans la fonction de partition.

Comment cela s'est-il répercuté sur le temps et la mémoire ?

Temps d'exécution	Mémoire utilisée

On perd une grosse seconde de temps d'exécution sur nos jeux de données ormis pour le jeu aléatoire qui ne bouge pas. C'est déjà une amélioration conséquente qui augmente la polyvalence de l'algorithme.

La mémoire ne bouge cependant pas, ce qui semble étonnant. On s'attend à ce que le fait de ne pas allouer de variable temporaire baisse l'utilisation. Cette variable est probablement optimisée (par le compilateur ?), ou n'est simplement pas décomptée par bin/time qui n'analyserait alors que la consommation RAM (ce qui ferait sens).

On trouve par la suite un autre endroit dans le code ou une permutation est aussi effectuée. On essai alors d'appliquer notre optimisation encore une fois.

Voila les résultats obtenus ensuite sur les copies et les instanciations de variable :

Copies	Instanciations de variables

On constate que aucune amélioration n'est faite sur les données aléatoires. En revanche on perd en copie et en instanciation sur les autres jeux. L'effet est moindre que celui de toute à l'heure, mais présent.
On constate cependant que les données aléatoires ne tracent plus des droites. Il y a donc eu un léger effet.

Un autre constat est que les droites des jeux de données uniques/triés/triés inverses se sont "découplés". Ils suivaient jusqu'ici la même droite et se superposaient parfaitement. Il semblerait que seul les valeurs uniques et croissantes se superposent maintenant.

Voyons maintenant si un effet est ressentit sur le temps d'exécution et l'utilisation mémoire :

Temps d'exécution	Mémoire utilisée

On augmente le temps d'exécution de quelques centième de seconde. Cette optimisation n'en est donc pas une du tout. Le nombre de comparaisons rajoutées pèse plus dans la balance que le nombre de permutations évitées. On décide de faire machine arrière.

On s'intéresse donc au reste du code pour essayer de comprendre d'ou viens la différence de temps d'exécution entre les jeux de données.

Il est évident que le pivot joue énormément sur le nombre d'itérations que fait notre algorithme. Si on imagine un tableau trié, et que l'on continue comme maintenant à prendre le dernier élément comme pivot, notre algorithme va partionner en boucle l'ensemble de notre tableau en enlevant la dernière valeur. Prendre la valeur du millieu de notre tableau passé en entrée peut probablement aider ici.

Mais on peut risquer si les tableaux sont partiellement triés de commettre la même erreur. Pour ne pas se poser trop de questions on va utiliser un pivot au hasard.

Voici le nombre d'itérations avant qu'on touche au pivot :

On met maintenant le pivot aléatoire et voici le résultat :

Les jeux de données triés à l'envers ou à l'endroit font bien moins d'itérations !

Voici les résultats en terme de temps :

Temps d'exécution

On constate que seul le jeu de donnée remplit des mêmes valeurs n'a pas bénéficié de cette amélioration. On gagne de nombreuses secondes sur les autres jeux.

Analyse des résultats expérimentaux

On constate clairement des expériences ci-dessus deux choses :

Réduire les transferts dans la mémoire (ici d'un facteur 25000) réduit pour beaucoup le temps que met l'algorithme à se dérouler. Il ne faut donc pas négligler l'usage de la mémoire sur des algorithmes qui traitent des milliers de valeur.

Réduire le nombre d'itérations et donc de cycles sur le CPU permet également de gagner immensément de temps. D'après nos graphes, la majeure partie du temps consommé est lié à de l'activité CPU, en effet on perd quasiment 3 secondes au maximum avec la technique du pivot, mais seulement 1 en améliorant l'utilisation de la mémoire.

Discussion des résultats expérimentaux

On constate clairement que plus l'algorithme "travail", c'est à dire plus il prend de temps et passe d'itérations sur le CPU, plus l'usage mémoire augmente. Cependant nos graphes ne mettent probablement pas en valeur l'utilisation du cache.

Conclusion et travaux futurs

Cette étude n'analyse pas tous les paramètres possibles et une amélioration future pourrait être d'utiliser plus de jeux de de données, dont des jeux "mixtes", comme des tableaux semi-ordonnées dans l'ordre croissant, décroissants ou même les deux (une moitié croissante et une décroissante) pour explorer comment se comporte l'algorithme dans ces cas la.

Il faudrait également augmenter la taille des échantillions et générer des tableaux encore plus grand avec plus de points de données pour s'assurer que le comportement du tri ne change pas.