An efficient approach to cyclic reference counting based on a coarse-grained search

Chin Yang Lin, Ting Wei Hou

Research output: Contribution to journalArticlepeer-review

Abstract

Reference counting is known to have problems working with cyclic structures. In this paper, we present an efficient approach to cyclic reference counting, consisting of two key components. The first is a coarse-grained cycle collection algorithm that essentially performs a coarser (lightweight) analysis of the computation graph and thus greatly reduces the tracing cost (in comparison with the algorithms based on trial deletion to detect cycles). Our new cycle collector relies on this algorithm to obtain efficiency. Second, a predefined backup algorithm is incorporated to eliminate a theoretical problem that appears in the coarse-grained algorithm, thereby making the collector more practical. In this regard, we develop a heuristic based on the runtime behavior of the cycle collection to help the collector determine when to trigger the backup one. We have implemented and evaluated the proposed cycle collector on the Jikes RVM, where the SPECjvm98 benchmarks were applied. The results demonstrate that the novel approach is efficient and practical, compared to a modern cycle collector based on trial deletion.

Original languageEnglish
Pages (from-to)1-10
Number of pages10
JournalInformation Processing Letters
Volume111
Issue number1
DOIs
Publication statusPublished - 2010 Dec 15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'An efficient approach to cyclic reference counting based on a coarse-grained search'. Together they form a unique fingerprint.

Cite this