Forum Programmation.c Coût d'un accès mémoire.

Posté par .
Tags : aucun
2
25
juin
2012

Bonjour, voila ça fait plusieurs fois que je me pose cette question, que je fais quelques test sans rien trouver de concluant.
Lorsque vous avez à des calculs relativement simples à faire sur un octet, une fonction pure uint8_t (uint8_t); (qui ne fait pas plus de 20 instructions).
Quelle solution adopter pour la performance dans le cas général :

  • une table ?
  • un (gros) switch case, ça revient revient à mettre la table dans le segment texte mais est-ce que l'accès est plus rapide, et est-ce que le coût de la localité du flux d'instruction ruinée est acceptable ?
  • un calcul ?
  • autre ?

Merci beaucoup

  • # Juste une idée.

    Posté par . Évalué à 1. Dernière modification le 26/06/12 à 23:56.

    Déjà, utilise un [u]int{std size register for your archi}.
    Éviter les conversions, si ton archi n'ai pas 8bit, n'utilise pas les uint8(par exemple)

    La suite je ne suis pas sur de comprendre… Mais je tente une réponse.
    Perso je pense que pour des fonctions "pure" type: int (*)(int)(enfin avec la même "signature") un tableau de pointeur sur func est la bonne solution.

    Je ne suis pas sur, mais l'utilisation de fonction static( + inline) devrais aussi aider le compilateur à réaliser quelques optimisations.

    GCC(si tu utilise ce compilateur) a des extensions qui permet(sur du x86, sur du x86_64 ce n'ai plus utile) de forcé l'utilisation des registers(func a <= 4 arg) ce qui permet de la aussi de faire gagner quelques cycles.

    Je ne suis pas sur de t'avoir répondu correctement, mais j’espère t'avoir un peu aidé.

  • # Vectoriser

    Posté par . Évalué à 2.

    Ta fonction sur un octet, si tu l'appelles plusieurs fois sur des données indépendantes, tu peux la réécrire en utilisant les instructions SSE2 entières (et les futures AVX2) qui les feront 16 par 16 (ou 32 par 32 pour les AVX2).

  • # Une table

    Posté par (page perso) . Évalué à 4.

    Tu fais le calcul une fois pour toutes pour les 256 valeurs au démarrage et stocke ça dans une globale, après c'est de l'accès direct en mémoire à l'index désiré. Si c'est beaucoup utilisé, ça va se retrouver dans le cache avec un accès très rapide, sinon… c'est que ça ne le mérite pas :-)

    Et éventuellement, tu peux définir:
    static inline uint8_t mafonction(uint8_t v)
    { return maglobale[v]; }

    Comme ça c'est masqué et si tu changes l'implémentation de mafonction(), ton code restera le même.

    Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

    • [^] # Re: Une table

      Posté par . Évalué à -2.

      Et éventuellement, tu peux définir:
      static inline uint8_t mafonction(uint8_t v)
      { return maglobale[v]; }
      Comme ça c'est masqué et si tu changes l'implémentation de mafonction(), ton code restera le même.

      Pour faire ça, on utilise un:
      #define mafonction(X) (X > UCHAR_MAX ? 0 : maglobale[X])

      • [^] # Re: Une table

        Posté par (page perso) . Évalué à 3.

        J'aime bien le inline avec le contrôle de type par le compilo & Co - je trouve ça plus propre que la définition de macros. Je me suis demandé quel coût avait le inline vs la définition de macro.

        Testé avec le source suivant (sous Linux 64 bits, gcc 4.6.3).

        // Fichier testinlinec.c
        #include <stdio.h>
        #include <stdint.h>
        #include <time.h>
        #include <limits.h>
        
        #define TESTSCOUNT  10000000
        
        static uint8_t mapping[256];
        
        // Définition avec du inline.
        static inline uint8_t mafonction1(uint8_t v)
        { return v>UCHAR_MAX? 0 : mapping[v]; }
        
        // Définition en macro.
        #define mafonction2(X) (X > UCHAR_MAX ? 0 : mapping[X])
        
        
        
        inline uint64_t rdtsc()
        {
            uint32_t lo, hi;
            __asm__ __volatile__ (
              "xorl %%eax, %%eax\n"
              "cpuid\n"
              "rdtsc\n"
              : "=a" (lo), "=d" (hi)
              :
              : "%ebx", "%ecx" );
            return (uint64_t)hi << 32 | lo;
        }
        
        
        void main(void)
        {
            int i;
            int x;
            uint64_t start, end;
            uint64_t tinline, tmacro;
        
            // Initialisation du mapping avec des valeurs décalées.
            for (i=0 ; i<256 ; i++)
                mapping[i] = (i+8)%UCHAR_MAX;
        
            // Test avec le inline.
            start = rdtsc();
            for (i=0 ; i<TESTSCOUNT ; i++)
                x = mafonction1(i % UCHAR_MAX)*2;
            end = rdtsc;
        
            tinline = end - start;
            printf("Inline: %lu\n", tinline);
        
            // Test avec la macro.
            start = rdtsc();
            for (i=0 ; i<TESTSCOUNT ; i++)
                x = mafonction2(i % UCHAR_MAX)*2;
            end = rdtsc;
        
            tmacro = end - start;
            printf("Macro:  %lu\n", tmacro);
        
            printf("Inline-Macro:  %lu\n", tinline - tmacro);
        }
        
        

        Le résultat dépend fortement de l'option de compilation choisie (je suppute que dans certains cas il n'inline pas). Sur ma machine (note: le temps est en nano-secondes):

        -O0 Inline-Macro:  227906089 nsec
        -01 Inline-Macro:   14369156 nsec
        -02 Inline-Macro:      94070 nsec
        -O3 Inline-Macro:      89284 nsec
        
        

        (note: avec des variations d'une exécution sur l'autre… vu la résolution c'est normal, les -O2 et -O3 sont quasi équivalent pour ce test)

        Note: code pour le timing issu de stackoverflow.

        Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

        • [^] # Re: Une table

          Posté par . Évalué à 3.

          Tu a essayé de compiler ton code ? Chez moi, avec GCC 4.7.1 en 64bit:

          testinline.c: In function ‘mafonction1’:
          testinline.c:13:1: warning: comparison is always false due to limited range of data type [-Wtype-limits]
          testinline.c: At top level:
          testinline.c:34:6: warning: return type of ‘main’ is not ‘int’ [-Wmain]
          testinline.c: In function ‘main’:
          testinline.c:49:9: warning: assignment makes integer from pointer without a cast [enabled by default]
          testinline.c:58:9: warning: assignment makes integer from pointer without a cast [enabled by default]
          testinline.c:37:9: warning: variable ‘x’ set but not used [-Wunused-but-set-variable]
          [23:5

          Et les résultats chez moi après avoir corrigé au moins les calculs de temps :

          O0 : Inline-Macro: 20691390, pas d'inline
          O1 : Inline-Macro: 25125555, fonction omise, lecture du tableau omise, mais boucle de 0 à TESTSCOUNT conservée
          O2 : Inline-Macro: 0 ou 18446744073709551595 (integer underflow), boucle de 0 à TESTCOUNT omise, lecture du tableau omise, on mesure plus rien du tout, mais l'initialisation du tableau est conservée.
          O3 : Code assembleur identique à O2.

          Enfin bref, c'est pas le tout de pondre du code de test, mais autant que ce code calcule quelque chose qui ne puisse pas être connu à l'avance, et qui soit ensuite réellement utilisé.

          Enfin bref, n'optimisez que des programmes finis qui servent à quelque chose.

          • [^] # Re: Une table

            Posté par (page perso) . Évalué à 3.

            Tu a essayé de compiler ton code ? Chez moi, avec GCC 4.7.1 en 64bit:

            Oui, en utilisant CMake + make, sinon je n'aurais pas pu donner les résultats.

            Enfin bref, c'est pas le tout de pondre du code de test, mais autant que ce code calcule quelque chose qui ne puisse pas être connu à l'avance

            Le but était de comparer l'inlining (effectif) vs la macro. Peut-être que toi tu connaissais à l'avance le résultat, moi pas.

            Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

          • [^] # Re: Une table

            Posté par (page perso) . Évalué à 2.

            testinline.c:13:1: warning: comparison is always false due to limited range of data type [-Wtype-limits]

            La ligne return v>UCHAR_MAX? 0 : mapping[v]; est là pour avoir le même code que dans la macro. Et gcc 4.7 semble avoir des contrôles en plus du 4.6.

            Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

            • [^] # Re: Une table

              Posté par (page perso) . Évalué à 3.

              … le code inline a donc l'avantage que le compilo cast le paramètre en uint8_t, ce que ne fait pas la macro, ce qui permettrais de supprimer le test (faudrais voir, coût du test vs coût du cast sans le test, avec un peu de chance le inline devient plus rapide).

              Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

          • [^] # Re: Une table

            Posté par (page perso) . Évalué à 2.

            Ah, en effet, gros bug (faudrais pas coder trop tard le soir):

            end = rdtsc

            Et je ne me souviens pas avoir vu d'erreur par gcc. Je reverrais ça ce soir…

            Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

            • [^] # Re: Une table

              Posté par (page perso) . Évalué à 2.

              En corrigeant mon bug (⇒ end = rdtsc();), c'est nettement mieux:

              pointal@soupir:~/testinlinec$ gcc testinlinec.c
              pointal@soupir:~/testinlinec$ ./a.out 
              Inline: 242608338
              Macro:  231264504
              Inline-Macro:  11343834
              pointal@soupir:~/testinlinec$ gcc -O1 testinlinec.c
              pointal@soupir:~/testinlinec$ ./a.out 
              Inline: 15078402
              Macro:  15015321
              Inline-Macro:  63081
              pointal@soupir:~/testinlinec$ gcc -O2 testinlinec.c
              pointal@soupir:~/testinlinec$ ./a.out 
              Inline: 342
              Macro:  342
              Inline-Macro:  0
              pointal@soupir:~/testinlinec$ gcc -O3 testinlinec.c
              pointal@soupir:~/testinlinec$ ./a.out 
              Inline: 351
              Macro:  342
              Inline-Macro:  9
              
              

              L'inlining est similaire à la macro.

              Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

              • [^] # Re: Une table

                Posté par (page perso) . Évalué à 2.

                Ben non (j'aurais dû lire Batchyx jusqu'au bout).

                Modifié en ajoutant une globale uint8_t coucou[10000000];
                Et en stockant les résultats coucou[i] = mafonction1(i % UCHAR_MAX)*2; pour que le résultat soit utilisé donc que la boucle ne soit pas réduite par l'optimiseur.

                pointal@soupir:~/testinlinec$ gcc testinlinec.c
                pointal@soupir:~/testinlinec$ ./a.out 
                Inline: 250650621
                Macro:  223207182
                Inline-Macro:  27443439
                pointal@soupir:~/testinlinec$ gcc -O1 testinlinec.c
                pointal@soupir:~/testinlinec$ ./a.out 
                Inline: 96174252
                Macro:  102364884
                Inline-Macro:  18446744073703360984
                pointal@soupir:~/testinlinec$ gcc -O2 testinlinec.c
                pointal@soupir:~/testinlinec$ ./a.out 
                Inline: 92908719
                Macro:  89149068
                Inline-Macro:  3759651
                pointal@soupir:~/testinlinec$ gcc -O3 testinlinec.c
                pointal@soupir:~/testinlinec$ ./a.out 
                Inline: 96442803
                Macro:  91111680
                Inline-Macro:  5331123
                
                

                Dont acte.

                Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

                • [^] # Re: Une table

                  Posté par (page perso) . Évalué à 2.

                  Pour le O1 y'a dû avoir un évènement pendant l'exécution (manque de stats - temps d'exec trop court, ça reste des nano secondes)

                  pointal@soupir:~/testinlinec$ ./a.out 
                  Inline: 105885747
                  Macro:  102699423
                  Inline-Macro:  3186324
                  
                  

                  Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

    • [^] # Re: Une table

      Posté par . Évalué à 0.

      Tu fais le calcul une fois pour toutes pour les 256 valeurs au démarrage et stocke ça dans une globale, après c'est de l'accès direct en mémoire à l'index désiré. Si c'est beaucoup utilisé, ça va se retrouver dans le cache avec un accès très rapide, sinon… c'est que ça ne le mérite pas :-)

      Si il y en a pas trop et que les contraintes(hardware) ne sont pas trop fortes.
      (Je dit ça juste parce que, la question est quand même sur une optimisation à des années lumières de la préoccupation de 99% des développeurs)
      C'est sur que une mise en cache peu être une bonne solution.

      • [^] # Re: Une table

        Posté par . Évalué à 1.

        Plus de détails, j'essaye de faire une implémentation patator d'un jeu de la vie de conway. Sans trop savoir pourquoi je m'étais fixé pour objectif de ne pas mettre avoir d'accès mémoire au cœur de la boucle principale. Pour le calcul du nouvel état ça prend en gros une 60ène d'instructions, que je peux échanger contre un test et une lecture de table.

        Je vais faire des tests et tenter d'autres implémentations, sur plusieurs machines. Je vous tiens au jus :)

        Please do not feed the trolls

  • # Commentaire supprimé

    Posté par . Évalué à 2. Dernière modification le 27/06/12 à 00:03.

    Ce commentaire a été supprimé par l'équipe de modération.

  • # Commentaire supprimé

    Posté par . Évalué à 1.

    Ce commentaire a été supprimé par l'équipe de modération.

    • [^] # Re: Tu utilises un tableau

      Posté par . Évalué à 2.

      Si ton compilateur n'est pas capable d'inliner une fonction qui retourne func[x]; alors change de compilateur.

      • [^] # Re: Tu utilises un tableau

        Posté par . Évalué à 0.

        Si tu choisi un compilo qui aime prendre des risques… (gcc ne fait pas d'inline tout seul, source a l’appui…)

        • [^] # Re: Tu utilises un tableau

          Posté par . Évalué à 1.

          Chez moi ça marche.

          static const uint8_t func[256] = {232, 21, 174 /*.....*/};
          static uint8_t macros_are_for_wimps(uint8_t v) {
              return func[v];
          }
          
          int main(int argc, char* argv[]) {
              if (argc <= 1)
                  return 0;
              return macros_are_for_wimps(atoi(argv[1]));
          }
          
          
          main:
          .LFB1:
              .cfi_startproc
              movl    $0, %eax
              cmpl    $1, %edi
              jle .L6
              subq    $8, %rsp
              .cfi_def_cfa_offset 16
              movq    8(%rsi), %rdi
              call    atoi
              movzbl  %al, %eax
              movzbl  func(%rax), %eax  <------
              addq    $8, %rsp
              .cfi_def_cfa_offset 8
          .L6:
              rep
              ret
              .cfi_endproc
          
          

          Et c'est du gcc -O, hein, c'est presque le flag d'optimisation que je met tout le temps même en debug.

          • [^] # Re: Tu utilises un tableau

            Posté par . Évalué à -1.

            Je n'ai rien dit. Je n'utilise pas de flag d'optimisation.
            Dans mon cas, je ne fait pas de static non plus.

            • [^] # Re: Tu utilises un tableau

              Posté par . Évalué à 3.

              Si tu n'utilise pas de flag d'optimisation, je vois pas pourquoi tu reproche à gcc de ne pas optimiser.

              Et par défaut si tu n'utilise pas static sur ta fonction, cela veut dire que la fonction doit être exportée, donc qu'elle doit pouvoir être appelée par du code externe. donc elle existera forcément, et du coup le compilateur aura moins envie de l'inliner. Du coup gcc n'inline qu'en -O2, et la fonction est encore présente, même en -O3. Il faut du -fwhole-program pour s'en débarrasser.

      • [^] # Commentaire supprimé

        Posté par . Évalué à 2.

        Ce commentaire a été supprimé par l'équipe de modération.

        • [^] # Re: Tu utilises un tableau

          Posté par . Évalué à 1.

          Parce que tu sait à l'avance que tu n'est même pas sûr qu'avoir le résultat précalculé dans un tableau soit une bonne idée. Et que si un jour tu a envie de changer et de calculer le résultat à la volée, t'aura pas à te faire chier à modifier tout les endroits ou tu à utilisé ton tableau directement.

          Si tu était en C++, par contre, ça pourrai se discuter, vu que tu pourrai remplacer ton tableau par un objet avec un operator [] sans avoir à changer le code qui accède au tableau.

          • [^] # Commentaire supprimé

            Posté par . Évalué à 2.

            Ce commentaire a été supprimé par l'équipe de modération.

            • [^] # Re: Tu utilises un tableau

              Posté par . Évalué à 2.

              Si tu utilise ton #define, tu à bien d'autres problèmes. Déjà tu est en train de mentir à l'utilisateur de ta macro, parce qu'il peut croire que c'est une fonction avec vérification des paramètres et documentation.

              Ensuite si ta macro à un problème, ou si l'utilisateur à une autre variable qui s'appelle "func", t'aura avec la plupart des compilos des messages d'erreurs incompréhensibles du genre "func indéfini" ou "func ne peut pas être indéxé" alors qu'il n'y a pas "func" dans la ligne en question.

              Si ça te fait plaisir de mettre tout ton code dans des macros et d'avoir que main() comme fonction, c'est ton problème.

              De plus, Le inlining n'est pas du tout une garantie (cfr. le standard). Il peut encore dans de nombreux cas avoir un appel. Un appel coûte dans 99.9% des cas extrêmement plus qu'un accès mémoire.

              Le standard ne te garanti pas qu'inliner sera forcement plus rapide que d'appeler une fonction, et ne te garanti pas non plus que ton compilo ne dé-inline pas ton code si tu fait trop de copier/coller.

              Mais si tu ne fait tellement pas confiance à ton compilateur, change le. Quand gcc refuse d'inliner, il peut te dire pourquoi, et tu peut bidouiller les heuristiques de gcc si tu te crois plus malin que lui. Mais n'oublie pas que la plupart des problèmes d'optimisations sont NP-complet, et que gcc peut refuser d'optimiser une fonction si elle devient trop compliquée pour éviter que le temps de compilation explose.

  • # profile

    Posté par (page perso) . Évalué à 3.

    Ça dépend de la taille de ton tableau, des optimisations dont ton compilateur est capables, des optimisations dont ta plateforme est capable et de la manière dont la fonction est utilisée.

    Commence par essayer avec l'implémentation la plus simple possible, mesure combien de temps la fonction met dans différents cas d'utilisation, optimise, mesure de nouveau et ainsi de suite. Tu devrais assez vite te rendre compte que certaines optimisations sont inutiles ou en fait ralentissent ce que tu pensais accélerer parce que tu as oublié de tenir compte d'une subtilité quelconque tandis que certaines approches a priori trop naïves te donne des gains significatifs.

    En pratique, si tu veux profiler sans trop modifier ton code (l'idéal pour avoir des scénarios d'utilisation réalistes), gprof, valgrind et oprofile sont des outils qui peuvent aider.

    pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

  • # Test

    Posté par (page perso) . Évalué à 3.

    Quel que soit les conseils ci-avant que vous déciderez de suivre, surtout n'oubliez pas de tester les performances des implémentations. La théorie c'est bien beau. Mais parfois en matière d'optimisation elle est mise en échec par les faits. Un peu comme ces méthodes de mise en cache de données dans le noyau qui avaient perdurées et prospérées des années jusqu'à ce qu'après vérifications et tout comptes faits elles soient systématiquement éliminées (je ne me souviens malheureusement plus d'un lien).

    • [^] # Re: Test

      Posté par . Évalué à 3.

      Effectivement j'ai clairement ce travers, À chaque ligne que j'écris je pense aux instructions générées et je me dis « il faut que j'y pense plus pour faire mieux ». Avec le code assembleur on peut se faire une image du programme qui tourne, mais en pratique, c'est ce qu'en fait le processeur qui compte, et rien d'autre.

      https://lwn.net/Articles/444336/ (un lien concernant prefetch pour linux, c'est à ça que vous faites référence je suppose)

      Please do not feed the trolls

  • # Question très difficile

    Posté par (page perso) . Évalué à 2.

    Pour commencer, évaluer la performance d'un programme dépend de l'architecture. Je vais bêtement supposer que tu es en x86, ce qui est une très mauvaise nouvelle car les heuristiques d'accélération de la puce (prefetch etc.) rendent la performance du code très difficile à prédire. Par exemple, il peut arriver que du code testant les bornes des indices lors de l'accès à des tableaux tourne plus vite que le code sans test correspondant, ce qui n'est pas très intuitif vu qu'il y a plus d'instructions.

    Si tu utilises très intensément ta table et que celle-ci est assez petite, il y a de bonnes chances que celle-ci reste dans le cache mémoire du processeur et que le coût d'accès à celle-ci soit minime. Ceci dit si ta fonction est simple (tests, additions, rotations de bits et branchements courts) je m'attends à ce que la vitesse d'exécution soit comparable à celle de la version avec table tandis que si ta fonction contient des instructions plus complexes (divisions, multiplications) la version précalculée sera vraisemblablement plus efficace.

    • [^] # Re: Question très difficile

      Posté par . Évalué à 2.

      D'accord, je vois, le coté "boite noire super efficace" c'est sympa quand on s'en sert, mais frustrant quand on veut comprendre ce qui ce passe :)

      Ta supposition bête est bien évidement très pertinente. Je pensais (moi bêtement) que l’architecture mémoire était grosso modo la même partout et que cette réponse trouvait une solution dans le cas général.

      J'ai pas eu le temps d'avancer ce projet, je suis retenu à l'insu de mon plein gré pour porter des briques. Mais je tiens à vous faire part des résultats de mes expérimentations.

      Please do not feed the trolls

      • [^] # Re: Question très difficile

        Posté par (page perso) . Évalué à 3.

        quand on veut comprendre ce qui ce passe

        x86 est une architecture pourrie car incompréhensible! Il est pratiquement impossible de prouver quoique ce soit et les optimisations du compilateur ne portent d'optimisation que le nom — en réalité leur impact sur la rapidité d'éxécution est très incertain.

        Si tu aimes avoir peur, tu peux lire ça et ça:

        http://compilers.iecc.com/comparch/article/96-02-165
        www.multicoreinfo.com/research/papers/2009/asplos09-producing-data.pdf

        En bref ils montrent que des variations de rapidité dans un facteur de 1 à 4 peuvent etre liés à l'environnement seul (le programme ne change pas). Cela veut dire que si tu optimises un programme et que la version optimisée tourne 4 fois plus vite, tu ne sais pas si le changement vient de ton programme ou de l'environnement. (C'est désagréable, mais c'est comme ça.)

Suivre le flux des commentaires

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