Forum Programmation.c Optimisation de code C

Posté par  .
Étiquettes : aucune
0
19
août
2004
Bonjour,

je cherche à ecrire en C une routine optimisée pour calculer un produit scalaire de deux vecteurs (de taille variable). Comme cette routine sera appelée plusieurs milliers (millions) de fois, je cherche à gagner le moindre cycle processeurs. Ma plate-forme est un athlon-XP (sans SSE2 donc). Pour l'instant j'ai 2 variantes:


* C-pure:


double dot(const double *a, const double *b, unsigned long n)
{
register double res=0.0;
register unsigned long i;


for(i=(n/4)*4; i != 0; i -= 4)
{
register const double res1=a[i] * b[i];
register const double res2=a[i+1] * b[i+1];
register const double res3=a[i+2] * b[i+2];
register const double res4=a[i+3] * b[i+3];

res += res1 + res2 + res3 +res4;
}

switch(n-i)
{
case 3: res += a[n-3] * b[n-3];
case 2: res += a[n-2] * b[n-2];
case 1: res += a[n-1] * b[n-1];
}

return(res);
}





* et une C/Asm (plus rapide)


double dot(const double *a, const double *b, unsigned long n)
{
double res;

__asm__ __volatile__ ("fldz\n\t"
"testl %1, %1\n\t"
"jbe .fem.dot.end\n"
".fem.dot.loop:\n\t"
"subl $1, %1\n\t"
# ifdef SSE
/*
* Theses 2 instructions do all the job!
* Whithout them, we get "only" 17% speedup
* note: 128 is an empirical value...
*/
"prefetcht2 -128(%3, %1, 8)\n\t"
"prefetcht2 -128(%2, %1, 8)\n\t"
# endif /* SSE */
"fldl (%3, %1, 8)\n\t"
"fmull (%2, %1, 8)\n\t"
"faddp %0, %0(1)\n\t"
"jne .fem.dot.loop\n"
".fem.dot.end:"
: "=%%st" (res)
: "q" (n) , "q" (a), "q" (b));
return(res);
}





Si il y a des grourous de l'optimisation de code, j'aimerai avoir vos avis!

Merci


ps. j'ai tester blas et atlas sans succès.
  • # Petits optimizs.

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

    Je vais pas reproposer un code entier mais dans ton code C, ya deux ou trois chtites choses qui bloquent :
    - tu utilise des registers de partout et en const, ca ne sert pas à grand chose, mieux vaut en utiliser moins mais plus ciblé pour éviter d'avoir à décharger les registres.
    - Tu utilises une boucle à répétition fixe, est-ce que tu as pas intérêt à la dérouler, sachant que tu fais une accumulation dans une variable.
    - Tu utilise un switch avec des valeurs 1, 2 et 3que tu réutilise comme indice, là ca vaut ptet le coup d'utiliser un chtit registre ?

    Ou alors je vais dire une connerie, utilise ta carte opengl, doit y avoir moyen de calculer ca rapidement, surtout si tu l'appelle des millions de fois.

    Un jour libre ?

  • # les sources d'optimisation

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

    le prefetch 3dnow et la vectorisation :

    http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_(...)

    le cache :
    http://josu.uninet.edu/n1/acox.html(...)

    si une des trois reponses est beaucoup plus courante dans le switch, utilise la prediction de branche avec l'algo "d-loop" sur onversity.com

    Ca depend de la taillle de ton ensemble, mais le prefetch doit surement etre la meilleure piste.
  • # Meuh

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

    Si tu peux te permettre d'optimiser comme un malade en assembleur pour un Athlon, le mieux est de prendre la doc où elle est :

    http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_(...)

    Cette doc est un trésor et je me mords les c****es de ne pas avoir eu accès à ce genre de trucs quand je faisais des démos en assembleur.
    • [^] # Re: Meuh

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

      en francais par http://linuxfr.org/~nicOnicO/(...)

      http://f-cpu.seul.org/nico/article_hack_C.html(...)

      (base entre autre sur ce document, justement)
      • [^] # Re: Meuh

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

        Il est d'ailleurs intéressant de noter que le premier exemple concret avec programme (écrire "(a+b)+(c+d)" au lieu de "a+b+c+d") est faux sur mon p4-HT. Les deux valeurs sont de 127 clock ticks. Ceci dit gcc n'a pas l'air de s'être bien débrouilllé dans le cas "opt" il charge en registre la quatrième valeur bien trop tard si je ne m'abuse. Et d'ailleurs c'est bizarre que nico ait obtenu 38 clocks ticks sur sa machine dans le premier cas, mes 127 font pâle figure..

        #APP
                RDTSC
        #NO_APP
                movl        %edx, -36(%ebp)
                .loc 1 17 0
                movl        -32(%ebp), %ecx
                movl        -28(%ebp), %edx
                .loc 1 16 0
                movl        %eax, -40(%ebp)
                .loc 1 17 0
                movl        -20(%ebp), %eax
                addl        %ecx, %edx
                movl        -24(%ebp), %ecx
                addl        %ecx, %eax
                leal        (%eax,%edx), %ecx
                .loc 1 18 0
        #APP
                RDTSC
        #NO_APP


        #APP
                RDTSC
        #NO_APP
                movl        %edx, -36(%ebp)
                .loc 1 24 0
                movl        -28(%ebp), %esi
                movl        -32(%ebp), %edx
                .loc 1 23 0
                movl        %eax, -40(%ebp)
                .loc 1 24 0
                movl        -20(%ebp), %edi
                movl        -24(%ebp), %eax
                addl        %edx, %esi
                addl        %eax, %esi
                addl        %edi, %esi
                .loc 1 25 0
        #APP
                RDTSC
        #NO_APP
        • [^] # Re: Meuh

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

          Pour les 127 cycles, c'est logique. Les testes ont été fait sur un PIII@300 Mhz (l'article a qq années...).

          Le pipeline est 2 fois plus court (moins de dépendance) et la différence de vitesse entre la mémoire et le bus mémoire n'est que de ~4.5 (2x moins que les derniers pentium4).

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

          • [^] # Re: Meuh

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

            Ca puxor ! 127 cycles sur un 2.8 GHz contre 38 sur un 300 MHz ça fait à peine un rapport de 2,8 :( donc ma machine est (sur ce truc) seulement 2,8 fois plus rapide alors que la fréquence est presque multipliée par 10.

            Intel puxor.
            • [^] # Re: Meuh

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

              L'intel mets 3.3x plus de cycles. Mais un cycle est 10x plus court.

              Au final, tu n'est "que" 3x plus rapide sur ce mini bouts de code.

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

  • # les appels de fonction Inline?

    Posté par  . Évalué à 2.

    Peut etre serait il bon de vérifier si il y a moyen de forcer le compilateur a "inliner" les fonction?

    Parce que si on passe par un appel standard de fonction
    il y a quand meme le temps
    -d'empiler les parametres d'entrée de la fonction,
    -de faire un jump vers la fonction elle meme.

    Cela me semble "couteux" par rapport au temps de calcul effectif dans la fonction.

    Un "inlining" de la fonction permettrait surement de gagner des cycles en plus..



    Sous GCC par exemple un -O2 ne fait pas de déroulement de boucles et d'inlining alors qu'un -03 le fait ..
    ( http://gcc.gnu.org/onlinedocs/gcc-3.1.1/gcc/Optimize-Options.html(...) )


    Sinon tu peux aussi envisager de transformer ta fonction en macro, au moins tu es sur que l'inlining est effectué ..
    • [^] # Re: les appels de fonction Inline?

      Posté par  . Évalué à 2.

      Sinon tu peux aussi envisager de transformer ta fonction en macro, au moins tu es sur que l'inlining est effectué ..

      Pour faire plus propre il y a le inline (ex : inline int add (int a, int b) {...})
  • # Option de compilation

    Posté par  . Évalué à 1.

    Hello,

    T'es sur que BLAS optimisé pour ton processeur ca couvre pas ton besoin ? Ca me parait bizarre. DDOT de tête.
    http://www.ccl.net/cca/software/SOURCES/C/kinetics1/ddot.shtml(...)

    Regarde comment sont stockés tes vecteurs.

    Joue avec les options de compil aussi.

    Bon courage,

    Enzo Bricolo
  • # taille ?

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

    (je reposte ici, c'est plus approprié)

    Tu pourrais donner plus d'info sur la taille de a et b ?

    Si c'est "moyen gros", tu peux essayer un bloc prefetch.

    genre rajouter :
    for(i=0; i < n; i += 16)
    {
    dummy1 += a[i]; dummy2 += b[i];
    }

    devant la 1er boucle mais vu que tu n'y fais pas grand chose peut-être que mixer la chose pourrais faire gagner du temps :

    for(i=0; i < (n/4)*4 ; i += 4){ // les prefetcher automatiques n'aiment pas les adresses descendantes

    dummy1 += a[j=(j+16) mod n]; dummy2 += b[j];
    res1+=a[i] * b[i];
    res2+=a[i+1] * b[i+1];
    res3+=a[i+2] * b[i+2];
    res4 +=a[i+3] * b[i+3];
    }
    res += res1 + res2 + res3 +res4;

    A coder en SSE si tu veux t'amuser (déroulant la boucle pareil !).

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

  • # Python

    Posté par  . Évalué à 1.

    La version python :)
    def dot (a, b):
      res=0
      for i in range(len(a)):
        res = res + (a[i] * b[i])
      return res

    enfin je pense que c'est ça le calcul.
    Je comprends pas le i=(n/4)*4 de for(i=(n/4)*4; i != 0; i -= 4) : i=n c'est pas pareil ?
    • [^] # Re: Python

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

      La version python :)

      T'es sûr que pour la performance de calcul c'est un bon choix ?

      Je comprends pas le i=(n/4)*4 de for(i=(n/4)*4; i != 0; i -= 4) : i=n c'est pas pareil ?

      Ça calcule n & ~3 mais le monsieur a dû trop faire d'assembleur et est trop habitué aux conséquences des décalages binaires.

Suivre le flux des commentaires

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