Profiling d'un projet c
Bonjour,
comme à chaque fois que j'ai eu un problème il a été réglé en deux coups de cuillère à pot grace à vos réponses, je me tourne une nouvelle fois vers vous
en effet, j'ai fait le profiling d'un code c avec gprof mais malheureusement le resultat n'est pas trés précis
(la plupart des fonctions ont un temps d'éxecution égale à zéro)
donc SVP s'il y a d' autres solutions pour faire le profiling essayer de m'informer
merci d'avance
comme à chaque fois que j'ai eu un problème il a été réglé en deux coups de cuillère à pot grace à vos réponses, je me tourne une nouvelle fois vers vous
en effet, j'ai fait le profiling d'un code c avec gprof mais malheureusement le resultat n'est pas trés précis
(la plupart des fonctions ont un temps d'éxecution égale à zéro)
donc SVP s'il y a d' autres solutions pour faire le profiling essayer de m'informer
merci d'avance
A voir également:
- Profiling d'un projet c
- Filigrane projet - Guide
- Gant projet - Télécharger - Gestion de projets
- Musique projet x - Forum Musique / Radio / Clip
- Comment projeter une image sur un mur - Forum TV & Vidéo
- J'aimerais projeter une image sur un mur - Forum TV & Vidéo
1 réponse
Bah en fait tout dépend de ce que tu cherches à faire. Ce que doit faire le programme dans l'état actuel doit être tellement simple qu'il ne semble pas y avoir grand chose à mesurer :-)
La complexité c'est quoi ?
De manière générale si tu veux générer un code performant, celui-ci doit avoir une complexité (au sens théorie de la complexité) aussi faible que possible. Supposons que je veuille stocker un ensemble de chiffre et tester si une valeur appartient à cet ensemble.
https://fr.wikipedia.org/wiki/Th%C3%A9orie_de_la_complexit%C3%A9_des_algorithmes#Complexit.C3.A9_en_temps_et_en_espace
Approche 1 : avec une std::list ou une liste chaînée
Je mets à la suite un nombre ajouté à la fin de la liste. Si je ne vérifie pas si la donnée est déjà présente dans la liste et que j'ai un pointeur sur la fin de la liste, l'insertion est faite sans "parcours". Dans ce cas la complexité est O(1).
Cependant je peux avoir des doublons (d'où une surcharge inutile en mémoire). Pas terrible si j'insère 20000 fois la même valeur dans cet ensemble. Si je veux ne pas mettre de doublon, je dois parcourir une liste de n éléments, la complexité passe alors à O(n) (le temps d'exécution pour insérer une valeur dans l'ensemble croit linéairement avec la taille de la liste).
Pour vérifier si une valeur est présente dans la liste, dans le pire cas je dois parcourir toute la liste ce qui donne encore du O(n). Avec un peu de chance je la croiserai avant la fin de la boucle (ce qui me permettra de faire un break) mais ça reste du O(n).
En C++, on utilise en général une std::list pour éviter de recoder une liste chaînée. Pour répondre à ce problème, on s'aperçoit que ce container s'avère peu adéquat.
Approche 2 : avec un std::set ou une structure d'arbre rouge noir
En C++, la STL fournit une classe (std::set) qui permet de stocker des éléments de manière unique et ordonnée. En interne, cette structure utilise un arbre rouge noir qui permet d'insérer ou de retrouver une donnée très rapidement (en O(log(n)).
https://fr.wikipedia.org/wiki/Arbre_bicolore
Si tu te rappelles de tes cours de maths, tu te souviens probablement que la fonction f(x) = x croit beaucoup plus rapidement que g(x) = log(x). Et bien là, c'est exactement la même chose. Ainsi en quelques itérations tu peux traiter efficacement un gros "ensemble". On va illustrer tout ça, parce que les maths c'est bien gentil, mais ça donne mal à la tête :p
Le principe est très simple. Imagine que je te dise "essaye de deviner le nombre auquel je pense" sachant qu'il est compris entre 1 et 100. Supposons que je pense à 23. Voilà ce qui se passerait :
tu dis 50
je dis -
tu dis 25
je dis -
tu dis 0
je dis +
tu dis 12
je dis +
tu dis 19
je dis +
tu dis 22
je dis +
tu dis 24
je dis -
tu dis 23
gagné
Un arbre rouge noir fonctionne exactement de la même façon. À chaque itération l'espace de recherche est divisé par deux (ce qui se traduit par un "log" en terme de complexité). Comme tu le vois en une dizaine d'itérations, sur un espace de 100 éléments tu as trouvé la réponse (contre 50 en moyenne pour une liste de même taille !). Plus l'ensemble est grand, plus cette différence s'accentue.
Ainsi cette approche est très nettement plus performante que la première. Sur une petite instance (ce qui semble être ton cas), un code mal architecture (avec une mauvaise complexité) donnera des performances sans doute voisine. Par contre dès que l'instance est plus grande c'est déterminant.
Approche 3 : les masques
Supposons que notre ensemble soit borné (ou mappable) avec par exemple 32 valeurs possibles. On peut alors utiliser un masque de bits, ce qui est encore plus performant qu'un std::set. On utilise un bloc mémoire de 32 bits (par exemple un int) où le ième bit vaut 1 si et seulement si la valeur i est dans l'ensemble.
En utilisant stratégiquement les opérateurs << et & en C/C++ on peut alors déterminer immédiatement si une valeur figure ou non dans l'ensemble (complexité O(1)). Mais contrairement au std::set on a fait une hypothèse supplémentaire. C'est donc mieux de suivre cette approche... mais ce n'est pas toujours possible !
Une implémentation équivalente (mais moins performante) consisterait à utiliser un vecteur de 32 bool (type du C++) ou par exemple 32 char en C.
Pourquoi tout ce speech ?
Si tu as bien tout suivi, le profiling ne sert qu'à une chose : si le code est peu performant, on voit à quel endroit il est lent, et c'est probablement dû à un code mal architecturé ou mal conçu (sous entendu avec une mauvaise complexité) qui engendre de mauvaises performances. Si l'instance est petite, ceci sera imperceptible et le profiling ne permettra pas de détecter ce genre de sections de code.
Tu l'auras également compris, ces considérations sont indépendantes du langage de programmation. Même si un compilateur sait faire quelques optimisations, il ne pourra pas faire de miracle si le code est mal conçu.
La notion de complexité est bien plus général qu'à la manière dont tu stockes tes données, elle se retrouve quand tu écris un algorithme (par exemple calculer un plus court chemin entre tel endroit et tel endroit...). À mon avis tout mon développeur doit être conscient de cette notion pour aligner de vraies lignes de code, le profiling ne sert qu'à détecter des défauts de conception.
Bonne chance
La complexité c'est quoi ?
De manière générale si tu veux générer un code performant, celui-ci doit avoir une complexité (au sens théorie de la complexité) aussi faible que possible. Supposons que je veuille stocker un ensemble de chiffre et tester si une valeur appartient à cet ensemble.
https://fr.wikipedia.org/wiki/Th%C3%A9orie_de_la_complexit%C3%A9_des_algorithmes#Complexit.C3.A9_en_temps_et_en_espace
Approche 1 : avec une std::list ou une liste chaînée
Je mets à la suite un nombre ajouté à la fin de la liste. Si je ne vérifie pas si la donnée est déjà présente dans la liste et que j'ai un pointeur sur la fin de la liste, l'insertion est faite sans "parcours". Dans ce cas la complexité est O(1).
Cependant je peux avoir des doublons (d'où une surcharge inutile en mémoire). Pas terrible si j'insère 20000 fois la même valeur dans cet ensemble. Si je veux ne pas mettre de doublon, je dois parcourir une liste de n éléments, la complexité passe alors à O(n) (le temps d'exécution pour insérer une valeur dans l'ensemble croit linéairement avec la taille de la liste).
Pour vérifier si une valeur est présente dans la liste, dans le pire cas je dois parcourir toute la liste ce qui donne encore du O(n). Avec un peu de chance je la croiserai avant la fin de la boucle (ce qui me permettra de faire un break) mais ça reste du O(n).
En C++, on utilise en général une std::list pour éviter de recoder une liste chaînée. Pour répondre à ce problème, on s'aperçoit que ce container s'avère peu adéquat.
Approche 2 : avec un std::set ou une structure d'arbre rouge noir
En C++, la STL fournit une classe (std::set) qui permet de stocker des éléments de manière unique et ordonnée. En interne, cette structure utilise un arbre rouge noir qui permet d'insérer ou de retrouver une donnée très rapidement (en O(log(n)).
https://fr.wikipedia.org/wiki/Arbre_bicolore
Si tu te rappelles de tes cours de maths, tu te souviens probablement que la fonction f(x) = x croit beaucoup plus rapidement que g(x) = log(x). Et bien là, c'est exactement la même chose. Ainsi en quelques itérations tu peux traiter efficacement un gros "ensemble". On va illustrer tout ça, parce que les maths c'est bien gentil, mais ça donne mal à la tête :p
Le principe est très simple. Imagine que je te dise "essaye de deviner le nombre auquel je pense" sachant qu'il est compris entre 1 et 100. Supposons que je pense à 23. Voilà ce qui se passerait :
tu dis 50
je dis -
tu dis 25
je dis -
tu dis 0
je dis +
tu dis 12
je dis +
tu dis 19
je dis +
tu dis 22
je dis +
tu dis 24
je dis -
tu dis 23
gagné
Un arbre rouge noir fonctionne exactement de la même façon. À chaque itération l'espace de recherche est divisé par deux (ce qui se traduit par un "log" en terme de complexité). Comme tu le vois en une dizaine d'itérations, sur un espace de 100 éléments tu as trouvé la réponse (contre 50 en moyenne pour une liste de même taille !). Plus l'ensemble est grand, plus cette différence s'accentue.
Ainsi cette approche est très nettement plus performante que la première. Sur une petite instance (ce qui semble être ton cas), un code mal architecture (avec une mauvaise complexité) donnera des performances sans doute voisine. Par contre dès que l'instance est plus grande c'est déterminant.
Approche 3 : les masques
Supposons que notre ensemble soit borné (ou mappable) avec par exemple 32 valeurs possibles. On peut alors utiliser un masque de bits, ce qui est encore plus performant qu'un std::set. On utilise un bloc mémoire de 32 bits (par exemple un int) où le ième bit vaut 1 si et seulement si la valeur i est dans l'ensemble.
En utilisant stratégiquement les opérateurs << et & en C/C++ on peut alors déterminer immédiatement si une valeur figure ou non dans l'ensemble (complexité O(1)). Mais contrairement au std::set on a fait une hypothèse supplémentaire. C'est donc mieux de suivre cette approche... mais ce n'est pas toujours possible !
Une implémentation équivalente (mais moins performante) consisterait à utiliser un vecteur de 32 bool (type du C++) ou par exemple 32 char en C.
Pourquoi tout ce speech ?
Si tu as bien tout suivi, le profiling ne sert qu'à une chose : si le code est peu performant, on voit à quel endroit il est lent, et c'est probablement dû à un code mal architecturé ou mal conçu (sous entendu avec une mauvaise complexité) qui engendre de mauvaises performances. Si l'instance est petite, ceci sera imperceptible et le profiling ne permettra pas de détecter ce genre de sections de code.
Tu l'auras également compris, ces considérations sont indépendantes du langage de programmation. Même si un compilateur sait faire quelques optimisations, il ne pourra pas faire de miracle si le code est mal conçu.
La notion de complexité est bien plus général qu'à la manière dont tu stockes tes données, elle se retrouve quand tu écris un algorithme (par exemple calculer un plus court chemin entre tel endroit et tel endroit...). À mon avis tout mon développeur doit être conscient de cette notion pour aligner de vraies lignes de code, le profiling ne sert qu'à détecter des défauts de conception.
Bonne chance