Java-alustan roskienkeräysmekanismi lisää huomattavasti kehittäjien tuottavuutta, mutta huonosti toteutettu roskienkerääjä voi kuluttaa liikaa sovelluksen resursseja. Tässä JVM:n suorituskyvyn optimointi -sarjan kolmannessa artikkelissa Eva Andreasson tarjoaa Java-aloittelijoille yleiskatsauksen Java-alustan muistimalliin ja GC-mekanismiin. Sitten hän selittää, miksi pirstaloituminen (eikä GC) on Java-sovellusten suorituskyvyn suurin “gotcha!” ja miksi sukupolvien välinen roskienkeräys ja tiivistäminen ovat tällä hetkellä johtavia (vaikkakaan eivät kaikkein innovatiivisimpia) lähestymistapoja kasan pirstaloitumisen hallintaan Java-sovelluksissa.

Roskienkeräys (GC) on prosessi, jonka tavoitteena on vapauttaa varattua muistia, johon mikään tavoitettavissa oleva Java-olio ei enää viittaa, ja se on olennainen osa Java-virtuaalikoneen (Java virtual machine, jäljempänä “JVM”) dynaamista muistinhallintajärjestelmää. Tyypillisessä roskienkeräyssyklissä säilytetään kaikki objektit, joihin vielä viitataan ja jotka ovat siten tavoitettavissa. Aiemmin viitattujen objektien viemä tila vapautetaan ja otetaan takaisin, jotta uudet objektit voidaan varata.

Ymmärtääksesi roskienkeräystä ja erilaisia GC-lähestymistapoja ja -algoritmeja sinun on ensin tiedettävä muutamia asioita Java-alustan muistimallista.

Hävikin keruu ja Java-alustan muistimalli

Kun Java-sovelluksen komentorivillä määritetään käynnistysvaihtoehto -Xmx (esimerkiksi: java -Xmx:2g MyApp), Java-prosessille osoitetaan muistia. Tähän muistiin viitataan nimellä Java heap (tai vain heap). Tämä on varattu muistin osoiteavaruus, johon kaikki Java-ohjelmasi (tai joskus JVM:n) luomat objektit varataan. Kun Java-ohjelmasi jatkaa suorittamista ja uusien objektien allokointia, Java heap (eli tuo osoiteavaruus) täyttyy.

Jaavan heap on lopulta täynnä, mikä tarkoittaa sitä, että allokoiva säie ei löydä tarpeeksi suurta peräkkäistä vapaan muistin jaksoa objektille, jonka se haluaa allokoida. Tässä vaiheessa JVM määrittää, että roskienkeräyksen on tapahduttava, ja se ilmoittaa siitä roskienkerääjälle. Roskienkeräys voidaan käynnistää myös, kun Java-ohjelma kutsuu System.gc(). System.gc():n käyttäminen ei takaa roskienkeruuta. Ennen kuin roskienkeräys voidaan aloittaa, GC-mekanismi määrittää ensin, onko sen aloittaminen turvallista. Roskienkeräyksen aloittaminen on turvallista silloin, kun kaikki sovelluksen aktiiviset säikeet ovat turvallisessa pisteessä, joka sallii sen, esim. yksinkertaisesti selitettynä olisi huono aloittaa roskienkeräys kesken meneillään olevan objektien allokoinnin tai kesken optimoitujen CPU-käskyjen sarjan suorittamisen (ks. edellinen artikkelini kääntäjistä), koska saatat menettää kontekstin ja siten sotkea lopputuloksen.

Roskienkeräysmekanismi ei saisi koskaan vaatia takaisin objektiobjektia, johon viitataan aktiivisesti; se rikkoisi Java-virtuaalikoneen spesifikaatiota. Roskienkerääjän ei myöskään tarvitse kerätä kuolleita objekteja välittömästi. Kuolleet objektit kerätään lopulta seuraavien roskienkeräysjaksojen aikana. Vaikka roskienkeräys voidaan toteuttaa monin eri tavoin, nämä kaksi oletusta pätevät kaikkiin lajityyppeihin. Roskienkeräyksen todellisena haasteena on tunnistaa kaikki elävät (edelleen viitatut) objektit ja ottaa takaisin kaikki viittaamaton muisti, mutta tehdä se vaikuttamatta käynnissä oleviin sovelluksiin enempää kuin on tarpeen. Roskienkerääjällä on siis kaksi toimeksiantoa:

1. Vapauttaa nopeasti viittaamatonta muistia, jotta sovelluksen allokointinopeus täyttyisi, jotta muisti ei loppuisi kesken.
2. Vapauttaa muistia takaisin niin, että suorituskykyyn vaikuttaa mahdollisimman vähän (esim, latenssi ja läpäisykyky) käynnissä olevan sovelluksen toimintaan.

Kahdenlaista roskienkeräystä

Tämän sarjan ensimmäisessä artikkelissa käsittelin kahta tärkeintä lähestymistapaa roskienkeräykseen, jotka ovat viittauslaskenta ja jälkikeräys. Tällä kertaa syvennyn tarkemmin kumpaankin lähestymistapaan ja esittelen sitten joitakin algoritmeja, joita käytetään jäljityskerääjien toteuttamiseen tuotantoympäristöissä.

Viittausten laskennan keräimet

Viittausten laskennan keräimet pitävät kirjaa siitä, kuinka monta viittausta osoittaa kuhunkin Java-objektiin. Kun objektin laskenta muuttuu nollaksi, muisti voidaan ottaa välittömästi takaisin. Tämä välitön pääsy takaisin hankittuun muistiin on viitteiden laskentaan perustuvan roskienkeräysmenetelmän suurin etu. Viittaamattoman muistin säilyttämisestä aiheutuu hyvin vähän yleiskustannuksia. Kaikkien viittauslaskentojen pitäminen ajan tasalla voi kuitenkin olla melko kallista.

Viittauslaskennan suurimpana vaikeutena on viittauslaskennan pitäminen tarkkana. Toinen tunnettu haaste on ympyrärakenteiden käsittelyyn liittyvä monimutkaisuus. Jos kaksi objektia viittaa toisiinsa eikä mikään elävä objekti viittaa niihin, niiden muistia ei koskaan vapauteta. Molemmat objektit pysyvät ikuisesti nollasta poikkeavalla lukumäärällä. Ympyrärakenteisiin liittyvän muistin palauttaminen vaatii suurta analyysia, mikä aiheuttaa kalliita yleiskustannuksia algoritmille ja siten sovellukselle.

Tracing collectors

Tracing collectors perustuvat olettamukseen, että kaikki elävät objektit voidaan löytää jäljittämällä iteratiivisesti kaikki viittaukset ja myöhemmät viittaukset alkujoukosta, jonka tiedetään olevan eläviä objekteja. Alkuperäinen joukko eläviä objekteja (joita kutsutaan juuriobjekteiksi tai lyhyesti vain juuriksi) paikannetaan analysoimalla rekisterit, globaalit kentät ja pinon kehykset sillä hetkellä, kun roskienkeräys käynnistetään. Kun alkuperäinen elävä joukko on tunnistettu, jäljityskerääjä seuraa näiden objektien viittauksia ja asettaa ne jonoon, jotta ne voidaan merkitä eläviksi ja niiden viittaukset voidaan jäljittää. Kaikkien löydettyjen viitattujen objektien merkitseminen eläviksi tarkoittaa, että tunnettu elävien objektien joukko kasvaa ajan mittaan. Tämä prosessi jatkuu, kunnes kaikki viitatut (ja siten kaikki elävät) objektit on löydetty ja merkitty. Kun jäljityskerääjä on löytänyt kaikki elävät objektit, se ottaa jäljelle jääneen muistin takaisin.

Jäljityskerääjät eroavat viittauslaskentakerääjistä siinä, että ne voivat käsitellä ympyrärakenteita. Useimpien jäljityskerääjien juju on merkitsemisvaihe, joka aiheuttaa odottelua ennen kuin ei-viitattua muistia voidaan vaatia takaisin.

Jäljityskerääjiä käytetään yleisimmin muistinhallintaan dynaamisissa kielissä; ne ovat ylivoimaisesti yleisimpiä Java-kielessä, ja ne ovat olleet kaupallisesti testattuja tuotantoympäristöissä useiden vuosien ajan. Keskityn tämän artikkelin loppuosassa jäljitettäviin keräilijöihin ja aloitan joistakin algoritmeista, jotka toteuttavat tämän lähestymistavan roskienkeräykseen.

Jäljitettävien keräilijöiden algoritmit

Kopiointikeräys ja merkitse ja pyyhkäise roskienkeräys (mark-and-sweep garbage collection) -algoritmit eivät ole mitään uutta tietoa, mutta ne ovat silti nykyäänkin kaksi yleisintä jäljitettävää roskienkeräystä toteuttavaa algoritmiä.

Kopioivat keräilijät

Traditionaaliset kopioivat keräilijät käyttävät from-avaruutta ja to-avaruutta — eli kahta erikseen määriteltyä osoiteavaruutta kasasta. Roskienkeräyshetkellä from-avaruudeksi määritellyn alueen sisällä olevat elävät objektit kopioidaan seuraavaan vapaaseen tilaan to-avaruudeksi määritellyn alueen sisällä. Kun kaikki from-avaruudessa olevat elävät objektit on siirretty pois, koko from-avaruus voidaan ottaa takaisin. Kun allokointi aloitetaan uudelleen, se alkaa ensimmäisestä vapaasta paikasta to-avaruudessa.

Tämän algoritmin vanhemmissa toteutuksissa from-avaruus ja to-avaruus vaihtavat paikkaa, mikä tarkoittaa, että kun to-avaruus täyttyy, roskienkeräys käynnistyy uudelleen ja to-avaruudesta tulee from-avaruus, kuten kuviossa 1 näkyy.

Nykyaikaisemmat kopiointialgoritmin toteutukset mahdollistavat sen, että kasan sisällä olevat mielivaltaiset osoiteavaruudet voidaan määrittää to-avaruudeksi ja from-avaruudeksi. Tällöin niiden ei välttämättä tarvitse vaihtaa sijaintia keskenään, vaan kummastakin tulee toinen osoiteavaruus kasan sisällä.

Yksi kopioivien keräilijöiden eduista on se, että objektit allokoidaan to-avaruudessa tiiviisti yhteen, jolloin pirstaloituminen poistuu kokonaan. Pirstaloituminen on yleinen ongelma, jonka kanssa muut roskienkeräysalgoritmit kamppailevat; käsittelen sitä myöhemmin tässä artikkelissa.

Kopioivien keräilijöiden haitat

Kopioivat keräilijät ovat yleensä stop-the-world-keräilijöitä, mikä tarkoittaa sitä, että mitään sovelluksen työtä ei voida suorittaa niin kauan kuin roskienkeräys on syklissä. Stop-the-world-toteutuksessa vaikutus sovelluksen suorituskykyyn on sitä suurempi, mitä suurempi kopioitava alue on. Tämä on haitta sovelluksille, jotka ovat herkkiä vasteajalle. Kopioivassa keräilijässä on otettava huomioon myös pahin mahdollinen skenaario, jolloin kaikki on elossa from-avaruudessa. Sinun on aina jätettävä riittävästi tilaa siirrettäville eläville objekteille, mikä tarkoittaa, että to-avaruuden on oltava riittävän suuri, jotta kaikki from-avaruudessa olevat objektit mahtuvat sinne. Kopiointialgoritmi on hieman muistitehoton tämän rajoituksen vuoksi.

Mark-and-sweep-kerääjät

Useimmissa kaupallisissa JVM:issä, joita käytetään yritysten tuotantoympäristöissä, käytetään mark-and-sweep (tai marking) -kerääjiä, joilla ei ole samanlaista suorituskykyvaikutusta kuin kopiointikerääjillä. Tunnetuimpia merkintäkerääjiä ovat CMS, G1, GenPar ja DeterministicGC (ks. Resurssit).

Merkitse-ja-pyyhkäise-kerääjä jäljittää viittaukset ja merkitsee jokaisen löydetyn objektin “elävällä” bitillä. Yleensä asetettu bitti vastaa osoitetta tai joissakin tapauksissa joukon osoitteita kasassa. Elävä bitti voidaan tallentaa esimerkiksi objektin otsikon bittinä, bittivektorina tai bittikarttana.

Kun kaikki on merkitty eläviksi, sweep-vaihe käynnistyy. Jos keräilijällä on pyyhkäisyvaihe, se sisältää periaatteessa jonkin mekanismin, jolla kasa (ei vain live-joukko vaan koko kasan pituus) kierretään uudelleen paikallistamaan kaikki peräkkäisten muistiosoiteavaruuksien merkitsemättömät kappaleet. Merkitsemätön muisti on vapaata ja palautettavissa. Kerääjä yhdistää sitten nämä merkitsemättömät palaset järjestetyiksi vapaiden muistien luetteloiksi. Roskienkerääjässä voi olla erilaisia vapaita luetteloita, jotka on yleensä järjestetty kappalekokojen mukaan. Jotkin JVM:t (kuten JRockit Real Time) toteuttavat keräilijät heuristiikoilla, jotka dynaamisesti kokoluokittelevat listoja sovelluksen profilointitietojen ja objektikokotilastojen perusteella.

Kun pyyhkäisyvaihe on päättynyt, allokointi alkaa uudelleen. Uusia allokaatioalueita varataan vapaista luetteloista, ja muistipaloja voidaan sovittaa objektien kokoihin, objektien kokokeskiarvoihin säikeen ID:tä kohti tai sovelluksen virittämiin TLAB-kokoihin. Vapaan alueen sovittaminen tarkemmin sen koon mukaan, mitä sovellus yrittää allokoida, optimoi muistia ja voi auttaa vähentämään pirstaloitumista.

Merkki- ja pyyhkäisykerääjien varjopuolet

Merkkausvaihe on riippuvainen elävän datan määrästä kasassa, kun taas pyyhkäisyvaihe on riippuvainen kasan koosta. Koska muistin talteenottoa varten on odotettava, kunnes sekä mark- että sweep-vaiheet ovat päättyneet, tämä algoritmi aiheuttaa taukoaikahaasteita suuremmille kasoille ja suuremmille eläville tietokokonaisuuksille.

Yksi tavaksi auttaa paljon muistia kuluttavia sovelluksia on käyttää GC:n viritysvaihtoehtoja, jotka mukautuvat erilaisiin sovellusskenaarioihin ja tarpeisiin. Viritys voi monissa tapauksissa auttaa ainakin lykkäämään jompaakumpaa näistä vaiheista, jotta niistä ei tulisi riskiä sovellukselle tai palvelutasosopimuksille (SLA). (Palvelutasosopimuksessa määritetään, että sovellus täyttää tietyt sovelluksen vasteajat eli latenssin.) Virittäminen jokaista kuormituksen muutosta ja sovelluksen muutosta varten on kuitenkin toistuva tehtävä, koska viritys on voimassa vain tietylle työkuormalle ja allokointinopeudelle.

Mark-and-sweep -keräyksen toteutukset

Mark-and-sweep -keräyksen toteuttamiseen on olemassa ainakin kaksi kaupallisesti saatavilla olevaa ja hyväksi havaittua lähestymistapaa. Toinen on rinnakkainen lähestymistapa ja toinen rinnakkainen (tai enimmäkseen rinnakkainen) lähestymistapa.

Rinnakkaiskerääjät

Rinnakkaiskeräyksellä tarkoitetaan sitä, että prosessille osoitettuja resursseja käytetään rinnakkain roskienkeräykseen. Useimmat kaupallisesti toteutetut rinnakkaiskerääjät ovat monoliittisia stop-the-world-kerääjiä — kaikki sovellussäikeet pysäytetään, kunnes koko roskienkeräyssykli on suoritettu loppuun. Kaikkien säikeiden pysäyttäminen mahdollistaa kaikkien resurssien tehokkaan rinnakkaiskäytön roskienkeräyksen loppuun saattamiseksi merkintä- ja pyyhkäisyvaiheiden kautta. Tämä johtaa erittäin korkeaan tehokkuuteen, mikä yleensä johtaa korkeisiin tuloksiin SPECjbb:n kaltaisissa läpimenoa mittaavissa vertailuarvoissa. Jos läpäisykyky on sovelluksellesi tärkeää, rinnakkainen lähestymistapa on erinomainen valinta.