Mesurer les performances d’un programme

L’objectif premier de cet exercice est de savoir instrumenter un code source Java de sorte à pouvoir faire certaines mesures lors de l’exécution du programme :

Un autre objectif de ce TP est de s’initier à la complexité algorithmique, simplement en comptant les instructions arithmétiques et les accès mémoire des programmes analysés.

La mécanique : comment/pourquoi ?

Pour faire des mesures comme le temps de traitement et le nombre d’appels effectifs à une méthode, pour un programme en cours d’exécution, il existe plusieurs techniques et outils.

Note : Quel qu’il soit, un dispositif de mesure influe sur le système mesuré. Donc l’emploi d’outils de profilage a un impact sur l’exécution du programme.

Les profileurs sont des programmes capables d’intercepter les communications et appels du programme avec l’OS pour en retirer des informations de toutes sortes (nb d’appels, temps, utilisation mémoire fine : pile, tas, défauts de cache, …).

Dans le cas particulier de Java, le compilateur javac ne produit pas directement un programme exécutable, au contraire du C/C++ par exemple. L’exécution du programme en Java passe par une machine virtuelle (JVM) et ainsi les profileurs mesurent aussi les appels des fonctions de la JVM. Cela complique l’analyse des résultats.

Il existe toutefois des profileurs dédiés à Java, mais leur emploi est souvent trop complexe pour notre niveau d’expertise. Dans Idea, deux profileurs sont proposés par défaut : Java Flight Recorder et Async Profiler.

Sans profileur, on peut simplement instrumenter notre code en y insérant des instructions de mesure/comptage.

Toutefois, on veut modifier le moins possible le code à analyser ; ainsi l’insertion des outils ne compromettra pas ou peu la lisibilité et la remise en configuration de production.

La solution la plus simple pour analyser une méthode est de la passer en paramètre à une méthode profileuse qui pourra ainsi dissimuler les instructions d’analyse. Ainsi, si on imagine par exemple que, dans une classe A, on cherche à analyser une méthode 

double oneMethod(double x){...}

alors, au lieu de l’appeler classiquement par exemple avec 

double r = oneMethod(0.6);

on l’appellera, dans le cadre du profilage, par 

double r = Profiler.analyse(A::oneMethod, 0.6);

La class Main

Voici le fichier java que nous allons analyser. 


        

            Nous allons y analyser trois méthodes :
            

        



        
La class Profiler

        

            Voici le code de la classe Profiler à compléter.
        

        






        
Travail à faire

        

            1. Ajouter les instructions nécessaires à la méthode Profiler::analyse de sorte à pouvoir mesurer le temps d’exécution de la méthode max.
        

        

            2. Ajouter une définition adéquate de la méthode Profiler::analyse qui permettrait maintenant de pouvoir mesurer le temps consommé par la méthode badSort.
        

        
 Les grandeurs cumulées 

        

            Comme vous avez pu le constater, les temps d’exécution des méthodes sont très court et donc difficiles à mesurer précisément.
            Pour pallier ce problème, on va exécuter plusieurs fois la méthode à analyser et cumuler les temps d’exécution.
        

        

            3. Modifier la classe Profiler pour lui ajouter un attribut static long globalTime. Cet attribut sera affecté à chaque appel de la méthode d’analyse.
        

        

            4. Modifier la méthode Profiler::analyse pour qu’elle cumule le temps d’exécution de chaque appel dans l’attribut globalTime.
        

        

            5. Ajouter les méthodes Profiler::init et Profiler::getGlobalTime.
            

        

        

            6. Modifier le code de la méthode main pour mesurer le temps total d’exécution des méthodes max et badSort sur 1000 appels chacune.
        

        

            7. Inspirez-vous des étapes 3 à 6 pour ajouter un compteur d’appels aux méthodes analysées.
            Quel est l'intérêt de ce compteur ?
        



        
 Qui sera le plus rapide ? 

        

            8. Implémenter la méthode fastSort dans la classe Main en utilisant un algorithme plus efficace que le tri à bulles.
            Mesurez son temps d’exécution sur 1000 appels et comparez-le avec celui de badSort.
        


        
 Analyse de complexité 

        

            9. Calculer la durée d'exécution de la méthode max pour différentes tailles de liste (par exemple, 1000, 2000, 4000, 8000, etc.) et 
            entrez ces données dans un tableau. Tracez un graphe de la durée d'exécution en fonction de la taille de la liste.
        

        

            10. Faire de même pour les méthodes badSort et fastSort.
            Que constatez-vous ?
        

        

            11. Réaliser la méthode de tri la plus rapide possible ! Comparez votre implémentation avec Collections.sort de la bibliothèque standard Java.