Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
865 connectés 

  FORUM HardWare.fr
  Programmation
  C++

  Problème d'allocation mémoire sur gros vecteur

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Problème d'allocation mémoire sur gros vecteur

n°1881823
Clarence W
Posté le 07-05-2009 à 12:52:25  profilanswer
 

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,
 

mood
Publicité
Posté le 07-05-2009 à 12:52:25  profilanswer
 

n°1881859
Taz
bisounours-codeur
Posté le 07-05-2009 à 14:27:16  profilanswer
 

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 ?

n°1881860
theshockwa​ve
I work at a firm named Koslow
Posté le 07-05-2009 à 14:27:30  profilanswer
 

* 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é  [:petrus75]


Message édité par theshockwave le 07-05-2009 à 14:28:00

---------------
last.fm
n°1881928
Clarence W
Posté le 07-05-2009 à 16:13:54  profilanswer
 

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).

n°1881954
Joel F
Real men use unique_ptr
Posté le 07-05-2009 à 17:15:45  profilanswer
 

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

n°1881975
Taz
bisounours-codeur
Posté le 07-05-2009 à 18:09:51  profilanswer
 

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).

n°1882862
Clarence W
Posté le 11-05-2009 à 10:22:53  profilanswer
 

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

n°1884083
bjone
Insert booze to continue
Posté le 13-05-2009 à 12:37:47  profilanswer
 

Clarence W a écrit :


Evidemment en 64 bits tout passe bien mais j'ai la contrainte de devoir rester en 32 bits...


 
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 ?


Message édité par bjone le 13-05-2009 à 12:38:30

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

  Problème d'allocation mémoire sur gros vecteur

 

Sujets relatifs
allocation mémoire optimisée au niveau bit[VBA] : problème d'affichage (Image.Visible = False ou true)
[ActionScript 3 ] Probleme affichage d'un rectangle (débutant)Problème conception objet pour modeleur UML en GWT
Probleme : Tiny_MCE et caractère avec accentsproblème de lecture de fichier binaire
Probleme variable entrante function Oracle[C] Matrice de structures : probleme de remplissage
Problème d'inbricatation avec mes if 
Plus de sujets relatifs à : Problème d'allocation mémoire sur gros vecteur


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR