Newsgroup: it.comp.lang.c++
Titolo: problema con std::list

Salve, vorrei sapere se quello che mi succede è normale oppure sto usando
male le liste...
praticamente ho una struttura cosi fatta:
Struct
{
    short  campo1;
     int    campo2;
}MiaStruttura
il compilatore allinea a  byte , quindi  sizeof(MiaStruttura) = 6
ora faccio questo:
for(int i = 0;i<32 * 1000 * 1000; i++)
{
      MiaStruttura *pStruct = new MiaStruttura;
}
cioè alloco 32 milioni di queste strutture
Il consumo di memoria sale a circa 350 MB  ( controllo effettuato come
scritto qui 
http://www.itwriting.com/dotnetmem.php
)
e correggetemi se sbaglio, ci siamo, perchè vengono allocati 6 bytes per
ogni struttura + 4 per ogni puntatore quindi:
(6+4) * 32.000.000 = 320 MB
ora voglio inserire tutte le strutture in una lista, modifico il codice come
segue
std::list<MiaStruttura >  *miaLista = new std::list<MiaStruttura>;
for(int i = 0;i<32 * 1000 * 1000; i++)
{
      MiaStruttura *pStruct = new MiaStruttura;
      miaLista->push_back(*pStruct ); //Aggiungo l'inserimento...
}
A questo punto il consumo di memoria sale a 880 MB, cioè si ciuccia 530 MB
per inserire gli elementi in lista.
Cosa fa si crea una copia per ogni struttura?
Se invece mi creo una lista di puntatori a struttura, le cose migliorano?
Grazie


Per come hai scritto il codice dire proprio di si
Ciao
Fabio

 Se invece mi creo una lista di puntatori a struttura, le cose migliorano?
Si, si crea una copia. Si le cose migliorano, anche perche' in questo
modo non ti perdi per strada tutta la memoria che allochi
dinamicamente.
Ciao,
Nicola

 dinamicamente.
Insomma devo fare o cosi:
for(int i = 0;i<32 * 1000 * 1000; i++)
{
       MiaStruttura struct;
        maiLista->push_back(struct); //si fa la copia della struttura
}
oppure cosi
for(int i = 0;i<32 * 1000 * 1000; i++)
{
       MiaStruttura *pStruct = new MiaStruttura ;
        maiLista->push_back(pStruct );  //si copia il  puntatore?
}
in questo secondo caso si fa la copia del puntatore, giusto? quindi le
strrutture le devo allocare dinamicamente per non perderle... o sbaglio?
grazie

 strrutture le devo allocare dinamicamente per non perderle... o sbaglio?
Corretto assumendo che nel primo caso tu abbia
std::list<MiaStruttura> * miaLista;
mentre nel secondo
std::list<MiaStruttura *> * miaLista;
Io userei la seconda, perche' std::list gia' alloca dinamicamente i
suoi nodi. In alternativa potrebbe essere addirittura conveniente
usare uno std::vector di puntatori. Attento pero' che coi puntatori
devi gestire la deallocazione della memoria.
Ciao,
Nicola

 suoi nodi.
Cioč? non ho capito... :? le strutture non le devo comunque allocare io?
Comunque ho fatto le due prove
cosi:
std::list<MiaStruttura> * miaLista;
...
for(int i = 0;i<32 * 1000 * 1000; i++)
{
       MiaStruttura struct;
        maiLista->push_back(struct); //si fa la copia della struttura
}
La memoria allocata č 506 MB che č sempre un boato!!!  dovrebbe essere  138
MB giusto?  eppure ora dinamicamente non alloco nulla ???
std::list<MiaStruttura *> * miaLista;
...
for(int i = 0;i<32 * 1000 * 1000; i++)
{
       MiaStruttura *pStruct = new MiaStruttura ;
        maiLista->push_back(pStruct );  //si copia il  puntatore
}
cosi la memoria č 880 MB !!!    :(

 essere  138 MB giusto?  eppure ora dinamicamente non alloco nulla ???
             ^^^^^^
pardon dovrebbe essere 192.000.000 = 183 MB
per arrivare a 506 ce ne vuole :(

Nicola Musatti ha scritto:

anche secondo me cmq questo è vero.
NEW (che poi chiama malloc, sui PC 80x86), è una funzione di 
allocazione generica e deve garantire di allineare correttamente 
qualsiasi tipo. Per antico retaggio, sempre degli 80x86 dai 
(brutti) tempi della segmentazione della memoria, questo 
allineamento era considerato un "paragrafo", di 16 byte.
Cmq la granularità dell'allocazione (che sul mio Visual C++ 
coincidono, e sono di sedici byte entrambi), imho non 
necessariamente devono coincidere per forza (anche se in pratica 
è la cosa più furba).
La granularità (dimensione del blocco minimo) potrebbe anche 
essere multipla dell'allineamento, anche se 32 byte già sono 
sprecosi per le stringhe piccole e credo non vengano 
implementati. Ad es. su windows c'è una funzione di allocazione 
di memoria per le aree di trasferimento di file non bufferizzati 
a lettura sincrona che devono avere granularità di 512 byte.
La granularità potrebbe anche essere sottomultipla (o 
inferiore), ma in questo caso l'assurdo sarebbe ancora maggiore 
: volendo ottemperare comunque all'allineamento di tutti i 
blocchi, allora dovrebbero restare dei vuoti inutilizzati tra 
l'uno e l'altro, nel qual caso tanto varrebbe estendere la 
granularità all'allineamento.
ciao
Soviet
CUT much



ma io infatti mi aspettavo un pò di overhead, ci mancherebbe, ma qui stiamo
oltre il doppio.... quasi il triplo...

 un solo colpo, invece che una lista dinamica.
chiaramente ci avevo pensato, ma il problema č che dopo questa lista la devo
ordinare, e volevo usare  il sort delle liste std (sono pigro...)  :)


Si', quando passi *pstruct a push_back stai richiedendo di fare una 
copia. Inoltre la std::list e' una lista double-linked quindi devi 
aggiungere 2 puntatori ad ogni oggetto. In totale ogni elemento della 
lista occupa 6+4*2=14 bytes. Immagino che quando vengono allocati ne 
sprechi altri 2 per l'allineamento quindi 16 bytes per elemento. 
16*32*1000*1000 = 544000000 che mi sembra che torni...
E.

 ordinare, e volevo usare  il sort delle liste std (sono pigro...)  :)
La libreria standard contiene funzioni per ordinare anche array e 
std::vector. Sono qsort, std::sort e std::stable_sort.
In particolare, la std::sort, contenuta in <algorithm>, e' tipicamente 
molto piu' veloce della std::list::sort.
Per esempio:
   bool compare(const MiaStruttura & a, const MiaStruttura & b) {
     if (a.campo1 < b.campo1) return true;
     if (a.campo1 > b.campo1) return false;
     return a.campo2 < b.campo2;
   }
...
   vector<MiaStruttura> miaLista;
   const long sz = 8 * 1000 * 1000;
   miaLista.reserve(sz);
   for(int i = 0; i < sz; ++i) {
     miaLista.push_back(MiaStruttura());
   }
   sort(miaLista.begin(), miaLista.end(), compare);
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

 cosi la memoria è 880 MB !!!    :(
Qui invece hai 3 puntatori per il nodo piu' la tua struttura, ovvero
20 byte per elemento, per un totale di 610 MB. Questo e' notevolmente
meno dei tuoi 880. Una spiegazione potrebbe essere che la tua
struttura occupa in realta' 16 byte perche' questa, come dice se non
sbaglio Soviet Mario, e' la dimensione minima usata dall'allocatore
standard, mentre i nodi della lista usano un'allocatore ottimizzato ed
occupano effettivamente 12 byte. Il totale sarebbe di circa 854 MB.
Ciao,
Nicola

 ordinare, e volevo usare  il sort delle liste std (sono pigro...)  :)
Essere pigro e' solo sano, ma se devi ordinare i tuoi elementi la
lista e' il contenitore peggiore possibile. O usi un contenitore
ordinato, tipo std::set o std::map, in modo da avere gli elementi
ordinati in partenza, o usi un std::vector e poi ordini con std::sort.
L'uso del vector ti garantirebbe anche il minimo spreco di memoria
possibile. In piu' dal momento che conosci a priori il numero di
elementi puoi usare capacity() ed evitare il problema delle
riallocazioni.
Ciao,
Nicola

 riallocazioni.
Mi inserisco nel thread solo x dire che se l'OP avesse la possibilita'
di usare la seguente struttura invece di quella con i campi ribaltati
typedef struct
{
     int    campo2;
     short  campo1;
} MiaStruttura;
... PROBABILMENTE otterrebbe elementi da 6 bytes invece che 8 :)
Con il GCC la cosa non e` vera nemmeno in questo caso, a meno di non 
utilizzare prima della dichiarazione della struttura:
#pragma pack(push, 2)
.. e dopo la dichiarazione della struttura:
#pragma pack(pop)
Per portare applicazioni che dipendono da formati di dati binari tali 
direttive sono molto comode :)
Bye,
  Gabry