Wat garbage collection echt kost

Het interessante deel is wie dat geheugen terugvordert en wanneer. Een stuk code moet bepalen dat een specifiek deel van het geheugen niet meer nodig is om het vervolgens vrij te geven, en dat bepalen is niet triviaal. Een waarde kan naar een andere functie worden doorgegeven, ergens worden opgeslagen voor langdurig gebruik of worden gedeeld tussen threads; de waarde blijft nodig zolang er nog iets naar verwijst. Als het te vroeg wordt teruggevorderd, ontstaat er geheugencorruptie. Als het te laat gebeurt, ontstaan er geheugenlekken.

De paradigma's

Er zijn twee paradigma's voor geheugenbeheer, die elk verschillende zaken optimaliseren.

Het eerste paradigma is om het aan de runtime van de taal over te laten. Een programma reserveert geheugen wanneer dat nodig is, gebruikt het zolang dat vereist is en stopt uiteindelijk met het refereren naar dit geheugen. Een garbage collector (GC) stelt vast wat niet langer bereikbaar is en vordert dit terug. Go, Java en veel andere veelgebruikte talen vallen in deze categorie. Je geeft de controle over het moment van vrijgeven op, maar in ruil daarvoor kun je geheugen niet te vroeg vrijgeven, niet twee keer vrijgeven of simpelweg vergeten het vrij te geven. Voor de meeste software is dit een zeer goed compromis; het vermindert de cognitieve belasting van geheugenbeheer, waardoor je je kunt concentreren op het eigenlijke probleem. Lekkages die ontstaan door het vergeten van het vrijgeven van geheugen verdwijnen hiermee volledig.

Het tweede paradigma is om de beslissing zelf in handen te houden. In C reserveer en geef je handmatig geheugen vrij, en je bent zelf verantwoordelijk voor elke bug die hieruit voortvloeit. In Rust schrijf je geen free-commando's, maar je legt de beslissing ook niet over aan een runtime. De compiler bepaalt tijdens het bouwen waar het leven van elke waarde eindigt, vordert het daar terug en weigert het programma te bouwen als hij niet kan bewijzen dat dit veilig is. Je behoudt dus controle over het geheugen en hebt een kleinere footprint, maar de inspanning verschuift: in C betaal je door het debuggen van corruptie, in Rust betaal je door je programma zo in te richten dat de compiler het kan verifiëren.

Daartussenin bevindt zich reference counting (referentietelling), wat wordt gebruikt in Swift en Python. Dit is eigenlijk een variant van de eerste benadering in plaats van een derde paradigma, en het is zelden voldoende op zichzelf. Tellingen kunnen cyclische referenties niet detecteren, dus moet een taal daar op een andere manier mee omgaan. Python voegt een tracing collector toe die jaagt op cycli. Swift doet dit niet en schuift het probleem terug naar de ontwikkelaar via weak en unowned annotaties. Reference counting heeft bovendien eigen runtime-kosten, die je betaalt bij elke kopie van een pointer en elke keer dat je er een verwijdert.

Welke moet je kiezen? Als garbage collection gratis was, zouden we allemaal kiezen voor een runtime die het geheugenbeheer zelf afhandelt. Maar dat is niet gratis, vandaar de discussie over de prestatiebeperkingen van GC en of deze relevant zijn.

Stack en heap

Wanneer een programma geheugen nodig heeft, komt dit van een van de twee plaatsen: de stack of de heap.

Geheugen op de stack kost de collector niets. De stack groeit en krimpt naarmate functies worden aangeroepen en terugkeren; de machine verplaatst simpelweg een pointer. Wanneer de functie terugkeert, is de waarde weg; er hoeft niets te worden teruggevorderd. Stacks zijn niet volledig onzichtbaar voor de collector, aangezien deze ze moet scannen als roots om te vinden waar de actieve objecten beginnen, maar hij hoeft daar nooit iets vrij te geven.

Een waarde komt op de heap terecht om een van twee redenen:

1. De waarde moet langer bestaan dan de functie die hem heeft aangemaakt (bijvoorbeeld omdat er een referentie naar is teruggegeven of omdat het elders langdurig is opgeslagen).
2. De grootte is vooraf niet bekend en kan groeien (bijvoorbeeld een slice waaraan voortdurend elementen worden toegevoegd, of een buffer waarvan de grootte afhangt van gebruikersinput).

Heap-allocatie is de klasse geheugen die de GC monitort en terugvordert, en dit is wat bijdraagt aan de GC-kosten.

De kosten van collectie

Om te bepalen wat de collectie kost, moeten twee vragen worden beantwoord: hoe vaak draait de collector en wat kosten de kosten per run?

Hoe vaak een collector draait, wordt bepaald door hoe snel je bytes verbruikt. Wanneer het geheugen volloopt, wordt de collector gedwongen om opnieuw vast te stellen welke objecten nog actief zijn.

Elke keer dat de collector draait, moet hij één vraag beantwoorden: wat is nog bereikbaar? Om dit te beantwoorden, bouwt hij een graaf op van de actieve objecten in je programma en de referenties daartussen, om vervolgens alles terug te vorderen wat niet in die graaf voorkomt. Dit hele proces — wakker worden, de graaf bouwen en het restant terugvorderen — is één GC-cyclus. Het bouwen van de graaf wordt meestal marking genoemd. Dit gebeurt door vanuit de roots te lopen en elke referentie te volgen; dit bepaalt de kosten van een cyclus.

Een GC-cyclus rekent je niet af voor het gebruikte geheugen, maar voor de objecten en referenties. De hoeveelheid geheugen achter een referentie speelt geen rol. Het collecteren van een graaf van 4 GB bestaande uit een miljoen kleine objecten die naar elkaar wijzen, is vele malen duurder dan een enkele buffer van 4 GB. Beide programma's gebruiken dezelfde hoeveelheid geheugen, maar vragen om een volledig verschillende hoeveelheid werk. Een verrassend resultaat hiervan is dat in de collectiestap de kosten proportioneel zijn aan de live pointers, niet aan de dode pointers of het afval (garbage).

Er is een tweede kost waarbij marking betrokken is. Terwijl de collector zijn graaf bouwt, blijft je programma draaien en pointers wijzigen. De collector kan geen beeld vastleggen van een graaf die onder hem beweegt. Om te voorkomen dat de graaf veroudert, voert elke pointer-schrijfactie die je programma uitvoert tijdens het proces een beetje extra werk uit om de wijziging te rapporteren. Dit werk wordt belast aan jouw programma, niet aan de collector, dus het verschijnt niet in de gemeten GC-tijd. Dit is een andere reden waarom code met veel pointers duurder is tijdens GC.

Runtimes verschillen sterk in hoe ze dit aanpakken. Sommige bouwen het beeld elke keer vanaf nul op, anderen houden het continu bij, en sommige houden een apart beeld bij voor jonge objecten (zoals de generational GC van Java), vanuit de redenering dat de meeste objecten snel sterven. De meeste runtimes bieden een instelling waarmee je de heap verder kunt laten groeien voordat er wordt gecollecteerd, zodat het minder vaak gebeurt, hoewel er in de tussentijd meer dood geheugen aanwezig blijft. Al dit beïnvloedt de constanten en het allocatieprofiel waarvoor wordt geoptimaliseerd, maar het verandert niet de factoren die de kosten bepalen.

Vergelijk dit met de wereld van handmatig of door de compiler beheerd geheugen. Allocatie is daar ook niet gratis; malloc heeft eigen free lists en last heeft van lock contention. Maar de kosten zitten in de instructies om een pointer te alloceren en vervolgens vrij te geven. Er is geen systeem dat de gehele set moet scannen om te bepalen welke pointer bereikbaar is en welke niet.

Wat te meten

Wanneer we zeggen dat een programma traag is of een Out Of Memory (OOM) fout geeft vanwege GC-druk, is het verbruik van de hoeveelheid geheugen niet het belangrijkste meetpunt. Er zijn drie relevantere vragen:

1. Hoeveel actieve objecten houdt het programma vast?
2. Hoe dicht zijn deze objecten met elkaar verbonden?
3. Hoe snel is er sprake van churn (omloop van nieuwe en oude objecten)?

Het meten gebeurt in drie fasen. De eerste is triage, om te bepalen of optimalisatie überhaupt nodig is. De tweede beantwoordt de vraag over churn. De derde beantwoordt de vragen over de hoeveelheid objecten en hun verbindingen.

Fase 1: Is de collector een probleem? Kijk naar het CPU-verbruik: welk aandeel van de processortijd gaat naar collectie in plaats van naar je programma? Elke CPU-cyclus die door GC wordt gebruikt, kan niet worden gebruikt voor het eigenlijke werk. In Go wordt dit gerapporteerd via het runtime/metrics pakket; Java geeft hetzelfde beeld via GC-logs of een profiler. Als dit aandeel klein is, kun je stoppen; GC is geen probleem dat optimalisatie vereist.

Fase 2: Welke delen van de code produceren het afval? Dit is een allocation profile. Je wilt het aantal allocaties en de bytes per allocatie meten, toegeschreven aan de plek waar ze vandaan komen. In Go is dat een heap-profiel via allocobjects en allocspace, of allocs/op en B/op bij benchmarks. In Java zijn dit allocation events uit een profiler, toegeschreven aan stack-traces. Meestal vind je een handvol call-sites die verantwoordelijk zijn voor het meeste churn; dit zijn de plekken om te optimaliseren.

Fase 3: Wat houdt het programma vast? Vaak is het optimaliseren van de hot allocation paths voldoende. Als je verder moet gaan, onthoud dan dat de kosten van een GC-cyclus proportioneel zijn aan het aantal actieve referenties, niet de dode. Een allocatieprofiel vertelt je wat je hebt aangemaakt, maar niets over wat is blijven bestaan. Een programma met een groot object in het geheugen zal in een allocatieprofiel onopvallend lijken. Hiervoor heb je een live view nodig: inuseobjects en inusespace in Go, of een heap histogram in Java.

Pointer-densiteit is een metriek die niet direct wordt gerapporteerd, maar die we kunnen afleiden. Deel de actieve bytes door de actieve objecten om de gemiddelde grootte te bepalen. Veel kleine objecten zijn duur, omdat dit betekent dat er veel referenties nodig zijn om ze bij elkaar te houden. Weinig grote objecten zijn goedkoop. Gemiddelde grootte is hierbij een proxy voor hoeveel pointers de collector moet volgen.

Voortijdige optimalisatie

Voor de meerderheid van de software is het maken van zorgen over GC-overhead een fout en zal optimalisatie leiden tot premature optimization.

Er is echter een klasse programma's waarbij dit anders ligt en het allocatiegedrag bepalend is voor succes of falen. Gebruik de volgende checklist om te bepalen of je dit in het ontwerp moet meenemen:

• Hoeveel data beweegt er door het 'hot path'? Eén allocatie per webverzoek is verwaarloosbaar. Dezelfde allocatie in een loop over tien miljoen rijen kan cruciaal zijn.
• Is de tail-latency belangrijk? Niet de gemiddelde latency, maar de uitschieters. Tijdens een collectie wordt CPU-tijd onttrokken aan je programma. In veel runtimes (waaronder Go) wordt een thread die probeert te alloceren tijdens een collectie, ingezet om te helpen met het markeren, waardoor het eigenlijke werk moet wachten. Als een incidentele trage respons acceptabel is, hoef je je hier geen zorgen over te maken.
• Push je de hardware tot het uiterste? De meeste programma's laten de machine grotendeels inactief en wachten op netwerken, databases of schijven. In die gevallen verdwijnt het werk van de collector in deze ongebruikte tijd. Het wordt pas zichtbaar wanneer je de CPU probeert te verzadigen.
• Draait het proces lang en houdt het veel vast? Denk aan een service met een grote cache in het geheugen, of een index opgebouwd uit miljoenen kleine objecten die naar elkaar wijzen. Elke pointer moet bij elke cyclus worden gevolgd, zolang het proces draait — zelfs als de service niets doet. Minder alloceren helpt hier niet, want de kosten zitten in wat je behoudt en niet in wat je creëert.

Een datapipeline, een database, een game-engine of een high-throughput service zal op meerdere van deze vragen "ja" antwoorden. Een typische webbackend of CLI-tool waarschijnlijk niet.

Wat volgt nu

Uit praktijkervaring blijkt dat de meeste ontwikkelaars het paradigma niet zelf kiezen; je erft een project of taal binnen een bedrijf. De nuttige vraag is daarom: wat kun je doen vanaf de positie waar je al staat?

Er zijn manieren om GC te optimaliseren. In Go is er meer ruimte voor optimalisatie dan men vaak denkt, mits je de juiste tools gebruikt. Je kunt minder alloceren, bestaande allocaties hergebruiken of regio's van het geheugen creëren die de collector helemaal niet hoeft te scannen. Dit is waar we in het vervolg op zullen ingaan.