java Garbage Collection Tuning

[Math-E-Mad-X]

Ik ben een search tree aan het implementeren, en zit met het probleem dat java extreem langzaam wordt naarmate de tree groter wordt. Ik vermoed dat dit komt doordat de Garbage Collector steeds meer tijd nodig heeft om het geheugen te checken. Nu is het zo dat ik weet dat het overgrote deel van het geheugen nooit 'out of scope' raakt (de search tree), en dus nooit opgeruimd hoeft te worden. Het is dus zeer inefficiënt dat de GC telkens weer die hele tree afzoekt.

Ik vroeg mij dus af of iemand hier weet hoe je garage collection efficiënter kunt maken. Bijvoorbeeld door het tweaken van parameters, of simpelweg door een andere JVM te gebruiken (op dit moment gebruik ik de standaard JVM die met de development kit van Sun meekomt).

Ik zat bijvoorbeeld te denken aan reference counting. Het nadeel van reference counting is dat dit niet goed werkt wanneer je circular references hebt, maar daar heb ik er niet zoveel van in mijn code, behalve dan in de search tree die sowieso niet opgeruimd moet worden. Het grote voordeel is dat de GC niet constant het hele geheugen hoeft af te zoeken.

Een andere oplossing zou misschien zijn om (in het geval van een generational GC) de GC zodanig af te stellen dat de tree op de old generation terecht komt en dat deze maar zelden gescand wordt.

Nou heb ik dus geen idee welke JVM's gebruik maken van deze technieken, of hoe je hun parameters kunt tweaken. Is hier misschien iemand die daar meer verstand van heeft?

Ik gebruik OS X Lion en gebruik Eclipse om te programmeren. Verder is het programma bedoeld voor wetenschappelijke doeleinden, dat wil zeggen dat het niet op andere machines hoeft te draaien dan de mijne, zolang ik er maar experimenten mee kan doen.

[eezacque]

Ik heb zelf nog nooit meegemaakt dat garbage collection een bottleneck is, hetgeen natuurlijk niet uitsluit dat het in jouw geval een probleem zou kunnen zijn. Het lijkt me verstandig eerst 'ns te kijken waar de bottleneck precies zit, door je code te profilen. Als ik het goed herinner, heeft Eclipse een bruikbare profiler aan boord, waarmee je kunt achterhalen in welk deel van je programma de meeste performance verstookt wordt.

Laat even weten of je hiermee uit de voeten kunt, desnoods help ik je hiermee op weg...

[Math-E-Mad-X]

cool, dat van die profiler wist ik niet, dus ik zal eens ff uitzoeken hoe dat beest werkt.

Ik had zelf wel al zo'n beetje uitgezocht waar de meeste tijd in zit, en dat is code die in theorie steeds even lang zou moeten duren. In de praktijk zie ik echter dat deze code steeds langzamer en langzamer gaat naarmate het algoritme langer runt. Het enige wat ik dus kan verzinnen is dat het iets te maken heeft met een voller geheugen.

Maar ik zal voor de zekerheid dus eerst nog even naar die profiler kijken.

[eezacque]

Een andere optie is dat je last hebt van een memory leak: er is geheugen dat je niet meer gebruikt, zonder dat de garbage collector het in de gaten heeft...

[Math-E-Mad-X]

Memory leaks?? in java? hoe is dat mogelijk? bedoel je dat er een bug zou zitten in de GC?

anyway, als dat zou is:

Wat kan ik daar dan aan doen? En waarom zou dat dan leiden tot langzamere executie?

[eezacque]

Als je slordig bent, bijvoorbeeld door pointers te bewaren naar objecten die je niet meer gebruikt, dan zal de garbage collector die objecten niet opruimen, je geheugen zou kunnen vollopen met deze objecten...

[Math-E-Mad-X]

ah, okee, je bedoelt dus gewoon dat ik misschien referenties naar objecten heb ik die ik eigenlijk helemaal niet meer nodig heb. Ik zal d'r nog eens grondig naar kijken, maar daar had ik eigenlijk al wel zo veel mogelijk rekening mee gehouden.

[317070]

Ik zat bijvoorbeeld te denken aan reference counting. (...)

Een andere oplossing zou misschien zijn om (in het geval van een generational GC) de GC zodanig af te stellen dat de tree op de old generation terecht komt en dat deze maar zelden gescand wordt.

1. De garbage collector in Java maakt gebruik van reference counting.
2. De garbage collector moet dus ook nooit scannen door je data om te vinden wat hij moet verwijderen, dat zou een bijzonder inefficiënte manier van werken zijn.

Nu is het wel zo dat als je geheugen voller en voller zit, je sowieso trager en trager gaat, onafhankelijk van je code. Het hangt er van af van hoe groot de RAM en de cache in je computer is en dus hoe vaak hij 'lang niet gebruikte' data terug moet opzoeken van je harde schijf. (cache-missers)

Maar je kunt inderdaad beter profilen.

[Math-E-Mad-X]

Nu is het wel zo dat als je geheugen voller en voller zit, je sowieso trager en trager gaat, onafhankelijk van je code. Het hangt er van af van hoe groot de RAM en de cache in je computer is en dus hoe vaak hij 'lang niet gebruikte' data terug moet opzoeken van je harde schijf. (cache-missers)

Ha, bedankt voor de uitleg! Je beweert dus dat de code gaat langzamer gaat doordat de JVM automatisch dingen op gaat slaan op de harde schijf in plaats van in het geheugen? Maar ik dacht dat hij bij gebrek aan geheugenruimte juist een OutOfMemoryException zou throwen? Hoe zit dat precies?

Dus in principe zou ik dit probleem kunnen oplossen door de JVM heap zo groot mogelijk te maken?

Overigens had ik de info over Gabarge Collection hier gevonden:

http://www.javaworld...ion.html?page=8

Ik kreeg hiervan de indruk dat reference counting juist niet zoveel gebruikt werd. Er staat namelijk, op pagina 2:

In the first article in this series I touched on the two main approaches to garbage collection, which are reference counting and tracing collectors.

En op pagina 3 staat:

Tracing collectors are most commonly used for memory management in dynamic languages; they are by far the most common for the Java language and have been commercially proven in production environments for many years.

[Landro]

Een andere optie is om te kijken of het algorithme effienter te maken is. Bijvoorbeeld door kleinere variable types te gebruiken waar mogelijk zoals een short ipv een long of een float ipv een double.

In het boek 'programming pearls' van Jon Bentley staan meerdere hoofdstukken over het efficienter maken van code. Dit boek kan ik van harte aanbevelen aan iedereen zich zich serieus met programmeren bezig houdt.

[Xenion]

Ook: gebruik je recursie in je algoritme? Het is mogelijk efficiënter om dat niet te doen en iteratief te werken door in lijsten bij te houden welke nodes je moet bekijken.

Van de GC ken ik niet genoeg om over het tunen ervan iets te zeggen, maar heb je er eventueel al aan gedacht om naar C++ over te stappen en het geheugen zelf te beheren met new en delete?

Misschien kan je het in Java een beetje forceren door bestaande instanties te hergebruiken ipv steeds nieuwe aan te maken? i.e. de waarden van een bestaande node overschrijven ipv een niet-gebruikte node weg te gooien en een nieuwe instantie te alloceren. Op die manier heb je misschien wat extra code te schrijven, maar je kan zo wel het geheugengebruik beperken tot de maximum branching factor.

Of zoals boven al aangehaald is, zorg dat niet gebruikte referenties ook zeker weg zijn zodat dat GC de objecten kan verwijderen: pointers op NULL zetten.

Maar ik dacht dat hij bij gebrek aan geheugenruimte juist een OutOfMemoryException zou throwen? Hoe zit dat precies?

Er is een verschil tussen een gebrek aan geheugenruimte en gewoon veel geheugen gebruiken. Om de details te kennen moet je maar eens zoeken naar virtueel geheugen,paging en caching.

[Math-E-Mad-X]

Een andere optie is om te kijken of het algorithme effienter te maken is. Bijvoorbeeld door kleinere variable types te gebruiken waar mogelijk zoals een short ipv een long of een float ipv een double.

Dankje, maar dat soort zaken had ik zelf ook al rekening mee gehouden.

Het is mogelijk efficiënter om dat niet te doen en iteratief te werken door in lijsten bij te houden welke nodes je moet bekijken.

Doe ik al

heb je er eventueel al aan gedacht om naar C++ over te stappen en het geheugen zelf te beheren met new en delete?

Ja, het zou in mijn geval inderdaad beter zijn om het in C++ te doen, maar helaas is dat geen optie. Ten eerste omdat ik zelf niet erg thuis ben in C++, maar vooral omdat ik afhankelijk ben van een aantal libraries die door een collega van mij in java geschreven zijn.

Misschien kan je het in Java een beetje forceren door bestaande instanties te hergebruiken ipv steeds nieuwe aan te maken? i.e. de waarden van een bestaande node overschrijven ipv een niet-gebruikte node weg te gooien en een nieuwe instantie te alloceren. Op die manier heb je misschien wat extra code te schrijven, maar je kan zo wel het geheugengebruik beperken tot de maximum branching factor.

Helaas is het essentieel in mijn algoritme dat ik een heel groot deel van de nodes uit de search tree bewaar.

1. De garbage collector in Java maakt gebruik van reference counting.
2. De garbage collector moet dus ook nooit scannen door je data om te vinden wat hij moet verwijderen, dat zou een bijzonder inefficiënte manier van werken zijn.

Ik heb het voor de zekerheid nog eens na gezocht, maar ook deze bron:

http://www.oracle.co...g-6-140523.html

bevestigd dat de verscheidene garbage collectors van sun wel degelijk allemaal gebruik maken van mark & sweep, en dus niet van reference counting.

[Xenion]

Welja, sommige algoritmes hebben nu eenmaal een grote tijd en/of geheugen complexiteit.

Controleer eerst eens via de profiler of de GC wel degelijk te bottleneck is, want het zou goed kunnen dat je tijd en geheugen gebruik normaal zijn voor de hoeveelheid data die je wil verwerken.

[eezacque]

We kunnen hier de rest van het jaar gaan zitten filosoferen over de vraag waarom je programma niet zo vlot loopt als verwacht. Ik stel voor dat je nu 'ns probeert de feiten boven water te krijgen door je code te profilen.

[Math-E-Mad-X]

We kunnen hier de rest van het jaar gaan zitten filosoferen over de vraag waarom je programma niet zo vlot loopt als verwacht. Ik stel voor dat je nu 'ns probeert de feiten boven water te krijgen door je code te profilen.

Tuurlijk, ga ik ook zeker meteen doen zodra ik er tijd voor heb

Maar afgezien van de vraag of de GC inderdaad de oorzaak van de vertraging is, vind ik het ook gewoon heel interessant om meer over GC te weten. Dus ik zou sowieso heel blij zijn als mensen hier me er meer over zouden kunnen vertellen.