Hjelp med minne allokering

[Sigdal]

Hei,

 

Jeg lurer på hvor stort behovet for minne bør være før man begynner å allokere objekter til Heapen? Eksempelvis vil jeg lage ca 15000 objekter av en egendefinert klasse (kalt Node) i hver 'run' av programmet, før de slettes, og vurderer om de skal lagres lokalt eller på Heapen

 

"sizeof(Node);" sier at denne kun er 4 bytes stor (det synes jeg er lite i.o.m. at deklarasjonen inneholder tre pointere, en int, samt noen metoder). 4 byte må vel kun være størrelsen på pointeren som peker til objektet Node?

 

 

Totalt minne jeg vil legge beslag på blir da 15000*4 = ca 60kbytes.

 

Fint om noen kunne kommentere.

mvh Sigdal

Endret 14. juli 2010 av Sigdal

[[kami]]

ja, det høres litt rart ut.

Her er et eksempel som viser hvordan du henter størrelsen på objektet:

class Dummy
{
 private:
   int a,b,c;
   int* peker;
};

int main ()
{
 Dummy* test = new Dummy;

 std::cout << "class size: " << sizeof(Dummy) << ", object pointer size: " << sizeof(test)  << std::endl;

 return 1;
}

 

class size: 24, object pointer size: 8

Forklaring: object size: 8 bytes fra int* peker, 4 bytes hver fra 3 ints, paddingen blir 4 bytes = 24b

Padding gjør den fordi den vil aligne minnet lik det største pod (plain old datatype) typen (kan også settes i compiler options) og siden størrelsen på en peker er 8 bytes. Den fyller med andre ord ut gapet, slik at den kan lese 8 og 8 bytes (dvs at den kan lese inn hele pekeren inn i minnet). Hadde den ikke paddet hadde den lest inn halve pekeren, så måtte den lest inn nye 8 bytes, og kombinert de 2, noe som ikke hadde vært særlig effektivt.

Med andre ord kan du fint slenge på en int til i denne klassen uten at størrelsen vil øke!

Kompilert og kjørt på 64bit linux. (pekerstørrelsen er forskjellig på 32 og 64 bit)

 

Størrelsen på klassen forandrer seg ikke selv om du lager mange metoder. om du lager en virituel funksjon vil størrelsen på klassen øke med 8 (og funksjonskallet til en virtual er litt tregere en til en ikke virtual)

 

Jeg ser ingen problemer med å allokere 15k av objektene dine på heapen om det er noe som allokeres på program start og slettes på program slutt. Om du derimot allokerer 15k objekter hver frame, kan det hende at det vil bli en bottleneck for deg og at du må optimere det litt. (gjerne ved å bruke en stl::vector for eksempel, den beholder nemmlig minnet du har gitt den når du fjerner objekter fra den!)

 

En fin huskeregel er å alltid putte de største objektene øverst i klassen.

class Dummy
{
   char a;
   int* m_test;
   char b;
};
/// Size = 24 bytes pga padding, selv om vi bare bruker 10 bytes!
/// Her må den legge på 7 bytes etter a, fordi int* er 8 bytes stor, og 7 bytes etter b for å få regnskapet til å gå opp
class Dummy
{
   int* m_test;
   char a;
   char b;
};
/// Size = 16 bytes pga padding, men den trenger kun å padde på slutten (6 bytes)

Endret 15. juli 2010 av [kami]

[Sigdal]

Hei, takk for svar! (Jeg er på 32 bits windows forresten).

 

Nå blir alle objektene av type Node lagret på Heapen (ca 15000 stk). Det jeg egentlig mente å spørre om var om, gitt at jeg også trenger en 'array av pointers' til disse objektene - om denne arrayen av pointere også bør lagres på Heapen eller om det er 'ufarlig' å ha den i 'vanlig minne', med tanke på størrelsen (15000*4bytes)?

 

Isåfall; hvordan deklarer jeg en slik array? Jeg har kun fått det til i 'vanlig minne' ved å bruke 'Node * A[15000];' ..

 

Takk igjen,

mvh, Sigdal

Endret 15. juli 2010 av Sigdal

[[kami]]

Isåfall; hvordan deklarer jeg en slik array? Jeg har kun fått det til i 'vanlig minne' ved å bruke 'Node * A[15000];' ..

 

Se på std::vector

 

Den kan resizes utover i programmet.

Eks:

#include <vector>
typedef std::vector<Node*> NodeVect_t;
NoceVec_t A(15000);

void add_node(Node*p)
{
 A.push_back(p);  // vil automatisk forstørre plassen din om du har flere enn 15k elementer også!
}

Node* remove_node(Node*p)
{
 Node* ret = NULL;
 NodeVec_t::iterator iNodeFind = find(A.begin(), A.end(), p);
 if (iNodeFind != A.end()
 { 
   ret = *iNodeF
   A.erase(iNodeFind);
 }
 return ret;
}

void run()
{
 for (NodeVec_t::iterator i = A.begin(); i != A.end(); ++i)
 {
   Node* noden_din = *i;
   noden_din->run();
 }
}

int main()
{ 
 Node*p = new Node(1,2,3);
 add_node(p);
 add_node(new Node(3,3,3));
 Node *d = remove_node(p);
 assert(d==p);
 delete d;
 return 1;
}

er du i en const funksjon må du bruke const_iterator (og da kan du kun kalle const funksjoner på Node objektet)

Endret 15. juli 2010 av [kami]

[[kami]]

Det er forøvrig ufarlig å ha minnet på stacken ("vanlig minne"), men jeg anbefaler sterkt at du bruker std::vector.

 

jeg tviler også på at klassen din tar 4 bytes, iogmed du sa du hadde 3 pekere og en int. På et 32 bits system vil størreelsen din bli 4*3+4 = 16 bytes. Så du allokerer 4 ganger mer minne enn det du tror. (15000*16=240k)

[Sigdal]

Jeg leser litt på nettet at Heapen og Stacken blir dynamisk justert av Windows; så da er er det vel ikke veldig kritisk å begrense bruk av stacken, slik som det var på tidligere operativsystemer, kanskje....

 

Nytt spørsmål: Jeg har en array av 'k' antall pointere til Nodeobjekter i A[]. (Verifisert at fungerer). Jeg vil så slette alt av dette i slutten av main(). Da skrev jeg:

 

for (int i=0; i<k; i++) delete A;' // skulle slette hvert av Nodeobjektene?

delete [] A; //skulle slette arrayen-av-pointere til Nodeobjektene?

 

Kompilerer ok, men jeg får runtimeerror på begge. Hvordan kan jeg slettet arrayen-av-pointere (på stacken) og alle objektene den peker til (som ligger på Heapen)?

 

(Nodeobjektene er ikke allokert på Heapen 'i en batch' men allokert rekursivt, en om gangen (15000 ganger) vha 'Node * ptr = new Node;'. Jeg regner med at Windows XP vil allokere dette greit, selvom det blir 15000 ganger?)

 

mvh Sigdal

Endret 15. juli 2010 av Sigdal

[zotbar1234]

Forklaring: object size: 8 bytes fra int* peker, 4 bytes hver fra 3 ints, paddingen blir 4 bytes = 24b (...) Med andre ord kan du fint slenge på en int til i denne klassen uten at størrelsen vil øke!

Kompilert og kjørt på 64bit linux. (pekerstørrelsen er forskjellig på 32 og 64 bit)

 

En ting som er verdt å merke her er at en implementasjon kan gjerne bruke litt plass til minnehåndtering selv per hvert allokerte objekt (f.eks. en peker), slik at blokkene som allokeres faktisk er større bare pga det (og ikke bare pga paddingen). En annen implementasjonsspesifikk observasjon er at det slettes ikke er sikkert at implementasjonen allokerer eksakt det antall bytes man blir bedt om (+ evt. plass for bokholderi): det kan gjerne tenkes at minste allokeringsenhet er, f.eks. 16 bytes, og om man ber om 1 eller 16 bytes er således lite interessant, da det alltid allokeres minst 16 bytes.

 

Dog, for 15'000 så små objekter på en vanlig maskin er alt dette kun av teoretisk interesse.

 

Størrelsen på klassen forandrer seg ikke selv om du lager mange metoder. om du lager en virituel funksjon vil størrelsen på klassen øke med 8 (og funksjonskallet til en virtual er litt tregere en til en ikke virtual)

 

Nei, det er ikke alltid tilfellet (både når det gjelder økningen på 8 og hastigheten av virtuelle metodekall).

[zotbar1234]

Nytt spørsmål: Jeg har en array av 'k' antall pointere til Nodeobjekter i A[]. (Verifisert at fungerer). Jeg vil så slette alt av dette i slutten av main(). Da skrev jeg:

 

for (int i=0; i<k; i++) delete A;' // skulle slette hvert av Nodeobjektene?

delete [] A; //skulle slette arrayen-av-pointere til Nodeobjektene?

 

Dersom du allokerer plassen som A henviser til vha "new[]", så skal den frigjøres vha "delete[]", og kun da. Dersom du har en lokal variabel:

 

Node *A[sz];

 

Så skal ikke plassen som A henviser til frigjøres eksplisitt.

 

Når det gjelder "delete A", så er forutsetningen for at det skal virke at hvert element er blitt allokert med new eller er NULL. Er det faktisk tilfellet? (evt. kunne du poste det minste eksempelet som illustrerer problemet).

 

Kompilerer ok, men jeg får runtimeerror på begge. Hvordan kan jeg slettet arrayen-av-pointere (på stacken) og alle objektene den peker til (som ligger på Heapen)?

 

Plassen til variablene med automatic storage duration frigjøres automatisk når man forlater den tilsvarende blokken. Plassen til variablene med static storage duration frigjøres når programmet avslutter. Plassen som man allokerer med new/new[]/malloc frigjøres hhv av delete/delete[]/free (og da i den rekkefølgen).

[Sigdal]

Minste eksempel som illustrerer problemet:

 

int a = 0;

Node * A[100];

void StorePtr(Node * Ptr) { A[a]=Ptr; a++; } //inlinefunksjon

 

void main() { //Lager 10 objekter og kaller funskjonen StorePtr

for (int i=0; i < 10 ; i++) {

Node * Ptr = new Node;

StorePtr(Ptr);

}

//Så skal jeg slette objektene og array-av-pointere og jeg får runtime error når disse linjene er med i koden:

for (int b=0; b < 10 ; b++) delete A;

delete [] A;

}

 

Alle 10 pointere som blir forsøkt slettet her er assignet til hvert sitt nodeobjekt på heapen. Allikevel krasjer det.

 

Spørsmål: Hva blir riktig kode her for å slette både array-av-pointere og objekter?

 

Tillegsspørsmål: Finnes det en enkel måte å initialisere de 90 resterende pointerne i A[100] til NULL?

 

/Sigdal

Endret 16. juli 2010 av Sigdal

[[kami]]

//Så skal jeg slette objektene og array-av-pointere og jeg får runtime error når disse linjene er med i koden:

for (int b=0; b < 10 ; b++) delete A;

delete [] A;

}

// Spørsmål: Hva blir riktig kode for å slette både array-av-pointere og objekter?

 

fjern delete [] A.

 

du har allokerte plass til 100 pekere på stacken. (som blir automatisk behandlet)

 

 

Tillegsspørsmål: Finnes det en enkel måte å initialisere de 90 resterende pointerne i A[100] til NULL?

 

Ja, bruk std::vector. Det er seriøst mye enklere å bruke enn å dille rundt med arrays.

std::vector<Node*> nodeListe(100,NULL);  // voila, alle elementene settes til NULL.
nodeListe[0] = new Node(..);
nodeListe[1] = new Node(..);

[[kami]]

Størrelsen på klassen forandrer seg ikke selv om du lager mange metoder. om du lager en virituel funksjon vil størrelsen på klassen øke med 8 (og funksjonskallet til en virtual er litt tregere en til en ikke virtual)

 

Nei, det er ikke alltid tilfellet (både når det gjelder økningen på 8 og hastigheten av virtuelle metodekall).

 

Sant nok, klassestørrelsen øker ikke alltid med 8, men den øker. Hvor mye den øker er compiler spesifikt.

 

Å kalle en virtual funksjon, derimot, er et tregere kall med mindre compileren har klart å optimere bort virtual kallet og gjort det !virtual (om den klarer å skjønne at ingen arver). Dette er fordi det må tas et ekstra oppslag i vtable.

 

Wikien har faktisk litt grei info om det (http://en.wikipedia.org/wiki/Virtual_table)

A virtual call requires at least an extra indexed dereference, and sometimes a "fixup" addition, compared to a non-virtual call, which is simply a jump to a compiled-in pointer. Therefore, calling virtual functions is inherently slower than calling non-virtual functions. Experiments indicate that approximately 6-13% of execution time is spent simply dispatching to the correct function, though the overhead can be as high as 50%[3]. The cost of virtual functions may not be so high on modern CPU architectures due to much larger caches and better branch prediction.

[Sigdal]

Kami:

Hvordan lager jeg en 2-dimensjonal array med denne std::vector?

Hvordan kan jeg slette den? (Nødvendig!)

Hvorfor er det så mye bedre å bruke std::vector?

 

mvh S

Ps: Gjerne diskutere v-tabeller, osv på en annen tråd:-) Jeg er kun interessert i praktisk kode her.

Endret 16. juli 2010 av Sigdal

[[kami]]

Hvordan lager jeg en 2-dimensjonal array med denne std::vector?

 

std::vector< std::vector<float> > yxArray;

for (int y =0; y < 100; y++)

for (int x = 0; x < 100; x++)

yxArray[y][x] = 0.1f;

 

Hvordan kan jeg slette den? (Nødvendig!)

 

yxArray.clear(); // sletter stuff (NB! har du pekere i std::vectoren blir de *ikke* slettet av dette. det må du gjøre selv. (men her vil det i stor grad gå an å ikke bruke pekere! - prøv det!)

 

det er også vanlig å bruke iterators for å iterere over containers istede for å bruke [] operatorene (xyArray[0][0] accesser element 0, std::vector< std::vector<float> >::iterator = yxArray.begin() accesser element 0.)

 

Hvorfor er det så mye bedre å bruke std::vector?

- Den *største fordelen* er at du kan vokse vectoren så mye du vil, noe man ikke kan med arrays. Om du for eksempel skal lese inn en liste du ikke vet hvor stor er, er ikke det noe problem. Bare kall myvector.push_back() til dataen går tom for minne.

- Den er tryggere - bruker du iterators vil du aldri accesse minne som du ikke har tilgang på (ie, med arrays kan du gjøre char array[10]; array[11] = 'a'; // minneoverskrivning.). Gjør du dette med vector i debug vil den gi deg en kontrollert krasj med callstack (assert).

- Den er like raskt som et dynamisk array å accesse (men ørlitt tregere enn static, men i de fleste tilfeller er ikke dette noe man merker)

- støtter standard algoritmene: (std::vector<int> myvector;)

- så for å sortere en vector kan du bare gjøre sort (myvector.begin(), myvector.end()); (her sorteres de med standard <> operatorene)

- for å finne et element std::vector<int>::iterator iFind = find(myvector.begin(), myvector.end(), 10);

if (iFind != myvector.end()) cout << "fant 10!";

- kan fjerne elementer i midten

myvector.erase(iFind); // vil fjerne 10 fra eksempelet ovenfor.

 

Du vil støte på stl (eller tilsvarende konsepter) over alt når/om du begynner å programmere i proffesjonelt. stl er et konsept som kom for ganske lenge siden og er brukt mye i kode rundt om kring.

 

På wikien finnes det flere eksempler på hvordan du kan bruke std::vector

http://en.wikipedia.org/wiki/Vector_%28C%2B%2B%29

[Sigdal]

Takker. Men jeg er allikevel nysgjerrig på å vite hva som var feil med dette fra to innlegg siden:

 

for (int b=0; b < 10 ; b++) delete A;

Endret 16. juli 2010 av Sigdal

[[kami]]

Takker. Men jeg er allikevel nysgjerrig på å vite hva som var feil med dette fra to innlegg siden:

 

for (int b=0; b < 10 ; b++) delete A;

delete [] A;

 

(NB: det var ikke så enkelt som bare å slette siste linje, som du foreslo..)

 

rart. jeg får ingen feil... og ser heller ingen feil med koden. Her er koden og all output fra da jeg kjørte.

 

> cat test.cpp

#include <iostream>

class Node
{
   char a;
   char b;
};

int a = 0;
Node * A[100];
void StorePtr(Node * Ptr)
{
 A[a]=Ptr;
 std::cout << "lager node " << a << "\n";
 a++;
} //inlinefunksjon

int main()
{ //Lager 10 objekter og kaller funskjonen StorePtr
 for (int i=0; i < 10 ; i++) {
   Node * Ptr = new Node;
   StorePtr(Ptr);
 }
 //Så skal jeg slette objektene og array-av-pointere og jeg får runtime error når disse linjene er med i koden:
 for (int b=0; b < 10 ; b++)
 {
   delete A[b];
   std::cout << "sletter node " << b << "\n";
 }
 return 1;
}

 

[14:48:41] anderse@yama:~/depot/TSW/Branches/tsw_gamecode/TSWCode/tools/MasterBuilder

> g++ test.cpp

[14:48:47] anderse@yama:~/depot/TSW/Branches/tsw_gamecode/TSWCode/tools/MasterBuilder

> valgrind ./a.out

==15199== Memcheck, a memory error detector.

==15199== Copyright © 2002-2005, and GNU GPL'd, by Julian Seward et al.

==15199== Using LibVEX rev 1575, a library for dynamic binary translation.

==15199== Copyright © 2004-2005, and GNU GPL'd, by OpenWorks LLP.

==15199== Using valgrind-3.1.1, a dynamic binary instrumentation framework.

==15199== Copyright © 2000-2005, and GNU GPL'd, by Julian Seward et al.

==15199== For more details, rerun with: -v

==15199==

lager node 0

lager node 1

lager node 2

lager node 3

lager node 4

lager node 5

lager node 6

lager node 7

lager node 8

lager node 9

sletter node 0

sletter node 1

sletter node 2

sletter node 3

sletter node 4

sletter node 5

sletter node 6

sletter node 7

sletter node 8

sletter node 9

==15199==

==15199== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 5 from 2)

==15199== malloc/free: in use at exit: 0 bytes in 0 blocks.

==15199== malloc/free: 10 allocs, 10 frees, 20 bytes allocated.

==15199== For counts of detected errors, rerun with: -v

==15199== All heap blocks were freed -- no leaks are possible.

 

 

 

== Her er hvordan det ser ut med delete [] A forøverig.

> g++ test.cpp

test.cpp: In function `int main()':

test.cpp:31: warning: deleting array `Node*A[100]'

[14:50:33] anderse@yama:~/depot/TSW/Branches/tsw_gamecode/TSWCode/tools/MasterBuilder

> valgrind ./a.out

==15449== Memcheck, a memory error detector.

==15449== Copyright © 2002-2005, and GNU GPL'd, by Julian Seward et al.

==15449== Using LibVEX rev 1575, a library for dynamic binary translation.

==15449== Copyright © 2004-2005, and GNU GPL'd, by OpenWorks LLP.

==15449== Using valgrind-3.1.1, a dynamic binary instrumentation framework.

==15449== Copyright © 2000-2005, and GNU GPL'd, by Julian Seward et al.

==15449== For more details, rerun with: -v

==15449==

lager node 0

lager node 1

lager node 2

lager node 3

lager node 4

lager node 5

lager node 6

lager node 7

lager node 8

lager node 9

sletter node 0

sletter node 1

sletter node 2

sletter node 3

sletter node 4

sletter node 5

sletter node 6

sletter node 7

sletter node 8

sletter node 9

==15449== Invalid free() / delete / delete[]

==15449== at 0x4905B14: operator delete[](void*) (vg_replace_malloc.c:256)

==15449== by 0x400AC7: main (in /home/anderse/depot/TSW/Branches/tsw_gamecode/TSWCode/tools/MasterBuilder/a.out)

==15449== Address 0x5013E0 is not stack'd, malloc'd or (recently) free'd

==15449==

==15449== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 5 from 2)

==15449== malloc/free: in use at exit: 0 bytes in 0 blocks.

==15449== malloc/free: 10 allocs, 11 frees, 20 bytes allocated.

==15449== For counts of detected errors, rerun with: -v

==15449== All heap blocks were freed -- no leaks are possible.

Endret 16. juli 2010 av [kami]

[Sigdal]

Det virker da ja.

 

En ting som ikke er representativt med koden min er at nodene blir _laget og allokert_ rekursivt, dvs 'Node * ptr = new Node' er deklarert i en metode i Nodeklassen, dvs første nodeobjekt lager Nodeobjekt nr 2 også videre. A[0] har pointeren til førstenode. Når førsteNodeobjekt blir slettet med 'delete A[0];' vil ikke da de resterende nodene bli slettet automatisk, iom at de alle "stammer fra" førstenode? Slik at det er unødvendig å 'delete' de resterende objektene, slik som gjort i koden?

 

/S

Endret 16. juli 2010 av Sigdal

[zotbar1234]

Sant nok, klassestørrelsen øker ikke alltid med 8, men den øker. Hvor mye den øker er compiler spesifikt.

 

Hvorfor må den øke? (Jeg understreker -- må (som i "absolutt alle situasjoner, selv der statisk analyse gjør det mulig å bestemme den kalte metoden")).

 

Å kalle en virtual funksjon, derimot, er et tregere kall med mindre compileren har klart å optimere bort virtual kallet og gjort det !virtual (om den klarer å skjønne at ingen arver). Dette er fordi det må tas et ekstra oppslag i vtable.

 

Ah, nå kom det en "med mindre", ja. Takk, det var det jeg ville fram til.

[zotbar1234]

En ting som ikke er representativt med koden min er at nodene blir _laget og allokert_ rekursivt, dvs 'Node * ptr = new Node' er deklarert i en metode i Nodeklassen, dvs første nodeobjekt lager Nodeobjekt nr 2 også videre. A[0] har pointeren til førstenode. Når førsteNodeobjekt blir slettet med 'delete A[0];' vil ikke da de resterende nodene bli slettet automatisk, iom at de alle "stammer fra" førstenode?

 

Nei. Hver new som du skriver i koden må ha en matchende delete som du også må skrive i koden. Du kan slette nodene rekursivt, eller, dersom du kan få tilgang til alle nodene via andre pekere, gjennom andre pekere. Men i det du frigjør et objekt med delete, vil du kun frigjøre plassen som objektet opptar og ikke plassen som pekere i det objektet du frigjør måtte peke på.

[Sigdal]

Takker. Hvordan er nå problematikken med Stack vs. Heap på f.eks windows XP?

"Jeg leser litt på nettet at Heapen og Stacken nå blir dynamisk justert av Windows; så da er er det vel ikke veldig kritisk å begrense bruk av stacken, slik som det var på tidligere operativsystemer"

[[kami]]

Takker. Hvordan er nå problematikken med Stack vs. Heap på f.eks windows XP?

"Jeg leser litt på nettet at Heapen og Stacken nå blir dynamisk justert av Windows; så da er er det vel ikke veldig kritisk å begrense bruk av stacken, slik som det var på tidligere operativsystemer"

 

stemmer, i de fleste tilfeller har det lite å si. stack allocation er også i de fleste (alle?) tilfeller raskere (fordi den kun trenger å flytte stack pekeren).