Lenteur du vector<string>

Bonjour,

Je souhaite créer et remplir un vecteur de strings à partir d'un fichier texte. J'ai suivi le conseil de la faq :
http://cpp.developpez.com/faq/cpp/?p...ream_iterators

Mon fichier contient 300000 lignes de 2 colonnes. Soit 600000 strings à stocker. Pour faire simple, disons que la taille ne varie pas (en pratique elle varie). Voici le code que j'ai écrit :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

// ouvre le fichier ifstream file("fichier.txt",ios::in) ;   // crée le vecteur de strings vector<string> list ;   // réserve la mémoire int size = 600000 ; list.reserve(size) ;   // remplit le vecteur copy(istream_iterator<string>(file),istream_iterator<string>(),back_inserter(list)) ;   // ferme le fichier file.close() ;

---

J'obtiens bien un vecteur de 600000 strings, pas de problème. Mon souci est dans le temps d'exécution : 1.4 secondes. Je trouve que c'est anormalement lent. Alors j'ai testé avec un tableau de strings :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

// ouvre le fichier ifstream file("fichier.txt",ios::in) ;   // crée le tableau de strings int size = 600000 ; string * list = new string[size] ;   // remplit le tableau for ( int i = 0 ; i < size ; i++ ) file >> list[i] ;   // ferme le fichier file.close() ;

---

Cette solution avec le tableau de strings s'exécute en 0.9 secondes. Je pensais que le vecteur était mieux adapté, et qu'il serait plus rapide. J'aimerais savoir si c'est "normal" ou si j'ai mal compris quelque chose. Je ne suis pas sûr de bien faire la réserve de mémoire avec le vecteur.

D'abord, comment as-tu effectué tes mesures?

Pour mesurer le temps d'exécution, j'ai utilisé la fonction clock(). Par exemple, pour mesurer la première solution :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

// Début de la mesure clock_t t1 = clock() ;   // Ce que je veux mesurer ifstream file("fichier.txt",ios::in) ; vector<string> list ; int size = 600000 ; list.reserve(size) ; copy(istream_iterator<string>(file),istream_iterator<string>(),back_inserter(list)) ; file.close() ;   // Fin de la mesure clock_t t2 = clock() ; cout << (float)(t2-t1)/CLOCKS_PER_SEC << endl ;

---

Je n'ai pas fait de boucle pour moyenner le temps sur plusieurs itérations. Mais j'ai exécuté plusieurs fois ce bout de code, et j'obtiens sensiblement (à 0.1 sec près) les mêmes valeurs.

SI tu compares la fonction cpy à ta fonction for, tu verras que copy effectue des choses en plus.

Code:

---

1 2 3 4 5 6

template<class InputIterator, class OutputIterator> OutputIterator copy ( InputIterator first, InputIterator last, OutputIterator result ) { while (first!=last) *result++ = *first++; return result; }

---

De plus le back_inserter rajoute un appel de fonction pour chaque ligne. Sur 100 ligne aucune différence, sur 30000 ça joue. Après ça vas dépendre de l'optimisation faite par le compilateur, a vérifié dans le code machine, ce n'est qu'une hypothèse.

le copy + iterator + back_inserter n'est pas une combinaison de performances, mais de facilité d'utilisation et de relecture.

As-tu testé avec les options d'optimisations adéquates? (Il ne sert à rien de faire des tests de rapidité en mode Debug par exemple).

std::vector::reserve() est ton ami -- et c'est ce que fait le tableau.
Tu as les deque aussi sinon.

J'ai essayé en Release et -O3 (sur mingw gcc4.5) et 1 000 000 lignes et 2 colonnes, j'obtiens 1.2 sec environs pour le code avec copy+iterator+back_inserter, 0.3 sec pour le tableau avec new et, quoi que j'essaie avec std::vector, je ne passe jamais en dessous de 0.9 sec (le plus performant ayant été resize (et non reserve) + file>>list[i];
Ce résultat me surprend : j'ai toujours cru que vector ralentissait presque pas l'exécution quand on insère pas au milieux.

Salut, j'ai testé ton code et j'obtiens des écarts bien inférieurs à ceux que tu rencontres.

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

#include <string> #include <vector> #include <fstream> #include <time.h> #include <iostream> #include <iterator>   using namespace std;   int main(int, char *[]) { clock_t t1, t2; ifstream file; int size = 600000;   // ! ---------- VECTOR -------------- t1 = clock();   file.open("strings",ios::in); vector<string> vector; vector.resize(size); for ( int i = 0 ; i < size ; i++ ) file >> vector[i];   //copy(istream_iterator<string>(file),istream_iterator<string>(),back_inserter(vector));   file.close() ;   t2 = clock() ; cout << "VECTOR : " << (float)(t2-t1)/CLOCKS_PER_SEC << endl ;     // ! ---------- TABLE --------------- t1 = clock() ;   file.open("strings",ios::in); string *list = new string[size] ;   for ( int i = 0 ; i < size ; i++ ) file >> list[i] ;   file.close() ;   t2 = clock(); cout << "[] : " << (float)(t2-t1)/CLOCKS_PER_SEC << endl ;   // ! ------ W8 INPUT -------------   int x; cin >> x;   delete[] list; return 0; }

---

Par exemple :

VECTOR 0.536
[] 0.493

De plus pour des fichiers volumineux il pourrait être intéressant de mapper le contenu dans la mémoire avant le parcours ?

Le bench va te donner des pistes, mais il faut garder une chose à l'esprit. Le vector ça sera intéressant quand tu effectueras pleins de random access après avoir mis tout ton bazar dans le vector. Et si tu peux l'aiguiller en faisant un reserve() comme le dit Luc avant, bah ça sera mieux. Tu as peut-être d'autres structures de données qui avaleront plus vite l'avalanche de données à stocker mais il faut voir celle qui te permettra d'accéder au plus vite pendant l'exécution, et de modifier biensûr.

Et si tu as des volumes énormissimes, effectivement faut voir du côté de mmap.

Salut,

Citation:

---

Envoyé par Musix

[...]

---

Remarque de méthode :
Tu fais varier au - 3 paramètres :
std::vector => new []
std::copy => for
std::istream_iterator =>operator>>

Comment peux tu dire que tes différences de perf ne tiennent qu'au changement std::vector vs new ? Comment peux-tu garantir que cela ne vient pas du changement d'itérateurs de flux en lecture directe ?

Merci pour toutes vos réponses :)

Première faute : j'étais en mode Debug :oops:
Deuxième faute : tu as raison 3DArchi, trop de paramètres varient à la fois.

J'utilisais déjà la fonction reserve(). Aussi bizarre que cela paraisse, ça améliore peu les performances. J'ai testé en mode release cette fois :

Code:

---

1 2 3 4

t1 = clock(); vector.reserve(size) ; // Test 1 : sans // Test 2 : avec copy(istream_iterator<string>(file),istream_iterator<string>(),back_inserter(vector)) ; t2 = clock() ;

---

Je passe de 0.56 sec à 0.48 sec en ajoutant la réserve.

Quant à la comparaison vector vs [], j'obtiens désormais les mêmes ordres de grandeur que rmdak. Lorsque les deux structures sont remplies par l'opérateur >> les performances sont quasiment identiques.

Citation:

---

J'utilisais déjà la fonction reserve(). Aussi bizarre que cela paraisse, ça améliore peu les performances.

---

La ré allocation de mémoire lorsqu'un vector est plein est censée être "intelligente" au sens ou elle réserve non pas une case supplémentaire mais plutôt double (pas sur exactement de la quantité) la taille du vector en mémoire.

Sa me rappel une entrée de la FAQ Stroustrup ou il parle du reserve vers la fin : http://www2.research.att.com/~bs/bs_...low-containers