[Optimisation]Eviter les boucles imbriquées

Version imprimable

Bonsoir tout le monde !
J'ai un code, tout fait, fonctionnel, mais qui doit probablement être optimisable.
Il s'agit d'un décodeur YUV, mais la partie qui m'intéresse peut en être indépendante (enfin, presque).

Donc, YUV format 4:2:0 (1U, 1V, 4Y) :
Shéma explicatif
Merci Wikipedia :).

Mes données sont stockées dans trois tableaux :

Code:

tab_y[width*height]

Contient toutes les luminances Y de l'image, c'est donc un tableau de taille largeur*hauteur (en octects).
Les deux autres sont sur le même modèle :
Code:

1 2 tab_u[(width*height)/4] tab_v[(width*height)/4]
Mais de taille 4 fois moindre, logique.

Le processus entame alors deux boucles imbriquées :
Code:

1 2 3 4 5 6 Pour i=1 to Width <div style="margin-left:40px">Pour j=1 to Height <div style="margin-left:40px">Y<-tab_y[j+width*i]; U<-tab_u[j/2 + (i/2)*(width/2)]; V<-tab_v[j/2 + (i/2)*(width/2)]; (R,G,B)=YUVToRGB(Y,U,V);</div>FinPour</div>FinPour
En clair, comment puis-je améliorer cette boucle ?
Merci d'avance de votre aide, je suis certain de trouver de bonnes idées:king:

22/02/2007, 02h14
souviron34

euh.....

Du vrai code serait pas mal...

Pour une optimisation dans ce genre de truc, c'est très dépendant du langage...

Mais déjà sur ce que tu donnes :

faire une variable contenant width/2
faire une variable contenant j/2 + i/2*(width/2)

Economie :

Width*Height*1 division (width/2)
+ Width*Height*2 divisions (i/2 et j/2)
+ Width*Height*1 multiplication (width/2)

Et je crois que (mais je crois que c'est dans les limites de boucles seulement) tu as inversé Width et Height... La boucle extérieure DOIT être sur les lignes... et c'est ce que dit le code ... i*width+j ...

Citation:

Et je crois que (mais je crois que c'est dans les limites de boucles seulement) tu as inversé Width et Height... La boucle extérieure DOIT être sur les lignes... et c'est ce que dit le code ... i*width+j ...

Oui, c'est à vérifier.

Pour ce qui est du code, Il y a du travail à faire ici :
Code:

1 2 U<-tab_u[j/2 + (i/2)*(width/2)]; V<-tab_v[j/2 + (i/2)*(width/2)];
Déjà, il faut que tu gardes width/2 en variable extérieure à tes boucles imbriqués. Il s'agit d'une constante, rien ne sert de la calculer à chaque tours de boucles.

Autre chose, tu peux éviter une division par deux en factorisant par un demi. Mais tu peux aussi multiplier par 0.5, c'est souvent plus rapide. Suivant ton langage, tu peux éventuellement effectuer un décalage de bits.

Enfin, comme tu fais deux fois ce calcul, il faut que tu le calcules en une seule fois. Ainsi, ton code devrait être ça (aux problèmes de boucles imbriquées près)
Code:

1 2 3 4 5 6 7 8 9 10 11 WIDTH_2 <- width * 0.5; Pour i=1 to Width Pour j=1 to Height k <- (j + i * WIDTH_2) * 0.5; Y<-tab_y[j+width*i]; U<-tab_u[k]; V<-tab_v[k]; (R,G,B)=YUVToRGB(Y,U,V); FinPour FinPour
Il doit être possible aussi d'en faire une version SSE (calcul de quatres valeurs RGB d'un seul coup).

22/02/2007, 08h49
progfou

Oui, il y a inversion, c'est bien :

Code:

j*width + i

:aie:

Je pense que la question est vraiment algorithmique, et pas liée au langage dans ce cas. Du coup, ta solution me plaît, PRomu@ld.
Je vais essayer, voir si je gagne un peu.
Petite précision, le code est destiné à un processeur type ARM, donc pas de SSE. Mais je creuserais l'idée ;).

Peut-on espérer virer l'imbrication ?

Edit: Je ne sais pas si ça peut jouer, mais les boucles commencent à 0, et non à 1 !
On a donc un :

Code:

for (i=0 ; i< width ; i++)

En C (idem pour j évidemment).
J'ai implémenté la solution, et je tombe "OutOfRange"...
22/02/2007, 09h39
random

on peut toujours remplacer deux boucles par une seule
pour x=1 to 10
pour y=1 to 10
par pour z=1 to 100
mais à chaque boucle on devra si on veut connaitre x et y
faire x=division entière(z,10)
y=modulo(z,10)
je ne suis pas certain que cela soit payant

A mon avis, toutes les optimisations proposées jusque ici n'apporterons rien, les compilateurs savent très bien faire eux même des choses comme extraire les invariants des boucles.

Une optimisation qui va apporter pas mal c'est de traiter 4 pixels à la fois, pour ne lire qu'une fois les valeurs U et V :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Pour i=1 to Width/2 Pour j=1 to Height/2 Y<-tab_y[j*2*width + i*2]; U<-tab_u[j*(width/2) + i]; V<-tab_v[j*(width/2) + i]; (R,G,B)=YUVToRGB(Y,U,V); Y<-tab_y[j*2*width + i*2 + 1]; (R,G,B)=YUVToRGB(Y,U,V); Y<-tab_y[j*2*width + i*2 + width]; (R,G,B)=YUVToRGB(Y,U,V); Y<-tab_y[j*2*width + i*2 + width + 1]; (R,G,B)=YUVToRGB(Y,U,V); FinPour FinPour

22/02/2007, 13h06
souviron34

Citation:

Envoyé par Sylvain Togni

A mon avis, toutes les optimisations proposées jusque ici n'apporterons rien, les compilateurs savent très bien faire eux même des choses comme extraire les invariants des boucles.

Ah oui ??? ou t'as vu ça ?? avec des flags (dépendants des compulateurs) tu peux optimiser certaines choses. Mais d'abord c'est pas par défaut, et ensuite ça ne résoud pas les problèmes de conception..

le problème des calculs d'indices dans les tableaux peut accélerer de 4 à 20 fois la vitesse...

Comme je l'ai suggéré ci-dessus et comme PRomu@ld l'a dit (et c'est indépendant du langage) :

sortir le width/2 des boucles
calculer une seule fois par i le i/2
calculer une seule fois par boucle intérieure le ((i/2)*(width/2))+(j/2)

Et ensuite c'est je pense dans le YUVtoRGB..

Sans doute aussi des simplifications dans les indices de tableaux...

YuvToRgb est et doit rester indépendante du type de format (aussi bien 4:4:4 que 4:2:0 etc.).
A l'intérieur, elle est optimisée.
Les améliorations à apporter sont donc dans la partie présentée ;) .

J'apporte une précision, concernant la méthode d'implémentation.
Le Bitmap en mémoire est accessible via un pointeur.
Celui-ci pointe, à l'initialisation, le premier pixel.
Le tableau du Bitmap est constitué ainsi :

Code:

|B|G|R|B|G|R| etc.

On voit donc ici qu'à chaque incrémentation dans les boucles initiales, il suffit d'ajouter une instruction :

Code:

p+=3

En considérant p comme le pointeur.
De plus, à chaque fin de ligne, il faut ajouter un offset qui est lié à la largeur d'une ligne en mémoire.

La proposition de Sylvain Togni, mise en parallèle de celle de PRomu@ld est sans doute le bout de mon aventure :mrgreen: .
Mon problème est de savoir comment jouer avec mon pointeur entre les deux.
Je donne ici le code "initial" :
Code:

1 2 3 4 5 6 7 8 9 10 Pour j=0 to Height <div style="margin-left:40px">Pour i=0 to Width Y<-tab_y[j+width*i]; U<-tab_u[j/2 + (i/2)*(width/2)]; V<-tab_v[j/2 + (i/2)*(width/2)]; (R,G,B)=YUVToRGB(Y,U,V); p+=3 FinPour</div>p+=offset FinPour
Comment me servir de vos codes ?
Je ne parviens pas à utiliser correctement mon pointeur...
Merci d'avance !

J'ai un peu modifié le code, pour utiliser le pointeur, mais je n'ai pas le bon résultat...
Où est mon erreur ?
Je ne la vois pas :cry: .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Pour j=0 to Height/2
 
    Pour i=0 to Width/2
 
        Y<-tab_y[j*2*width + i*2];
        U<-tab_u[j*(width/2) + i];
        V<-tab_v[j*(width/2) + i];
       (R,G,B)=YUVToRGB(Y,U,V); 
 
       p += 3;
 
        Y<-tab_y[j*2*width + i*2 + 1];
       (R,G,B)=YUVToRGB(Y,U,V); 
 
       p += offset;
 
        Y<-tab_y[j*2*width + i*2 + width + 1];
       (R,G,B)=YUVToRGB(Y,U,V); 
 
       p -= 3;
 
        Y<-tab_y[j*2*width + i*2 + width];
       (R,G,B)=YUVToRGB(Y,U,V); 
 
       p  = p - offset + 6;
 
    FinPour
 
    p += 2*offset;
FinPour

En gros, j'occupe la moitié de mon écran, et l'image est élargie par rapport à l'originale...
Merci d'avance de votre aide !