Zliczanie referencji

Zliczanie referencji (ang. reference counting) – jedna z najłatwiejszych metod odśmiecania pamięci, opracowana w 1959 roku przez Johna McCarthy’ego na potrzeby zarządzania pamięcią w języku programowania Lisp. W metodzie tej, wraz z każdym zaalokowanym obiektem, skojarzony jest licznik, który służy do zliczania wszystkich aktualnych odwołań do obiektu. Za każdym razem, kiedy tworzone jest nowe odwołanie do obiektu, licznik ten jest zwiększany o jeden, natomiast kiedy odwołanie to jest usuwane, licznik jest zmniejszany o jeden. Kiedy wartość licznika osiągnie zero, oznaczać to będzie, że dany obiekt nie jest już osiągalny w prawidłowy sposób, więc można zwolnić pamięć wcześniej mu przydzieloną. Jeśli przed skasowaniem ów obiekt sam używał referencji do innych obiektów, to liczniki odwołań tych obiektów także są zmniejszane; mogą zatem również osiągnąć wartość zero, co spowoduje rekursywne skasowanie kolejnych obiektów. Zaletą metody jest fakt, że zaalokowana pamięć jest zwalniana tak szybko jak to możliwe – tuż po tym, jak licznik referencji osiągnie wartość 0. Metoda ta jest także prosta w implementacji. Jedną z wad zliczania referencji jest to, że nie radzi sobie ona z zależnościami cyklicznymi pomiędzy obiektami. Jeśli obiekt A wskazuje na obiekt B, natomiast obiekt B wskazuje z powrotem na obiekt A, to żaden z nich nie zostanie nigdy zwolniony. Wykorzystanie tej metody może także prowadzić do nadmiernej fragmentacji stosu pamięci. Waizenbaum zaproponował zmodyfikowaną wersję algorytmu, w której zamiast kasować rekursywnie obiekty dodaje się je do listy obiektów nieużywanych, a proces zwalniania pamięci jest przeprowadzany w późniejszym czasie.