Miksi muistinsiivousta ylipäätään tarvitaan? Koska koneiden käytössä olevat muistiresurssit ovat rajallisia on mielekästä, että niitä käytetään mahdollisimman tehokkaasti ja muistia liialti haaskaamatta hyväksi. Ohjelmaa suoritettaessa edellisestä kirjoituksesta tutut oliot syntyvät ja aikanaan kuolevat. Muistinsiivouksen ajatuksena onkin siivota näitä kuolleita olioita pois muistista, jotta olioiden "ruumiiden" viemää tilaa voidaan hyödyntää uudelleen. Pohjimmiltaan kyse on siis vain elintilan luomisesta olioille. Tässä tapauksessahan oliot eivät luonnosta poiketen lahoa itsestään vain säilyttävät katatonisen tilansa, kunnes joku tajuaa hankkiutua niistä eroon.
Luennolla esitettiin Stroustrupin (C++:n pääkehittäjä) esittämä mielipide siitä, että kaikkia kuolleita olioita ei välttämättä tarvitse tai kannata siivota. Tarkemmin puhe oli nimenomaan pienien muistivuotojen sallimisesta. Nähdäkseni tässä ajatuksessa ydin oli siinä, että vaatimus muistivuodottomasta ohjelmistosta saattaa olla jopa liian rankka. Mikäli tästä vaatimuksesta joustaminen tekee ohjelmistojen kehittämisestä helpompaa, saattaa se olla sen arvoista. Tässä kannattaa pitää mielessä erityisesti alusta, jolle ohjelmistoa ollaan kehittämässä. Mikäli laitteistoresurssit antavat myöden, voi olla hyvinkin tehokasta joustaa hieman.
Luennolla esitettiin kolme perustekniikkaa, joiden avulla muistinsiivousta voidaan tehdä. Jotta näitä tekniikoita voi ymmärtää tulee ymmärtää, että muistia kannattaa hahmottaa graafina. Graafilla on juurisolmuja, joista viitataan varsinaisiin käytettyihin olioihin. Oliot voivat viitata vapaasti toisiinsa.
Esitetyistä tekniikoista itselleni intuitiivisin oli viittauslaskuriin pohjautuva ratkaisu. Ajatuksena on, että kuhunkin olioon liittyy luku, joka kuvaa siihen liittyvät viitteet. Lukua päivitetään viitteitä lisättäessä tai poistettaessa. Mikäli luku on nolla, voidaan olio poistaa. Viittauslaskurin ongelmana on tapaus, jossa oliot muodostavat keskenään syklisiä luuppeja. Tällöin voidaan luoda tahattomasti saarekkeita, jotka eivät liity juurisolmuihin siten, että juurisolmuista voitaisiin kulkea saarekkeisiin. Huomaa, ettei tämä tarkoita etteikö saarista voisi kulkea juurisolmuihin! Tästä seuraa, että saarekkeita ei poisteta, koska niiden viittausmäärää kuvaava luku ei luonnollisestikaan ole nolla. Kyseistä ongelmaa voisi kenties pyrkiä kiertämään. Seuraavana esitänkin alkeellisen ratkaisun, jota en tosin ole todentanut käytännön testein.
Kaikki oliot liittyvät juurisolmuihin jossain vaiheessa. Tämä seuraa tavasta, jolla olioita luodaan. Uuden olion tulee liittyä johonkin juurisolmuihin liittyvään solmuun tai juurisolmuihin itseensä. Ongelma onkin saareen liittyvän viitteen poistamisen havaitseminen. Toisaalta tämä edellyttää, että saaren käsite tulisi voida määritellä eksplisiittisesti oliograafissa.
Huomaa, että määrittelen saaren syklisenä kahden tai useamman olion muodostamana osagraafina. Saaren syntymän voi havaita, kun luodaan uusi viite ja tarkistetaan viitteen lähde- ja kohdeolion välinen suhde käymällä graafi läpi lähtien kohdeoliosta ja pyrkien löytämään lähdeolio. Mikäli lähdeolio löydetään, syntyy liitoksen myötä saari.
Jotta tästä löydöksestä voisi hyötyä, tulee saareen liittyviin olioihin kuhunkin muodostaa oma viittauslaskurinsa saariviitteitä varten. Kun saari löydetään, siirretään kunkin olion varsinaisesta viittauslaskurista yksi viite saarilaskuriin. Tästä seuraa pieni muutos tapaan, jolla "saariolioita" poistetaan. Vaikka saariolion varsinainen viitelaskuri olisikin nolla ei se tarkoita, että olio voitaisiin poistaa. Saarioliot voidaan poistaa vain ja ainoastaan jos kaikkien saareen kuuluvien olioiden varsinainen viitelaskuri on nolla. Toisaalta tulee muistaa huolehtia tilanteesta, jossa saaria tuhoutuu (ts. sykli invalidoituu) ja päivittää laskureita jälleen tällöin.
Saariolioiden käyttäminen edellyttäisi ylimääräistä laskuria, mutta toisaalta niiden avulla voitaisiin kenties parantaa viittauslaskurin perusmallin kykyä poistaa muistista kaikki turhat oliot sykliset tapaukset mukaanlukien. Lisäksi suorituskyky saattaisi kärsiä hieman ylimääräisistä graafin läpikäynneistä johtuen.
Viittauslaskurille löytyy varmasti muitakin variantteja kuin edellä esitelty. Toinen esitelty tekniikka oli ns. merkkaa ja lakaise (mark and sweep). Yllättäen tämä oli vanhin keksityistä tekniikoista. Perusajatuksena on, että oliograafi käydään juuresta lähtien läpi ja kukin vierailtu olio merkitään vierailluksi. Tämän jälkeen kaikki oliot käydään läpi siten, että näistä poistetaan ne, joita ei ole merkattu. Näin jälkikäteen ajatellen metodi on hämmästyttävän yksinkertainen.
Kolmas läpikäyty tekniikka oli ns. "pysäytä ja kopioi". Tekniikan perusajatuksena on, että koko muisti ajatellaan kahtena osana. Toista osaa vuorollaan käytetään varsinaisena muistina toisen toimiessa varalla. Tätä varaosaa käytetään, kun muistia halutaan siivota. Tällöin kukin olio vuorollaan juuresta lähtien kopioidaan tähän varaosaan. Kun olioita kopioidaan pidetään huoli myös siitä, että olioiden väliset viitteet säilyvät ennallaan. Kopioinnin jälkeen varaosasta tulee käytettävä osa ja entisestä osasta varaosa. Kopioinnin etuna on se, että samalla voidaan "defragmentoida" muistia. Tämä etu perustuu siihen, että muistia osoitetaan varaosasta olioita varten peräkkäin. Kun kaikki oliot on kopioitu osan loppu sisältää tyhjää, helposti allokoitavaa muistia.
Siihen, mitä edellä esitellyistä tekniikoista pitäisi käyttää ja milloin, en osaa vastata. Kuitenkin oli virkistävää nähdä kuinka sama asia voidaan tehdä niinkin eri tavoin. Olennaista vielä lienee mainita, että tekniikoita voidaan varioida ja pyrkiä optimoimaan eri tavoin. Jo tämä sinällään tarjoaa mielenkiintoisia pähkinöitä purtavaksi.
Tulisiko muistinsiivoustekniikoita yleensäkään käyttää, koska ne voivat hidastaa ohjelman toimintaa (90-luvun Java lienee tunnetuin esimerkki)? Omasta kokemuksestani C:n parissa voin todeta, että kannattaa, mikäli suorituskyky ja ohjelmoijan kontrolli eivät ole olennaisimpia asioita ohjelmiston kehityksessä. Muistinsiivoustekniikoiden olemassaolo tekee nykyajan ohjelmiston kehittäjän elämän asteen helpommaksi.
Muistinsiivoustekniikoiden käsittelyn jälkeen siirryttiin luennon varsinaiseen aiheeseen eli kontrollivuon ohjaukseen. Aiemmin käsitellyt suoraviivaohjelmat eivät ole kovinkaan hyödyllisiä sellaisinaan. Ne kuitenkin tarjoavat teoreettisen pohjan, jonka päälle voidaan rakentaa oikeasti käyttökelpoisia kieliä. Jotta voidaan tehdä jotain hyödyllistä, tarvitaan vähintään ehtolause (if
Näiden yksinkertaisten konstruktioiden avulla voidaan rakentaa nykykielistä tuttu while. while on pohjimmiltaan vain ehdollinen goto. Tärkein seikka, mikä erottaa whilen gotosta on nimenomaan se, että while on hyvin rajoittunut tapa käyttää gotoa. Syy, minkä takia goton käytöstä ei juurikaan pidetä johtuu juurikin siitä, että se on niin voimakas työkalu. Suuren voiman mukana tulee suuri vastuu. Voikin olla hyvä, että goton käyttämistä karsastetaan sen väärinkäyttömahdollisuuksien vuoksi. Toisaalta sen hyödyntäminen saattaa olla joskus houkuttelevaa ja kenties jopa käytännöllistäkin.
Kielten konstruktioita pohdittaessa voidaan havaita, että kukin konstruktio pyrkii omalla tavallaan rajoittamaan kielen käyttämistä. Hyvä esimerkki on whilen rajoitettu muoto for. for voi pakottaa, kielestä riippuen, kehittäjän tekemään kyseisestä silmukasta äärellisen. Toisaalta for kasaa monta whilea käytettäessä hajanaisissa paikoissa olevaa seikkaa samaan paikkaan. Jo tämä sinällään tekee siitä arvokkaan ja erittäin käyttökelpoisen konstruktion. Iteraattoripohjaiset (esim. for alkio in alkiot) for konstruktiot tekevätkin ohjelmoinnista helppoa. Tosin niilläkin on omat rajoituksensa.
Sen lisäksi, että konstruktiot pyrkivät rajaamaan, pyrkivät ne toisaalta myös selkeyttämään asioita. Pahimmillaan ne kuitenkin vain sekoittavat asioita. Hyvä esimerkki tästä on ehtolausekkeiden evaluointi. Esimerkiksi kielestä riippuen ei ole lainkaan selvää mitä esimerkiksi ehtolauseesta 3 > 2 > 1 seuraa. Mielestäni hyvässä toteutuksessa keskimmäistä tekijää vertailtaisiin erillisesti sen naapureihin. Tämän perusteella voitaisiin päätellä koko lauseen totuusarvo. Toki menetelmän tulisi yleistyä. Tällöin keskimmäisen tekijän sijaan otettaisiin kaikki reunimmaisten tekijöiden väliin osuvat tekijät ja kullekin tehtäisiin vertailu samaan tapaan.
Toisinaan ehtolauseista on hyötyä myös sijoituksessa. Esim. Lua ja Python sisältävät seuraavanlaiset and ja or konstruktiot:
foo = bar or baz
foo = bar and baz
Itse hyödynnän erityisesti or tapausta. Ajatuksena tässä tapauksessa on, että mikäli bar on epätosi, sijoitetaan foo muuttujaan bazin arvo. Muulloin sijoitetaan bar. and tapauksessa bazin arvo sijoitetaan foo muuttujaan vain ja ainoastaan jos myös bar on tosi.
Kolmas, Pythonissa joskus käytetty, mielenkiintoinen konstruktio on seuraavanlainen:
foo = bar if
Tässä tapauksessa barin arvo sijoitetaan foohon ehdon ollessa tosi. Muulloin sijoitetaan baz. Luettavuudeltaan konstruktio ei ole mielestäni paras mahdollinen. Tämä johtuu ifin hieman oudosta paikasta. Toisaalta konstruktio voi paisua merkkimäärällisesti turhankin pitkäksi. Tällöin suosii mieluummin perinteistä if-else paria.
Luennolla esiteltiin myös ifistä vaihtoehtoinen muoto, joka tunnetaan nimellä vahtikomento. Tässä tapauksessa ajatuksena on epädeterminismin(!) salliminen ohjelmointikielessä. Toisin sanoen siitä, mitä seuraavaksi tapahtuu ei ole välttämättä takeita. Tällaisesta konstruktiosta ja ohjelmointitavasta saattaisi olla kenties hyötyä tilanteissa, joissa ajoa halutaan satunnaistaa. Toisaalta satunnaistaminen on mahdollista deterministisissäkin kielissä, joten en näe epädeterminismiä mitenkään ylivoimaisen hyvänä ominaisuutena. Mielestäni vahtikomennoissa mennään jo kielen kannalta hieman väärään suuntaan ottaen huomioon, että kielten perustehtävähän on yksinkertaistaa asioita sopivasti sen sijaan, että luotaisiin lisää kompleksisuutta. Tosin voi olla, että en ole huomannut jotain vahtikomentojen oleellista hyvää ominaisuutta, joten voi olla että niillekin löytyy käyttönsä.
Yhteenvetona todettakoon, että luennolla sain kattavamman kuvan muistinsiivoamistekniikoista sekä paremman käsityksen primitiivisistä konstruktioista (if, goto, while, ...) sekä niiden variointimahdollisuuksista. Samalla käsitykseni siitä, mitä ohjelmointikielet loppujen lopuksi ovat, vankistui hieman.
Päiväkirjaa kirjoittaessa en keksinyt sovelluksia vahtikomennoille. Nyt hieman tekoälyä opiskeltuani ymmärrän, että ne olisivat varsin mukava, joskaan ei välttämätön ominaisuus agenttien kehittämisen kannalta.
VastaaPoistaKuten postauksessa mainitsin pystyy epädeterminismiä matkimaan helposti satunnaislukugeneraattorin (satunnaistaminen) ja if-lausekkeen avulla.
Näin jälkikäteen tuntuu ehkä hieman oudolta, että luennolla ei mainittu lainkaan labeleita. Ajatuksena labelien käytössähän on, että niihin voidaan viitata esim. breakista suoraan (break labelin_nimi). Kyseistä konstruktiota voidaan käyttää pätevästi sisäkkäisten luuppien rikkomiseen.
Sisäkkäisiin luuppeihin liittyen opin kurssin kuluessa näppärän keinon, jolla niitä pystyy kiertämään. Apukeinona voidaan käyttää zipiä (http://docs.python.org/library/functions.html#zip). Se toimii esim. seuraavasti (esimerkki voisi olla ehkä parempi mutta tuosta saa ainakin idean selville):
names = ('Joe', 'Jack', 'Jill', )
surnames = ('Jackson', 'Johnson', 'Jimson', )
whole_names = []
# perusluupilla
for name, surname in zip(names, surnames):
____whole_names.append(name + ' ' + surname)
# nyt kirjoittaisin näin (list comprehension)
whole_names = [name + ' ' + surname for name, surname in zip(names, surnames)]
Lähinnä ajatuksena on, että pienen apurin avulla luuppeja voi karsia. Toki zipin ym. käyttäminen on siinä mielessä arveluttavaa, että ne lisäävät koodin kompleksisuutta, jos ei satu tietämään, miten nuo pelittävät.