[JAVA] HashMap: grotere init. capacity -> trager?

[Mitt3nz]

Hoi,

Voor een ontwerpproject moet ik een programma schrijven dat voor een lijst met lijnen de optimale tekenvolgorde van deze lijnen bepaald. Hiervoor maak ik gebruik van een dynamisch geprogrammeerd recursief algoritme, dat simpelweg alle mogelijke tekenvolgordes bekijkt en de kortste bepaalt. Tussenresultaten worden door dit algoritme opgeslagen in een HashMap, zodat ik deze resultaten er later ook weer snel uit kan halen.

Nou probeerde ik de snelheid van dit algoritme te verbeteren door de initiële capaciteit van de HashMap zodanig te kiezen dat er zo min mogelijk rehashes optreden. Dit is mogelijk omdat ik van te voren ongeveer kan bepalen hoeveel stores er plaats gaan vinden in de HashMap voor een bepaald aantal lijnen. Ik ging dus wat lopen testen en kwam tot de volgende resultaten:

230.000 stores, initial capacity 2: 182 seconds.
230.000 stores, initial capacity 3.000: 184 seconds.
230.000 stores, initial capacity 30.000: 187 seconds.
230.000 stores, initial capacity 300.000: 201 seconds.

Zoals je ziet neemt de rekentijd voor grotere initiële capaciteiten toe, in plaats van af. Ik zou juist denken dat door een grotere initiële capaciteit er minder rehashes hoeven plaats te vinden waardoor het juist sneller zou moeten gaan. Ga maar na, voor 230.000 stores moet je met een initial capacity van 2 maar liefst 18 rehashes uitvoeren (ervan uitgaande dat een rehash de capaciteit grofweg verdubbeld) terwijl je met een initial capacity van 300.000 geen enkele rehash zou hoeven uit te voeren. Heeft iemand enig idee hoe het toch trager kan zijn? Ligt dit aan de JVM?

Wat relevante info: AMD XP 1900+, 512 MB DDR, Windows XP SP2, Java SDK 1.4.2.

B.v.d.

[ Voor 7% gewijzigd door Mitt3nz op 29-03-2005 21:14 ]

[Alarmnummer]

Hoeveel keer heb je deze tests achter elkaar gedraait?

[Mitt3nz]

Stuk of 5 keer geprobeerd, ook met andere groottes.

[Alarmnummer]

Draai het eens 100 keer.. en als het dan nog steeds zo vreemd is, pak eens een profiler erbij. Ik heb erg goeie ervaring met JProfiler.

[ Voor 13% gewijzigd door Alarmnummer op 29-03-2005 21:50 ]

[MrBucket]

Off-topic: kan je geen line-sweep methode toepassen ipv brute-force alle mogelijkheden te testen?
Voorbeeld voor intersectie testen van segmenten met behulp van zo'n imaginaire sweep kan bijv. hier gevonden worden: http://www.lems.brown.edu/~wq/projects/cs252.html

[Zoijar]

Kan door caching komen. Bij een hele grote map zullen de waardes vaak ver uit elkaar liggen; verder dan een block cache. Het gevolg is dus een cache miss bij elke read/write. Dat kan ontzettend traag zijn.

[Mitt3nz]

Bedoel je paging? Ik had al reeds de aantallen page faults vergeleken voor de verschillende initiële capaciteiten maar die verschilden onderling niet of zeer weinig. Daar ligt het dus niet aan denk ik..

[ Voor 15% gewijzigd door Mitt3nz op 29-03-2005 23:06 ]

[Mitt3nz]

MrBucket schreef op dinsdag 29 maart 2005 @ 22:20:
Off-topic: kan je geen line-sweep methode toepassen ipv brute-force alle mogelijkheden te testen?
Voorbeeld voor intersectie testen van segmenten met behulp van zo'n imaginaire sweep kan bijv. hier gevonden worden: http://www.lems.brown.edu/~wq/projects/cs252.html

Ik zie niet in hoe ik een line-sweep methode kan toepassen bij een TSP-gerelateerd probleem

[MrBucket]

Mitt3nz schreef op dinsdag 29 maart 2005 @ 23:12:
[...]


Ik zie niet in hoe ik een line-sweep methode kan toepassen bij een TSP-gerelateerd probleem

Je zei "een programma schrijven dat voor een lijst met lijnen de optimale tekenvolgorde van deze lijnen bepaald". Niet dat het om een NP-compleet probleem ging.

Succes verder.

[Mitt3nz]

MrBucket schreef op dinsdag 29 maart 2005 @ 23:32:
[...]

Je zei "een programma schrijven dat voor een lijst met lijnen de optimale tekenvolgorde van deze lijnen bepaald". Niet dat het om een NP-compleet probleem ging.

Succes verder.

Kortste route door alle punten (lijnen) bepalen -> TSP

[ Voor 4% gewijzigd door Mitt3nz op 30-03-2005 14:32 ]

[ACM]

In diverse java-performance boeken wordt aangeraden om een priem-getal als initiele waarde voor een HashMap te gebruiken. Je 2 is dat wel, je andere getallen niet... Er zijn overigens een aantal "extra goede" priemgetallen (11 is er een van meen ik), waarbij het allemaal nog wat efficienter gaat.
De reden waarom die priemgetallen zo goed waren ben ik vergeten, het had met de indeling in hashbuckets te maken geloof ik.

Diezelfde reden is echter bij jou ook aan de orde. Met een grootte van 300.000 elementen zit elk element in zijn eigen bucket, maar daar wordt het niet per se sneller van.

[misfire]

Hoe heb je deze tests uitgevoerd? Lijkt me dat je discrepanties ziet door heap trashing, JIT compiler performance hit al wel/niet gehad, enz. Heb je de testen voldoende geisoleerd uitgevoerd?

De initial capacity beinvloedt trouwens niet de localiteit van de HashMap verzameling. Het onderliggende array wordt namelijk altijd als één blok gedeclareerd op één vast moment in de tijd, of dit pas na een aantal rehashes is is in principe niet relevant voor de localiteit.

Ook is de impact op de performance niet dramatisch, afhankelijk van hoe vaak je de map vult en wat je er verder nog mee doet natuurlijk. De tijdwinst met die rehashes en de extra gc's is op zijn hoogst enkele milisecondes, en als een enkele run al minimaal 3 minuten duurt, dan kun je beter ergens anders gaan profilen/optimaliseren.

[misfire]

Vanaf versie 1.4 zou de standaard HashMap van Java automatisch de capaciteit aan moeten passen aan een getal dat lekkerder in het algoritme past. De performance tip dat je zelf priem getallen/^2 getallen moet bepalen voor de hashmap is niet meer relevant. Ik heb nog even gekeken in de Java 5 source en daar gebeurt dit al, maar je zou in de source van jouw java versie kunnen kijken of het daar ook gebeurt...

[Alarmnummer]

Heb je intussen al een profiler geprobeerd om te achterhalen wat de oorzaak van het probleem is, ipv alleen te speculeren?