Discussion :

[progfou]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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 ...

[PRomu@ld]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[progfou]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

j*width + i

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

En C (idem pour j évidemment).
J'ai implémenté la solution, et je tombe "OutOfRange"...

[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

[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.

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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