Pensez vous quil y ait possiblité de simplifier cette routine???

Pensez vous quil y ait possiblité de simplifier cette routine??? - Algo - Programmation

Marsh Posté le 12-03-2007 à 14:14:50    

pour un intro vraiment tres petite (256b),  j'ai besoin que cette routine prenne le moins de place possible et j'aimerai savoir s'il y a possiblilité d'optimiser (en taille) ce calcul:  
 

Code :
  1. l1=abs(1/dx);
  2. l2=abs(1/dy);
  3. l3=abs(1/dz);
  5. l=min(min(max(l1,l2),max(l2,l3)),max(l1,l3));
  7. ix=dx*l;
  8. iy=dy*l;
  9. iz=dz*l;

Reply

Marsh Posté le 12-03-2007 à 14:14:50   

Reply

Marsh Posté le 12-03-2007 à 14:44:46    

L'idée c'est pas de voir le code assembleur qui est généré à partir de ce code et de le réduire si c'est possible ?


---------------
Töp of the plöp
Reply

Marsh Posté le 12-03-2007 à 15:14:11    

L'idée c surtout deviter de tout coder en assembleur , se rendre compte que on peut optimiser des lignes en simplifiants les calculs et de tout recoder apres :o (car en asm tout est souvent tres lié).....

Reply

Marsh Posté le 15-03-2007 à 19:47:22    

Tu peux déjà éviter de calculer 1/dx,1/dy,1/dz en divisant par l au lieu de multiplier par l:

Code :
  1. l1=abs(dx);
  2. l2=abs(dy);
  3. l3=abs(dz);
  5. l=min(min(max(l1,l2),max(l2,l3)),max(l1,l3));
  7. ix=dx/l;
  8. iy=dy/l;
  9. iz=dz/l;


Message cité 1 fois
Reply

Marsh Posté le 16-03-2007 à 12:01:03    

Si tes nombres sont des entiers, tu peux utiliser certains algo particuliers pour calculer abs, min et max.
 
Jette un coup d'oeil là : http://graphics.stanford.edu/~seander/bithacks.html
 
Il y a des algo amusants et peu évident pour faire tout ça.
Avec un peu de chance, ca te permettra de faire un code plus concis.

Reply

Marsh Posté le 16-03-2007 à 12:03:59    

ouais enfin si c'est des entiers, 1/x c'est vite vu ...

Reply

Marsh Posté le 16-03-2007 à 12:10:43    

dividee a écrit :

Tu peux déjà éviter de calculer 1/dx,1/dy,1/dz en divisant par l au lieu de multiplier par l:

Bonne idée, mais dans ce cas là il faut faire attention aux min/max : les valeurs directes dx, dy et dz ne sont pas rangées dans le même ordre que leurs inverses...
 

Message cité 1 fois

---------------
TriScale innov
Reply

Marsh Posté le 16-03-2007 à 12:53:00    

bon pour info
 
on a effectivement viré les 1/dx 1/dy et pour le moment ca pose pas trop de problemes au minmax
 
pour linstant on est a 300bytes a peu pres tout compris (routine de base , vsync and co)
 

Reply

Marsh Posté le 16-03-2007 à 13:16:37    

franceso a écrit :

Bonne idée, mais dans ce cas là il faut faire attention aux min/max : les valeurs directes dx, dy et dz ne sont pas rangées dans le même ordre que leurs inverses...


 
Effectivement, elles sont rangées dans l'ordre inverse, mais le calcul avec min/max est en fait le calcul de la valeur médiane, et l'inverse de la médiane est égale à la médiane des inverses...
 
[edit:] Si le nombre de valeur est impair (pour que la médiane soit bien définie).

Message cité 1 fois
Message édité par dividee le 16-03-2007 à 13:24:42
Reply

Marsh Posté le 16-03-2007 à 13:33:51    

dividee a écrit :

Effectivement, elles sont rangées dans l'ordre inverse, mais le calcul avec min/max est en fait le calcul de la valeur médiane, et l'inverse de la médiane est égale à la médiane des inverses...
 
[edit:] Si le nombre de valeur est impair (pour que la médiane soit bien définie).


:jap:
 
effectivement, j'avais pas prêté attention à ce détail...


---------------
TriScale innov
Reply

Marsh Posté le 16-03-2007 à 13:33:51   

Reply

Marsh Posté le 16-03-2007 à 13:50:29    

Solution tangente, vectorisons.
Disons que l'on a  a { l1,l2,l3 }, et par rotation b { l2,l3,l1 }, c { l3,l1,l2 }.
Prenons le masque de mask_ab = a > b et mask_ac = a > c, alors le masque mask = mask_ab ^ mask_ac désigne la valeur médiane.
Extraction du masque etc...

 

SSE ftw.

Message cité 1 fois
Message édité par tbp le 16-03-2007 à 13:52:42
Reply

Marsh Posté le 16-03-2007 à 18:07:31    

tbp a écrit :

Solution tangente, vectorisons.
Disons que l'on a  a { l1,l2,l3 }, et par rotation b { l2,l3,l1 }, c { l3,l1,l2 }.
Prenons le masque de mask_ab = a > b et mask_ac = a > c, alors le masque mask = mask_ab ^ mask_ac désigne la valeur médiane.
Extraction du masque etc...
 
SSE ftw.


tu peut detailller un peu sil te plait??
 
 
sinon on a aussi une autre routine qui prend de la place :  
 

Code :
  1. cx=cos(t*0.6);
  2. cy=cos(t*0.1);
  3. cz=cos(t*0.4);
  5. sx=sin(t*0.6);
  6. sy=sin(t*0.1);
  7. sz=sin(t*0.4);
  10. dx1=dx*cz-dy*sz; 
  11. dy1=dx*sz+dy*cz; 
  12. dz1=dz;
  14. dx2=dx1;   
  15. dy2=dy1*cx-dz1*sx;
  16. dz2=dy1*sx+dz1*cx;
  18. dx3=dx2*cy-dz2*sy;
  19. dy3=dy2;
  20. dz3=dx2*sy+dz2*cy;


 
 
pour le moment on la simplifié par :  

Code :
  1. c=sin(t);
  2. s=sin(t);
  4. rotate(dx,dy,c,s);
  5. rotate(dy,dz,c,s);
  6. rotate(dx,dz,c,s);
  8. void rotate(&dx,&dy,c,s)
  9. fx=dx*c-dy*s;
  10. fy=dx*s+dy*c;
  11. dx=fx;
  12. dy=fy;


bon ca fait pas tout fait la meme chose (calcul de c et s) mais bon

Message cité 1 fois
Reply

Marsh Posté le 16-03-2007 à 19:54:53    

red faction a écrit :

tu peut detailller un peu sil te plait??


Feignasse.
En plus les types sont mal définis, mais je vais supposer que a) ya que des flottants b) SSE2 n'est pas verbotten.
 
Avec les 3 flottants alignés (à 16 octets) sur la pile

Code :
  1. 40f0ff:       andnps (%esp),%xmm0
  2. 40f103:       movaps %xmm0,%xmm2
  3. 40f106:       movaps %xmm0,%xmm1
  4. 40f109:       shufps $0xc9,%xmm0,%xmm2
  5. 40f10d:       shufps $0xd2,%xmm0,%xmm1
  6. 40f111:       cmpltps %xmm0,%xmm2
  7. 40f115:       cmpltps %xmm0,%xmm1
  8. 40f119:       xorps  %xmm1,%xmm2
  9. 40f11c:       movmskps %xmm2,%edx
  10. 40f11f:


... ce qui nous fait en gros 32 octets pour trouver une valeur absolue + mediane.
Reste 2 points à élucider.
Premierement d'ou vient le masque (dans xmm0 au début) pour virer les bits de signe: 2 solutions, soit le génerer avec

Code :
  1. pxor   %xmm0,%xmm0 // 4 octets
  2. pcmpeqd %xmm0,%xmm0 // 4 octets
  3. pslld  $0x1f,%xmm0 // 5 octets


ou un truc plus lent dans le genre, soit le charger.
 
Ensuite, on a un masque dans un GPR mais il faut triturer les doublons.
En gros

Code :
  1. uint_t bits = %edx;
  2. uint_t index = 0;
  3. if (bits & 2) index = 1;
  4. if (bits & 4) index = 2;
  5. const float l = (esp, index, 4);


mais rien de bien fringuant me vient à l'esprit, alors une bonne vielle LUT fera l'affaire.
Voilà.

Reply

Marsh Posté le 16-03-2007 à 22:01:13    

et gcc 4.0 inventa les intrinsics SSE2 :o
Ca fait qquelques temps qu'on a plus besoin de descendre au niveau ASM pour vectoriser quoique ce soit

Message cité 2 fois
Reply

Marsh Posté le 16-03-2007 à 22:17:10    

Joel F a écrit :

et gcc 4.0 inventa les intrinsics SSE2 :o
Ca fait qquelques temps qu'on a plus besoin de descendre au niveau ASM pour vectoriser quoique ce soit


Quelle intéressante notion!
Soit dit en passant  
a) j'ai posté un désassemblage parce que le critère était la taille du code généré et incidemment mis à contribution g++ & intrinsics en amont.
b) les intrinsics viennent en droite ligne de chez Intel, historiquement gcc/g++ exposaient le tout via builtins.

Reply

Marsh Posté le 17-03-2007 à 02:10:21    

Joel F a écrit :

et gcc 4.0 inventa les intrinsics SSE2 :o
Ca fait qquelques temps qu'on a plus besoin de descendre au niveau ASM pour vectoriser quoique ce soit


sauf que la c un com qui doit tenir en 256b donc pas question de compiler quoi que se soit de haut niveau....

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed