Välimuistitietoisuuden vaikutus k-aristen puiden suorituskykyyn

Abstract

Tietokoneiden keskusmuisti ei ole nopeutunut samaa tahtia prosessorien kanssa. Tämän vuoksi tehokkailla prosessorisiruilla on nykyään nopeaa välimuistia. Välimuistin tehokkaalla hyödyntämisellä voi olla suurempi vaikutus ohjelman suorituskykyyn kuin suoritettavien käskyjen määrällä.

Tässä tutkielmassa vertaillaan kolmen k-arisen puurakenteen suorituskykyä välimuistin tehokkaan hyödyntämisen näkökulmasta. Puista kaksi on tyypillisiä osoittimista koostuvia puurakenteita, ja yksi on uusi syvyystaulukkoon pohjautuva puurakenne. Osoittimista koostuvista puista testataan naiivin version lisäksi muistivarantoa käyttävä versio, joka vähentää vaadittavien muistinvarausoperaatioiden määrää ja parantaa tietorakenteen sisäistä välimuistipaikallisuutta.

Puurakenteiden arviointi suoritetaan käyttäen useita erilaisia muokkaus- ja lukuoperaatioita, ja ennen jokaista testiä välimuisti tyhjennetään vertailukelpoisen lähtötilanteen takaamiseksi.

Testit osoittavat, että osoitinpuiden tapauksessa muistivarannon käyttäminen parantaa puiden suorituskykyä muokkausoperaatioissa 10 -- 80 %, ja että syvyystaulukkopuu suoriutuu lukuoperaatioista osoitinpuita 20 -- 90 % lyhyemmässä ajassa.