Viitteiden laskenta on tekniikka , jolla tallennetaan viitteiden , osoittimien tai kuvaajien määrä johonkin resurssiin, kuten objektiin tai muistilohkoon. Yleensä käytetään keinona vapauttaa esineitä, joita ei enää tarvita ja joihin ei enää viitata.
Viitteiden laskenta tunnetaan myös yhtenä roskankeräysalgoritmeista , jossa jokainen objekti sisältää muiden objektien käyttämien viittausten määrän. Kun tämä laskuri laskee nollaan, se tarkoittaa, että kohde on poissa käytöstä ja se on sijoitettu tuhottavien kohteiden luetteloon.
Yksinkertainen viitteiden laskenta vaatii laskurin säännöllisiä päivityksiä. Aina kun objektiviittaus tuhotaan tai kirjoitetaan päälle, objektin viitemäärää pienennetään, ja kun objektin viittauksia luodaan tai kopioidaan, objektin viitemäärää lisätään.
Viitelaskentaa käytetään myös levykäyttöjärjestelmissä ja hajautetuissa järjestelmissä, joissa täysi ei-inkrementaalinen roskankeräilijöiden seuranta olisi liian aikaa vievää toisiinsa yhdistettyjen objektien kaavion koon ja hitaan pääsynopeuden vuoksi.
Viitelaskennan tärkein etu roskankeräilijöiden seurantaan verrattuna on, että kohteet poistetaan heti, kun niihin ei voida viitata, ja asteittain, ilman pitkiä taukoja keräysjaksoissa ja kunkin kohteen selkeästi määritellyllä käyttöiällä. Reaaliaikaisissa sovelluksissa tai järjestelmissä, joissa on rajoitettu muisti, tämä on erittäin tärkeää nopeiden vasteaikojen ylläpitämiseksi. Viitelaskenta on myös yksi yksinkertaisimmista tavoista toteuttaa jätteenkeruu. Se tarjoaa myös tehokkaan muistin lisäksi myös muiden resurssien, kuten käyttöjärjestelmäobjektien, tehokkaan hallinnan, joita on usein paljon vähemmän kuin muistia (järjestelmät, joissa on roskakeräyksen seuranta, käyttävät viimeistelyjä , mutta viivästynyt puhdistus voi silti aiheuttaa ongelmia) . Painotetut viitemäärät ovat hyvä ratkaisu hajautettujen järjestelmien roskien keräämiseen.
Viitemäärät ovat myös hyödyllisiä syötteenä erilaisille ajonaikaisille optimoijille. Esimerkiksi järjestelmät, jotka ovat voimakkaasti riippuvaisia muuttumattomista objekteista (monet toiminnalliset kielet ), voivat menettää suorituskykynsä toistuvien kopiointitoimintojen vuoksi. Jos kuitenkin tiedämme, että jollakin objektilla on vain yksi linkki ja tämä linkki katoaa, mutta samalla luodaan samanlainen uusi objekti (kuten merkkijonon lisäyslausekkeessa str ← str + "a"), voimme korvata tämän toiminnon muutoksella ( Englanninkielinen mutaatio ) alkuperäinen objekti.
Viitteiden laskemisella yksinkertaisimmassa muodossaan on kaksi suurta haittaa roskienkeruun seurantaan verrattuna. Molemmat vaativat lisämekanismeja parantaakseen:
Jätteenkeräysmenetelmien kanssa työskennellessä on usein kätevää ajatella linkkigraafia , joka on suunnattu graafi, jossa kärjet ovat objekteja, ja jos objekti A sisältää viittauksen objektiin B, pisteet yhdistetään kärjestä A olevalla reunalla. B:hen on olemassa myös erikoispisteitä, jotka edustavat suoritusympäristöön (ajonaikaiseen) liittyviä paikallisia muuttujia tai viittauksia. Reunat eivät koskaan osoita näihin pisteisiin, mutta reunat voivat siirtyä näistä kärkeistä muihin.
Tässä yhteydessä kohteen yksinkertaisin viiteluku on kärjen saapuvien reunojen lukumäärä. Vertexin poistaminen tarkoittaa objektin vapauttamista (poistamista). Huippupisteen poistaminen tapahtuu, kun kärjellä ei ole enää saapuvia reunoja. Siksi poistaminen ei vaikuta muiden kärkien lähtevien reunojen määrään, mutta se voi vaikuttaa niiden sisään tulevien reunojen määrään, mikä puolestaan voi johtaa vastaavien objektien vapautumiseen.