Välimuistitietoisuuden vaikutus k-aristen puiden suorituskykyyn
Rajaniemi, Riku (2017-11-22)
Välimuistitietoisuuden vaikutus k-aristen puiden suorituskykyyn
Rajaniemi, Riku
(22.11.2017)
Tätä artikkelia/julkaisua ei ole tallennettu UTUPubiin. Julkaisun tiedoissa voi kuitenkin olla linkki toisaalle tallennettuun artikkeliin / julkaisuun.
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe201801111288
https://urn.fi/URN:NBN:fi-fe201801111288
Tiivistelmä
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.
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.