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 Émilien Kia (site web personnel) . Évalué à 1.
- 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 ?
[^] # Re: Petits optimizs.
Posté par tuan kuranes (site web personnel) . Évalué à 2.
# les sources d'optimisation
Posté par tuan kuranes (site web personnel) . Évalué à 1.
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.
[^] # Re: les sources d'optimisation
Posté par tuan kuranes (site web personnel) . Évalué à 2.
=>
Si un vecteur peut-etre reutilise plusieurs fois de suite, si ta memoire est aligne (buffer de vecteurs alignes), etc...
# Meuh
Posté par gc (site web personnel) . Évalué à 2.
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 tuan kuranes (site web personnel) . Évalué à 2.
http://f-cpu.seul.org/nico/article_hack_C.html(...)
(base entre autre sur ce document, justement)
[^] # Re: Meuh
Posté par gc (site web personnel) . Évalué à 2.
#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 Nicolas Boulay (site web personnel) . Évalué à 1.
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 gc (site web personnel) . Évalué à 2.
Intel puxor.
[^] # Re: Meuh
Posté par Nicolas Boulay (site web personnel) . Évalué à 1.
Au final, tu n'est "que" 3x plus rapide sur ce mini bouts de code.
"La première sécurité est la liberté"
[^] # Re: Meuh
Posté par gc (site web personnel) . Évalué à 2.
[^] # Re: Meuh
Posté par Nicolas Boulay (site web personnel) . Évalué à 1.
"La première sécurité est la liberté"
# les appels de fonction Inline?
Posté par . Takhi . Évalué à 2.
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 Anonyme . Évalué à 2.
Pour faire plus propre il y a le inline (ex : inline int add (int a, int b) {...})
[^] # Re: les appels de fonction Inline?
Posté par tuan kuranes (site web personnel) . Évalué à 2.
(comme register d'ailleurs.)
donc utiliser une macro force le inline.
# Option de compilation
Posté par Enzo Bricolo 🛠⚙🛠 . Évalué à 1.
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 Nicolas Boulay (site web personnel) . Évalué à 1.
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 Pinaraf . Évalué à 1.
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 gc (site web personnel) . Évalué à 2.
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.