std::list, std::vector et allocation mémoire

Bonjour,

Une question que je me pose sur l'allocation de mémoire dans les listes et les vecteurs :

Est-il possible de stocker dans un pointeur l'adresse d'un objet inséré dans une liste ou dans un vecteur et d'être sûr que ce pointeur pointe toujours sur l'objet ?

En gros, faire :

Code:

---

1 2 3 4 5

std::list conteneur; ou std::vector conteneur; cObject objet; cObject *pObjet = &objet;   conteneur.push_back(objet);

---

Pour les listes, il s'agit de listes chainées, donc à priori, pas de soucis...

Mais pour les vecteurs, que se passe-t-il en cas de réallocation (pour cause de dépassement, par exemple) ?

Est-ce qu'au moment de la réallocation, l'objet lui-même est déplacé ?
Ou est-ce que seulement la zone réservée pour les itérateurs est réallouée et seulement les itérateurs sont déplacés ?

Merci !

Si tu prends l'adresse avant insertion, tu es coulé à tous les coups car c'est une copie qui est stockée. Si tu la prends après, elle est valide tant que tu ne fais pas d'opération invalidante sur ton conteneur :
- Suppression et ajout de n'importe quel élément dans un vector, un deque ou un string
- Suppression de l'élément en question dans tout autre conteneur (list, set, map)

Pour les vecteurs il est certain que ça ne fonctionnera pas.
Sinon, il y a un truc formidable pour ne pas avoir à se poser la question: boost::ptr_container. Ce sont des variantes pointées des containers de la stl.
En dehors de ça, stocker des itérateurs serait peut-être préfèrable, mais d'autres sur ce forum t'en diront plus sur le sujet (je ne suis pas certain de la façon dont évoluent les itérateurs si leur conteneur est modifié).

Laurent Gomila :

Citation:

---

car c'est une copie qui est stockée

---

Tu veux dire que l'ensemble de mon objet est recopié pour l'insertion ?
L'objet existe donc 2 fois en mémoire ?

Citation:

---

Suppression et ajout de n'importe quel élément dans un vector, un deque ou un string

---

Tu veux dire que si j'insere un autre élément apres celui-ci, son adresse a changée ?

Citation:

---

Suppression de l'élément en question dans tout autre conteneur

---

Je suppose que c'est parceque le destructeur de l'élément est appelé lors de sa suppression d'un autre conteneur... Mais si l'objet est recopié lors de son insertion, pourquoi ça pose soucis ?

Citation:

---

En dehors de ça, stocker des itérateurs serait peut-être préfèrable

---

Pointeur ou itérateur c'est pareil. Par contre pour un vector on peut stocker des indices, ça peut aider dans certains cas.

Citation:

---

Tu veux dire que l'ensemble de mon objet est recopié pour l'insertion ?
L'objet existe donc 2 fois en mémoire ?

---

Oui. Enfin comme le premier est déclaré sur la pile il sera détruit pas longtemps après.

Citation:

---

Tu veux dire que si j'insere un autre élément apres celui-ci, son adresse a changée ?

---

Potentiellement. S'il n'y a pas assez de place, il y aura réallocation de mémoire et donc déplacement des éléments en mémoire.

Citation:

---

Je suppose que c'est parceque le destructeur de l'élément est appelé lors de sa suppression d'un autre conteneur...

---

Ben c'est surtout parce que l'élément n'existe plus. Donc tout pointeur qui pointerait dessus deviendrait invalide.

Citation:

---

Mais si l'objet est recopié lors de son insertion, pourquoi ça pose soucis ?

---

Parce que c'est sur la copie que tu pointes. L'original ayant été détruit depuis longtemps.

Ok, merci pour toutes ces precisions.

Je vais un peu preciser le contexte :

Je crée des objets, suite à des actions de l'utilisateur. Donc de facon dynamique.

La liste de certains de ces objets doit être parcourue très très fréquemment pour en lire le contenu.

Le parcours de cette liste est à peu de chose près, le coeur de mon programme. Je souhaite donc l'optimiser au maximum.

Dans un premier temps, j'ai fait ça :

- création de chaque objet avec un new()
- insertion dans une std::list
- parcourt de la liste

Ensuite, ça :
- création de chaque objet avec un new()
- insertion dans un std::vector
- parcourt du vecteur

Ici, j'ai gagné un déréfencement à chaque parcourt de la liste, au prix d'une réallocation de temps en temps (pas très grave)

Maintenant, j'essaie de faire en sorte que chaque objet créé puis inséré soit dans la même zone mémoire que les autres, afin d'éviter de devoir recharger le cache mémoire à chaque fois que l'on passe à l'objet suivant.

Je pensais trouver une astuce en les allouant sur la pile afin qu'ils soient proches les uns des autres... visiblement c'est rapé !

Auriez-vous des suggestions ?

Salut,

Si ton vecteur (ou ta liste ou ... d'une manière générale, ton conteneur) est prévu pour contenir des pointeurs, rien ne t'empeche d'écrire un code du genre de

Code:

---

1 2 3 4

monvecteur.push_back(new MonObjet(...)); mamap.insert(std::make_pair(key,new Monobjet(...)); //etc

---

Les ... dans les parentheses représentant, bien évididemment, les arguments à passer au constructeurs ;)

Tu te pose bien beaucoup de questions, et certains de tes raisonnements sont bizarres. Pour choisir ton conteneur, voici ce que tu dois te dire:
- si tu fais des ajouts/suppressions fréquents en mileu de liste, prends une list
- si tu fais des parcours aléatoires, prends un vector
- les deux? normalement un deque doit te fournir un compromis
Pense aussi à jouer avec la capacité des vector et des deque.
Et ça ne sert à rien d'instancier par pointeur si c'est pour copier ton objet dans un conteneur juste après, de même que c'est un peu l'inverse que de vouloir optimiser le cache mémoire (puisque tes objets peuvent être instanciés n'importe où dans la mémoire). Soit dit en passant, pense plutot à minimiser la complexité de tes algos plutot que d'optimiser le cache mémoire, en général ça paie plus :mouarf:

Pour preciser :

- les ajouts/suppressions sont très rares par rapport au nombre de lectures

- je crée les objets avec un new() mais je stocke leur reference, pas l'objet lui-même, sinon rien ne marcherait

- je ne fais pas de parcourt aléatoire, mais séquentiel. Eventuellement en commencant au milieu.

- la capacité des vecteurs est prévue pour "a priori" ne pas être dépassée, sinon tant pis (tres peu d'insertions, donc tres peu de realloc)

- les algos sont déjà minimés au maximum (!!!) comme dernier levier d'optimisation, il me reste le parcourt de la liste....

D'après ce que j'ai compris, tu fais un truc du style

Code:

---

1 2 3

std::vector<Object> v; Object* o = new Object; v.push_back(*o);

---

?
C'est-à-dire n'importe quoi ?

meuh non !

Quand meme pas !

Juste :

Code:

---

1 2 3

std::vector<Object> v; Object* o = new Object; v.push_back(o);

---

J'vais quand même pas m'amuser a stocker, dans un vecteur, un pointeur sur un pointeur sur un objet.

Surtout si c'est dans le but d'economiser des déréferencements !!!

En même temps, on ne sait toujours pas ce que tu fais vu que le code que tu donnes n'est pas correct et n'est donc vraissemblablement pas celui que tu utilises.

Citation:

---

J'vais quand même pas m'amuser a stocker, dans un vecteur, un pointeur sur un pointeur sur un objet.

---

Dans le code de loufoque ce n'est pas un pointeur sur un pointeur sur un objet, mais une copie d'un objet alloué sur le tas.

Je suis pas chez moi, j'ai pas tout mon code sous la main, mais j'ai au moins ça :

Code:

---

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

// Je declare un vecteur : std::vector<cObjet*> m_vecteurObjet;   // J'y insere des objets (plusieurs) : pObjet = new cObjet(...); m_vecteurObjet.push_back(pObjet);   // Mon traitement principal consiste à : std::vector<cObjet*>::iterator It;   for(It=m_vecteurObjet.begin();It!=m_vecteurObjet.end();It++) { (*It)->traitement(...); }

---

Maintenant : sachant que ma fonction traitement est extrement simple :
- addition d'un membre de l'objet avec un parametre de la fonction
- comparaison du resultat
- stockage du resultat (ou non) dans u autre membre de l'objet

Je souhaiterais rendre le parcourt de la boucle le plus rapide possible :

1/ eviter des déréferencement ?

2/ faire en sorte que tous les objets soient stockés dans la même zone mémoire pour être tous chargés en cache ? (les objets font entre 32 et 64 octets, il y a en une centaine environ)

3/ d'autres pistes ?


Désolé si je ne suis pas très clair.

Pourquoi tu stockes des pointeurs et pas des objets directement ?

Plusieurs raisons à cela :

- ailleurs dans le code, j'ai besoin d'acceder à certains objets du vecteur. Mais cela pourrait se faire via un indice ou un itérateur

surtout :

- je ne veux pas que les objets soient détruits lorsqu'ils sont retiré du vecteur : j'en ai besoin ailleurs

Dans ce cas si ce n'est pas le vecteur qui gère la durée de vie des éléments, il faudra bien n'en stocker que des pointeurs.

C'est ce que je pensais.

D'où l'idée de créer les objets dans la même zone mémoire afin d'éviter les erreurs de cache.

Je ne vois pas trop d'autres leviers pour optimiser...

Mais je ne sais pas trop comment faire, ni même si ça a un impact significatif, étant donné le déreferencement qui precede le chargement de l'objet.

Pourquoi je me prend la tete sur ce bout de code vous demandez-vous peut-etre ?

Parcque c'est un bout de code qui doit tourner à fond les manettes !

Oui, mais :

Citation:

---

Dans ce cas si ce n'est pas le vecteur qui gère la durée de vie des éléments, il faudra bien n'en stocker que des pointeurs.

---

Avec seulement une centaine d'objets, on peut pas dire que ça soit vraiment indispensable de "tourner à fond les manettes". Et puis si on commence à compter les dérèfèrencements, pourquoi pas les appels de fonctions tant qu'on y est?
Sinon, je capte de moins en moins tes explications. Tu nous dit que tes objets sont dans un conteneur mais que ce n'est pas lui qui gère leurs cycles de vie... :roll: Ce n'est donc qu'une sorte d'index non? Dans ce cas pourquoi t'acharner uniquement la dessus, tes objets devront bien être gérés par autre chose qui sera probablement un... conteneur. Faudrait pas plutot se pencher la dessus?

Pour ce qui est de tourner à fond les manettezs, si c'est indispensable car c'est une partie du code qui doit tourner en "quasi-temps réél".

Citation:

---

tes objets devront bien être gérés par autre chose qui sera probablement un... conteneur. Faudrait pas plutot se pencher la dessus?

---

Effectivement, je vais revoir ça de plus pret.

Pour info : dans cette boucle je compte aussi les appels de fonctions : elle est inliné (il n'y en a qu'une)

Et ça vaut la peine de se prendre la tete : sur cette boucle, avec un petit bench, je suis passé de 22ms à 8ms pour 200 itérations...