A propos de list::erase

Bonjour,

je viens vers vous car je me pose une question concernant le fonctionnement de list::erase.

J'ai remarqué par erreur que le code suivant supprimait un élément de la list A. Pourquoi cela ?

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

list<double> A;   for ( int i = 0; i<10; i++) { A.push_back((double)i); }   list<double> B;   for ( int i = 9; i!=-1; i--) { B.push_back((double)i); }   list<double>::iterator it;   it = A.begin();   it++; it++;   B.erase(it);

---

Bien sur je sais qu'it est initialisé sur A. Ma question porte plutôt sur l'intérêt d'écrire B.erase(it) plutôt que erase(it) si cela revient au même. Est ce uniquement pour transmettre le type de données ?

Merci d'avance pour vos réponses.

C'est que, probablement pour des raisons de performance, il n'y a pas de vérifications faites (qui nécessiteraient, par exemple, un pointeur supplémentaire dans chaque chaînon) pour vérifier que le chaînon à "isoler" et détruire appartient bel et bien à la liste sur laquelle erase() a été appelé.
Je soupçonne des problèmes bizarres si on supprime le premier ou dernier élément, par contre.

Je parie qu'officiellement, tout appel à erase() sur un "mauvais" itérateur est un comportement indéfini. Donc, quelque chose qui ne doit pas être tenté.

Intéressant.

Je me suis retrouvé dans cette configuration car je stocke actuellement des données dans une list (nombreuses insertions/suppressions d'élément) mais sa list::max_size() n'est plus suffisante pour mon application. Auriez vous une idée pour surmonter ce problème ? J'imaginais "bêtement" utiliser plusieurs list mais la suppression des éléments me pose problème car pour les mêmes raison que vous évoquiez, je ne souhaite pas stocker dans chaque élément un pointeur vers la list qui le supporte.

Merci d'avance pour votre aide

Dans ce code je ne serais pas surpris d'avoir une exception iterateur non valide, puisque tu utilises un itérateur de A sur B. Ou du moins un comportement indéterminé.
Pour dépasser la taille de list::max_size... faut y aller. :weird:

C'est un code de calcul numérique c'est pour cela que j’atteins "facilement" la max_size de ma list. Je dis facilement car cette max_size est au alentour de 100 millions d'élément pour mon type de donnée et il m'en faudrait bien plus.

Je pose mes gros sabots ici mais en quoi est-ce aberrant?
Tu utilises un itérateur de la liste A comme parametre a la méthode erase (existante pour l'objet B) apres tout.

Seule exception trouvée :aie:

Citation:

---

If position (or the range) is valid, the function never throws exceptions (no-throw guarantee).
Otherwise, it causes undefined behavior.

---

En meme temps, cela force a faire attention aux itérateurs en question.
Merci de m'avoir fait connaitre cette particularité :D

Je reviens à la charge avec une remarque supplémentaire qui doit aller dans le sens de ma première intervention.

J'ai rempli, par palier d'un million d'élément, une list puis deux jusqu'à faire planter mon code. J'ai constater qu'il échouait dans le premier cas au moment d'ajouter le 44ème million et dans le second au moment d'ajouter les deux 22ème million.

La mémoire des list serait partagée ? list::max_size() renverrait la capacité globale stockable dans DES list ?

Partagée? oui en quelque sorte.
max_size est la limite en nombre d'éléments indexables dans une liste.
Tu ne peux mécaniquement pas en mettre plus. De même qu'il n'y a que 256 valeurs possibles dans un octet.

Ta limite concrête est autre: ton processus utilise trop de mémoire (la RAM).
std::list est doublement chainée.
Chaque élément stocké correspond au minimum à l'élément lui-même plus deux pointeurs. cela correspond à sizeof(T) + 2*sizeof(Node<T>*).
Supposons gentillement que ton type soit double, le tout fait probablement 12 octets (pointeurs en 32bits) ou 24 (en 64bits).

44M * 12 = plus ou moins 512 Mo
44M * 24 = 1Go

Je parie que tu utilises un ordinateur windows 64bits avec 1Go de RAM.

Ton calcul a-t-il réellement besoin d'avoir la liste de tous les éléments à l'avance?
Ne pourrais-tu pas calculer des valeurs intermédiaires, et oublier les éléments initiaux (un par un ou par paquets)?

Ben justement c'est ce que je ne comprend pas... Je suis effectivement sur un 64 bits mais je dispose de 8Go de RAM :calim2: ! C'est pour ça que j'ai commencé à m’intéresser à list::max_size() car ça me paraissait être l'unique autre blocage possible...

Petite question qui va paraitre bête :? : Sous 64 bits, pour des double et si la list est doublement chainée (donc deux pointeurs en plus de la donné) pourquoi le poids n'est pas sizeof(double) + 2*sizeof(double*) = 8 + 2*4 = 16 ? :oops: (mon système me renvoit sizeof(double) = 8 et sizeof(double*) = 4)

Si sizeof(double*)==4, alors ton programme est compilé en tant que programme 32 bits.

Alors ça c'est interessant :weird: ! Je travaille avec code::block, savez vous ou l'on peut voir/modifier cela ? C'est du au compilateur ?

Probablement dans les options de compilations du projet.
Il est tout aussi probable qu'il y ait deux installeurs de Code::blocks, un pour le 32bits, et un pour le 64bits. Ca ne m'étonnerait pas que tu aies installé le mauvais.

Je viens de faire le même essai (remplir une list jusqu'au plantage) sur un ordinateur disposant de 32Go de RAM et mon code à planté exactement au même niveau de remplissage ce qui vient alimenter l'idée que le problème vient de list::max_size() !

Le fonctionnement est tout de même étrange : s'il y a une limite mécanique à l’expansion d'un list (mettons X ), il parait logique pour pouvoir disposer de davantage de mémoire d'en créer une seconde. De la sorte nous pourrions stocker 2*X données. Or si je crée deux list, la taille de mes list devient limitée en pratique à X/2 :calim2: (même si leur list::max_size() n'a pas changé)... J'avoue que je suis un peu perdu là :( ...

Sache qu'en 32bits, les programmes ne peuvent pas accéder à plus de ~4Go de mémoire.
Le mécanisme limitant n'est pas max_size(), mais bien le fait qu'il y a une limite au valeurs désignable par un pointeur.
Du coup, lors de l'allocation mémoire du nouveau bloc (celui "de trop"), le système n'est plus capable de trouver une adresse 32bits disponible.

Définitivement, un processeur n'est pas capable de faire une opération (au sens processeur) avec plus de deux arguments simultanément. Même pour additionner trois nombres, il faut procéder en deux étapes.
Essaie de ne pas tout stocker.
En général, dans une simulation numérique, il n'est pas nécessaire de conserver plus qu'un nombre précis d'états calculés (en général, deux).
Ca m'étonnerait que ton état à l'instant courant contienne plus de 44 millions de points.

Et encore, ce n'est généralement pas 4Go.
J'ignore comment ça marche sous *n*x (je ne sais même pas si un *n*x 64 bits peut faire tourner des programmes 32 bits), mais sous Windows, les programmes 32 bits n'ont droit qu'à 2Go de mémoire s'ils ne sont pas déclarés comme "Large-address aware" (ce qui vient avec son lot de dangers).

Malheureusement dans mon problème ce n'est pas le nombre de nœuds le problème, enfin pas directement. C'est davantage les interactions entre les nœuds puisque chaque nœuds influe sur tous les autres. Il me faut donc stocker pour n nœuds les n² interactions... Et je ne travaille pas en dynamique, je n'ai donc pas d'instant antérieur dont je pourrais me débarrasser en les écrivant dans un fichier. Je ne peux donc pas résoudre mon problème mémoire de ce coté la...

Concernant la limite des programmes en 32bits, c'est très intéressant. C'est peut être évident pour certains mais ça ne m'avais pas effleuré l’esprit ! Comment avez vous fait votre calcul ? 2^32 c'est bien ça ? Donc si je compile mon programme en 64 bits le problème devrait être complètement disparaitre ?

En 32 bits, la taille théorique de l'espace mémoire est 4Go (2^32). Mais la taille disponible pour le code non-Kernel est 2Go (2^31), sauf pour les programmes 32 bits /LARGEADDRESSAWARE tournant sur:

• Un Windows 32 bits démarré avec le switch /3GB
• Un Windows 64 bits.

C'est exactement cela, mon code plante passé 1,8 Go de RAM allouée pour ma list...

Du coup en suivant le même raisonnement, si je compile mon code en 64 bit l'espace mémoire allouable sera donc de 2^63 = beaucoup ? Ce sera donc la RAM physiquement installée qui dimensionnera mon calcul ? J’essaie ça et je vous redis ;)...

Par ailleurs, essaie d'utiliser autre chose que std::list.

Si tu as une taille stable, tu peux utiliser std::vector. Il n'y a pas de surcoût par élément dans un vector, uniquement un prix global (comme avec list), négligeable si les éléments sont nombreux.
Par contre, cela signifie disposer d'un énorme paquet de mémoire contigüe.

Tu peux tempérer ce problème de plusieurs moyens: un appel à reserve si la taille ne doit pas changer, préférer std::deque, etc.

Citation:

---

Envoyé par kipgon

Du coup en suivant le même raisonnement, si je compile mon code en 64 bit l'espace mémoire allouable sera donc de 2^63 = beaucoup ? Ce sera donc la RAM physiquement installée qui dimensionnera mon calcul ? J’essaie ça et je vous redis ;)...

---

À ma connaissance l'espace allouable sera plus petit parce qu'au début de l'ère du x86-64, une partie des bits de poids fort était réservée pour une utilisation spéciale. Mais l'espace allouable est quand même au minimum plusieurs To, tu as donc de la marge.

Résultat j'ai changé de compilateur et ma list ne plante plus :D ! D'ailleurs je dois encore mal faire quelque chose car en comptabilisant la mémoire comme je faisais tout à l'heure

Code:

---

memory = (sizeof(Data) + 2*sizeof(Data*))*myList.size()

---

j'en viens à dépasser la taille de ma RAM :weird: !

Toujours est il que je vais lancer une simulation cette nuit et je pourrais vous dire si ça a fonctionné mais à priori c'est le cas :D !

Citation:

---

j'en viens à dépasser la taille de ma RAM !

---

Le swap/ la mémoire virtuelle sont tes amis.
La limite, c'est pas la RAM, c'est "la RAM+taille du swap affecté à ton programme".
Mais les performances vont en prendre un bon gros coup derrière les oreilles.

Bel euphémisme... En général, quand ça commence à swapper, c'est juste foutu; il vaut mieux essayer sur une autre machine ou changer l'algo.

Un algo avec une bonne localité mémoire peut s’accommoder du swap; mais pour un truc avec une énorme liste chaînée, j'ai de sérieux doutes sur la localité mémoire.

Je reviens pour vous confirmer que mon code ne plante plus, même pour de grosses simulations :).

Je vous remercie vivement pour votre aide car je n'aurais jamais trouver cela tout seul et que cela représentait une sérieuse limitation à mon avancement. Je vous en suis très reconnaissant...

Concernant la mémoire virtuelle, encore une question bête : est ce qu'avec un disque SSD le temps d'accès mémoire pourrait être équivalent à celui d'accès à la RAM ?

Citation:

---

est ce qu'avec un disque SSD le temps d'accès mémoire pourrait être équivalent à celui d'accès à la RAM ?

---

Une RAM dans les années 1960 peut-être, sinon, non.
le SSD, c'est pas Merlin l'Enchanteur.

Cependant, le SSD est probablement beaucoup plus rapide qu'un disque dur (un HDD). Il a par contre le défaut de s'user à l'écriture.

Ah je ne savais pas que le SSD s’usait à l'écriture :calim2: !

En tout cas merci pour toutes ces infos toutes très pertinentes, je passe la discussion en résolu.