difference entre clear() et swap()

Bonjour,

lorsque j'ai un conteneur (vector, set, map...), et que je veux le vider, j'ai pris l'habitude de faire un swap:

Code:

---

1 2 3 4 5

vector<int> mon_vecteur;   //... je remplis mon vecteur   vector<int>().swap( mon_vecteur ); // je vide le vecteur

---

Mais j'ai un doute soudain: quelle est la différence entre le swap ci-dessus et la fonction membre clear()?

ps: la seule "doc" aue j'arrive à trouver sur clear() est: "erase all the elements".

ps2: en fait, ce doute m'est venu parce que je dois optimiser un code et là je cherche à optimiser la moindre ligne.

Erase/remove trick pour enlever d'un conteneur.

swap trick pour libérer la mémoire. (ie le conteneur reste en mémoire en fait au cas où tu le reconstruises après.)

swap trick :
vector<int>(foo).swap(foo). ;)

Salut,

Je dirais que clear() ne libère pas la mémoire allouée alors que ton swap() va réinitialiser l'espace réservé à la valeur initiale.
Essaye de faire un capacity() après un clear()/swap( std::vector<...>() ) sur un vecteur avec pas mal d'éléments pour voir la différence ?

MAT.

Ouai enfin, j'ai dis erase remove, mais bon, pour le vider tu fais un clear. Sa libère les objets mais pas la mémoire associé au vecteur lui même, (optimisation apparemment).
Pour la libérer vraiment t'as le swap trick.


(avec les déboires du server je me suis trompé dans ce que j'ai posté ^^).

Salut,
La différence c'est que clear() ne désalloue pas la mémoire. Par exemple pour un vecteur, un clear est très rapide, il détruit les objets et set le pointeur de taille au début du tableau. (size = 0, capacité = inchangé)

L'équivalent C++0x du swap trick serait :

Code:

---

1 2 3

v.clear(); v.shrink_to_fit() // ajuste la capacité, donc ici désalloue entièrement.

---

Chez moi, la différence (en terme de perf) est nulle.

Citation:

---

Envoyé par Mat007

Salut,

Je dirais que clear() ne libère pas la mémoire allouée alors que ton swap() va réinitialiser l'espace réservé à la valeur initiale.
Essaye de faire un capacity() après un clear()/swap( std::vector<...>() ) sur un vecteur avec pas mal d'éléments pour voir la différence ?

MAT.

---

Oui c'est bien ça, tu as raison.

Citation:

---

Envoyé par JulienDuSud

Chez moi, la différence (en terme de perf) est nulle.

---

Chez moi il y a de grosses différences, tant en debug qu'en release. Teste avec le code suivant par ex.:

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

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <ostream>   #include "windows.h" // oué bon je sais... (mais j'ai pas boost d'installé là et je suis pressé :p )   using namespace std;   class PerfTimer { public: PerfTimer(); ~PerfTimer();   static bool Init() { LARGE_INTEGER proc_freq;   if ( !QueryPerformanceFrequency( &proc_freq ) ) return false;   frequency = 1.0 / proc_freq.QuadPart; return true; }   void Start() { QueryPerformanceCounter( &start ); }   double Stop() { QueryPerformanceCounter( &stop ); return ( ( stop.QuadPart - start.QuadPart ) * frequency ); }   void StopAndPrint( const std::string & message, std::ostream & ostr ); { double duracion = Stop(); ostr << message << duracion << " ms" << std::endl; }   private: static double frequency; LARGE_INTEGER start; LARGE_INTEGER stop; };   double PerfTimer::frequency = 0;   struct MyGenerate { MyGenerate():counter(0){} int operator () () { return counter++; } private: int counter; };   int main() { if ( !PerfTimer::Init() ) { cout << "error: problema en la inicializacion de PerfTimer" << endl; return EXIT_FAILURE; }   PerfTimer pt; vector<int> v( 500000 );   pt.Start(); generate( v.begin(), v.end(), MyGenerate() ); pt.StopAndPrint( "generate: ", cout );   pt.Start(); v.clear(); pt.StopAndPrint( "clear: ", cout );   cout << "cap: " << v.capacity() << endl;   vector<int> v1( 500000 ); generate( v1.begin(), v1.end(), MyGenerate() );   pt.Start(); vector<int>().swap( v1 ); pt.StopAndPrint( "swap: ", cout );   cout << "cap: " << v1.capacity() << endl;   cout << "end" << endl; cin.get(); return EXIT_SUCCESS; }

---

Non mais les perfs à gagné sont au niveau de l'occupation mémoire. Pas au niveau de la rapidité. Le swap trick met à 0 la capacity du vector, c'est comme ça que tu gagnes de la place.

Citation:

---

Envoyé par Goten

Le swap trick met à 0 la capacity du vector, c'est comme ça que tu gagnes de la place.

---

:koi:
Je pensais qu'il inversait (en gros) les buffers ce qui fait que mon_vecteur a un buffer vide et que le vecteur temporaire non nommé libère l'ancien buffer. La différence de temps doit être dans le delete[] globalement non ?

Ben il swap aussi la capacity, la capacity du temporaire étant à 0...

Et c'est ça le plus important la capacity. (c'est ça qui prend de la place en mémoire).

Citation:

---

Envoyé par Goten

Ben il swap aussi la capacity, la capacity du temporaire étant à 0...

Et c'est ça le plus important la capacity. (c'est ça qui prend de la place en mémoire).

---

En gros, MinGW :

Code:

---

1 2 3 4 5 6 7 8

std::vector::swap() { /*[...] */ std::swap(this->_M_impl._M_start, __x._M_impl._M_start); std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); std::swap(this->_M_impl._M_end_of_storage, __x._M_impl._M_end_of_storage); }

---

En gros, MS VCExpress 2008 :

Code:

---

1 2 3 4 5 6 7

std::vector::swap() { /*[...] */ std::swap(_Myfirst, _Right._Myfirst); std::swap(_Mylast, _Right._Mylast); std::swap(_Myend, _Right._Myend); }

---

capacity s'est à chaque fois XXXend - XXXfirst. J'ai quand même l'impression que l'important est bien le swap des buffers et le fait que le temporaire va faire un delete sur le buffer qu'on souhaite supprimer.

Oui mais quand tu fais :

std::vector<foo>().swap(myVec);

std::vector<foo>() <== crée un temporaire avec une capacity de 0, donc XXXend = XXXfirst = 0;

Là c'est pour supprimer tout, prend un exemple plus concret, t'as un vec (myVec) de 50000 éléments, ton vector tombe à 500 éléments suite à des erase / remove, alors tu fais un :

std::vector<foo>(myVec).swap(myVec);

Sa va construire un temporaire qui sera une copie de myVec mais capacity sera construit depuis 0 et donc adapté à sa nouvelle taille, puisque le copy ctor fait un uninitialized_copy (). (ie 500, exactement 500 ou pas je sais pas). Puis on swap le tout sur myVec existant.
Tu gagnes donc _M_end_of_storage - _M_last

Citation:

---

Envoyé par r0d

Chez moi il y a de grosses différences, tant en debug qu'en release.

---

Alors vu que je suis pas sous windows, ce code, chez moi:

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

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <ostream>   #include <time.h>   struct PerfTimer { struct GetTimeFailure{};   timespec start;   PerfTimer() { restart(); }   void restart() { start = getTime(); }   double elapsed() { timespec now = getTime(); return (now.tv_nsec - start.tv_nsec) / 1000000.0; // nano to ms }   timespec getTime() { timespec ret; if( clock_gettime( CLOCK_REALTIME, &ret ) == -1 ) throw GetTimeFailure(); return ret; } };   struct MyGenerate { MyGenerate():counter(0){} int operator () () { return counter++; } private: int counter; };   using namespace std;   int main() { PerfTimer t;   double sum = 0;   vector<int> v(5000000);   for( int i = 0; i < 1000000; ++i ) { generate( v.begin(), v.end(), MyGenerate() ); t.restart(); v.clear(); sum += t.elapsed();   }   cout << "clear within " << sum << "ms." << endl;   sum = 0;   for( int i = 0; i < 1000000; ++i ) { generate( v.begin(), v.end(), MyGenerate() ); t.restart(); vector<int>().swap( v ); sum += t.elapsed(); }   cout << "swap within " << sum << "ms." << endl;   cin.get(); return EXIT_SUCCESS; }

---

donne

Citation:

---

clear within 55.044ms.
swap within 56.4456ms.

---

Avec -O3, bien sûr.

edit: je viens de lancer 1000 tests d'affilés (dans le code, pas en externe), et j'obtiens ça:

Citation:

---

clear averages 19.3602ms.
swap averages 19.407ms.

---

Donc c'est vraiment pareil au niveau du temps mis "par instruction". Par contre, l'un libère la mémoire l'autre pas. Tout dépend de ce que tu veux faire, donc. Si tu comptes réinsérer des éléments par la suite, clear() est mieux. Si t'as besoin d'espace tout de suite (gros gros vector sur une petite machine), swap est le mieux.

Je rejoins donc goten.

Comme je l'ai dit. Le but du swap trick est de sauver de la mémoire pas du temps processus.

Citation:

---

Envoyé par JulienDuSud

Alors vu que je suis pas sous windows, ce code, chez moi:

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

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <ostream>   #include <time.h>   struct PerfTimer { struct GetTimeFailure{};   timespec start;   PerfTimer() { restart(); }   void restart() { start = getTime(); }   double elapsed() { timespec now = getTime(); return (now.tv_nsec - start.tv_nsec) / 1000000.0; // nano to ms }   timespec getTime() { timespec ret; if( clock_gettime( CLOCK_REALTIME, &ret ) == -1 ) throw GetTimeFailure(); return ret; } };   struct MyGenerate { MyGenerate():counter(0){} int operator () () { return counter++; } private: int counter; };   using namespace std;   int main() { PerfTimer t;   double sum = 0;   vector<int> v(5000000);   for( int i = 0; i < 1000000; ++i ) { generate( v.begin(), v.end(), MyGenerate() ); t.restart(); v.clear(); sum += t.elapsed();   }   cout << "clear within " << sum << "ms." << endl;   sum = 0;   for( int i = 0; i < 1000000; ++i ) { generate( v.begin(), v.end(), MyGenerate() ); t.restart(); vector<int>().swap( v ); sum += t.elapsed(); }   cout << "swap within " << sum << "ms." << endl;   cin.get(); return EXIT_SUCCESS; }

---

donne


Avec -O3, bien sûr.

edit: je viens de lancer 1000 tests d'affilés (dans le code, pas en externe), et j'obtiens ça:



Donc c'est vraiment pareil au niveau du temps mis "par instruction". Par contre, l'un libère la mémoire l'autre pas. Tout dépend de ce que tu veux faire, donc. Si tu comptes réinsérer des éléments par la suite, clear() est mieux. Si t'as besoin d'espace tout de suite (gros gros vector sur une petite machine), swap est le mieux.

Je rejoins donc goten.

---

Je ne souhaite pas me montrer excessivement cruel, mais ton code ne fait pas grand chose, étant donné que

1) le vecteur est créé en dehors de toute boucle, ce qui fait que après le second clear ne change pas l'état du vecteur : puis v.begin() == v.end().

2) idem, ce qui fait qu'une fois le premier swap effectué, le vecteur est cette fois complètement vide : v.begin() == v.end() = NULL ; donc aucune deallocation n'aura lieu après.

C'est donc assez normal que tu ait les même resultats.

Je rajoute les lignes v.resize() qui vont bien, le code devient :

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

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <ostream>   #include <time.h>   struct PerfTimer { struct GetTimeFailure{};   timespec start;   PerfTimer() { restart(); }   void restart() { start = getTime(); }   double elapsed() { timespec now = getTime(); return (now.tv_nsec - start.tv_nsec) / 1000000.0; // nano to ms }   timespec getTime() { timespec ret; if( clock_gettime( CLOCK_REALTIME, &ret ) == -1 ) throw GetTimeFailure(); return ret; } };   struct MyGenerate { MyGenerate():counter(0){} int operator () () { return counter++; } private: int counter; };   using namespace std;   int main() { PerfTimer t;   double sum = 0;   // bloc, histoire de contrôler la destruction de v { vector<int> v;   for( int i = 0; i < 100000; ++i ) { v.resize(10000); generate( v.begin(), v.end(), MyGenerate() ); t.restart(); v.clear(); sum += t.elapsed(); } }   cout << "clear within " << sum << "ms." << endl;   sum = 0;   // bloc, histoire de contrôler la destruction de v { vector<int> v;   for( int i = 0; i < 100000; ++i ) { v.resize(10000); generate( v.begin(), v.end(), MyGenerate() ); t.restart(); vector<int>().swap( v ); sum += t.elapsed(); } } cout << "swap within " << sum << "ms." << endl; }

---

La ligne de commande :

$> g++ -O3 -o swaptrick swaptrick.cpp -lrt

Le résultat :

clear within 196.558ms.
swap within 205.515ms.

Il y a clairement une différence, mais vu le nombre d'itérations, ça n'est pas vraiment clairement significatif. A noter que dans le premier cas, le v.resize() n'est pas censé avoir d'effet, puisque la capacité ne change pas. Dans le second cas, v.resize() a besoin de faire une allocation, ce qui peut être une perte de temps supplémentaire dans certains contextes...

Il y a tout de même quelque chose de bizzarre dans cette histoire, parce que j'ai testé le code que j'ai posté ci-dessus sur plusieurs machines, et à chaque fois j'obtiens des résultats fort différents... là par exemple, j'ai:

Citation:

---

generate: 0.107798 ms
clear: 1.10955e-006 ms
cap: 50000000
generate 2: 0.107292 ms
swap: 0.0103587 ms
cap: 0
end

---

Ce qui signifie que le clear() est environ 10000 fois plus rapide que le swap :calim2:
des fois c'est l'inverse... et des fois c'est pareil :?

comprends pô :koi:

Citation:

---

Envoyé par Emmanuel Deloget

Je ne souhaite pas me montrer excessivement cruel, mais ton code ne fait pas grand chose, étant donné que

1) le vecteur est créé en dehors de toute boucle, ce qui fait que après le second clear ne change pas l'état du vecteur : puis v.begin() == v.end().

2) idem, ce qui fait qu'une fois le premier swap effectué, le vecteur est cette fois complètement vide : v.begin() == v.end() = NULL ; donc aucune deallocation n'aura lieu après.

C'est donc assez normal que tu ait les même resultats.

---

Oui, tu as raison :aie:.

Citation:

---

A noter que dans le premier cas, le v.resize() n'est pas censé avoir d'effet, puisque la capacité ne change pas. Dans le second cas, v.resize() a besoin de faire une allocation, ce qui peut être une perte de temps supplémentaire dans certains contextes...

---

dans ce cas-ci, ça ne devrait pas influencer sur les mesures vu qu'on mesure pas le temps d'allocation, juste le temps qu'il faut pour vider.

Mes valeures sont plutôt fixes:

Citation:

---

clear within 4.2654ms.
swap within 7.72939ms.

---

La différence de vitesse c'est celle de la désallocation, prenons ce 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 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

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <ostream>   #include <time.h>   struct PerfTimer { struct GetTimeFailure{};   timespec start;   PerfTimer() { restart(); }   void restart() { start = getTime(); }   double elapsed() { timespec now = getTime(); return (now.tv_nsec - start.tv_nsec) / 1000000.0; // nano to ms }   timespec getTime() { timespec ret; if( clock_gettime( CLOCK_REALTIME, &ret ) == -1 ) throw GetTimeFailure(); return ret; } };   struct A { ~A() { std::cout << "destruction" << std::endl; } };   struct MyGenerate { MyGenerate(){} A operator () () { return A(); } private: //int counter; };   using namespace std;   int main() { PerfTimer t;   double sum = 0;   sum = 0;   // bloc, histoire de contrôler la destruction de v { for( int i = 0; i < 10; ++i ) { vector<A> v; v.resize(5); generate( v.begin(), v.end(), MyGenerate() ); t.restart(); cout << "hi" << endl; vector<A>().swap( v ); cout << "ha" << endl; sum += t.elapsed(); } }   cout << "swap within " << sum << "ms." << endl;   }

---

Il y a désallocation entre t.restart() et t.elapsed(), donc c'est normal qu'il y ait une différence de temps (clear ne désalloue pas).

Euh ...
Je vais avoir l'air idiot (sûrement :aie: ), mais pourquoi v.clear() remet-il à zéro tout ? Pourquoi ne fait-il pas simplement XXXlast = XXXbegin ? Ca améliorerait les performances, non ?

Citation:

---

Envoyé par r0d

Il y a tout de même quelque chose de bizzarre dans cette histoire, parce que j'ai testé le code que j'ai posté ci-dessus sur plusieurs machines, et à chaque fois j'obtiens des résultats fort différents... là par exemple, j'ai:
Ce qui signifie que le clear() est environ 10000 fois plus rapide que le swap :calim2:
des fois c'est l'inverse... et des fois c'est pareil :?

comprends pô :koi:

---

Ben, même si la version swap force à rappeler le pooler de vector, tu ne contourne en rien le pooler global. De plus, ce code est un affreux paradoxe : d'un côté perte d'efficacité à cause du rappelle de fonction, de l'autre perte d'efficacité du à un nombre incalculable de cache fault ><...

Citation:

---

Envoyé par Lenoa

Euh ...
Je vais avoir l'air idiot (sûrement :aie: ), mais pourquoi v.clear() remet-il à zéro tout ? Pourquoi ne fait-il pas simplement XXXlast = XXXbegin ? Ca améliorerait les performances, non ?

---

Ca porte un nom : Le LLTINT (Leak Like There Is No Tomorow) Principle. Je sais pas pourquoi, mais c'est généralement peu apprécié -_-'.

C'est peu apprécié ?
Au vu du smiley, je sens que j'ai bel et bien l'air idiot, mais bon ... :calim2:
Laisser des objets dans une zone non utilisée n'est pas un gain de temps ? De toute façon, où est l'intérêt de r.a.z la mémoire ? La complexité de clear() passerait de O(N) à O(1) ... ? C'est comme le new (ou le calloc) qui r-a-z la mémoire. Pourquoi une alloc en O(N) et pas en O(1) ? (sans compter le temps système.) Pourquoi l'OS r-a-z la mémoire avant que new/calloc ne le refasse ? (cf. le comportement de malloc, pour lequel rien n'est spécifié sur les données)
Que de questions :aie: