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.
 
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...
 
Cordialement,
 

Passe en 64bits ?
 
Tu as fait des mesures avec std::deque ? Est-ce qu'en début de programme, tu es capable d'allouer autant ? Même si tu passes sur une structure de données avec des blocs (pire des cas == liste chainée), tôt ou tard, tu va te heurter à un problème de fragmentation.
 
Ca ressemble à quoi ta structure de données de 20octets ?

* Voir si tu peux passer en 64 bits, ca te donnerait plus de liberté pour manipuler d'aussi gros blocs de données.
 
* passer par une autre structure de données que vector ? (genre, deque). Il faut voir si, proportionnellement au traitement que tu fais, ca va pas avoir un impact monstrueux, aussi...
 
Edit : grillé en beauté  

J'ai testé deque, évidemment, du fait que les blocs mémoire non sont plus contigus, ça passe. Cependant les perfs s'effondrent. Sur un algo qui pond un résultat en quelques heures, je ne peux pas me permettre ...
 
En fait le deque est entre un vecteur et une liste sauf que la taille des blocs est trop petites. De fait, dans mon cas, vu la taille de la structure, la deque se comporte comme une liste (en terme de complexité)...
 
Evidemment en 64 bits tout passe bien mais j'ai la contrainte de devoir rester en 32 bits... Pour un algo qui frise les 1,8 go d'occupation mémoire en pic, je sais que c'est très critique et que je vais être obliger d'accepter une fragmentation relativement importante de la mémoire...
 
Ma structure de 20 octet contient deux champs de bits et quelques entiers (c'est une classe).

faut peut etre voir à passer du modele tableau de structure à celui de structure de tableau

Sinon une technique à la noix: un fichier, que tu map avec une fenêtre glissante en fonction des accès.
 
Vois avec ton windows pour passer en mode 3G ?
T'as bien regarder de ne pas avoir de trou dans ta structure (question con).

Qu'entends tu par mapper un fichier avec une fenêtre glissante en fonction des accès?  
 
Quant à adopter une structure de tableau plutôt qu'un tableau de structure, ça me semble pas pensable vu la complexité du code. ça force à tout repenser... Celà dit, c'est une solution...

 
Franchement insiste auprès des décideurs au dessus de toi pour leur faire comprendre que viser du 64bits permet d'avoir une solution qui serait simple, performante et facile à maintenir par la suite, là où la version 32bits, ramera et sera super contraignante au niveau implémentation & maintenance.
 
C'est quoi le contexte ? Industrie ou projet universitaire ?