Optimisation de code C++

Version imprimable

Bonjour a tous...

Voila je dois remplacer une librairie qui me fait ce calcul, mais j'ai un temps de calcul bien supérieur au leur. Je voulais savoir si quelqu'un a des idées d'optimisation qui pourrait diminuer cet écart de temps de calcul (2 à 3 fois supérieur que ce qu'il est possible de faire).

Pour le contexte, c'est l'extraction d'une coupe 2D dans un volume 3D.

J'ai calculé un vecteur de déplacement équivalent au déplacement entre deux pixels. 1 Sur l'axe des X l'autre sur l'axe des Y. a chaque itération (et donc a chaque pixel) j'effectue mon déplacement, regarde le voxels qui contient le point et en extrait la données.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int CVolume::RasterizeSliceNearest(void* aiSlice,
							const double* adOrigVOL, 
							const double* adVectorDepVOL,
							const double* adResVOL, 
							const int iNbWidthVIEW, 
							const int iNbHeightVIEW,	
							const int iValMinVOL)
{
	double adCurPosVOL[3];
	double adOrigPosVOL[3];
	double adVectorPosVOLX[3];
	double adVectorPosVOLY[3];
	int aiVoxelVOL[3];
	short* aiVolumeTemp;
	unsigned char* acVolumeTemp;
	int iPos=0;
 
	for(int k = 0 ; k<3;k++)
	{
		adOrigPosVOL[k] = adOrigVOL[k]/adResVOL[k];
		adVectorPosVOLX[k] = adVectorDepVOL[k]/adResVOL[k];
		adVectorPosVOLY[k] = adVectorDepVOL[k+3]/adResVOL[k];
	}
 
	aiVolumeTemp = (short*)m_aiPixelsValue;
	for(int i=0; i<iNbHeightVIEW;i++)
	{
		adOrigPosVOL[0]+=adVectorPosVOLY[0];
		adOrigPosVOL[1]+=adVectorPosVOLY[1];
		adOrigPosVOL[2]+=adVectorPosVOLY[2];
		adCurPosVOL[0] = adOrigPosVOL[0];
		adCurPosVOL[1] = adOrigPosVOL[1];
		adCurPosVOL[2] = adOrigPosVOL[2];
		for(int j=0;j<iNbWidthVIEW;j++)
		{
			adCurPosVOL[0] += adVectorPosVOLX[0];
			adCurPosVOL[1] += adVectorPosVOLX[1];
			adCurPosVOL[2] += adVectorPosVOLX[2];
			aiVoxelVOL[0] = (int)adCurPosVOL[0];
			aiVoxelVOL[1] = (int)adCurPosVOL[1];
			aiVoxelVOL[2] = (int)adCurPosVOL[2];
			if(adCurPosVOL[0]>=0&&adCurPosVOL[1]>=0&&adCurPosVOL[2]>=0
					&&aiVoxelVOL[0]<GetVolDimWidth()&&aiVoxelVOL[1]<GetVolDimHeight()&&aiVoxelVOL[2]<GetVolDimDepth())
			{
				((short*)aiSlice)[iPos] = (short)aiVolumeTemp[aiVoxelVOL[0]+m_aiDecalInWidthPos[aiVoxelVOL[1]]+m_aiDecalInWidthHeightPos[aiVoxelVOL[2]]];//Aislice est de type void * (tableau à 1 dimension)
//m_aiDecalInWidthHeightPos contient les déplacement de mon tableau
 
			}
			else
			{
				((short*)aiSlice)[iPos] = (short)iValMinVOL;
			}
			iPos++;
		}
	}
return 0;
}

19/04/2010, 10h35
white_tentacle

Une idée comme ça, c'est de sortir de ta boucle toutes les opérations qui ne dépendent ni de i, ni de j (toutes celles qui ne dépendent pas de ipos en fait).

Ca devrait largement améliorer tes performances ;).
19/04/2010, 11h34
Thauglor

a savoir lesquelles? car je pense les avoir toute enlevées.

En fait je me sers de mes boucles également pour ajouter chaque composante de mon vecteur. je ne peux sortir ce calcul de mes boucles.

C'est plus un problème de syntaxe ( stockage et accès de données) je pense car niveau algorithmique itérative je pense avoir fait le tour
19/04/2010, 11h47
camboui

Les appels à GetVolDimWidth(), GetVolDimHeight() et GetVolDimDepth() peuvent être sortis de la boucle.
19/04/2010, 11h51
Thauglor

c'est des fonctions inline

Code:

inline int GetVolDimWidth(void){return m_aiVolDim[0];};

dans le doute j'ai remplacé les appels à ces fonctions par les

m_aiVolDim[0] correspondant... Toujours trop de temps de calcul
19/04/2010, 14h14
camboui

Calcul parallèle -> MMX, SSE, assembleur, etc...

Effectivement, j'ai regardé un peu vite, pas évident de sortir des choses de la boucle.

Tu peux tenter ceci :
Code:

1 2 3 4 5 6 7 int CVolume::RasterizeSliceNearest(void* aiSlice, const double* __restricted__ adOrigVOL, const double* __restricted__ adVectorDepVOL, const double* __restricted__ adResVOL, const int iNbWidthVIEW, const int iNbHeightVIEW, const int iValMinVOL)
(plus tout à fait sûr de la position du __restricted__, ne marche qu'avec gcc, pour visual il y a un autre mot clé je crois). Ton optimiseur devrait pouvoir optimiser un peu plus. Ca n'explique toutefois pas un x3.

Sinon, mettre le m_aiVolDim[x] dans une variable de pile plutôt que dans le tableau peut aider (dépend du volume de données --> la variable se trouvera sur la pile ou dans un registre plutôt que dans ta ram, ça peut potentiellement réduire le nombre de page faults et augmenter les perfs).

19/04/2010, 15h27
Arzar

Citation:

Envoyé par camboui

Calcul parallèle -> MMX, SSE, assembleur, etc...

Il me semble qu'il y a d'autres choses à tenter avant d'en arriver à ce point...

Il faudrait surtout savoir ce que représente et comment ont été alloué m_aiPixelsValuesavoir, aiSlice, m_aiDecalInWidthPos et m_aiDecalInWidthHeightPos.

Il y a beaucoup de perf à gagner en parcourant ces images - je suppose que c'est des images ? - de la bonne manière, c'est à dire en optimisant la localité du cache (par exemple en parcourant sous forme de tuile si je me souviens bien)
Enfin bref, malheureusement, je ne suis pas assez compétent dans ce domaine pour en dire plus. :aie:

( :summon: Joel F :mrgreen:)
19/04/2010, 15h53
camboui

Si la librairie dont question au début est vraiment 2-3x plus rapide sur ce simple code, je suis quasi sûr qu'elle utilise des outils inaccessibles en C++ tel quel (en supposant que la comparaison ait été bien faite en mode release, avec les bonnes optimizations, etc). Itaque je suggérai MMX, SSE, etc.

Citation:

Envoyé par Arzar

Il me semble qu'il y a d'autres choses à tenter avant d'en arriver à ce point...

Il faudrait surtout savoir ce que représente et comment ont été alloué m_aiPixelsValuesavoir, aiSlice, m_aiDecalInWidthPos et m_aiDecalInWidthHeightPos.
Code:

1 2 3 4 m_aiPixelsValue = new short[GetVolDimWidth()*GetVolDimHeight()*GetVolDimDepth()]; aiSlice= new short[m_iWidth * m_iHeight]; m_aiDecalInWidthHeightPos = new int[m_aiVolDim[2]]; m_aiDecalInWidthPos = new int[m_aiVolDim[1]];
Je remplit m_aiDecalInWidthHeightPos et m_aiDecalInWidthPos une seule fois. ce tableau m'évite des i*m_iWidth * m_iHeight ou j*m_iWidth à chaque itération. C'est une optimisation que j'ai fait pour avoir des "+" au lieu de "*" quand je calcul la position dans mon volume.

Citation:

Envoyé par Arzar

Il y a beaucoup de perf à gagner en parcourant ces images - je suppose que c'est des images ? - de la bonne manière, c'est à dire en optimisant la localité du cache (par exemple en parcourant sous forme de tuile si je me souvient bien)

AiSlice est une image si l'on peut dire. Comme tu peut le voir au dessus c'est un tableau à une dimension (mais utilisé comme s'il était à deux dimensions).

Pour ce qui est de m_aiPixelsValue c'est un tableau à une dimension utilisé pour simulé un tableau à 3 dimensions (coordonnées homogènes d'un volume 3D, construit à partir d'images DICOM)

J'en extirpe une coupe définit par une orientation que ej récupère par une matrice. Grâce à elle je calcul mes vecteur de déplacement dans le volume entre chaque Pixels

19/04/2010, 16h01
Thauglor

Citation:

Envoyé par camboui

Si la librairie dont question au début est vraiment 2-3x plus rapide sur ce simple code, je suis quasi sûr qu'elle utilise des outils inaccessibles en C++ tel quel (en supposant que la comparaison ait été bien faite en mode release, avec les bonnes optimizations, etc). Itaque je suggérai MMX, SSE, etc.

Mode release : Oui
En général 2X plus rapide.

optimisation : code tel que présenter

Citation:
Envoyé par white_tentacle
Effectivement, j'ai regardé un peu vite, pas évident de sortir des choses de la boucle.

Tu peux tenter ceci :
Code:

1 2 3 4 5 6 7 int CVolume::RasterizeSliceNearest(void* aiSlice, const double* __restricted__ adOrigVOL, const double* __restricted__ adVectorDepVOL, const double* __restricted__ adResVOL, const int iNbWidthVIEW, const int iNbHeightVIEW, const int iValMinVOL)
(plus tout à fait sûr de la position du __restricted__, ne marche qu'avec gcc, pour visual il y a un autre mot clé je crois). Ton optimiseur devrait pouvoir optimiser un peu plus. Ca n'explique toutefois pas un x3.

Sinon, mettre le m_aiVolDim[x] dans une variable de pile plutôt que dans le tableau peut aider (dépend du volume de données --> la variable se trouvera sur la pile ou dans un registre plutôt que dans ta ram, ça peut potentiellement réduire le nombre de page faults et augmenter les perfs).
J'ai pas compris ce que tu essayes de me faire faire et je ne trouve pas le mot clé correspondant sur Visual.
Tu peux me dire deux mots sur le restricted ou me donner un lien vers un article l'expliquant, pas réussit à trouver ça. J'ai du chercher un peu vite... Je continue à chercher.

Variable de pile??? j'ai pas compris :calim2:

19/04/2010, 16h15
Thauglor

Citation:

Envoyé par camboui

Calcul parallèle -> MMX, SSE, assembleur, etc...

Ouhlala... Euh ça va un peu loin pour moi la. MMX SSE???

Le programme doit tourner sur des config assez faibles, je doute que le parallélisme soit un bon choix avec une machine qui je ne suis pas sur, n'aura pas de double coeur. après c'est un peu trop loin de mon domaine de compétence.
19/04/2010, 16h59
camboui

SIMD (Sngle Instruction Multiple Data): intruction unique sur plusieurs données, ça existe depuis le pentium premier du nom et ça porte le doux nom de MMX (multimedia extension). Avec les pentiums suivants il y a eu SSE, version 4 depuis 2-3 ans. Chez AMD il y a les instructions 3Dnow! etc. Pas besoin de double coeur.
Ce n'est donc pas récent, loin de là.
Les applications 3D, codecs vidéo, etc, doivent passer par là s'ils veulent être performants.
Et si ça peut te rassurer, ça dépasse mes compétences à moi aussi :aie:

Mais quand un code simple en apparence optimum qui ne fait aucun appel io est 2-3 foix plus lent qu'un autre, on peut soupçonner un peu d'assembleur derrière pour le plus rapide. Mais je peux me tromper.
C'est quoi la librairie d'origine ?
19/04/2010, 17h09
Thauglor

Citation:

Envoyé par camboui

Mais quand un code simple en apparence optimum qui ne fait aucun appel io est 2-3 foix plus lent qu'un autre, on peut soupçonner un peu d'assembleur derrière pour le plus rapide. Mais je peux me tromper.
C'est quoi la librairie d'origine ?

C'est la librairie d'une boite spécialisé dans le domaine de la reconstruction 3D. j'ai leur doc mais rien de bien précis sur les méthodes employées. Mais l'assembleur n'est pas impossible...

Par contre est ce que ce que tu me proposes s'adapte suivant la technologie de processeur ou est ce qu'il faut coder en connaissant le processeur qui sera utilisé? La je suis ultra profane.

EDIT :
je viens de regarder cet article pour comprendre ce que tu me propose :

http://fr.wikipedia.org/wiki/Single_..._Multiple_Data

Mais je en vois pas comment profiter de cette technologie, alors que le processeur qui va servir à effectuer ces calculs n'est pas unique et pourra évoluer au cours du temps.
19/04/2010, 17h22
Thauglor

Je viens de penser a quelque chose.

La méthode que 'j utilise est contenu dans une classe.

La méthode de l'autre version (plus rapide) est appelé dans une librairie. Cela peut il jouer
19/04/2010, 17h31
white_tentacle

Citation:

Envoyé par Thauglor

J'ai pas compris ce que tu essayes de me faire faire et je ne trouve pas le mot clé correspondant sur Visual.

Changer la signature de ta fonction pour dire au compilateurs que tes tableaux sont bien des tableaux distincts, et qu'il a le droit de faire certaines optimisations qu'il n'aurait pas le droit de faire sinon. Le mot clé sous visual est __restrict (et __restrict__ sous gcc, pas __restricted__, comme tu peux le voir, ça s'utilise tous les jours ;) ).

Citation:

Tu peux me dire deux mots sur le restricted ou me donner un lien vers un article l'expliquant, pas réussit à trouver ça. J'ai du chercher un peu vite... Je continue à chercher.

http://msdn.microsoft.com/en-us/libr...=VS.80%29.aspx

Citation:

Variable de pile??? j'ai pas compris :calim2:

Tes variables locales à la fonction sont allouées dans la pile. Les variables allouées avec new ou malloc sont allouées dans le tas. La pile est toujours dans le cache processeur, mais la taille de la mémoire fait que les variables du tas n'y sont que lorsqu'on y accède, chargées par page. Si tu accèdes régulièrement à une variable qui est dans le tas, il peut être intéressant de la copier sur la pile pour en accélérer les accès (cela dit, il est possible que ton compilateur le fasse déjà pour toi, mais sur un élément d'un tableau j'ai des doutes).
19/04/2010, 17h40
Thauglor

Citation:

Envoyé par white_tentacle

Tes variables locales à la fonction sont allouées dans la pile. Les variables allouées avec new ou malloc sont allouées dans le tas. La pile est toujours dans le cache processeur, mais la taille de la mémoire fait que les variables du tas n'y sont que lorsqu'on y accède, chargées par page. Si tu accèdes régulièrement à une variable qui est dans le tas, il peut être intéressant de la copier sur la pile pour en accélérer les accès (cela dit, il est possible que ton compilateur le fasse déjà pour toi, mais sur un élément d'un tableau j'ai des doutes).

Est ce qu'une variable membre dans une classe, est considérée comme locale à une fonctions de cette même classe, car ici c'est mon cas, tous mes tableaux sont membres de cette classe.

Le mot clef _Restrict ne me fait gagner aucun temps d'après mes nouveaux tests. mais j'ai l'impression que les valeurs de temps que j'obtiens sont plus stables et moins éparses. c'est peut être une coïncidence non?

Citation:

Est ce qu'une variable membre dans une classe, est considérée comme locale à une fonctions de cette même classe, car ici c'est mon cas, tous mes tableaux sont membres de cette classe.

Tout dépend où a été alloué ton objet, et comment a été alloué ton tableau. Petit exemple :
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 class A { public: int toto[3]; A() {}; }; class B { public: int* toto; B() { toto = new int[3]; } ~B() { delete[] toto; } }; main() { A a1; A* a2 = new A(); B b1; B* b2 = new B(); delete b2; delete a2; }
Dans ce cas :

a1 est alloué sur la pile, donc a1.toto aussi
a2 est alloué dans le tas, donc a2.toto aussi
b1 est alloué sur la pile, mais b1.toto est alloué avec new, donc dans le tas
b2 est alloué dans le tas, et b2.toto aussi

Cela dit, si tous tes tableaux sont membres de la même classe, il y a fort à parier qu'ils soient dans le même espace mémoire, et donc que ça ne cause pas spécialement de page faults. Il me semble qu'avec le perfmon de windows, tu peux vérifier le nombre de page faults de ton programme, et voir si tes problèmes de perf viennent de là.

L'autre possibilité, c'est que la lib utilise un algorithme plus efficace que le tien (mais là, je ne peux pas t'aider). Une différence de x3, il y a soit un problème dans ton agencement mémoire (mais j'ai pas l'impression que ce soit le cas), soit (plus probable ici) des optimisations algorithmiques que tu ne fais pas.

Sinon, je ne pense pas que ça change grand chose, mais pourquoi ne déclares-tu pas aiVoxelVol en short ? Tu passes ton temps à le caster de short vers int et inversement, c'est sûr que c'est du temps perdu :) (et je crois que tu peux supprimer totalement cette variable et utiliser directement adCurPosVOL, sauf si j'ai fait une erreur de lecture).

20/04/2010, 11h26
Thauglor

Citation:

Envoyé par white_tentacle

Sinon, je ne pense pas que ça change grand chose, mais pourquoi ne déclares-tu pas aiVoxelVol en short ? Tu passes ton temps à le caster de short vers int et inversement, c'est sûr que c'est du temps perdu :) (et je crois que tu peux supprimer totalement cette variable et utiliser directement adCurPosVOL, sauf si j'ai fait une erreur de lecture).

Je la cast en int (d'où je le cast en short????) car j'ai besoin de ne garder que la partie entière de adCurPosVOL et en parallèle à cause de mes plus égales, je ne dois pas perdre d'infos sur adCurPosVOL ... D'où les deux variables. (je ne les cast qu'une fois par boucle justement pour ne pas perdre de temps a le faire plusieurs fois)