Utilisation de la class std::vector est très lourde!

**mathro** · 29/04/2013, 01h39

Enfin merci beaucoup Ehonn il faudra activer les optimisations

**JolyLoic** · 29/04/2013, 08h51

Envoyé par mathro

J'ai trouvé que push_back est de complexité o(n^2) si on veux insérer n élement, c'est pour ça je l'ai pas utilisé.

C'est faux. Insérer n éléments est en O(n).

**ketan** · 29/04/2013, 10h52

Bonjour,

Vis à vis des grosses différences de performance, et vu que tu sembles utiliser Visual Studio 2010, j'ai peut-être une idée du problème.

Dans la configuration par défaut du mode Debug, il y a l'option "Basic Runtime Check" (dans les options de compilation C/C++ => Code Generation) qui semble ralentir énormément les objets de type class quand il n'est pas mis sur Default.

J'ai remarqué ça quand j'ai fait un simple wrapper autour de l'API random du système (méthode Rand() qui appel la fonction rand() du système). En mode Release, les temps étaient sensiblement semblable, mais en Debug, ils étaient juste beaucoup trop éloignés.

Sans l'option de compilation modifiée : API C : 16s, wrapper class : 25s
Avec l'option de compilation modifiée : API C : 17s, wrapper class : 19s

**jblecanard** · 29/04/2013, 13h52

Et sinon vu qu'on travaille en taille fixe, on peut aller chercher std::array dans C++11 ou Boost.

**mathro** · 29/04/2013, 14h53

Envoyé par ketan

Dans la configuration par défaut du mode Debug, il y a l'option "Basic Runtime Check" (dans les options de compilation C/C++ => Code Generation) qui semble ralentir énormément les objets de type class quand il n'est pas mis sur Default.

J'ai éxécuter une partie du code la ou le problème ce pose, sans changer cette option de compilation j'ai eu les résultats suivant
Allocation dynamique: 14 s; class std::vector 97 s
En changeant cette option
Allocation dynamique: 14 s; class std::vector 52 s
en activant de plus les optimisation (/O2; /Ot)
Allocation dynamique: 13 s; class std::vector 30 s

**mathro** · 29/04/2013, 16h21

En faisant l'éxécution du programme en entier avec des données de taille moyenne (n=30) avec activation des optimisations (/O2, /Ot) mettre l'option 'Basic Runtime Checks' à 'Default' et l'option 'Debug Information format' à 'C7 compatible (/Z7)' car /ZI n'est pas compatible avec /O2, j'ai eu les résultats suivants:

Allocation dynamique
Debug:76s ; Release:33s
std::Vector
Debug:175s ; Release:32s

Donc voilà, il faudra exécuter en mode Release

; reste à voir C++11

**camboui** · 30/04/2013, 10h27

Envoyé par Bousk

Le "plus rapide" sera surement le reserve et push_back, puisque le resize fait de l'initialisation à une valeur par défaut via l'opérateur T().

Maintenant, j'en pense qu'à ton niveau on n'en est pas à vouloir quelque chose qui tourne 0.0002ms plus vite mais tout simplement un script qui fonctionne..

Avant de vouloir courir, on apprend à marcher.

+1000

Ceci aussi aide un peu à retirer des casseroles inutiles sous VS:
_SECURE_SCL=0

J'use et abuse de std::vector<> dans mes prg.
Je n'ai jamais fait de resize() et n'ai jamais initialisé un vector à une taille donnée, la plupart du temps c'est inutile et contreproductif.
Par contre les méthodes reserve() et capacity() sont utiles et importantes.

Voici un exemple de bon usage:

Code :

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

1
2
3
4
std::vector<int> v;
v.reserve(1000);
for (int i=0; i<1000; ++i)
 v.push_back(i);

Voici un exemple catastrophique

Code :

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

1
2
3
4
5
6
std::vector<int> v;
for (int i=0; i<1000; ++i)
{
 v.reserve(v.capacity()+1);
 v.push_back(i);
}

**Ehonn** · 30/04/2013, 10h56

Envoyé par camboui

Je n'ai jamais fait de resize() et n'ai jamais initialisé un vector à une taille donnée, la plupart du temps c'est inutile et contreproductif.

Dans le traitement d'image, tu connais la taille de l'image avant de déclarer ton vector donc tu peux l'initialiser directement à la bonne taille. Tu ne peux pas utiliser std::array (ou un tableau à la C) car cette taille n'est connu qu'à l'exécution (et que tu ne peux pas t'assurer que ton image tienne dans la pile). Utiliser reserve ici serait inutile et contre productif.

Pour ton exemple, je pense que ceci est plus rapide si l'initialisation est plus rapide que le surcoût dû au push_back (même sans réallocation) (à tester) (mais c'est pas toujours possible j'en conviens).

Code :

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

1
2
3
4
5
std::vector<int> v(1000);
for (std::size_t i = 0; i < v.size(); ++i)
{
    v[i] = i;
}

**Bousk** · 30/04/2013, 23h39

Envoyé par Ehonn

Dans le traitement d'image, tu connais la taille de l'image avant de déclarer ton vector donc tu peux l'initialiser directement à la bonne taille. Tu ne peux pas utiliser std::array (ou un tableau à la C) car cette taille n'est connu qu'à l'exécution (et que tu ne peux pas t'assurer que ton image tienne dans la pile). Utiliser reserve ici serait inutile et contre productif.

Le traitement d'image ne fait pas exception.
As-tu une quelconque utilité à initialiser les élément de ton vector à une valeur donnée ? Je n'en ai jamais eu besoin en faisait du traitement d'image.
Le vector sert à stocker les pixels, on sait combien on veut en stocker, initialiser notre stockage par un pixel/une couleur par défaut à chaque emplacement/pixel ne sert à rien. On réserve la taille nécessaire, puis on lit/écrit/stocke chacun des pixels.

Envoyé par Ehonn

Pour ton exemple, je pense que ceci est plus rapide si l'initialisation est plus rapide que le surcoût dû au push_back (même sans réallocation) (à tester) (mais c'est pas toujours possible j'en conviens).

Code :

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

1
2
3
4
5
std::vector<int> v(1000);
for (std::size_t i = 0; i < v.size(); ++i)
{
    v[i] = i;
}

Etant donné l'appel au constructeur par défaut *1000 avant, non.
Le push_back ne coûte rien tant qu'il ne doit pas faire une réallocation.
L'opérateur[] utilise le constructeur par copie, tout comme le push_back.

**Ehonn** · 01/05/2013, 00h25

Je trouve qu'il est plus simple (et plus court) d'utiliser la size du vector.

push_back fait un if que operator[] ne fait pas, l'operator[] est donc potentiellement plus rapide.

**Kalith** · 01/05/2013, 13h17

Envoyé par Bousk

Le traitement d'image ne fait pas exception.
As-tu une quelconque utilité à initialiser les élément de ton vector à une valeur donnée ? Je n'en ai jamais eu besoin en faisait du traitement d'image.
Le vector sert à stocker les pixels, on sait combien on veut en stocker, initialiser notre stockage par un pixel/une couleur par défaut à chaque emplacement/pixel ne sert à rien. On réserve la taille nécessaire, puis on lit/écrit/stocke chacun des pixels.

Il me semble qu'on est assez souvent amené à devoir utiliser des bibliothèques C, auquel cas on est obligé de faire un resize pour à la fois allouer la mémoire et dire au std::vector qu'il contient quelque chose. Même si l'initialisation des valeurs est effectivement inutile dans ce cas.

**koala01** · 01/05/2013, 14h52

Salut,

Envoyé par Kalith

Il me semble qu'on est assez souvent amené à devoir utiliser des bibliothèques C, auquel cas on est obligé de faire un resize pour à la fois allouer la mémoire et dire au std::vector qu'il contient quelque chose. Même si l'initialisation des valeurs est effectivement inutile dans ce cas.

Ben, j'ai presque envie de dire que, dans ce cas là, on disposer d'un constructeur particulièrement sympa...

Au sortir d'une bibliothèque C, on aura sans doute soit un char * soit un void * (soit même un UnType * qui correspond à la structure C en question), mais on aura, aussi, une indication du nombre d'éléments que l'on doit s'attendre à y trouver.

Une fois la conversion (si nécessaire) effectuée du char * ou en void * en un UnType*, tu devrait pouvoir utiliser le constructeur prenant les deux itérateurs, sous la forme de

Code :

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

std::vector<UnType> tab(ptr, ptr+size);

Il me sembleque ce constructeur commence par calculer la taille requise (std::distance) et par faire un reserve avant de faire l'équivalent d'un grand memcpy global

**jabbounet** · 01/05/2013, 17h24

Envoyé par mathro

Puisque tu fais un retour par copie, il pourrait également être plus intéressant de passer le vector en paramètre out de la méthode à la place.

Je comprend pas exactement ce que vous voulez dire

je pense qu'en parlant de retour par copie il parle de ce sujet
http://stackoverflow.com/questions/1...nt-copy-values
http://en.wikipedia.org/wiki/Return_value_optimization

cela peut couter cher un retour par copie ou pas…

**Kalith** · 01/05/2013, 20h48

Envoyé par koala01

Ben, j'ai presque envie de dire que, dans ce cas là, on disposer d'un constructeur particulièrement sympa...

Oui bien sûr, et il serait bête de s'en priver

Mais j'ai déjà vu des cas (par exemple avec libpng) où la bibliothèque ne gère pas la mémoire elle même, et attend qu'on lui donne un pointeur vers une zone mémoire valide où elle pourra ranger les pixels.

**Bousk** · 01/05/2013, 20h51

Envoyé par Kalith

Oui bien sûr, et il serait bête de s'en priver

Mais j'ai déjà vu des cas (par exemple avec libpng) où la bibliothèque ne gère pas la mémoire elle même, et attend qu'on lui donne un pointeur vers une zone mémoire valide où elle pourra ranger les pixels.

Perso dans ces cas-là, je préfère utiliser un simple C-Array, et si j'ai vraiment besoin d'un vector par la suite, je crée un vector avec après