Optimisation d'une fonction img 2D

Optimisation d'une fonction img 2D - C - Programmation

Marsh Posté le 23-02-2006 à 11:49:58    

A coup de grof j'ai remarque que cette partie de code prenait 50% du temps du rendu :S
Quel modifs je pourrais fait pour rendre cette partie un peu plus rapide ?  (mmx?)
 
ici l'algo prend juste les 8 points voisin dun pixels et fait la moyenne, reduce est fixe a 3
eg :  trilinearfilter(img,3,640,480)
 

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     BYTE *dest;
  5.     int len=width/reduce*height/reduce*3;
  6.     dest=malloc(len);
  7.     for(i=0;i<width/reduce;i++)
  8.     {
  9.         for(j=0;j<height/reduce;j++)
  10.         {
  11.             int cp=(1+j*reduce)*width+(1+i*reduce);
  12.             int rp=j*width/reduce+i;
  13.             int a1=max(cp-width-1,0);
  14.             int a2=max(cp-width,0);
  15.             int a3=max(cp-width+1,0);
  16.             int a4=max(cp-1,0);
  17.             int a6=min(cp+1,width*height);
  18.             int a7=min(cp+width-1,width*height);
  19.             int a8=min(cp+width,width*height);
  20.             int a9=min(cp+width+1,width*height);
  21.             dest[rp*3+0]=(image[a1*3+0]+image[a2*3+0]+image[a3*3+0]+image[a4*3+0]+image[a6*3+0]+image[a7*3+0]+image[a8*3+0]+image[a9*3+0])/8;
  22.             dest[rp*3+1]=(image[a1*3+1]+image[a2*3+1]+image[a3*3+1]+image[a4*3+1]+image[a6*3+1]+image[a7*3+1]+image[a8*3+1]+image[a9*3+1])/8;
  23.             dest[rp*3+2]=(image[a1*3+2]+image[a2*3+2]+image[a3*3+2]+image[a4*3+2]+image[a6*3+2]+image[a7*3+2]+image[a8*3+2]+image[a9*3+2])/8;
  24.         }
  25.     }
  26.     memcpy(image,dest,len);
  27.     free(dest);
  28. }


Message édité par red faction le 23-02-2006 à 11:50:54
Reply

Marsh Posté le 23-02-2006 à 11:49:58   

Reply

Marsh Posté le 23-02-2006 à 12:07:13    

il y a beaucoup de choses que tu peux pré calculées ('height/reduce', width*height, ...) quand meme, et utilises plus de constantes
 
aussi vérifie l'ordre dans le quel tu accedes aux éléments pour optimiser l'utilisation du cache, la tu parcours ton image en width->height et si c'est équivalent à un tableau [height][width] c'est pas bon

Reply

Marsh Posté le 23-02-2006 à 12:38:23    

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     BYTE *dest,*dp;
  5.     int destwidth=width/reduce;
  6.     int destheight=height/reduce;
  7.     int totalsize=width*height;
  8.     int len=destwidth*destheight*3;
  9.     dp=dest=malloc(len);
  10.     for(j=0;j<destheight;j++)
  11.     {
  12.         for(i=0;i<destwidth;i++)
  13.         {
  14.             int cp=(1+j*reduce)*width+(1+i*reduce);
  15.             int cpup=cp-width;
  16.             int cpdown=cp+width;
  17.             int a1=3*max(cpup-1,0);
  18.             int a2=3*max(cpup,0);
  19.             int a3=3*max(cpup+1,0);
  20.             int a4=3*max(cp-1,0);
  21.             int a6=3*min(cp+1,totalsize);
  22.             int a7=3*min(cpdown-1,totalsize);
  23.             int a8=3*min(cpdown,totalsize);
  24.             int a9=3*min(cpdown+1,totalsize);
  25.             *dp=(image[a1+0]+image[a2+0]+image[a3+0]+image[a4+0]+image[a6+0]+image[a7+0]+image[a8+0]+image[a9+0])>>3; dp++;
  26.             *dp=(image[a1+1]+image[a2+1]+image[a3+1]+image[a4+1]+image[a6+1]+image[a7+1]+image[a8+1]+image[a9+1])>>3; dp++;
  27.             *dp=(image[a1+2]+image[a2+2]+image[a3+2]+image[a4+2]+image[a6+2]+image[a7+2]+image[a8+2]+image[a9+2])>>3; dp++;
  29.         }
  30.     }
  31.     memcpy(image,dest,len);
  32.     free(dest);
  33. }

Reply

Marsh Posté le 23-02-2006 à 12:55:33    

si reduce, width et height ne changent pas d'un rendu à l'autre, le variable cp et celles qui en dépendent peuvent etre précalculées dans une table au moment ou reduce, width et height sont fixés


Message édité par skelter le 23-02-2006 à 12:55:50
Reply

Marsh Posté le 23-02-2006 à 13:03:39    

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     BYTE *dest,*dp;
  5.     int destwidth=width/reduce;
  6.     int destheight=height/reduce;
  7.     int totalsize=width*height;
  8.     int len=destwidth*destheight*3;
  9.     dp=dest=malloc(len);
  10.     for(j=0;j<destheight;j++)
  11.     {
  12.         int cp=(j*width*reduce)+1;
  13.         for(i=0;i<destwidth;i++)
  14.         {
  15.             int cpup=cp-width;
  16.             int cpdown=cp+width;
  17.             BYTE *a0=image+3*max(cpup-1,0);
  18.             BYTE *a1=image+3*max(cpup,0);
  19.             BYTE *a2=image+3*max(cpup+1,0);
  20.             BYTE *a3=image+3*max(cp-1,0);
  21.             BYTE *a4=image+3*min(cp+1,totalsize);
  22.             BYTE *a5=image+3*min(cpdown-1,totalsize);
  23.             BYTE *a6=image+3*min(cpdown,totalsize);
  24.             BYTE *a7=image+3*min(cpdown+1,totalsize);
  25.             *dp=(*(a0+0)+*(a1+0)+*(a2+0)+*(a3+0)+*(a4+0)+*(a5+0)+*(a6+0)+*(a7+0))>>3; dp++;
  26.             *dp=(*(a0+1)+*(a1+1)+*(a2+1)+*(a3+1)+*(a4+1)+*(a5+1)+*(a6+1)+*(a7+1))>>3; dp++;
  27.             *dp=(*(a0+2)+*(a1+2)+*(a2+2)+*(a3+2)+*(a4+2)+*(a5+2)+*(a6+2)+*(a7+2))>>3; dp++;
  28.             cp+=reduce;
  29.         }
  30.     }
  31.     memcpy(image,dest,len);
  32.     free(dest);
  33. }


Message édité par red faction le 23-02-2006 à 13:32:36
Reply

Marsh Posté le 23-02-2006 à 13:27:17    

euh tu redéclares tes variables à chaque tour de boucle, là...[:pingouino]

Message cité 2 fois

---------------
Can't buy what I want because it's free -
Reply

Marsh Posté le 23-02-2006 à 13:33:25    

ca pose un probleme ?

Reply

Marsh Posté le 23-02-2006 à 13:34:58    

à tester.[:skeye]
Sors les déclarations de la boucle, au pire ce sera pareil...et au mieux tu éviteras la création/destruction à chaque tour.


---------------
Can't buy what I want because it's free -
Reply

Marsh Posté le 23-02-2006 à 13:39:14    

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     int cp,cpup,cpdown;
  5.     BYTE *dest,*dp,*a0,*a1,*a2,*a3,*a4,*a5,*a6,*a7;
  6.     int destwidth=width/reduce;
  7.     int destheight=height/reduce;
  8.     int totalsize=width*height;
  9.     int len=destwidth*destheight*3;
  10.     dp=dest=malloc(len);
  11.     for(j=0;j<destheight;j++)
  12.     {
  13.         cp=(j*width*reduce)+1;
  14.         for(i=0;i<destwidth;i++)
  15.         {
  16.             cpup=cp-width;
  17.             cpdown=cp+width;
  18.             a0=image+3*max(cpup-1,0);
  19.             a1=image+3*max(cpup,0);
  20.             a2=image+3*max(cpup+1,0);
  21.             a3=image+3*max(cp-1,0);
  22.             a4=image+3*min(cp+1,totalsize);
  23.             a5=image+3*min(cpdown-1,totalsize);
  24.             a6=image+3*min(cpdown,totalsize);
  25.             a7=image+3*min(cpdown+1,totalsize);
  26.             *dp++=(*(a0+0)+*(a1+0)+*(a2+0)+*(a3+0)+*(a4+0)+*(a5+0)+*(a6+0)+*(a7+0))>>3;
  27.             *dp++=(*(a0+1)+*(a1+1)+*(a2+1)+*(a3+1)+*(a4+1)+*(a5+1)+*(a6+1)+*(a7+1))>>3;
  28.             *dp++=(*(a0+2)+*(a1+2)+*(a2+2)+*(a3+2)+*(a4+2)+*(a5+2)+*(a6+2)+*(a7+2))>>3;
  29.             cp+=reduce;
  30.         }
  31.     }
  32.     memcpy(image,dest,len);
  33.     free(dest);
  34. }

 
40 ms

Reply

Marsh Posté le 23-02-2006 à 13:42:28    

Bon après tu peux p-e gagner en déroulant la boucle. Du genre remplacer ton i++ par un i+=4 et dérouler le contenu sur 4...


---------------
Can't buy what I want because it's free -
Reply

Marsh Posté le 23-02-2006 à 13:42:28   

Reply

Marsh Posté le 23-02-2006 à 13:43:15    

(si tu as un multiple de 4, évidemment. :D)
 
...et plus éventuellement (8, 16...?), faut voir ce que t'y gagnes et si tu peux.:o


Message édité par skeye le 23-02-2006 à 13:44:22

---------------
Can't buy what I want because it's free -
Reply

Marsh Posté le 23-02-2006 à 13:43:53    

si je maitrisait les template :p mais bon le projet est en C

Message cité 1 fois
Reply

Marsh Posté le 23-02-2006 à 13:46:28    

(en faire plusieurs à la suite te permettrait de réutiliser tes indices aX au lieu de les recalculer pour chaque...;))


---------------
Can't buy what I want because it's free -
Reply

Marsh Posté le 23-02-2006 à 14:01:30    

red faction a écrit :

si je maitrisait les template :p mais bon le projet est en C


 
meme avec les templates du c++ tu ne pourrais pas dérouler une boucle dont le nombre d'itération n'est pas connu à la compilation, et un bon compilateur peu faire la meme chose
 
que représente width, height et reduce ? si c'est fixe entre chaque rendu tu peux tout précalculé

Reply

Marsh Posté le 23-02-2006 à 14:15:30    

skeye a écrit :

euh tu redéclares tes variables à chaque tour de boucle, là...[:pingouino]


ce qui ne change rien. plutot que d'optimiser à l'aveugle, regarde l'assembleur et fait des mesures. je suis pas sur du tout qu'il y ait une différence entre ton code du début et le dernier.
 
 
par contre ça :
 
#
           a0=image+3*max(cpup-1,0);
#
           a1=image+3*max(cpup,0);
#
           a2=image+3*max(cpup+1,0);
 
 
 
t'as certainement moyen d'éviter de faire ces 3 max. idem pour les min.

Message cité 1 fois
Reply

Marsh Posté le 23-02-2006 à 14:17:27    

skeye a écrit :

euh tu redéclares tes variables à chaque tour de boucle, là...[:pingouino]


mais cesses donc de dire des anneries [:pingouino]

Message cité 1 fois
Reply

Marsh Posté le 23-02-2006 à 14:19:25    

taz a raison. Par exemple regarde ce que ton compilo fais de ca :
 

Code :
  1. int cp=(1+j*reduce)*width+(1+i*reduce);


 
s'ils te sort bien les invariants de la boucle et remplace ta multiplication par un increment tout seul comme un grand, bin change rien, sinon fais le, la tu fais 3muls par pixel qui servent a rien


Message édité par chrisbk le 23-02-2006 à 14:20:06
Reply

Marsh Posté le 23-02-2006 à 14:20:17    

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     BYTE *cp,*cpup,*cpdown;
  5.     BYTE *dest,*dp,*a0,*a1,*a2,*a3,*a4,*a5,*a6,*a7;
  6.     BYTE *lastp=image+(width*height*3);
  7.     int linewidth=3*width;
  8.     int destwidth=width/reduce;
  9.     int destheight=height/reduce;
  10.     int len=destwidth*destheight*3;
  11.     dp=dest=malloc(len);
  12.     for(j=0;j<destheight;j++)
  13.     {
  14.         cp=image+j*reduce*linewidth+3;
  15.         for(i=0;i<destwidth;i++)
  16.         {
  17.             cpup=cp-linewidth;
  18.             cpdown=cp+linewidth;
  19.             a0=max(cpup-3,image);
  20.             a1=max(cpup,image);
  21.             a2=max(cpup+3,image);
  22.             a3=max(cp-3,image);
  23.             a4=min(cp+3,lastp);
  24.             a5=min(cpdown-3,lastp);
  25.             a6=min(cpdown,lastp);
  26.             a7=min(cpdown+3,lastp);
  27.             *dp++=(*(a0+0)+*(a1+0)+*(a2+0)+*(a3+0)+*(a4+0)+*(a5+0)+*(a6+0)+*(a7+0))>>3;
  28.             *dp++=(*(a0+1)+*(a1+1)+*(a2+1)+*(a3+1)+*(a4+1)+*(a5+1)+*(a6+1)+*(a7+1))>>3;
  29.             *dp++=(*(a0+2)+*(a1+2)+*(a2+2)+*(a3+2)+*(a4+2)+*(a5+2)+*(a6+2)+*(a7+2))>>3;
  30.             cp+=reduce*3;
  31.         }
  32.     }
  33.     memcpy(image,dest,len);
  34.     free(dest);
  35. }

Reply

Marsh Posté le 23-02-2006 à 14:23:18    

sinon tu fais des alias plein pot, d'une part ca peut perturber le compilo et d'autre part ca te fais faire un quintal d'addition inutile (tous tes a1...an)
 
Vu la facon dont tu accede à tes données, je crains qu'il n'y ai pas grand chose a faire en mmx
 
oups pardon c'est red faction le roi de l'alias
 
 

Code :
  1. *(a0+0)


 
a part rendre la lecture penible, c'est quoi l'interet par rapport a a0[0] ?

Message cité 2 fois
Message édité par chrisbk le 23-02-2006 à 14:24:35
Reply

Marsh Posté le 23-02-2006 à 14:27:45    

Premiere version : 1.5s
derniere : 260ms

Reply

Marsh Posté le 23-02-2006 à 14:29:01    

chrisbk a écrit :

sinon tu fais des alias plein pot, d'une part ca peut perturber le compilo et d'autre part ca te fais faire un quintal d'addition inutile (tous tes a1...an)
 
Vu la facon dont tu accede à tes données, je crains qu'il n'y ai pas grand chose a faire en mmx
 
oups pardon c'est red faction le roi de l'alias

 

Code :
  1. *(a0+0)


 
a part rendre la lecture penible, c'est quoi l'interet par rapport a a0[0] ?


c quoi se bo*** :o  je demande comment ameliorer on me dit : "tu peux pré calculées ('height/reduce', width*height, ...)"

Message cité 1 fois
Reply

Marsh Posté le 23-02-2006 à 14:29:06    

Une petite suggestion à propos de:
    memcpy(image,dest,len);
tu peux p-e t arranger pour faire les calculs inplace, avec un tableau plus petit (3 lignes de pxl) pour garder les valeurs initiales.

Reply

Marsh Posté le 23-02-2006 à 14:33:26    

Pour éviter les min et max, tu peux envisager de travailler sur une taille d image plus grande d un pixel sur chaque bord.

Message cité 1 fois
Reply

Marsh Posté le 23-02-2006 à 14:34:13    

chrisbk a écrit :


oups pardon c'est red faction le roi de l'alias



 
 :pfff:  

chrisbk a écrit :

Code :
  1. *(a0+0)


 
a part rendre la lecture penible, c'est quoi l'interet par rapport a a0[0] ?


Bon ok cest pa bon

Message cité 1 fois
Reply

Marsh Posté le 23-02-2006 à 14:34:28    

red faction a écrit :

c quoi se bo*** :o  je demande comment ameliorer on me dit : "tu peux pré calculées ('height/reduce', width*height, ...)"


 
du calme [:twixy] chu tellement pas reveilé que j'avais vu que le topic etait de toi :d

Reply

Marsh Posté le 23-02-2006 à 14:34:59    

nargy a écrit :

Pour éviter les min et max, tu peux envisager de travailler sur une taille d image plus grande d un pixel sur chaque bord.


 
oui mais il faut redecouper apres :/
 

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     BYTE *cp,*cpup,*cpdown;
  5.     BYTE *dest,*dp,*a0,*a1,*a2,*a3,*a4,*a5,*a6,*a7;
  6.     BYTE *lastp=image+(width*height*3);
  7.     int linewidth=3*width;
  8.     int destwidth=width/reduce;
  9.     int destheight=height/reduce;
  10.     int len=destwidth*destheight*3;
  11.     dp=dest=malloc(len);
  12.     for(j=0;j<destheight;j++)
  13.     {
  14.         cp=image+j*reduce*linewidth+3;
  15.         for(i=0;i<destwidth;i++)
  16.         {
  17.             cpup=cp-linewidth;
  18.             cpdown=cp+linewidth;
  19.             a0=max(cpup-3,image);
  20.             a1=max(cpup,image);
  21.             a2=max(cpup+3,image);
  22.             a3=max(cp-3,image);
  23.             a4=min(cp+3,lastp);
  24.             a5=min(cpdown-3,lastp);
  25.             a6=min(cpdown,lastp);
  26.             a7=min(cpdown+3,lastp);
  27.             *dp++=(a0[0]+a1[0]+a2[0]+a3[0]+a4[0]+a5[0]+a6[0]+a7[0])>>3;
  28.             *dp++=(a0[1]+a1[1]+a2[1]+a3[1]+a4[1]+a5[1]+a6[1]+a7[1])>>3;
  29.             *dp++=(a0[2]+a1[2]+a2[2]+a3[2]+a4[2]+a5[2]+a6[2]+a7[2])>>3;
  30.             cp+=reduce*3;
  31.         }
  32.     }
  33.     memcpy(image,dest,len);
  34.     free(dest);
  35. }


 
210 ms pour du 1994x2610, qui dit mieux ??
 
joffre une glace a celui qui me donne une meilleure solution

Message cité 1 fois
Message édité par red faction le 23-02-2006 à 14:36:56
Reply

Marsh Posté le 23-02-2006 à 14:35:14    

red faction a écrit :

:pfff:  


 
bah tu vas pas me quoter 15x non plus ?
 

red faction a écrit :


Bon ok cest pa bon


nan mais jpense ca change rien au code generer, c'est juste que c'est moche

Reply

Marsh Posté le 23-02-2006 à 14:38:22    

bah moi non plus jsuis pa reveille  
deja que jme suis amene a la bourre au taf  
 
10h30 c pa des heures :whistle:

Reply

Marsh Posté le 23-02-2006 à 14:53:53    

Allez, courage: découpe ton algo en:

  • bord supérieur
  • bord gauche - centre - bord droit
  • bord inférieur

Et fait sauter les a1, a2, etc. dans la partie du centre....

Reply

Marsh Posté le 23-02-2006 à 15:39:10    

Taz a écrit :

ce qui ne change rien.


 
C'est bien ce que je disais, au pire c'est pareil.[:petrus75]
 

chrisbk a écrit :

mais cesses donc de dire des anneries [:pingouino]


 
C'est pas pour aujourd'hui, ça.[:dawa]
 
...et essayer de dérouler un peu la boucle si possible pour gagner sur les calculs de positions, aneries aussi? [:petrus dei]
 


---------------
Can't buy what I want because it's free -
Reply

Marsh Posté le 23-02-2006 à 16:00:53    

Citation :


Pour éviter les min et max, tu peux envisager de travailler sur une taille d image plus grande d un pixel sur chaque bord.


 
Peut ne s appliquer qu au tableau temporaire de 3 lignes.
Au total: Gain en mémoire + gain en cache + gain min/max
 

Reply

Marsh Posté le 24-02-2006 à 22:27:51    

red faction a écrit :


 
210 ms pour du 1994x2610, qui dit mieux ??
 
joffre une glace a celui qui me donne une meilleure solution


Bah, tu vas voir l'API de ta carte graphique...
Sinon la suggestion de Lam's et nargy est certainement la meilleure, ton temps de calcul devrait faire un bond.
Ou au minimum vérifie que min/max sont des macros et pas des appels de fonctions (en C, normalement c'est le cas).


Message édité par el muchacho le 25-02-2006 à 08:01:16
Reply

Marsh Posté le 25-02-2006 à 08:52:19    

personne m'écoute avec l'histoire des min/max à la con ...

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

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