Vrijgeven van datastructuren 16k + 1 byte duurt erg lang

[Verwijderd]

Lang verhaal: In een critical section heb ik een insert in een Stack< .. , std::vector< .. > > staan. Wanneer de vector moet reallocaten ben je langer in die critical section dan gewenst. Mijn oplossing: maak je eigen stack welke een wrapper om std::vector is. reserve() 10.000 elementen or-so, noem dat een link, wanneer de link vol is maak je een nieuwe link aan. Dit noemen we een EfficientStack en bevat intern een vector van link's (wat dus ook weer een vector is).

In feite is er natuurlijk niets 'efficient' aan, behalve dat de wordt-case insertion time wat beter is.

Strikvraag: hoeveel elementen per link is optimaal? Met 1000 elementen duurt het vrijgeven veel langer dan bij 100 of 10000 elementen. Dat vraagt om meer onderzoek.


testcase ( download. De testcase pakt ~3GB aan data, als je hem als 32-bit app compileet moet je de count in main() wat tweaken. Maar het effect neemt erg af naarmate de datastructuur kleiner wordt.)

C++:

class Item {
public:
    Item( int n ) {
        foo = new int[ n ];
    }

    Item( Item&& other )
    {
        foo = other.foo;
        other.foo = 0;
    }

    ~Item()
    {
        delete foo;
    }

    int* foo;
    int bar[9]; // some filler data..
};

C++:

int count = 30 miljoen ofzo.

QTime time;
time.restart();
{
    EfficientStack< Item > stack( size );  // size = hoeveel items er in één link gaan.
    for( int i = 0; i < count; i++ )
    {
        stack.push( Item( 5 ) ); // 'random' getal.
    }

    timeEnqueue += time.elapsed();
    time.restart();
}   // let stack go out of scope
timeDestroy += time.elapsed();

data. X-as = aantel items per link. Y-as = tijd in ms. De eerste grafiek is logaritmisch.


Gecompileerd onder: msvc 2012 x64. MinGW laat vergelijkbare resultaten zien.

Concrete vraag: hoe kan het dat het vrijgeven van een array van 342 items zo veel langer duurt dan het vrijgeven van 341 items? Overigens is het performanceverschil nog minstens 10x zo groot bij het gebruik van mijn multithreaded deleter.

Waarschijnlijk heeft het iets te maken met de hoeveelheid cache. één Item is 48 bytes. 48 * 341 = 16368. Maar hoe kan dat er nu weer voor zorgen dat het destructen van data meer dan 3 maal zo lang duurt terwijl er nauwelijks impact te zien is in het constructen van de elementen?


Rauwe data (tijd van destruction)

test 1 ( 2 x )		test 2 ( 256 ... 512 )		test 3 ( 336 ... 352 )
N	tijd (in ms)	N	tijd (in ms)	N	tijd (in ms)
2	2500	256	1187	336	1172
4	1605	272	1250	337	1235
8	1375	288	1262	338	1250
16	1312	304	1141	339	1125
32	1234	320	1297	340	1234
64	1391	336	1360	341	1328
128	1359	352	3844	342	3657
256	1375	368	3891	343	3688
512	3937	384	3625	344	3730
1024	3844	400	3750	345	3750
2048	3376	416	3641	346	3828
4096	1672	432	3610	347	3667
8192	1344	448	3766	348	3657
16384	1235	464	3734	349	3829
32768	1171	480	3906	350	3750
65536	1251	496	3938	351	3687
		512	3687	352	3750

[EddoH]

Het antwoord op je concrete vraag weet ik niet, maar ik weet wel dat je in je Item destructor delete[] ipv delete moet gebruiken

[Verwijderd]

Ehh.. ja.

Zonder dat gedoe met die new[] array schaalt hij overigens ook erg slecht, ongeveer een factor 2 verschil tussen 341 en 342 elementen. Mijn testcase had dus nog een stuk minimaler gekund.

Met mijn multithreaded deleter gebeurt overigens hetvolgende in mijn progsel:


Ergo, het effect is daar nog 100x erger. De solution is inderdaad ranzig

[ Voor 43% gewijzigd door Verwijderd op 08-05-2013 11:14 ]

[EddoH]

Wellicht een long shot, maar het lijkt me dat je gewoon op de L1 cache limiet van je cpu zit.
Waarom deleten vs alloceren zoveel meer tijd kost durf ik je niet te zeggen, maar het lijkt me dat je data storage gefragmenteerd is gezien het niet meer in L1 cache past, en daarom het deleten inefficient wordt (.oisyn of soultaker kunnen hier veel meer zinnige dingen over zeggen).

Iets om te overwegen is om een memory pool te gebruiken, en niet alles op de heap te alloceren.

[Verwijderd]

Mijn CPU heeft 8k L1 cache per core en 256KB L2 cache per core (en 8MB L3 cache).

Maar dat verklaart nog niet waarom het ook zo lang duurt als ik Item een triviale destructor geef. Ik neem aan dat de vector de hele array dan simpelweg wegknikkert in plaats van voor elk object de destructor aan te roepen?

[MLM]

Zie ik daar nou een loop van 30 miljoen iteraties die allemaal een heap allocatie doen?
Zou je die niet eerst eens weghalen, en zien of je stack nou wel het probleem is, of dat het de heap is
Het zou me niet verbazen als daar 90% van je tijd in zit, en dan je misschien beter eens een custom allocator erbij pakken afhankelijk van je allocatie patroon.
Daarnaast (ik las ergens critical section, dus ik ga even uit van multi-threaded), heap alloc/free zijn ook (potentieel) serializerend.

Denk ook aan dat het sneller is om met 10 threads 1000 items in 1 "blok" te gooien waarbij je niet hoeft te synchroniseren, en dan dat blok in in een critical section op je stack te gooien, dan om met 10 threads 1000x los de stack te gaan pushen in een critical section

[ Voor 71% gewijzigd door MLM op 08-05-2013 20:56 ]

[Verwijderd]

MLM schreef op woensdag 08 mei 2013 @ 20:51:
Zie ik daar nou een loop van 30 miljoen iteraties die allemaal een heap allocatie doen?
Zou je die niet eerst eens weghalen, en zien of je stack nou wel het probleem is

Een vector de array erachter wordt sowieso op de stack heap... geallocaard. Mijn application alloceert daadwerkelijk zo veel elementen.

Daarnaast wil ik juist uitvinden waarom het vrijgeven zo lang duurt. Maar met een trivial constructor en destructor is 16k+1 nog steeds significant trager dan 16k.

Ik zal even een profile draaien om te kijken wat er gebeurt.

Denk ook aan dat het sneller is om met 10 threads 1000 items in 1 "blok" te gooien waarbij je niet hoeft te synchroniseren, en dan dat blok in in een critical section op je stack te gooien, dan om met 10 threads 1000x los de stack te gaan pushen in een critical section

Dat heb ik inderdaad al eens gebruikt, maar ik heb nog wat moeite om het op de huidige situatie toe te passen (vanwege starvation issues ed), je zult toch ergens moeten synchroniseren.

Edit: profile levert niets op, ik kan in release niet ver genoeg de stack in kijken om te zien wat er gebeurt. Onder debug heb je hele andere bottlenecks.

[ Voor 31% gewijzigd door Verwijderd op 09-05-2013 19:13 ]