[C/Win32] Realloc performance probleem

[Verwijderd]

Wij hebben hier wat software die nogal inefficient een array aan het vergroten is dmv van realloc. Nu gaat dit toch nog redelijk snel op Linux (zo'n 15 sec totaal), maar als we dezelfde code onder windows draaien, dan duurt het plots 1550 sec. Nu de vraag, is de realloc onder windows (Visual Studio 6 ) ontzettend inefficient, of is dit toevallig een bug, die bv onder VS.NET al is opgelost?

Ligt dit misschien gewoon aan de implementatie van realloc en zijn er toevallig andere implementaties beschikbaar die sneller zijn? Kortom wie kent dit probleem nog meer?

[MSalters]

Ik heb van het voorjaar nog geprobeerd om aan de makers van de Microsoft CRT wat uitspraken te ontlokken over de snelheid van geheugenallocators, maar veel heb ik er niet uitgekregen. Memory allocators zijn een voortdurend nderwerp van studie, maar je zit fundamenteel met een speed/size tradeoff. Als ikbij de eerste malloc alvast een Megabyte extra reserveer, dan kunnen daaropvolgende realloc's best wel snel. Is dat een bug? Of is het juist een bug om precies genoeg te reserveren, waardoor de realloc's traag zijn?

Jouw programma heeft blijkbaar een tradeoff aanname gemaakt die niet overeenkomt met de tradeoff die Microsoft heeft gemaakt. Dat is niet noodzakelijk een bug of een inefficientie.

[curry684]

MSalters schreef op 08 oktober 2003 @ 07:17:
Jouw programma heeft blijkbaar een tradeoff aanname gemaakt die niet overeenkomt met de tradeoff die Microsoft heeft gemaakt. Dat is niet noodzakelijk een bug of een inefficientie.

Realloc is known to be inefficient, vooral als je grote groeibewegingen maakt. Ik ken realloc onder Windows wel en die is niet al te snel, maar het doorlopend gebruik ervan is ook gewoon niet slim. Ik gebruik voor dit soort problemen een BinaryBuffer class die te grote blokken alloceert en daardoor maar eens per X allocaties hoeft te reallocen.

Ik weet dat Windows gewoon 'op een rijtje' malloct, en ik vermoed dat Linux geheugen ruim uit elkaar alloceert zodat je de mogelijkheid hebt om grote stukken bij te realloceren, wat het veel sneller maakt bij voldoende geheugen. Voor beide methodes is veel te zeggen, ik moet zelf zeggen dat ik de voorkeur geef aan zo min mogelijk fragmentatie.

[demonite]

Misschien is smartheap een idee: www.microquill.com

[curry684]

demonite schreef op 08 oktober 2003 @ 08:35:
Misschien is smartheap een idee: www.microquill.com

Hmm interessant concept

* curry684 gaat dat ook maar eens bouwen voor z'n software

[Verwijderd]

Ik geef toe, de methode die werd gebruikt was nogal inefficient, (ja... ik heb het niet geschreven ), we hebben het veranderd zoals Curry al beschreef, elke keer een als de array groter moet worden in een keer een block geheugen reserveren, ipv net genoeg om de volgende data in de array op te slaan. Nu blijkt dat de gehele operatie (array opvullen was maar een klein deel er van ) nog maar 45 sec (vs 1550 sec) duurt.

Trouwens, zowel Linux als Itanium (HP-UX) zijn een stuk efficienter voor ons met realloc dan Windows. Ik neem aan dat als er zoiets als smartheap bestaat, dat het meer ligt aan de implementatie van alloc, dan aan de eigenlijke system calls.

[curry684]

Verwijderd schreef op 08 oktober 2003 @ 15:24:
Nu blijkt dat de gehele operatie (array opvullen was maar een klein deel er van ) nog maar 45 sec (vs 1550 sec) duurt.

Ik vind dit nog steeds een achterlijk verschil met die 15 sec van Linux. Heb je er al eens een profiler op los gelaten? Of gewoon met eigen benchtests gekeken waar die tijd verstookt wordt?

[.oisyn]

En is het wel een release build? In de debug build wordt er heel veel aan boekhouding gedaan

[Verwijderd]

curry684 schreef op 08 October 2003 @ 15:36:
[...]

Ik vind dit nog steeds een achterlijk verschil met die 15 sec van Linux. Heb je er al eens een profiler op los gelaten? Of gewoon met eigen benchtests gekeken waar die tijd verstookt wordt?

Sorry... dat moest 35 sec zijn.

[Verwijderd]

.oisyn schreef op 08 October 2003 @ 15:48:
En is het wel een release build? In de debug build wordt er heel veel aan boekhouding gedaan

Beide zijn release builds ja..

Nu geef ik wel toe, dat we beter kuynnen optimaliseren op Linux (i586) dan op Windows (blended option). Dus daar zou ook nog een verschil in kunnen zitten. Verder zit er nogal wat disk io in die nogal kan uitmaken als je het bijvoorbeeld 2x in laad...

[ Voor 36% gewijzigd door Verwijderd op 08-10-2003 16:20 ]

[curry684]

Verwijderd schreef op 08 October 2003 @ 16:14:
[...]
Sorry... dat moest 35 sec zijn.

* curry684 heeft wel eens zin om hier "Het grote optimalisatietopic" van te maken

Heb je wellicht mogelijkheden om hier wat stukken van de meest pijnlijke code te posten en/of wat preciezere beschrijving van de programmatuur te leveren?

Ik als Windowshippie laat natuurlijk niet over me heen gaan dat Linux sneller is

[Verwijderd]

curry684 schreef op 08 October 2003 @ 16:18:
[...]

* curry684 heeft wel eens zin om hier "Het grote optimalisatietopic" van te maken

Heb je wellicht mogelijkheden om hier wat stukken van de meest pijnlijke code te posten en/of wat preciezere beschrijving van de programmatuur te leveren?

Ik als Windowshippie laat natuurlijk niet over me heen gaan dat Linux sneller is

Ik kan geen stukken code posten, maar ik kan wel wat achtergrond info geven. De code is uit een library die 3d/2d cellen sorteert. Als test file hadden we een 2.7 miljoen tellend grid met voornamelijk poly cells. Het sorteren gebeurt meestal wanneer je zo'n file in laadt in 1 van onze programma's. Dat duurde dus eerst bijna 2 uur voordat was ingeladen (inclusief sorteren). Na het optimaliseren van de sorting routine, bleek op o.a een aantal Unix platformen ong een minuut te duren. Met verdere optimalisatie hier en daar konden we het nog sneller krijgen... dus gingen we het testen op windows, en bleek het nog steeds erg langzaam te zijn. Met de profiler er bij, bleek dat ie 90% van z'n tijd in realloc zat. Met de optimimalisatie zoals beschreven hierboven komt Windows dus weer bij het gemiddelde tijd die het duurt om het uit te voeren.


Oh... de meest pijnelijk code was in de trant van...

bereken grote van array, gebaseerd op celltype, behalve polycell...
loop over alle cellen,
kopieer data van cellen naar array..
als we een poly cell tegen komen, vergroot array om polycell te kunnen storen..

[ Voor 12% gewijzigd door Verwijderd op 08-10-2003 16:33 ]

[PommeFritz]

Zoals je het uitlegt lijkt het mij toe dat je uberhaupt niet met arrays / realloc moet gaan werken, maar gewoon een dynamische structuur zoals een linked list moet gaan gebruiken. Mis ik iets?

[curry684]

PommeFritz schreef op 08 oktober 2003 @ 23:16:
Zoals je het uitlegt lijkt het mij toe dat je uberhaupt niet met arrays / realloc moet gaan werken, maar gewoon een dynamische structuur zoals een linked list moet gaan gebruiken. Mis ik iets?

Ja, nl. dat 2.7 miljoen allocs langzamer is dan 20000 reallocs

[PommeFritz]

Haha, wat ik bedoelde is natuurlijk een linked list met een eigen block allocator die b.v. 500 nodes in 1 keer alloceert. Hmm, maar dan wordt het sorteren ervan een niet triviale opgave.

Maar alles om realloc te vermijden, want die moet 3 dingen doen: geheugen alloceren, bestaande data erin kopieren, oude geheugen vrijgeven...

[.oisyn]

maar goed, het klinkt allemaal als een goede taak voor de C++ std::deque

In plaats van 1 grote array, maar je gebruik van aan elkaar gekoppelde kleinere arrays (zeg 1mb per stuk ofzo). Hoe groot is de uiteindelijke grootte van de array (in bytes) eigenlijk?

Of zoals het x86 paging systeem in elkaar zit, of linux' inode filesystem. Je werkt dan met blokken van een X aantal bytes (waarbij X een macht van 2 is), en dan heb je een index array waarin referenties naar de blokken staan. Maar dat werkt eigenlijk alleen maar als je echt een array van vaste elementen hebt

[ Voor 38% gewijzigd door .oisyn op 09-10-2003 00:09 ]

[Verwijderd]

.oisyn schreef op 09 October 2003 @ 00:01:
maar goed, het klinkt allemaal als een goede taak voor de C++ std::deque

In plaats van 1 grote array, maar je gebruik van aan elkaar gekoppelde kleinere arrays (zeg 1mb per stuk ofzo). Hoe groot is de uiteindelijke grootte van de array (in bytes) eigenlijk?

Dat ligt er aan hoe groot de file is... als alle cellen maar 4 nodes hebben, dan kom je uit op

aantal cellen * 4 * grootte van een int.

Heb je nou heel veel poly cellen, dan zit je toch gemiddeld op

aantal cellen * 15 * grootte van een int

[Verwijderd]

curry684 schreef op 08 October 2003 @ 23:25:
[...]

Ja, nl. dat 2.7 miljoen allocs langzamer is dan 20000 reallocs

Wij komen nu terecht op ong 2000 allocs voor het hele programma...

[curry684]

Verwijderd schreef op 09 oktober 2003 @ 00:24:
[...]
Wij komen nu terecht op ong 2000 allocs voor het hele programma...

En dat is verwaarloosbaar

Ik zit toevallig op m'n werk vergelijkbare kutprogrammatuur in mekaar te proggelen alwaar ik zsm met zo ranzig mogelijk code o.a. 1.7 miljoen gestackte regels binnen moet tanken, koppelen aan 85000 attributes en 60000 onderdelen, en daarna aan 230000 vergelijkingen etc. etc. etc.

Zit allerhande superranzige allocatorcode in, maar lightning fast, en sortable big-block-allocations. Als je 2 lijsten van 170000 en 15000 elementen undubbed en sorted krijgt samengevoegd tot 1 lijst van 39000 elementen in 15/100 seconde geeft dat best ff een kick

[MSalters]

Te veel allocs is pijnlijk, omdat het veel calls zijn. Maar weinig allocs kan ook pijnlijk zijn, omdat je allocs dan teveel bytes moeten reserveren. 2 keer 1 byte reserveren duurt langer dan 1 keer 2 bytes, 2keer een gigabyte is waarschijnlijk sneller dan 1 keer 2Gb.

Die verschillende grootte cells klinken ook langzaam. Hoe maak je een array waarin ze allebei passen? Via pointers kan niet als je maar 2000 allocs gebruik voor je programma.

[Verwijderd]

MSalters schreef op 09 October 2003 @ 12:37:
Te veel allocs is pijnlijk, omdat het veel calls zijn. Maar weinig allocs kan ook pijnlijk zijn, omdat je allocs dan teveel bytes moeten reserveren. 2 keer 1 byte reserveren duurt langer dan 1 keer 2 bytes, 2keer een gigabyte is waarschijnlijk sneller dan 1 keer 2Gb.

Die verschillende grootte cells klinken ook langzaam. Hoe maak je een array waarin ze allebei passen? Via pointers kan niet als je maar 2000 allocs gebruik voor je programma.

Alle nodes worden opgeslagen in X, Y en Z arrays. vervolgens hebben we een aantal lookuptables om de verschillende cellen te identificeren. De echte performance drain was trouwens die realloc. We hebben er nog steeds een aantal, maar niet zoveel kleine reallocs. De array waarover we het hadden, was trouwens cell-2-node array.