Bon voilà un truc dont on se doutait fortement mais qui fait un peu mal au coeur quand même. Je vous remets toute la sauce. Splash :
[quote]On a appris, et c’est bien naturel, que pour un algorithme donné, il faut chercher à minimiser le nombre d’opérations effectuées par la machine. Par exemple, pour les algorithmes de tri, on considère que le nombre de comparaisons est significatif du coût de l’algo.
En algorithmique numérique, le tableau se nuance. Il s’agit non seulement de minimiser les calculs, mais aussi d’améliorer la localité de l’accès aux données. Malheureusement, ça rallonge le code des fonctions. Par exemple, pour une multiplication matricielle qui s’écrit naturellement en trois lignes, on obtient une fonction d’une cinquantaine de lignes.
C’est un coup majeur porté à ceux (dont je suis) qui croient à la notion d’« élégance » en programmation.
L’élégance du code est la croyance diffuse qu’un bon code est à la fois clair, concis et efficace. C’est le pendant de l’idéal grec de l’esprit sain dans un corps sain. Or, dans le cas de la multiplication matricielle, le code le plus efficace est de loin le moins clair.
La pilule est amère, mais reste supportable. Les deux implantations en concurrence effectuent le même nombre d’opérations, mais dans des ordres différents, ce qui explique la différence de performance.
Maintenant, je vais montrer comment la comparaison de deux implantations d’un algo peut tourner en faveur de celui qui comporte le plus d’opérations. Soit la suite entière classique :
i_max = 0;
for(k = 2; k < 113000; k++) {
unsigned int u;
int i;
i = 0; u = k;
while(u != 1) {
u = u%2==0 ? u/2 : 3*u+1;
i++;
}
if(i > i_max) i_max = i;
}
printf("i_max=%d
",i_max);
[/quote]Les valeurs prises par u(0) varient entre 2 et 113000 (au-delà, les valeurs de la suite deviennent trop grosses pour être codées sur 32 bits), et on cherche le nombre maximal d’itérations avant de converger.
Je compile ce code, et je mesure son temps d’exécution (gcc 3.1, G4 866), résultat :
real 0m0.137s
user 0m0.110s
sys 0m0.010s
[/quote]Maintenant, recodons la boucle while de la manière suivante :
real 0m0.101s
user 0m0.070s
sys 0m0.010s
[/quote]Donc la seconde version est plus rapide. Pourtant, à chaque itération, les deux alternatives de la suite sont calculées. En assembleur PPC, la boucle fait 7 ou 9 instructions (selon l’alternative) dans le premier cas, et 11 dans le second.
La différence de performances est due au branchement qu’il y a dans la première version. Un branchement est très domageable à la fluidité de l’exécution, car il perturbe l’ordre des instructions dans le pipeline.
En réalité, il y a un compromis à faire entre la pénalité introduite par le branchement et le coût du calcul des deux alternatives de l’opération. Si par exemple on codait u sur 64 bits (unsigned long long), sur lesquels on calcule en deux fois plus d’opérations, la tendance s’inverse.
On est parfois obligé d’adopter la solution 2, quand le flux de programme ne peut pas être contrôlé. C’est notamment le cas quand on programme en SIMD.
Le même programme en SIMD PowerPC (Altivec). On travaille sur 128 bits, donc on calcule la suite pour quatre valeurs initiales à la fois (4 * 32 bits = 128 bits). On utilise une extension du C dans laquelle les types vectoriels sont préfixés par « vector » et les opérations vectorielles commencent par « vec_ » :
i_max = 0;
for(k = 2; k < 113000; k += 4) {
unsigned int v0[4] = {k,k+1,k+2,k+3};
vector unsigned int u;
vector bool int stopped;
/* ==0xffffffff si le u correspondant a « convergé », 0 sinon */
int i;
u = vec_ld(0,v0); /* charge v0 dans le registre vectoriel /
stopped = false; / personne n’a convergé */
i = 0;
while(vec_any_eq(stopped,false)) { /* une des suites n’a pas convergé /
vector unsigned int u_ev, u_odd;
vector unsigned int mask =
vec_sub(vec_and(u,one),one); / and et sub membre à membre /
u_ev = vec_sr(u,one); / shift right 1 = div 2 /
u_odd = vec_add(vec_add(u,u),vec_add(u,one)); / (u+u)+(u+(1,1,1,1)) /
u = vec_sel(u_odd,u_ev,mask); / sélectionne selon masque /
stopped = vec_or(vec_cmpeq(u,one),stopped); / màj de stopped */
i++;
}
if(i > i_max) i_max = i;
}
printf("i_max=%d
",i_max);[/quote]On voit bien ici que l’implantation est longue, inélégante, qu’elle calcule les deux membres de l’alternative, qu’elle calcule certaines itérées de la suite alors qu’elle a convergé. Pourtant c’est la plus rapide :
real 0m0.077s
user 0m0.040s
sys 0m0.010s
[/quote]La morale de cette histoire, c’est que l’idéal d’élégance (d’origine grecque) est illusoire, qu’il faut en permanence faire des compromis entre la concision et l’efficacité d’un code. En particulier, les calculs de complexité doivent prendre en compte les opérations réellement coûteuses (comme ici les branchements)
PS: À titre de comparaison, sur PC (P4 1800) les résultats sont encore plus nets parce que le pipeline est plus profond (20 contre 7) :
real 0m0.091s
user 0m0.090s
sys 0m0.000s
$ time ./test2
i_max=353
real 0m0.066s
user 0m0.060s
sys 0m0.000s[/quote]J’ai pas fait l’implantation vectorielle…
PS2: la technique de Strassen est une implantation de la multiplication matricielle basée sur diviser pour régner qui permet de faire moins d’opérations.
Certes intéressant, mais ne pouvait-on pas s’en douter à partir du fonctionnement des options -Ox de gcc, dont un des boulots est de dérouler toutes les boucles déroulables ?[/quote]Dans le cas du déroulement de boucles, on ne fait pas plus de calculs.
Edit: C’est que j’en avais marre des techno web !
Ce message a été édité par xentyr le 20/09/2003