Probleme temps de calcul sur un vector

Bonjour à tous, j'ai un petit soucis concernant la gestion d'un tableau.

Dans le code de base de ma fonction, j'utilise un tableau de float :

Code:

---

1 2 3 4 5 6 7 8

int nbPix = width*height; float * A = new float [nbPix]; float * B = new float [nbPix]; int * C = new int [nbPix]; for (int i=0; i<nbPix; ++i) A[i] = 10000000; B[i] = 10000000; C[i] = 453;

---

et si j'utilise les vector ça me donne tout simplement ça :

Code:

---

1 2 3 4

vector<float> A(nbPix,10000000); vector<float> B(nbPix,10000000); vector<int> C(nbPix, 453);

---

le temps de calcul est plus long pour la solution vector, est-ce normal ?
y a t-il une solution plus rapide ?

Bonjour,
Si votre premier code compile, c'est que vous êtes sous un vieux Visual. Il ne devrait pas car 'i' n'existe plus lors des deux dernières lignes.
Vous avez oubliez les accolades après le for (on est pas en python ;) ), et du cou les deux dernière ligne ne passe pas dans la boucle. Donc c'est normale que ca n'aille pas a la même vitesse.

oui en fait je n'ai pas recopié les acolades dans la citation mais elles sont bien présentes dans le code (dslé de l'oubli).

olivier21c, est-ce que tu es bien en mode release ?

Aussi, le premier code ne contient pas de delete alors que le second si.

A part cela et ce qui à été dit dans les messages précédents, les deux codes devraient avoir à peu près les même performances.

non j'étais ne mode debug,
si je passe en mode release, l'utilisation des vector est toujours plus lente mais l'écart est proportionnellement baissé par rapport au temps d'exécution final :

différence de 100ms sur l'exécution en mode debug (440ms pour la fonction totale)
différence de 10ms sur l'exécution en mode release (90ms pour la fonction totale)
il est encore plus intéressant d'utiliser float* ici.
par contre si j'initialise comme suit :

Citation:

---

memset(A, 10000000.0f, nbPix);
memcpy(B, A, nbPix * sizeof(float));
memset(C, _453, nbPix);

---

je gagne encore près de 10ms (mais mon 10000000.0f passe en int).

sinon pour ma culture, quelle la différence en mode debug et mode release ? qd utiliser l'un ou l'autre?

le delete est présent à la fin de la fonction pour l'utilisation de float* (et int* bien sur).

je pensait qu'utiliser des vector améliorerait la rapidité de mon exécution, mais la je ne vois comment améliorer.

vector n'accelere rien hein.

si t'es sous visual, quelle version ? La STL de MSVC est notoirement mauvaise.

je suis sous visual 2005 pro

L'efficacité des vector dépend le l'implémentation. Par exemple chez moi les deux méthode vont a la même vitesse, avec un minGW récent.
Après, un autre intérêt des vector c'est de gérer proprement le mémoire. Par exemple votre code avec des new n'as pas de delete. Et même si il les avait, il ne serait pas exception-safe.

Autre chose, la manière dont vous utilisez memset ne peut pas marcher car memset initialise char par char et non float par float. Elle n'est pas template, il faut don plutôt utiliser std::fill, et std::copy.

Pour la difference release/debug, en general le mode debug contient des donnée supplémentaire pour pouvoir débugger (faire du pas a pas surtout). Le mode release n'est pas fait pour debuger, le compilateur peut donc optimiser beaucoup plus.

d'accord d'accord
je te remercie pour l'explication, et du temps passé à mon pb.
bonne journée :ccool:

Citation:

---

Envoyé par olivier21c

sinon pour ma culture, quelle la différence en mode debug et mode release ? qd utiliser l'un ou l'autre?

---

en mode release le compilateur produit un code optimisé plus court et donc rapide
en mode debug le code produit est plus 'standard' avec une exécution moins 'surprenante' sous debugger

ceci dit cela concerne visual C++ qui offre moins de possibilités que g++ par exemple

on compile en mode debug ... quand on veut debugger ;)

Citation:

---

Envoyé par olivier21c

je pensait qu'utiliser des vector améliorerait la rapidité de mon exécution,

---

et non, vector facilite l'écriture du code lorsque le vecteur est de taille variable, mais vector est un peu plus lent, on n'a rien sans rien

[edit]et bien, que de collisions de réponse simultanées :lol:[/edit]

merci aussi pour cette réponse ^^

Citation:

---

Envoyé par bruno_pages

et non, vector facilite l'écriture du code lorsque le vecteur est de taille variable, mais vector est un peu plus lent, on n'a rien sans rien

---

Moi je ne vois pas de raison pour que vector soit plus lent que l'équivalent avec new[]/delete[]. Et même avec la STL de MSVC il ne devrait pas.

et pourtant si, au niveau principe et sans rentrer dans des détails d'implémentation on remarque que type[] est un conteneur à un seul niveau, une fois qu'on a l'adresse dans un registre et l'index dans un autre l'accès ne demande qu'une unique instruction machine. Par contre un vecteur est un conteneur à deux niveaux, un accès demande donc une lecture de plus, c'est donc au minimum deux fois plus cher.

si on regarde ensuite le code de la stl on voit que cet accès passe par la création d'un itérateur temporaire désignant le nième éléments, puis on 'traverse' cet itérateur , au total on exécute donc un code assez invraisemblable ... heureusement très très optimisé par un g++ en mode O2 comme on va le voir

soit le code suivant :

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

#include <vector> using namespace std;   int f(int * v, int i, int j) { v[i] = i; return v[j]; }   int f(vector<int> & v, int i, int j) { v[i] = i; return v[j]; }   int main(int, char ** argv) { long n; int * v1 = new int[1]; vector<int> v2;   v2.push_back(0);   for (n = atol(argv[1]); n; n -= 1) f(v1, 0, 0);   system("ps x | grep a.out | grep -v grep");   for (n = atol(argv[1]); n; n -= 1) f(v2, 0, 0);   system("ps x | grep a.out | grep -v grep");   return 0; }

---

utilisation compilé optimisé et non optimisé :

Code:

---

1 2 3 4 5 6 7 8

vxl15036 /tmp % g++ -O2 wxc.c vxl15036 /tmp % ./a.out 10000000000 6944 pts/12 S+ 0:10 ./a.out 10000000000 6944 pts/12 S+ 0:26 ./a.out 10000000000 donc 16 sec vxl15036 /tmp % g++ wxc.c vxl15036 /tmp % ./a.out 1000000000 7106 pts/12 S+ 0:08 ./a.out 1000000000 7106 pts/12 S+ 1:25 ./a.out 1000000000 donc 77 sec

---

et là on comprend que la compilation O2 à vraiment du mérite et élague incroyablement les 'divagations' de la stl ;)

C'est sûr il y a quelques cas ou il faut faire attention, comme le passage d'argument.

Si la fonction ne modifie pas la taille du vecteur et que les performances sont importantes il ne faut pas passer le vecteur en entier, juste un pointeur vers son premier élément ou un couple d'iterateurs comme dans les algorithmes de la STL.

Donc oui, une utilisation "à la C" de std::vector peut être plus lente, mais il existe souvent un équivalent aussi rapide, std::vector a été conçu pour.

Citation:

---

Envoyé par Sylvain Togni

Si la fonction ne modifie pas la taille du vecteur et que les performances sont importantes il ne faut pas passer le vecteur en entier, juste un pointeur vers son premier élément ou un couple d'iterateurs comme dans les algorithmes de la STL.

---

les réferences font la tête, tu les as méchamment oubliés :o

Y'a un bench de Mr Stepanov (hébergé chez adobe me semble) nommé : " The cost of encapsulation" (quelque chose comme ça). Et dans ce jeu de bench y'en a un justement sur la différence itérateur / raw pointer. Sur l'implémentation de gcc les deux sont aussi rapides, la STL de VS est un poil plus lente par contre il me semble. Et chez borland c'est kif kif.

le stepanov-penalty-test:

http://codepad.org/kIxv9Oqt

Ah yep, abstraction penalty bench :
http://www.stepanovpapers.com/Abstra...yBenchmark.cpp (contexte original).

Le benchmark de chez adobe était plus fourni et comprends celui là en fait.

vous pouvez toujours utiliser la méthode coué (je ne sais pas comment cela s'écrit), cela ne change rien à l'affaire, ni à l'indirection additionnelle, ni au résultât des mesures précédentes ;)

Citation:

---

Envoyé par bruno_pages

vous pouvez toujours utiliser la méthode coué (je ne sais pas comment cela s'écrit), cela ne change rien à l'affaire, ni à l'indirection additionnelle, ni au résultât des mesures précédentes ;)

---

Avec ton code de la page précédente j'obtiens avec vs2010 : 8.346s pour le tableau dynamique et 8.346s pour le std::vector (ça fluctue un peu dans les deux cas à plus ou moins 10ms). C'est bizarre, comment peut-on obtenir le même temps alors qu'il y a pourtant une "'indirection supplémentaire au minimum deux fois plus chère." !?

Citation:

---

for (n = size; n; n -= 1)
0119109D mov eax,540BE400h
011910A2 mov ecx,2
f(v1, 0, 0);
011910A7 xor ebx,ebx
011910A9 add eax,0FFFFFFFFh
011910AC adc ecx,0FFFFFFFFh
011910AF mov edx,eax
011910B1 or edx,ecx
011910B3 jne main+67h (11910A7h)

for (n = size; n; n -= 1)
011910B5 mov edx,dword ptr [esp+14h]
011910B9 mov dword ptr [esi],ebx
011910BB mov eax,540BE400h
011910C0 mov ecx,2
f(v2, 0, 0);
011910C5 xor ebx,ebx
011910C7 add eax,0FFFFFFFFh
011910CA adc ecx,0FFFFFFFFh
011910CD mov esi,eax
011910CF or esi,ecx
011910D1 jne main+85h (11910C5h)

---

l'indirection supplémentaire est là : 011910B9 mov dword ptr [esi],ebx

belle optimisation dans le code générée car elle est faite une fois pour les deux accès dans le vecteur (via recherche de code commun et détection de registres inchangés)

maintenant le programme ne fait pas que des accès, je n'ai jamais dis que l'utilisation d'un vector doublais le temps total d'exécution, seulement la partie liée au vector lui même, et si il n'y a une seule lecture traversant le vector à la recherche du 'vrai' vecteur interne c'est parce le code faisait 'suffisamment rien' pour laisser les registres disponibles.

[edit]on remarque aussi que les deux fonctions on été inliné[/edit]

Citation:

---

Envoyé par bruno_pages

l'indirection supplémentaire est là : 011910B9 mov dword ptr [esi],ebx

---

Alors sans vouloir être méchant, entre toi, Stepanov et mes propres mesures, j'ai vite fait le choix, et mauvaise nouvelle, c'est pas toi qui gagne.

Et ca fait pas mal de temps que lire l'assembleur lineairement n'apporte rien au vu des multiples pipeline internes.

Citation:

---

Envoyé par Joel F

Et ca fait pas mal de temps que lire l'assembleur lineairement n'apporte rien au vu des multiples pipeline internes.

---

l'exécution dans un proc est effectivement quelque chose de compliqué avec du parallélisme, sans compter ce qui peux se passer dans les caches, je me souviens avoir été ébahi par les prodiges des 68xxx il y a pas mal de temps déjà.

a noté que j'ai dis une bêtise dans ma réponse précédente, si l'écriture est (heureusement) bien effectué les lectures liées au return sont passées à la trappe, les fonctions ayant été inliné le compilateur à pu voir que le résultât n'était pas utilisé

Je crois que vous pouvez quand même tomber d'accord sur le fait que le temps d'accès à un vecteur est supérieur ou égal à celui d'un tableau, mais jamais inférieur ;).