Élégance et rapidité ne font pas toujours bon ménage

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 :

u(n+1) = u(n)/2 si u(n) pair,  3*u(n)+1 sinon [/quote]Apparemment, cette suite converge vers la séquence (1,4,2) quelle que soit la valeur de u(0). On peut le vérifier par le petit code :
int k, i_max;

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 :

$ time ./test1 i_max=353

real   0m0.137s
user   0m0.110s
sys 0m0.010s
[/quote]Maintenant, recodons la boucle while de la manière suivante :

while(u != 1) {   unsigned int mask = (u&1)-1;   u = (mask & (u/2)) | ((~mask) & (3*u+1));   i++; } [/quote]Ce qui signifie :mask = 0xffffffff si u pair, mask = 0 si u impair.On exprime l'alternative par des opérations booléennes.
$ time ./test2 i_max=353

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_” :

int k, i_max; vector unsigned int one = (vector unsigned int)(1,1,1,1);   /* 4 int, tient dans un registre */ vector bool int false = (vector bool int)(0,0,0,0);   /* idem, mais considérés comme des booléens */

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 :

$ time ./test3 i_max=353

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) :

$ time ./test1 i_max=353

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.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Mijnheer a rétorqué:
François avait répondu au premier message:

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.
 

L’élégance ne dépend pas du langage. J’ai vu du code fortran présenté de manière limpide, et du Java ficelé comme du poisson pourri.

Edit: C’est que j’en avais marre des techno web !
Ce message a été édité par xentyr le 20/09/2003

Très intéressant, mais déjà connu depuis des années, et qui s’explique de manière très simple : toutes les instructions CPU n’ont pas le même coût en temps d’execution (d’une part), et les accés mémoire non plus (d’autre part).

Du coup, il faut jouer sur ces 2 facteurs pour tendre vers la version “optimale”. Et la vous voyez ça sur des processeurs puissants, avec beaucoup de mémoire cache, mais sur des processeurs moins véloces et plus limités en cache (qui a dit R5900 de la PS2 ? Ah non je proteste c’est pas moi !), la différence peut être encore beaucoup plus flagrante.

Effectivement, c’est connu, enfin, indirectement pour beaucoup d’entre nous, dès qu’on veut optimiser en fait. Car le discours ambiant prône bel et bien un absolutisme du code élégant, qui effectivement passe très mal en algo num ou parallèle. Les différents algos de multiplication matricielle sont vraiment flagrants à ce sujet mais là, je trouvais cet exemple assez abordable (une bête suite de Tale), didactique (le pourquoi est bien expliqué), court (niveau longueur de code), et reproductible chez soi, ce que je n’ai pas souvent vu sur le net. Donc paf sur le forum.
Ce message a été édité par xentyr le 20/09/2003

C’est surtout que dans 99.9% des applications ils vaut largement mieux un code clair, concis et elegant facile a maintenir, comprendre et modifier, qu’une horreur optimisee. C’est tout. Les perfs ne sont qu’une contrainte souvent peripherique dans la plupart des applications. (Du moment que ca se traine pas lamentablement). De plus les optimisations d’algo et de structure de donnees (sans parler de layout des donnees) , au lieu de l’ordre des operations dans l’algo ou autre, sont beaucoup beaucoup plus efficaces et a faire en priorite. Du avant d’avoir a optimiser avec ce genre de techniques il y a deja un enorme travail d’optimisation en restant concis et elegant. Si apres on a besoin des quelques % supplementaires apportes par ces techniques parceque: 1) on ecrit un compilateur et il faut faire au mieux, 2) on est dans une application ou les 3% grapilles sont important ou enfin 3) on est dans une appli ou 90% des calculs sont fait dans quelques boucles bien precises et ou ce genre d’optimisation fait gagner plus que 3%.

Donc en gros, continuez a faire du code elegant et concis, meme si c’est pas optimise pour le compilateur ou votre CPU. Si vous etes dans un domaine ou il faut faire expres de depasser ca, vous le savez deja

Ah oui, faut être clair, continuez à faire du code élégant et concis.

C’est ensuite, si votre appli est trop lente (pour vous ou le client), qu’il faut se mettre à optimiser en laissant de côté l’élégance pour axer sur la vitesse, quitte, comme on le voit ici, à faire quelques calculs de trop qui en terme de “vitesse” se révèleront moins pénalisants que des embranchements à tout va par exemple.

Je suis pas d’accord, faites du code crade qui pue de la gueule !

Sans dec vous enfoncez une porte ouverte la les gars hein, le problème n’est pas “faites du code élégant et conci”, le soucis c’est que beaucoup de codeur ne savent même pas ce que c’est que du code élégant et concis (et je ne développerai pas plus loin sinon je vais ENCORE me faire incendier par xentyr )

Bref, continuez a coder.

N’hésite pas à développer, je n’ai jamais incendié quelqu’un pour rien.

Par contre pour les portes ouvertes, je ne suis pas tout à fait d’accord. Elles ne sont ouvertes que pour les connaisseurs (qui par définition, connaissent le sujet), dont toi visiblement. Je n’en ai pas vraiment entendu parler en cours par exemple, excepté en algo parallèle.

Edit: Je n’ai vraiment aucune “dent” contre toi, je discutais tout simplement.
Ce message a été édité par xentyr le 22/09/2003

Juste une petite remarque.
Ce qui est important (et fondamental) dans ce papier, ce n’est pas l’élégance du code (par ex, une récursion est rarement plus rapide qu’une boucle simple, la programmation objet,  y’a des milliard d’exemples…), mais simplement le fait que quelque chose de plus long à exprimer (donc plus d’opérations) puisse être plus rapide. Ce peut remettre en cause pas mal de choses.
Personnelement, je pense que l’interprétation du compilo et le type de proc est la principale cause de ces résultats. Ce qui n’a rien à voir avec l’élégance “algorithmique” d’une procédure.

Moi je pense que le plus important c’est d’optimiser son code, tout en
restant dans les limites du lisible et de la clarté … Les autres
optimisations sont trop dépendantes de paramètres mal maitrisés : je
m’explique. J’ai fait des cours de compilation ainsi que des
compilateurs pour certains mini langages : si vous voyiez les
différences entre le code généré par le compilateur et ce que vous
aviez codé (et ceci par exemple à cause des prédictions de saut, des
pipelines à squasher, etc …) que des fois ça ne sert à rien de
vouloir trop optimiser !!!