School of Computing

Cyclic reference counting with lazy mark-scan

Rafael D Lins

Technical Report 26-92*, University of Kent, Computing Laboratory, University of Kent, Canterbury, UK, August 1992.

Abstract

We present an algorithm that removes the drawback of running mark-scan every time a pointer to a cell with multiple references is deleted in the cyclic reference counting with local mark-scan algorithm. This new algorithm places a reference to these cells onto a queue. The deletion of the last pointer to a shared cell will recycle it immediately, regardless of whether there is a reference to it on the queue. This means that more shared cells will now be claimed directly without the need of the mark-scan phase. Only if the free-list is empty or the queue is full is the local mark-scan required. Our performance figures show that lazy mark-scan is far more efficient than local mark-scan.

(to appear in Information Processing Letters)

Download publication 36 kbytes

Bibtex Record

@techreport{120,
author = {Rafael D Lins},
title = {Cyclic Reference Counting with Lazy Mark-Scan},
month = {August},
year = {1992},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1992/120},
    address = {University of Kent, Canterbury, UK},
    hensa_abstractfilename = {pub/misc/ukc.reports/comp.sci/abstracts/26-92},
    hensa_ftpaddress = {unix.hensa.ac.uk},
    hensa_reportfilename = {pub/misc/ukc.reports/comp.sci/reports/26-92.ps.Z},
    institution = {University of Kent, Computing Laboratory},
    number = {26-92*},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014