Utilisation std::vector vs std::deque

Le
David FLEURY
Bonjour,

je suis plutôt pour l'utilisation générale du std::vector, et
j'utiliserais plus volontiers des std::list lors de fréquente insertion
(même si mon usage est plutôt restreint des std::list, les std::map
m'étant souvent plus utiles).

Avec des collègues, on a reparlé des std::deque. Il y a une dizaine
d'année, après des tests (*), j'en étais arrivé à la conclusion que ce
n'était pas vraiment rapide, en accès notamment, et qu'un std::vector
bien reservé (en cas de volume important) était bien plus efficace.

Aujourd'hui, je recherche de nouveau sur le sujet et je tombe (ou
retombe) sur http://www.gotw.ca/gotw/054.htm où il préfère l'utilisation
du std::deque et ce malgré son tableau de performance qui donne toujours
l'avantage au std::vector.
Du coup, j'ai un peu du mal à comprendre son raisonnement.

Avez-vous une idée sur la question(**)?


(*) Je referais des tests ce matin pour voir si les choses ont changé.

(**) La question pourrait s'étendre à l’intérêt nouvelle classe
std::array, utile ou juste pour rassurer des développeurs d'autres
horizons ? Est-ce que le std::vector est vraiment aussi lent que ça
et/ou "trop" gros pour avoir à utiliser une nouvelle classe pour
représenter un tableau (ou un espace de mémoire continue?)

David
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Fabien LE LEZ
Le #24157241
On Fri, 13 Jan 2012 07:57:23 +0100, David FLEURY
(**) La question pourrait s'étendre à l’intérêt nouvelle classe
std::array, utile ou juste pour rassurer des développeurs d'autres
horizons ?



Il me semble que l'intérêt de std::array est que chaque objet de cette
classe est nettement plus léger que std::vector, ce qui le rend plus
adéquat quand on a beaucoup de tableaux. Par exemple, si tu veux
représenter un point dans un espace 3D (i.e. des triplets de 'int' ou
de 'double'), std::array est plus adapté.

Ajoutons que la taille d'un std::array est connue à la compilation, ce
qui peut permettre au compilo d'optimiser.

Par exemple :

template <class Conteneur> int Sommme (Conteneur const& c)
{
int s= 0;
for (size_t i=0; i<c.size(); ++i)
{
s+= c[i];
}
return s;
}

Si tu passes un vector à cette fonction, on aura bien une boucle.
En revanche, si tu lui passes un array<int,3>, le compilateur verra
quelque chose comme

int s= 0;
for (size_t i=0; i<3; ++i)
{
s+= c[i];
}
return s;

et pourra remplacer ça par :

return c[0] + c[1] + c[2];

Du moins, en théorie...
Fabien LE LEZ
Le #24157271
On Fri, 13 Jan 2012 07:57:23 +0100, David FLEURY
Aujourd'hui, je recherche de nouveau sur le sujet et je tombe (ou
retombe) sur http://www.gotw.ca/gotw/054.htm où il préfère l'utilisation
du std::deque et ce malgré son tableau de performance qui donne toujours
l'avantage au std::vector.



Mon conseil : choisis un conteneur par défaut, et utilise-le partout.
Dans la plupart des cas, ce choix n'aura pas d'influence mesurable sur
les performances.
Dans les rares cas où il a une influence, effectue des mesures, et
choisis le conteneur le plus adapté à ce cas précis.
Antonio
Le #24157301
Le 13/01/2012 08:49, Fabien LE LEZ a écrit :
On Fri, 13 Jan 2012 07:57:23 +0100, David FLEURY
Aujourd'hui, je recherche de nouveau sur le sujet et je tombe (ou
retombe) sur http://www.gotw.ca/gotw/054.htm où il préfère l'utilisation
du std::deque et ce malgré son tableau de performance qui donne toujours
l'avantage au std::vector.



Mon conseil : choisis un conteneur par défaut, et utilise-le partout.
Dans la plupart des cas, ce choix n'aura pas d'influence mesurable sur
les performances.
Dans les rares cas où il a une influence, effectue des mesures, et
choisis le conteneur le plus adapté à ce cas précis.




Je suis aussi de cet avis. J'utilise couramment std::deque pour
le bon compromis souplesse/rapidité, mais dès que les perfs
sont demandées alors j'adapte: je stocke plutôt des pointeurs, si pas
suffisant je passe à std::vector (surtout si les insertions se font
plutôt à la fin).
Lucas Levrel
Le #24157551
Le 13 janvier 2012, Fabien LE LEZ a écrit :

En revanche, si tu lui passes un array<int,3>, le compilateur verra
quelque chose comme

int s= 0;
for (size_t i=0; i<3; ++i)
{
s+= c[i];
}
return s;

et pourra remplacer ça par :

return c[0] + c[1] + c[2];

Du moins, en théorie...



Pourquoi « en théorie » ? Le compilateur Intel par exemple fait ce genre
d'optimisations (entre autres).

--
LL
David FLEURY
Le #24157671
Le 13/01/2012 09:17, Antonio a écrit :
Le 13/01/2012 08:49, Fabien LE LEZ a écrit :

Mon conseil : choisis un conteneur par défaut, et utilise-le partout.
Dans la plupart des cas, ce choix n'aura pas d'influence mesurable sur
les performances.
Dans les rares cas où il a une influence, effectue des mesures, et
choisis le conteneur le plus adapté à ce cas précis.




Je suis aussi de cet avis. J'utilise couramment std::deque pour
le bon compromis souplesse/rapidité, mais dès que les perfs
sont demandées alors j'adapte: je stocke plutôt des pointeurs, si pas
suffisant je passe à std::vector (surtout si les insertions se font
plutôt à la fin).




Ok merci à vous.
A priori pas de raison de changer mes habitudes. Rester sur std::vector
(j'utilse aussi des pointeurs pour mon cas présent) et voir au cas par cas.
Marc
Le #24159361
Fabien LE LEZ wrote:

Mon conseil : choisis un conteneur par défaut, et utilise-le partout.
Dans la plupart des cas, ce choix n'aura pas d'influence mesurable sur
les performances.
Dans les rares cas où il a une influence, effectue des mesures, et
choisis le conteneur le plus adapté à ce cas précis.



À noter qu'il existe des outils pour aider dans ces choix. Par exemple :
http://gcc.gnu.org/onlinedocs/libstdc++/manual/profile_mode.html
(pas idéal, mais mieux que rien).
David FLEURY
Le #24159471
Le 13/01/2012 20:16, Marc a écrit :
À noter qu'il existe des outils pour aider dans ces choix. Par exemple :
http://gcc.gnu.org/onlinedocs/libstdc++/manual/profile_mode.html
(pas idéal, mais mieux que rien).




Merci, je ne connaissais pas.
Fabien LE LEZ
Le #24160051
On Fri, 13 Jan 2012 10:33:41 +0100, Lucas Levrel

Pourquoi « en théorie » ? Le compilateur Intel par exemple fait ce genre
d'optimisations (entre autres).



Est-ce que l'optimisation en question est bien effectuée dans ce cas
précis (array<int,3> et template) ?
Tant que je n'ai pas de réponse positive, je garde mon "en théorie".
Alain Ketterlin
Le #24160921
int s= 0;
for (size_t i=0; i<3; ++i)
{
s+= c[i];
}
return s;

et pourra remplacer ça par :

return c[0] + c[1] + c[2];

Pourquoi « en théorie » ? Le compilateur In tel par exemple fait ce genre
d'optimisations (entre autres).



Est-ce que l'optimisation en question est bien effectuée dans ce cas
précis (array<int,3> et template) ?
Tant que je n'ai pas de réponse positive, je garde mon "en théo rie".



C'est du déroulage de boucle ("unrolling"), et ça ne se passe pas au
niveau du code source, mais au niveau de la représentation intermà ©diaire
du compilateur (donc ce qui est écrit ci-dessus est une "vue d'artiste ",
mais ne correspond pas exactement à ce que fait le compilateur).

Le compilateur le fera (après l'instanciation du template et l'inlinin g)
s'il estime que ça vaut le coup. C'est à dire que ça dé pend du corps de
boucle, et de la myriade d'heuristiques qu'il applique dans ces cas.
Pour le code ci-dessus, cela devrait arriver (avec un niveau
d'optimisation non trivial, toutefois).

-- Alain.
Publicité
Poster une réponse
Anonyme