Forum Programmation.c++ Mesurer le temps d'exécution d'un fragment de code

Posté par  .
Étiquettes : aucune
0
19
juin
2008
Slt les gars,

voila j'ai développé un programme en C++ sous Linux (gcc)

Ça fait un petit moment que je traine sur le Web à la recherche d'une fonction qui me permettrait de calculer le temps exact d'exécution (le plus exacte possible) d'un bout de code (pas un programme en entier).

J’ai commencé avec la fonction clock(), mais elle avait une granularité trop importante (de l'ordre de la seconde) j'ai donc décidé de chercher autre chose.

Je me suis donc rabattu sur gettimeofday. Elle donne une précision assez acceptable. Le problème est que ce type de fonction donne des mesures assez biaisées. Je m'explique. gettimeofday est utilisé afin de récurer un instant de début et un instant de fin. La différence entre les deux me donne théoriquement le temps d'exécution. Le problème est que ce temps d'exécution n'est vrai que dans le cas où un seul et unique processus s'exécute sur la machine. Ce qui n'est pas le cas. Les lauses de temps ou le sheduleur à fait tourné d'autre programme sont inclus dans la mesure. Ce qui ne m'arrange pas du tout. Ceci me donne des fluctuations de l'ordre de 3 à 10 millisecondes. Ce qui est inacceptable pour moi (même en marchant avec le minimum de processus). Je ne sais pas s’il est possible de faire en sorte qu'un fragment de code ne soit pas arrêté par le shiduleur tant qu'il n'a pas été complètement exécuté. Une sorte de bloc atomique.

Sinon peut être qu'une bibliothèque existe et qui m'a échappé !!!

Je me tourne donc vers vous (mon ultime espoir).

Le problème peut se résumer ainsi.

Peut-on obtenir le temps d'exécution d'un fragment de code uniquement lorsque ce dernier est au niveau du processeur ou le nombre de cycles processeur qu'il a consommé ?

Merci d'avance.
  • # TSC

    Posté par  (site Web personnel) . Évalué à 2.

    Sur x86 tu peux utiliser le timestamp counter (le fameux registre TSC et son instruction rdtsc) pour connaître le nombre de cycles CPU depuis son démarrage. Il faut se faire des petites fonctions autour de cette opération pour avoir un merveilleux compteur.

    Pour du code, on peut se reporter à http://www.fftw.org/cycle.h

    2 défauts :
    - sur des systèmes SMP, les différents CPU peuvent avoir des TSC avec des valeurs relativement différentes
    - Avec des processeurs qui changent de fréquence dynamiquement, il est pas immédiat de déduire du nombre du cycles un temps.

    J'avais trouvé un pdf vraiment intéressant avec des considérations sur l'utilisation du registre TSC pour les mesures de performances : http://www.cs.toronto.edu/~demke/469F.06/Lectures/Lecture5.p(...)
    • [^] # Re: TSC

      Posté par  (site Web personnel) . Évalué à 2.

      Je viens de retrouver du code que j'avais fait il y a quelques mois.

      #ifdef ARCH_X86_64
      static inline guint64 counter_read_time(void)
      {
      guint64 a, d;
      __asm__ __volatile__ (
      "rdtsc\n\t"
      : "=a" (a), "=d" (d)
      );
      return (d << 32) | (a & 0xffffffff);
      }
      #elif ARCH_X86
      static inline guint64 counter_read_time(void)
      {
      guint64 l;
      __asm__ __volatile__ (
      "rdtsc\n\t"
      : "=A" (l)
      );
      return l;
      }
      #endif

      static inline guint64 counter_elapsed(guint64 t0, guint64 t1)
      {
      return t1 - t0;
      }


      et ça s'utilise avec :

      guint64 start, end, cycles_nb;
      start = counter_read_time();
      {
      /* code à mesurer */
      }
      end = counter_read_time();
      cycles_nb = counter_elapsed(start, end);
  • # times(2)/getrusage(2)

    Posté par  . Évalué à 5.

    Les appels systèmes times ou getrusage permettent d'obtenir le temps CPU consommé par le process appelant et/ou ses descendants.
    man times ou man getrusage pour plus de détails.

    PS: C'est "scheduler", pas "sheduleur" ou "shiduleur" (et "ordonnanceur" ou "planificateur" en français)
  • # gprof

    Posté par  . Évalué à 3.

    Ca me laisse perplexe ta recherche. Pourquoi mesurer le temps soi-disant exact de ta fonction si elle est généralement exécutée en plusieurs fois ? Tu seras bien avancé de savoir qu'elle met théoriquement 3ms alors que dans la vraie vie elle mets, justement, entre 3ms et 10ms.
    Si tu veux t'amuser à mesurer quelque chose qui n'existe pas, alors tu ne peux pas le mesurer directement.

    Si il existe un outil tout à fait standard:
    --> man gprof
  • # Une solution à l'ancienne (en assembleur)

    Posté par  . Évalué à 1.

    D'abord merci pour vos réponses rapides.

    Pour réponde à ta question Kerro, j'ai en fait besoin de faire quelques mesures expérimentales pour des recherches scientifiques dans le domaine des bases de données.

    Le principe de cette expérience et de mesurer le temps d'exécution d'une requête (floue) avec et sans index sur certain champs d'une table.

    En utilisant times et getrusage je me retrouve avec des résultats qui me disent qu'une requête sur une base de données sans index sur les champs intérogés est relativement (de quelque milliseconde) meilleure qu'une base de données (la même) sans index. Ce qui est aberrant. L’intérêt des index est bien d'accélérer le temps d'exécution et non le ralenti.

    Je ne demande pas le temps d'exécution exacte (à la nanoseconde près), mais des temps qui ne défient pas le bon sens.

    getrusage me semble intéressante, mais ne renvoie que le temps d'exécution que du programme au complet et non d'un fragment comme j'ai besoin.

    comme il l'a si bien résumé le document que Damien nous a déniché (page 5)

    Temps d'exécution d'un programme = temps d'exec des appels système + temps d'exec des appels utilisateurs + autres.

    Sachant que autres représente le temps où d'autres processus sont exécuter autres que celui qui nous intéresse. J’ai bien essayé getrusage avant est après le bout de code qui m'intéresse dans l'espoir en faisant la soustraction d'avoir ce que je voulais, mais sa ne marchais pas. Il me donne les mêmes valeurs comme si le bout de code que j'avais entre les deux ne consommait rien du tout. Ce qui n'est pas le cas.

    Je suis tombé il y'a de sa quelque instant sur un article de chez ces messieurs de Intel(http://softwarecommunity.intel.com/articles/eng/2589.htm). Je pense qu'il apporte beaucoup d'explications sur des zones d'ombres. D'après ces messieurs de chez Intel, une mesure du temps d'exécution basée sur l'horloge système possède une précision de l'ordre de +/-10 ms~ dans la meilleure des cas. « The system timer can be used to measure events with an accuracy of 10 ms. » ; la fonction time() sous C possède une précision de l'ordre de -/+1 s ; les fonctions en rapport avec le temps qui existe dans les bibliothèques pour le traitement multimédia (ils parlent de la fonction timeGetTime qui existe sous Windows Plus exactement) de l'ordre de +-/10 ms.

    En s'appuyant sur les cycles du processeur grâce à l'instruction Read Time Stamp Counter (RDTSC) pour les processeurs Intel (je pense qu'il existe aussi qlq chose de similaires sous les processeurs AMD) on peut atteindre une précision de 0.33 nanoseconde pour un processeur de 3 GHz. ce qui me convient parfaitement :-p.

    Je vais donc me pencher sur la solution proposée par Damien (que je remercie). Pas de bolle je suis sur une machine possédant un processeur centrions double coeur (SMP). Pas le choix on fera avec.

    Je pense qu'il est possible de désactiver le SpeedStep Technology et Enhanced Intel® SpeedStep Technology sous le Biois. Enfin, je l'espère.
    • [^] # Re: Une solution à l'ancienne (en assembleur)

      Posté par  . Évalué à 2.

      J'avoue que je n'ai pas tout lu, mais je voulais te préciser un truc assez inévitable sur les systèmes modernes : tu ne pourras jamais avoir le temps exact de l'exécution d'un programme.

      Par contre, tu peux essayer de minimiser l'influence des choses extérieures à ton programme et le faisant boucler un certain nombre de fois, et en divisant le résultat par le nombre d'itérations. C'est une des techniques de base de la mesure de temps d'exécution.

      Met ta fonction principale dans une boucle, et calcule le temps qu'elle met à s'exécuter 10000 fois par exemple, tu auras une bien meilleure idée du temps d'exécution de ton programme.
    • [^] # Re: Une solution à l'ancienne (en assembleur)

      Posté par  . Évalué à 3.

      L’intérêt des index est bien d'accélérer le temps d'exécution et non le ralenti.

      Sauf si la base est petite.

      Par contre, tu peux essayer de minimiser l'influence des choses extérieures à ton programme et le faisant boucler un certain nombre de fois, et en divisant le résultat par le nombre d'itérations. C'est une des techniques de base de la mesure de temps d'exécution.

      Je ne trouve pas que c'est une bonne façon de faire, c'est une façon très artificiel de faire une mesure, surtout pour un micro benchmark.

      Je m'étais amusé à bencher une multiplication matriciel avec rdtsc. Le temps max était donné par la 1er itération, puis le nombre de cycle décroissait jusqu'à la 3 ième itération avant de se stabiliser : en gros tu remplis les caches. Pourtant, ton "vrai" temps est le premier, pas le plateau obtenu ensuite 10% plus rapide.

      "La première sécurité est la liberté"

    • [^] # Re: Une solution à l'ancienne (en assembleur)

      Posté par  (site Web personnel) . Évalué à 1.

      Je pense qu'il est possible de désactiver le SpeedStep Technology et Enhanced Intel® SpeedStep Technology sous le Biois. Enfin, je l'espère.
      SI tu te compileton noyau SANS activer le driver speedstep & Co, cela ne suffit pas? (ou bien meme si tu as de la chance, en dechargeant le module correspondant)

      Sinon, comme beaucoup l'ont deja suggeres, je ne suis pas sur que mesurer de facon tres precise le temps d'execution d'un bout de code court ne soit pas voue a l'echec sur un system multitache... Vu que des en fonction des taches que le processeur effectue, tu va vider ton cache ou pas, vider le cache du disque dur ou pas, ... En general, pour obtenir des mesures de temps stable, il faut prevoir dans son benchmark une etape qui nettoie les caches (je ne l'ai jamais fait pour le cache cpu, mais par contre je l'ai deja fait et vu faire pour le cache disque).

      Mathias
      PS: si ton bout de code demandait plusieurs minutes/heures de temps cpu, brassait des Go de donnees, alors la il n'y aurait plus vraiment ces problemes!
  • # Posix time API ?

    Posté par  . Évalué à 3.

    Pour la mesure de temps de précision, tu as:
    * clock_gettime qui renvoit une structure timespec avec une granularité à la nanoseconde.
    * times qui te permet de mesurer plus finement le temps cpu occupé par ton processus et les processus fils (système et utilisateur). Le seul bémol, c'est que c'est en nombre de tics d'horloges, donc il faudra récupérer le nombre de tics/seconde avec un appel sysconf(_SC_CLK_TCK)

    Ce sera plus clair avec un exemple simplifié:
    double clockticks, cticks;
    clock_t tcstart, tcend;
    struct tms tmstar, tmendt;

    clockticks = (double) sysconf(_SC_CLK_TCK);
    printf("Nombre de tics d'horloge par seconde: %f\n", clockticks);

    tcstart = times(&tmstart)
    ma_fonction_a_mesurer();
    tcend = times(&tmend)

    cticks = tmend.tms_utime + tmend.tms_stime - tmstart.tms_utime - tmstart.tms_stime;
    printf("Temps CPU utile %f secondes\n", tcicks/clockticks);

    Tu peux même calculer la fraction de temps CPU utilisé par ton programme: cticks/(tcend -tcstart)


    Personnellement, j'utiliserais plutôt un outil de profilage (gprof) comme on te l'a conseillé ailleurs, si c'est pour améliorer les performances de ton soft.
    • [^] # Re: Posix time API ?

      Posté par  . Évalué à 1.

      Ce n'est pas une optimisation de mon application que je fais. mais uniquement des mesures expérimentales.

      voilà les temps d'exécution que me renvoi times().

      0,09
      0,08
      0,1
      0,1
      0,09
      0,07
      0,09
      0,09
      0,11
      0,1
      0,1
      0,08
      0,09
      0,09
      0,1
      0,1
      0,08
      0,12
      0,09

      des différences allant jusqu'à 5ms !!! de me meilleure cas . ce qui n'est pas acceptable pour moi (voir mon poste précedent).
      • [^] # Re: Posix time API ?

        Posté par  (site Web personnel) . Évalué à 1.

        Mais heu, t'as pas un risque de toutes façon d'avoir des valeurs différentes d'une mesure à une autre, ne serait ce que par le cache du CPU qui peut varier en fonction des autres processus qui tournent sur le système ?
      • [^] # Re: Posix time API ?

        Posté par  . Évalué à 2.

        Tu déduis l'écart de 5 ms (ce ne serait pas plutôt 50 ms ?) des deux valeurs extrêmes qui n'apparaissent qu'une seule fois dans ton échantillon.

        Tu as une moyenne de 0,9 et un écart type de 0,1.
        Mesurer des temps de l'ordre de 100 ms à 10% près, moi je trouve ça plutôt bien :)

        Tu peux peut-être améliorer la dispersion des résultats en augmentant la priorité de ton programme:

        nice -n -20 ton_prog

        lui donnera la priorité maximum (il faut être root pour utiliser des valeurs négatives).
        • [^] # Re: Posix time API ?

          Posté par  . Évalué à 2.

          au pire il rend la tache temps réel, par contre, il ne faut pas compter sur un ctrl-c pour le tuer :)

          "La première sécurité est la liberté"

  • # clock_gettime

    Posté par  (site Web personnel) . Évalué à 1.

    clock_gettime() qui normalement en interne (dans le noyau linux) utilise getnstimeofday (avec les compteurs/timers du CPU, donc précision théorique de l'ordre de la nanoseconde) doit pouvoir t'aider à mesurer des durée d'exécution pour un processus (paramètre CLOCK_PROCESS_CPUTIME_ID) ou un thread (CLOCK_THREAD_CPUTIME_ID).

    Attention, ne pas se fier à ce que renvoie clock_getres() (qui devrait donner la résolution du timer) car sa valeur de retour doit être fixée en dûr à quelque chose qui n'a rien à voir avec le matériel (valeur imposée par POSIX si je me souviens bien).
    • [^] # Re: clock_gettime

      Posté par  . Évalué à 1.

      La fonction clock_gettime() m'a l'air très intéressante (comment j'ai pu passer à côté).

      corriger moi si je me trompe :

      CLOCK_PROCESS_CPUTIME_ID définie une horloge propre à mon processus qui prend en compte que le temps où mon processus est actif et ne prend pas en compte le temps où l'ordonnanceur le met en attente afin de faire tourner d'autres processus.

      Par contre, CLOCK_REALTIME s'appuie sur l'horloge physique globale et donc comptabilise tout ce qui se passe entre deux appels à clock_gettime.

      C’est ça ?

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.