Addition fausse dans un cas

Version imprimable

Bonjour tout le monde !
Je dois avoir la tête dans le c** car j'ai beau chercher je ne vois pas la différence entre ce code :
Code:

1 2 3 4 for (x=0 ; x<size ; x++) { dst[x]+=src[x]; }
et celui-ci :
Code:

1 2 3 4 5 6 7 8 9 10 11 for (x=0 ; x<size/8 ; x+=8) { dst[x]+=src[x]; dst[x+1]+=src[x+1]; dst[x+2]+=src[x+2]; dst[x+3]+=src[x+3]; dst[x+4]+=src[x+4]; dst[x+5]+=src[x+5]; dst[x+6]+=src[x+6]; dst[x+7]+=src[x+7]; }
Je précise que dst et src sont deux tableaux de type short*, et que taille est bien entendu divisible par 8. Dans le premier cas, le résultat est bon, pas dans le second...

Merci d'avance !

09/07/2007, 11h36
Jean-Marc.Bourguet

Pourquoi changes-tu la condition d'arret?
09/07/2007, 11h39
progfou

Eh bien, je fais 8 additions successives, il y a 8 fois moins de tours dans la boucle, non ?
09/07/2007, 11h39
Jean-Marc.Bourguet

Tu modifies deja ton pas.
09/07/2007, 11h39
progfou

:aie: le boulet...
Merci !
09/07/2007, 11h44
Médinoc

PS: Ton code ne marchera que si la taille est multiple de 8...
09/07/2007, 11h45
r0d

J'en profites que le sujet est résolu pour poser une question.
Il semble qu'avec les processeurs actuels, il est inutile de dérouler les boucles (en terme d'optimisation). Cependant, je ne trouve rien de précis à ce sujet, ni sur la toile, ni dans les bouquins que j'ai à ma disposition.
Est-ce que quelqu'un aurait quelques infos?
09/07/2007, 11h51
progfou

En général, sur les petites boucles, les compilateurs s'en sortent pas trop mal.
Mais il est possible de faire du cache blocking, en adaptant le déroulage de grosses boucles, pour améliorer la localité spatiale.
09/07/2007, 14h29
Charlemagne
Citation:

Envoyé par r0d

J'en profites que le sujet est résolu pour poser une question.
Il semble qu'avec les processeurs actuels, il est inutile de dérouler les boucles (en terme d'optimisation). Cependant, je ne trouve rien de précis à ce sujet, ni sur la toile, ni dans les bouquins que j'ai à ma disposition.
Est-ce que quelqu'un aurait quelques infos?

C'est pas tant la boucle développée qui fait améliorer la vitesse (ça joue quand même), mais plutôt les instructions utilisées à l'intérieur de la boucle. Il faudrait voir comment les compilos codent la boucle développée précédente (ça dépend des compilos de toute façon), mais je ne crois pas qu'il le fasse aussi bien qu'avec la boucle suivante.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 for (int i=0; i<n; i+=8) { int *px=&x[i], *py=y[i]; py[0]=px[0]; py[1]=px[1]; py[2]=px[2]; py[3]=px[3]; py[4]=px[4]; py[5]=px[5]; py[6]=px[6]; py[7]=px[7]; }
La grosse différence c'est que les index sont constants, et que le compilo peut utiliser des instructions assembleurs plus rapides (les décalages sont précalculés).
C'est l'une des 3-4 techniques de base pour améliorer les boucles.

Citation:

Envoyé par progfou

Mais il est possible de faire du cache blocking, en adaptant le déroulage de grosses boucles, pour améliorer la localité spatiale.

Le cache blocking n'a pas de rapport direct avec le développement des boucles. Une boucle non développée peut très bien utiliser la mémoire cache.
09/07/2007, 14h51
progfou
Le cache blocking a un rapport tout de même, puisque c'est diviser une boucle en deux (ou plus) pour améliorer la localité spatiale.

Ceci dit, dans les techniques d'optimisation de boucles, quelqu'un voit comment améliorer le problème suivant ?
Code:

1 2 3 4 5 6 7 8 for (j=0 ; j<sizeY ; j++) { for (i=0 ; i<sizeX ; i++) { px[i] = py[j+stride]; } }
Où stride est un décalage en mémoire du nombre d'octets correspondant ?
C'est un cas "d'école" de transposition, mais c'est quelque chose que l'on peut rencontrer dans le cas de filtres en image (où l'on utilise les pixels des lignes et des colonnes en même temps)...
Comment, donc, éviter le saut ?
09/07/2007, 15h02
Charlemagne
C'est bien ce que je dit: Y'a pas de rapport direct. Diviser une boucle en 2 (ou plus...)ne nécessite pas de développer cette boucle. Ton exemple divise bien une boucle en créant 2 boucles imbriquées...

Un stride, c'est un facteur multiplicatif sur l'index. Ce que tu décrit est un offset / décalage.
Rien de plus facile pour ôter un offsset:
Code:

1 2 3 4 5 6 7 8 float *p=py[offset]; for (j=0 ; j<sizeY ; j++) { for (i=0 ; i<sizeX ; i++) { px[i] = p[j]; } }

Oups, effectivement, problème mal décrit...
Je vais donner le vrai cas :

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
 
for( UInt y = 0; y < uiSizeY; y++)
{
	for( UInt x = 0; x < uiSizeX; x++)
	{
		Int iTempX;
		iTempX  = SrcX[x - 0];
		iTempX += SrcX[x + 1];
		iTempX  = iTempX << 2;
		iTempX -= SrcX[x - 1];
		iTempX -= SrcX[x + 2];
		iTempX += iTempX << 2;
		iTempX += SrcX[x - 2];
		iTempX += SrcX[x + 3];
 
		Int iTempY;
		iTempY  = SrcY[x - 0*iSrcStride];
		iTempY += SrcY[x + 1*iSrcStride];
		iTempY  = iTempY << 2;
		iTempY -= SrcY[x - 1*iSrcStride];
		iTempY -= SrcY[x + 2*iSrcStride];
		iTempY += iTempY << 2;
		iTempY += SrcY[x - 2*iSrcStride];
		iTempY += SrcY[x + 3*iSrcStride];
 
		Dest[x] = (iTempX + iTempY + 1) >> 1;
	}
}

Pour info, c'est un code qui fait de l'interpolation de mouvement. Dans mon cas, j'utilise les instructions SSE2, mais avant cela, j'aimerais réduire la complexité des accès.

09/07/2007, 15h15
Charlemagne

J'ai pas regardé ton code. Un stride ne se laisse pas ôter facilement , voir pas du tout. Essaye de le remplacer par des constantes, à la façon que j'expose plus haut, mais je suis pas convaincu du tout que ce soit possible.

Si par "interpolation de mouvement" tu entends "Motion Estimation", on pourra peut-être comparer les perfs avec mon implémentation...
09/07/2007, 15h23
progfou

C'est l'interpolation quart de pixel de h.264.
09/07/2007, 15h29
Charlemagne

ah ok. Je n'ai qu'une implémentation sur les pixels entiers.
Il paraît que ça n'apporte pas grand chose ces interpolations. (déjà pour pour les 1/2 pixels). Et puis ça ne peut se faire qu'autour de l'estimation à pixels entiers. Tu confirmes?
09/07/2007, 15h37
progfou

Je vais peut-être ouvrir un autre topic... :).

Ca apporte, car ça réduit quand même beaucoup les résidus après compensation de mouvement.

Citation:

Envoyé par Charlemagne

Et puis ça ne peut se faire qu'autour de l'estimation à pixels entiers

Ca je n'ai pas compris :aie: .
09/07/2007, 15h46
Charlemagne

Ca apporte, mais in fine ça apporte beaucoup sur la qualité/taille de la vidéo?

Citation:

Et puis ça ne peut se faire qu'autour de l'estimation à pixels entiers

Je veux dire que j'imagine que pour des raisons de performances on ne peut faire les interpolations que raisonablement dans le voisinage d'une première estimation, non?
09/07/2007, 15h51
progfou

La référence :
http://www.rgu.ac.uk/files/h264_interpred.pdf

C'est court, mais suffisant. Je n'ai pas les chiffres quand à l'intérêt, mais il me semble que c'est pas mal du tout, comparé à ce qu'il se faisait jusque là.
09/07/2007, 16h00
Charlemagne

Je sais pas maintenant, mais y'a 2-3 ans, H264 était aussi un champion de la lenteur. Du genre, il fallait le PC dernier cri pour lire une vidéo.
09/07/2007, 17h43
progfou

Le codec x264 est particulièrement meilleur, il suffit d'avoir 800MHz pour décoder un flux...
Disons que les techniques de codage mises en oeuvre dans H.264 permettent un gain (en terme de débit) de 50% à qualité égale (en HD 1080i).

Ceci explique aussi cela... :).