bad_alloc sur gros vecteurs

Bonjour,

Je code une application de calcul sur graphe qui travaille sur de très gros graphes (+20 millions d'arêtes, + 10 millions de sommets).

Je code en C++ avec code::block / mingw / gcc 4.3.0 et gdb 6.6.

Lorsque je lance l'appli, le déroulement du programme est le suivant:

Au lancement, la lecture et la transformation du graphe fait monter l'occupation mémoire à 1,2 go. Ensuite, certaines structures sont vidées et je n'atteint plus que 392 mo de ram. Ensuite, je dois créer un vecteur gigantesque ( qui prend 795 Mo ). Je fais donc un vector::reserve à l'avance (vu que je connais la taille) pour éviter que lorsque j'ajoute des éléments les éléments du vecteur soit déplacés dans un autre bloc mémoire lorsque le bloc courant est de taille insuffisante. Je rappelle que les éléments d'un vecteur sont contigus en mémoire.

Lorsque je cherche à allouer 795 mo à mon vecteur avec reserve, l'appli me déclenche une exception std::bad_alloc (pour 300 mo ça passe très bien...). J'imagine que ça vient du fait qu'il n'y a plus d'emplacement mémoire libres contigus sur 795 mo... Je précise que la taille de mon vecteur est de 40 millions et que les objets contenus sont des instances d'une classe qui fait 20 octets. On obtient donc 40.000.000*20(taille d'une instance) = 800 mo.

Ma question est la suivante: Comment m'affranchir de la structure contigues de 800 mo ? Je pensais découper le vecteur en plusieurs vecteurs plus petits mais c'est assez crade... Avez vous une solution? Existe t'il une structure de donnée du type vector qui ne nécessite pas d'espace mémoire contigu? std::deque prendrait trop de mémoire...

Je précise que je n'ai pas de fuites mémoires et que l'occupation mémoire de l'appli est exactement ce que j'obtiens théoriquement sur papier.

Cordialement,

EDIT: J'ai testé deque à la place de vector mais le code devient 2 fois plus lent au début... puis devient encore beaucoup plus lent...

En observant le graph' proposé ici, j'opterai pour une std::list.

Normalement std::deque serait la solution à ton problème.

Malheureusement, je ne sais pas pourquoi, la plupart des implémentations utilisent des taille de bloc minuscules. Celle de Microsoft par exemple (Dinkumware) utilise des blocs de UN SEUL ELEMENT si le type fait plus de 8 octets 8O8O8O. La preuve :

Code:

---

1 2 3 4

#define _DEQUESIZ (sizeof (_Ty) <= 1 ? 16 \ : sizeof (_Ty) <= 2 ? 8 \ : sizeof (_Ty) <= 4 ? 4 \ : sizeof (_Ty) <= 8 ? 2 : 1) /* elements per block (a power of 2) */

---

Ce qui donne une énorme pénalité tant en vitesse que en occupation mémoire par rapport à std::vector.

Une solution serait peut-être d'implémenter ta propre classe deque avec une taille de bloc plus importante. Mais il faut quand même s'attendre à une légère dégradation des performances due à la double indirection inhérente à une telle structure.

Du coup avec des blocs aussi petits, on tend quasi asymptotiquement vers l'occupation mémoire et la complexité d'opération de la structure list non?

Il faudrait que j'implémente ma propre deque ou quelque chose de ce style...

Charmant ... :roll:

Passe en 64 bits, ça devrait résoudre le problème.
Normalement, avec de la mémoire virtuelle, la contiguïté n'est pas un problème.

En utilisant la STL, je pense que la "bonne" solution à ton problème serait de modifier l'allocateur du gros vecteur qui ne passe pas. Je pense aussi que c'est assez dur à mettre au point.

A mon avis, le plus simple serait de couper le vecteur en 2 ou 3 morceaux qui passent, et de cacher tout cela dans une classe "emballeuse". Si tous tes acces au vecteur se font via l'opérateur [], il te suffit alors de surcharger le [] de la classe emballeuse, et tout se passera comme si celle ci était un gros vecteur. Si tu utilises des itérateurs, il va aussi te falloir redéfinir leur opérateur d'incrémentation (pour qu'ils passent bien, quand il faut, d'un vecteur au suivant).

Comme ceci crée une indirection supplémentaire, il est possible que cela ralentisse ton code... Si cela pose problème, le découpage de ton problème en sous problèmes plus petits, au niveau du code, sera la solution. Ce n'est effectivement pas très propre, mais c'est souvent la meilleure solution sur de très gros volumes de données.

Francois

Salut,
As-tu essayé de faire ton reserve avant la montée à 1Go histoire de le garder sous le coude ?