[C++] Deleten van ontzettend veel instanties

[Verwijderd]

Hallo,

Ik gebruik een stl::vector om pointers op te slaan naar instanties van bepaalde objecten, waarvan het aantal op kan lopen tot wel zo'n 100000.

Het deleten van deze, alsmede het aanmaken duurt een poos. Hoe kan ik dit versnellen?

[curry684]

Snellere CPU kopen. Het vrijgeven van 100000 blokken geheugen kost nu eenmaal een hoop kruim, daar doe je niets aan.

Of je gaat die vector gewoon gebruiken zoals het hoort en je ditcht die pointers, gewoon objecten rechtstreeks erin. Dan is het nog maar 1 blok geheugen

[Soultaker]

Als het allemaal instanties van dezelfde klasse zijn, zou je je je eigen allocator kunnen gebruiken om grote blokken data tegelijk te alloceren. Daarvoor zou je operator new en operator delete moeten overriden.

[Verwijderd]

curry684: dan moet hij toch 100000 keer de copy constructor aanroepen?

soultaker: het zijn 3 klassen derived van 1 enkele klasse

[BoAC]

Verwijderd schreef op vrijdag 26 november 2004 @ 16:33:
curry684: dan moet hij toch 100000 keer de copy constructor aanroepen?

soultaker: het zijn 3 klassen derived van 1 enkele klasse

Haal je code dan door een profiler heen..
Ik heb op een AMD 300 weinig problemen gehad met 100000 objecten in een bsp. Dit was in een grafisch tekenpakket, dus de objecten waren ook nog eens van verschillend type.
Geef es een uitgebreidere beschrijving van je objecten

[curry684]

Soultaker schreef op vrijdag 26 november 2004 @ 16:30:
Als het allemaal instanties van dezelfde klasse zijn, zou je je je eigen allocator kunnen gebruiken om grote blokken data tegelijk te alloceren. Daarvoor zou je operator new en operator delete moeten overriden.

Waarom operator new overloaden?

Je kunt gewoon een pooled allocator gebruiken middels placement new, hoef je niks voor te overloaden. Alloceren per zeg 1000*sizeof(class), en dan initialiseren middels placement new \o/

Verwijderd schreef op vrijdag 26 november 2004 @ 16:33:
curry684: dan moet hij toch 100000 keer de copy constructor aanroepen?

Bij het deleten toch niet?

soultaker: het zijn 3 klassen derived van 1 enkele klasse

Ow polymorphisme, dan heb je een beetje pech ja Dan kun je overigens alsnog een pooling class factory schrijven per derivant though.

[ Voor 5% gewijzigd door curry684 op 26-11-2004 16:43 ]

[Soultaker]

curry684 schreef op vrijdag 26 november 2004 @ 16:42:
Waarom operator new overloaden?

Je kunt gewoon een pooled allocator gebruiken middels placement new, hoef je niks voor te overloaden. Alloceren per zeg 1000*sizeof(class), en dan initialiseren middels placement new \o/

Een allocator is toch zo'n ding wat die STL containers gebruiken? Daar heb je toch niets aan als je instanties buiten de container gemaakt worden? Of hoe werkt dat normaal gesproken?

[curry684]

Euj nee, allocator is in mijn vocabulaire een algemeen ding dat dingen alloceert Als je dus een pooling factory bouwt die per tig-duizend instances alloceert kun je deze ook voor derived classes gebruiken

[Soultaker]

Hmz, volgens mij hebben we het dan over hetzelfde ding. Ik zou in zo'n geval operator new en delete willen overloaden, zodat de rest van de code hetzelfde blijft. Voor de werking van het programma maakt het immers niet uit hoe instanties gealloceerd worden.

[curry684]

Mmmmja op zo'n fiets, da's ook nog geen slecht idee idd, een singleton class factory static in de te creeren class opbergen en dan via z'n eigen operator new werken

* curry684 vraagt zich alleen af of TS er nu nog iets van snapt

[Zoijar]

Kijk anders eens naar de Loki library, die heeft een optimized small-object allocator, misschien kan je daar iets aan sleutelen. Of...misschien als veel objecten ongeveer gelijk zijn, dan kan je een 'Flyweight' pattern gebruiken. Dat werkt bv bij een tekst verwerker, als alle characters objecten zijn. Met flyweight hoef je dan slechts voor elk verschillend karakter een object aan te maken.

[Verwijderd]

even voor de duidelijkheid:
het gaat hier om simpele objecten die hooguit 12 bytes groot zijn per stuk.

curry684: ik moet de objecten ook razendsnel instantieren, aangezien deze uitgelezen worden uit een file en in 1 keer in een het geheugen (vector) geplaatst worden. Daarom lijkt mij een kopie van de instantie die je op de stack gemaakt hebt in de vector plaatsen niet echt handig, want dan gaat het deleten wel snel, maar het plaatsen in de vector duurt weer langer...

Een object pool lijkt mij wel erg interessant. Er zijn volgens mij genoeg kant en klare implementaties te vinden, dus ik denk dat ik daar maar eens naar ga kijken en ga zien of ik qua performance er (veel) op vooruit ga. Bedankt allemaal, zodra ik meer weet over de performancewinst, zal ik het hier melden.

[MSalters]

12 bytes en je zet pointers in een vector? Sorry, dat is gewoon niet handig. Zet dat soort objecten direct in een std::deque. Spaar je de moeite van custom allocators en probeer de standaard spullen eerst.

[farlane]

Het zijn een basisklasse en afgeleiden daarvan

[Verwijderd]

inderdaad, niet aan gedacht dat het performanceprobleem ook wel eens bij de container kon liggen ipv bij het instantieren van de objecten.

bedankt, ik eerst eens proberen mijn vector te vervangen door een deque en daarna kijken of dit een performancewinst oplevert.

[Verwijderd]

farlane: dat maakt in het geval van het verwisselen van de vector met een deque toch niet uit? ik sla toch alleen pointers van het baseclass type?

[curry684]

Zolang je alleen lineair per veul aanmaakt en lineair per veul delete zal een vector (veel) sneller zijn dan een deque.

[Verwijderd]

ik zie het volgende staan op "the codeproject":
vector is the type of sequence that should be used by default. ... deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence.

lijkt mij in dit geval een deque interessanter...

[Zoijar]

Ik snap eerlijk gezegd niet waarom een deck ineens veel sneller zou zijn....?

[curry684]

Verwijderd schreef op vrijdag 26 november 2004 @ 22:54:
ik zie het volgende staan op "the codeproject":
vector is the type of sequence that should be used by default. ... deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence.

lijkt mij in dit geval een deque interessanter...

Je zegt dat je in 1 ruk 100000 instances inleest en push_back erop doet, en ze dan alle 100000 tegelijk delete?

Waar komen exact die 'insertions and deletions at the beginning' voor waarvoor een double ended queue ineens geschikter zou zijn dan een vector?

[farlane]

Verwijderd schreef op vrijdag 26 november 2004 @ 22:49:
farlane: dat maakt in het geval van het verwisselen van de vector met een deque toch niet uit? ik sla toch alleen pointers van het baseclass type?

Dat klopt, maar MSalters wilde de objecten direct in de container opslaan volgens mij. ( Dus niet de pointers )

[MrBucket]

Het opslaan van pointers in een vector of deque zal volgens mij niet de bottleneck zijn, eerder het alloceren en vrijgeven van al die kleine objecten van 12 bytes. Ik weet niet precies hoe de C runtime geheugenblokken alloceert, maar om een idee te krijgen van hoeveel werk er wordt verzet tijdens dat alloceren en deleten, trace eens door de new en delete code heen. Ik meen me te herinneren dat het soort van doubly linked list is.

Mocht het probleem hier idd zitten, dan zou ik idd een soort van class factory schrijven die intern een groot blok geheugen alloceert (bijv een array met 1000 entries van 16 a 20 bytes) en die zelf het alloceren en deleten voor zijn rekening neemt door te vlaggen of zo'n entry in gebruik is.

[MSalters]

deque is een page-based structuur. Als je heel veel geheugen alloceert is dat beter; vector moet anders een onafgebroken blok alloceren. Nou is dat toegegeven met 1.2M nog niet zo belangrijk; bij 1.2G is het een heel ander verhaal (dat lukt niet met vector in Windows)

Evengoed is het in deze handiger om de objecten direct in de container op te slaan. De standaard operator new kost waarschijnlijk >=16 bytes per allocatie, plus 4 bytes voor de pointers - met bijbehorend verlies van "locality of reference". Direct in de container is dan handiger.

Nou moet er meteen bij worden gezet dat je moet gaan prutsen om objecten van drie verschillende types in een container te zetten, dwz je moet waarschijnlijk het soort trucen gaan uithalen dat boost::any doet. (wrapper, char[] storage, placement new).

Zonder dat is een pool allocator inderdaad de betere oplossing, al was het alleen maar omdat je dan maar 4 bytes overhead hebt per 100000 objecten, ipv 4 bytes per object.

[Zoijar]

Misschien dat je ipv inheritance, een soort van vlag op kan slaan bij elk object. Dan maak je daarna geen gebruik van virtuele functies, maar check je die vlag voor wat je moet doen. Als je toch weet dat je maar 3 objecten hebt... (of natuurlijk een functie pointer, of een index in een externe functie pointer tabel...) het is natuurlijk niet zo netjes en extendable etc, maar het kan wel een hoop problemen schelen. Wat maak je eigenlijk? 12 bytes per object klinkt als een of ander particle systeem (vector van 3 floats?) met 3 particles die zich verschillend gedragen?

[ Voor 9% gewijzigd door Zoijar op 27-11-2004 15:56 ]

[MrBucket]

Zoijar schreef op zaterdag 27 november 2004 @ 15:54:
Misschien dat je ipv inheritance, een soort van vlag op kan slaan bij elk object. Dan maak je daarna geen gebruik van virtuele functies, maar check je die vlag voor wat je moet doen. Als je toch weet dat je maar 3 objecten hebt... (of natuurlijk een functie pointer, of een index in een externe functie pointer tabel...) het is natuurlijk niet zo netjes en extendable etc, maar het kan wel een hoop problemen schelen. Wat maak je eigenlijk? 12 bytes per object klinkt als een of ander particle systeem (vector van 3 floats?) met 3 particles die zich verschillend gedragen?

Bijkomend voordeel is dat de grootte van je objecten met 4 bytes verminderd wordt, omdat je geen vtable-pointer meer nodig hebt.

[Verwijderd]

Dan ga ik toch voor de pool, want de netheid van de code staat voorop, dus wil toch inheritance gaan gebruiken ipv een type-id op te slaan bij iedere instantie.

ik maak een indexer die interessante punten opslaat in een file en aangeeft wat voor een punt het betreft. (offset + type + evt. specifieke data)

[MSalters]

MrBucket schreef op zaterdag 27 november 2004 @ 16:51:
[...]
Bijkomend voordeel is dat de grootte van je objecten met 4 bytes verminderd wordt, omdat je geen vtable-pointer meer nodig hebt.

En vermeerderd met 4 bytes omdat je de flag moet opslaan. Dat is namelijk precies wat een vtable pointer doet, het object type identificeren.

[MrBucket]

MSalters schreef op zaterdag 27 november 2004 @ 19:52:
[...]

En vermeerderd met 4 bytes omdat je de flag moet opslaan. Dat is namelijk precies wat een vtable pointer doet, het object type identificeren.

Zo'n flag kan in twee bits gepropt worden als het nodig is.

Maar het beste zou volgens mij gewoon een aparte object pool voor elk type object zijn. Dan hoef je geen type-nummer meer op te slaan, plus dat je geen geheugen verkwist omdat je niet gebonden bent aan de grootte van het grootste object (wat je ws. wel zou hebben als je de drie soorten objecten in 1 array zou willen stoppen).

[Zoijar]

MSalters schreef op zaterdag 27 november 2004 @ 19:52:
En vermeerderd met 4 bytes omdat je de flag moet opslaan. Dat is namelijk precies wat een vtable pointer doet, het object type identificeren.

Precies. Vandaar dat ik ook de hint naar een index in een tabel van functie pointers gaf. Je hebt dan eigenlijk gewoon virtuele functies, maar je moet ze 'zelf maken', met het voordeel dat het nu slechts 1 type is. Maar je kan idd, als je bv maximaal 8 verschillende hebt, het in 3 bits opslaan. Die bits kan je in een apparte bitmap alloceren, dan heb je ook geen alignment problemen bij de opslag van de objecten.

[.oisyn]

curry684 schreef op zaterdag 27 november 2004 @ 11:39:
Waar komen exact die 'insertions and deletions at the beginning' voor waarvoor een double ended queue ineens geschikter zou zijn dan een vector?

Omdat bij een deque de hele array niet de hele tijd opnieuw gealloceerd en gekopieerd hoeft te worden bij elke insert aan het eind wanneer de huidige grootte te klein is.

[.oisyn]

MrBucket schreef op zaterdag 27 november 2004 @ 20:50:
[...]

Zo'n flag kan in twee bits gepropt worden als het nodig is.

Jammer alleen dat je het geheugen niet per bit aan kunt spreken en de rest van de members van de class nog altijd op hun grootte gealignt worden.
(Overigens, als je een pool maakt per type dan kun je van een pointer in principe achterhalen uit welke pool hij komt, en dus wat voor type het is, zodat dat vlaggetje niet eens nodig is)

[ Voor 23% gewijzigd door .oisyn op 28-11-2004 16:44 ]

[curry684]

.oisyn schreef op zondag 28 november 2004 @ 16:34:
[...]

Omdat bij een deque de hele array niet de hele tijd opnieuw gealloceerd en gekopieerd hoeft te worden bij elke insert aan het eind wanneer de huidige grootte te klein is.

100000 elementen is bij een vector in MSVC 13 reallocates en copies, daar die gewoon dubbelt zodra out-of-bounds. Daar mag een page-based container nog aardig z'n best op doen om te evenaren qua snelheid.

Bovendien kun je natuurlijk op basis van filesize meestal al de container op het (min of meer) correcte formaat zetten

[MrBucket]

.oisyn schreef op zondag 28 november 2004 @ 16:38:
[...]


Jammer alleen dat je het geheugen niet per bit aan kunt spreken en de rest van de members van de class nog altijd op hun grootte gealignt worden.

Maar 2 bits is nog altijd een heel stuk minder dan 4 bytes voor een vtable-pointer. In principe hoef je in je hele class maar 2 ongebruikte bits te hebben waar je het object-type in kunt proppen.
En die default-alignment kan je uitzetten, wat voor 100000 objecten trouwens best nog wel eens prettige effecten kan hebben qua geheugen.

(Overigens, als je een pool maakt per type dan kun je van een pointer in principe achterhalen uit welke pool hij komt, en dus wat voor type het is, zodat dat vlaggetje niet eens nodig is)

Yup

TS, hoe staan de zaken?

[Verwijderd]

iedereen ontzettend bedankt voor zijn bijdrage, ik ben bezig met het maken van een pool op dit moment, om te kijken of dit performancewinst oplevert. zodra ik meer weet laat ik het horen!

[Zoijar]

.oisyn schreef op zondag 28 november 2004 @ 16:38:
Jammer alleen dat je het geheugen niet per bit aan kunt spreken en de rest van de members van de class nog altijd op hun grootte gealignt worden.

Die bits kan je in een apparte bitmap alloceren, dan heb je ook geen alignment problemen bij de opslag van de objecten.

[MSalters]

.oisyn schreef op zondag 28 november 2004 @ 16:38:
... als je een pool maakt per type dan kun je van een pointer in principe achterhalen uit welke pool hij komt, en dus wat voor type het is, zodat dat vlaggetje niet eens nodig is

Niet in portable C++, je mag alleen pointers binnen een enkel geheugenblok (new/new[]/malloc/enkel object) met > en < vergelijken (== mag wel)

[.oisyn]

Dat is waar
Maar kun jij een platform opnoemen waarvoor dat ook geldt?

[Zoijar]

.oisyn schreef op maandag 29 november 2004 @ 11:19:
Dat is waar
Maar kun jij een platform opnoemen waarvoor dat ook geldt?

Two-space garbage collector

[MSalters]

.oisyn schreef op maandag 29 november 2004 @ 11:19:
Dat is waar
Maar kun jij een platform opnoemen waarvoor dat ook geldt?

8086, far pointers