[C++] quelle structure de donnée utiliser pour stocker des vertices ?

Version imprimable

12/07/2007, 16h13
johnnyjohnny

[C++] quelle structure de donnée utiliser pour stocker des vertices ?

bonjour,

j'ai commencé une appli en opengl et j'ai une classe qui contient un vector pour stocker les vertices.
j'ai lu sur les tutoriaux de nehe qu'il était pas recommandé d'utiliser les vectors pour cela, pour des raisons de vitesse.
je débute en c++ et en opengl avec glut, et je voulais savoir quelle structure vous utilisez et pourquoi ou pas des vectors, histoire de prendre de bonnes habitudes.

merci pour vos réponses.
12/07/2007, 16h29
alt3

D'une manière générale, plus les "déplacements" entre tes vertices sera simple, plus ça ira vite à l'execution.

Tu peux faire plusieurs choses:
- balancer tes vertices avec un vector au rendu : lent
- balancer tes vertices en liste chainées de struct au rendu : + rapide
- Préparer un vertex buffer avant le rendu, avec un liste chainée de structs ou un vector :kifkif.
12/07/2007, 16h32
Laurent Gomila

Citation:

j'ai lu sur les tutoriaux de nehe qu'il était pas recommandé d'utiliser les vectors pour cela, pour des raisons de vitesse.

Ca ce sont des sottises de gens qui ne savent pas de quoi ils parlent (NeHe n'est pas une référence en C++). Une fois optimisé et inliné (et bien utilisé), std::vector ne laisse aucune trace par rapport à un tableau brut.

Citation:

je débute en c++ et en opengl avec glut, et je voulais savoir quelle structure vous utilisez et pourquoi ou pas des vectors, histoire de prendre de bonnes habitudes.

Perso j'utilise un max les conteneurs standards, std::vector en premier. Evidemment si l'API graphique propose des trucs hardware du genre VBO, il faut les privilégier.

Citation:

- balancer tes vertices en liste chainées de struct au rendu : + rapide

Plus rapide ? J'ai du mal à voir comment, tu peux développer un peu ?
12/07/2007, 16h34
alt3

Citation:

Envoyé par Laurent Gomila

Plus rapide ? J'ai du mal à voir comment, tu peux développer un peu ?

Entre déplacer un pointeur dans un tableau et parcourir un vector, le parcours du vector sera au moins un peu plus lent, et s'il faut parcourir la liste à chaque boucle de rendu, je privilégierais le tableau.
12/07/2007, 17h14
Laurent Gomila

Citation:

Entre déplacer un pointeur dans un tableau et parcourir un vector, le parcours du vector sera au moins un peu plus lent

Pas si tu parcours ton vector comme il faut (avec un itérateur).
12/07/2007, 17h17
alt3

Citation:

Envoyé par Laurent Gomila

Pas si tu parcours ton vector comme il faut (avec un itérateur).

L'incrémentation d'un itérateur équivaut strictement à un déplacement de pointeur ?
12/07/2007, 17h21
Laurent Gomila

Avec inlining, oui. Ce n'est pas parce que std::vector est une encapsulation des tableaux bruts que la moindre de ses utilisations induit forcément une perte de performances. Pour itérer sur un tableau il suffit de déplacer un pointeur ; ce n'est pas le fait de cacher ça dans std::vector::iterator qui va changer quoique ce soit une fois le code compilé.
12/07/2007, 18h41
alt3

Citation:

Envoyé par Laurent Gomila

Avec inlining, oui.

Ok, donc pas "out of the box" (même si je chippote, j'en conviens).

Bah quand on sait pas ce que ça donne côté perf (et qu'on a pas envie de désassembler), on peut toujours faire quelques petits tests... Ca permet de pas suivre bêtement les on dit et rumeurs diverses et variéss. (Je précise que je suis pas une référence non plus en C++ :aie: )

L'algo testé est la somme d'entiers contenus dans un tableau ou un vecteur non initialisé (Chercher pas l'intérêt !).
Testé sous VC2005, ne se compilera pas avec gcc.

Test à blanc de OptimizedTestVector pour échauffer le processeur :
2646

TestArrayStack, allocation d'un tableau dans la pile, très rapide mais pas souvent adapté :
455

TestArrayHeap, allocation du tableau dans le tas, 2 à 3 fois plus lent ici :
1168

TestVector, codé sans se poser de question :
3149

OptimizedTestVector, en sortant la récupération de l'itérateur final de la boucle :
1973

C'est pas inintéressant de changer la taille du tableau pour voir des écarts se creuser ou se resserrer (L'allocation dans le tas, c'est cher).

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
 
#include "windows.h"
#include <vector>
 
#define ARRAY_SIZE 200
 
int __stdcall TestArrayStack()
{
  int AnTab[ARRAY_SIZE];
  int res = 0;
 
  for (int i = 0 ; i < ARRAY_SIZE ; i++)
    res += AnTab[i];
 
  return res;
}
 
int __stdcall TestArrayHeap()
{
  int * AnTab = new int[ARRAY_SIZE];
  int res = 0;
 
  for (int i = 0 ; i < ARRAY_SIZE ; i++)
    res += AnTab[i];
 
  delete[] AnTab;
 
  return res;
}
 
int __stdcall TestVector()
{
  int res = 0;
 
  using namespace std;
  {
    vector<int> AnTab(ARRAY_SIZE);
 
    for (vector<int>::iterator i = AnTab.begin() ; i != AnTab.end() ; ++i)
      res += *i;
  }
  return res;
}
 
int __stdcall OptimizedTestVector()
{
  int res = 0;
 
  using namespace std;
  {
    vector<int> AnTab(ARRAY_SIZE);
 
    vector<int>::iterator end = AnTab.end();
    for (vector<int>::iterator i = AnTab.begin() ; i != end ; ++i)
      res += *i;
  }
  return res;
}
 
int __cdecl main()
{
  HANDLE hConsole;
  DWORD nBuffer;
  DWORD nBegin;
  char sOutPut[256];
  char sFormat[] = "%d\n";
  int nCurrentFonc = 0;
  void * AuFunc[5];
 
  __asm
  {
    // Mise en place de pointeurs sur les fonctions
    mov eax, dword ptr OptimizedTestVector
    mov [AuFunc], eax
    mov eax, dword ptr TestArrayStack
    mov [AuFunc + 4], eax
    mov eax, dword ptr TestArrayHeap
    mov [AuFunc + 8], eax
    mov eax, dword ptr TestVector
    mov [AuFunc + 12], eax
    mov eax, dword ptr OptimizedTestVector
    mov [AuFunc + 16], eax
 
    // Récupération du handle de la console
    push -11
    call dword ptr GetStdHandle
    mov dword ptr hConsole, eax
 
NextFunc:
    // Début du chrono
    rdtsc
    mov nBegin, eax
 
    // Appel de la routine
    lea eax, AuFunc
    add eax, nCurrentFonc
    call dword ptr [eax]
 
    // Fin du chrono
    rdtsc
 
    // Calcul du nombre de front écoulés
    sub eax, nBegin
 
    // Formatage du nombre de front
    push eax
    lea eax, sFormat
    push eax
    lea eax, sOutPut
    push eax
    call dword ptr wsprintf
 
    // Calcul de la taille de la chaîne
    lea eax, sOutPut
    push eax
    call dword ptr lstrlen
 
    // Affichage du nombre de front
    push 0
    lea ebx, nBuffer
    push ebx
    push eax
    lea eax, sOutPut
    push eax
    push dword ptr hConsole
    call dword ptr WriteConsole
 
    // Passage au suivant
    add nCurrentFonc, 4
    cmp nCurrentFonc, 20
    jne short NextFunc
 
    // Fin du programme
    xor eax, eax
  }
}

13/07/2007, 10h12
Laurent Gomila

Les tests ne sont pas équivalents. Les deux premiers tableaux sont parcourus avec un indice, le vector est parcouru avec un itérateur.

De plus il manque le plus important pour juger de la fiabilité du test : les options de compilation.

Et puis pourquoi coder le main() en ASM ? On n'est pas tous capables de lire dans la matrice.
13/07/2007, 13h06
Kurisu

Perso, j'utilise le std::vector<> très souvent (pas pour stocker les vertices, vu Nintendo nous offre un joli format de liste d'affichage plus rapide à utiliser).
L'avantage du vecor, c'est que je peux définir sa taille à l'initialisation et que j'ai toujours sa taille (size()) et la sécurité de l'existence d'un membre (avec at()).
L'autre avantage, c'est qu'il occuppe la memoire de facon consécutive sans créer des trous. Lorsqu'on n'a que 88Mo de dispo pour toutes ses données, c'est le genre de trucs auquel il faut prendre garde.
13/07/2007, 14h38
rt15

Citation:

Envoyé par Laurent Gomila

De plus il manque le plus important pour juger de la fiabilité du test : les options de compilation.

J'ai mis les chiffres à titre indicatif. Je vous invite à copier coller sous VC et remplacer les routines par ce que vous auriez fait. Les options était notamment -O2, privilégiation de la vitesse par rapport à la taille, et MBCS (L'asm du main est écrit pour du MBCS).

Citation:

Envoyé par Laurent Gomila

Et puis pourquoi coder le main() en ASM ?

Au moins, le compilo ne peut pas divaguer sur cette portion de code.
13/07/2007, 14h42
Laurent Gomila

Je suis sceptique quant à ces résultats. Puisque tu maîtrises l'ASM, tu ne pourrais pas sortir le code compilé pour chaque fonction ? En remplaçant les parcours indicés par des parcours avec pointeur, pour que ça ait une chance d'être équivalent au parcours de vecteur.
13/07/2007, 15h54
rt15

Heu ok. Je poste le tout lundi. Je vais essayer de commenter, mais ça va être moche à regarder : le compilo de VC2005 fait du code rapide mais peu lisible.:?

Je n'ai désassemblé que les deux qui m'ont parues les plus semblables :
La nouvelle tableau + pointeur et OptimizedTestVector.
(La version avec allocation dans la pile qui est la plus rapide s'explique par le fait qu'à la place d'un lourd appel de new qui ne doit pas être léger, une simple soustraction à esp est effectuée.)

Voici la nouvelle version tableau + pointeur :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int __stdcall TestArray()
{
  int * AnTab = new int[ARRAY_SIZE];
  int res = 0;
 
  for (int * i = AnTab ; i < AnTab + ARRAY_SIZE; i++)
    res += *i;
 
  delete[] AnTab;
 
  return res;
}

La version du tableau avec pointeur est un peu moins rapide qu'avec les indices.
Avec les indices, le compilo faisait plusieurs additions dans la zone du pointeur avant de le faire progresser.

Le désassemblage du code avec le tableau :

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
 
eax : Adresse du tableau
edx : Adresse de fin du tableau   
ecx : Pointeur de parcourt
esi : res
 
    On sauvegarde esi pour pouvoir le restituer plus tard.
  push esi
    On pousse la taille du tableau 200 * 4 = 320h
  push 320h
    On alloue la mémoire dans le tas
  call new
    On calcul l'adresse de la fin du tableau
  lea edx, [eax+320h]
    On dépile l'argument de new, probablement en cdecl
  add esp, 4
    Mise à 0 de esi
  xor esi, esi
    On compare l'adresse de début avec l'adresse de fin
  cmp eax, edx
    On place le pointeur en début de parcourt
  mov ecx, eax
    On saute si l'adresse de début est supérieur ou égale à l'adresse de fin
  jae FinBoucle
    Probablement pour aligner l'adresse du saut
  lea esp, [esp]
 
Boucle:
    On cumule
  add esi, dword ptr [ecx]
    On fait progresser le pointeur
  add ecx, 4
    On compare le pointeur avec l'adresse de fin de tableau
  cmp ecx, edx
    On boucle si on est pas au bout
  jb Boucle
 
FinBoucle:
    On pousse l'adresse du tableau
  push eax
    On demande sa libération
  call delete
    On dépile l'argument de delete
  add esp, 4
    On restitue esi tout en affectant la valeur de retour
  pop esi
    Retour à l'appelant
  ret

Le désassemblage du code de OptimizedTestVector :

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
ebx : res
edi : Adresse de fin du vecteur
esi : Parcourt du vecteur
ebp : Adresse de début du vecteur
 
    Sauvegarde du pointeur de base
  push ebp
    Mise à jour du pointeur de base
  mov ebp, esp
    Correction d'un éventuel défaut d'alignement de la pile  
  and esp, 0FFFFFFF8h 
    Réservation de 24 octets qui récupérerons des infos sur le vecteur
  sub esp,18h
    Sauvegarde de quelques registres
  push ebx  
  push ebp
  push esi  
  push edi 
    On met res à 0 
  xor  ebx, ebx 
    Le template prend apparament deux pointeurs en argument dans edi et esi.
  lea edi, [esp+14h] 
  lea esi, [esp+18h] 
    On met 0 dans l'argument pointé par edi
  mov dword ptr [esp+14h], ebx
    Appel du code génréré par le template
  call ConstructionDuVector 
    Récupération dans des registres les données affectées par ConstructionDuVector
  mov ebp, dword ptr [esp+1Ch] 
  mov edi, dword ptr [esp+20h] 
    Vérification qu'il y a de la place dans le vector
  cmp ebp, edi
  jbe Suite1
    Vi, il y en a bien deux...
  call _invalid_parameter_noinfo
  call _invalid_parameter_noinfo 
Suite1 :
  mov esi, ebp 
Boucle:
    Comparaison du pointeur courant avec le pointeur de fin
  cmp esi, edi 
  je Fin
    On signal un problème si on a dépassé la fin du vecteur
  jb Suite2 
  call _invalid_parameter_noinfo
Suite2:
    On cumule
  add ebx, dword ptr [esi] 
    Heuuu, mais on vient de la faire celle là !
  cmp esi, edi 
jb Saut1 
  call _invalid_parameter_noinfo 
Saut1:
    Progression du pointeur
  add esi, 4 
    On boucle
  jmp Boucle       
Fin:
    On saute à Fin2 si ebp = 0
  test ebp, ebp 
  je EBP0 
    Libération de ce qui est pointé par ebp
  push ebp
  call delete
    Libération de l'argument de delete 
  add esp ,4 
EBP0:
    Restitution de edi
  pop edi  
    Mise en place de la valeur de retour
  mov eax, ebx 
    Restitution des autres registres
  pop esi  
  pop ebp  
  pop ebx  
    Remise en place des pointeurs de pile
  mov esp, ebp
  pop ebp
     Retour à l'appelant
  ret

La boucle sur le tableau pèse 4 instructions, contre 7 pour celle du vector, qui contient plusieurs sauts qui plus est.
Bien que relativement court, le constructeur du vecteur a une méchante boucle qui sert à initialiser le vecteur (_Ufill) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
	void _Construct_n(size_type _Count, const _Ty& _Val)
		{	// construct from _Count * _Val
		if (_Buy(_Count))
			{	// nonzero, fill it
			_TRY_BEGIN
			_Mylast = _Ufill(_Myfirst, _Count, _Val);
			_CATCH_ALL
			_Tidy();
			_RERAISE;
			_CATCH_END
			}
		}

Le vecteur est donc parcourut deux fois dans le programme : le constructeur remplit de 0 et la routine les additione...