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

Chin Yang Lin, Ting Wei Hou

研究成果: Article同行評審


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.

頁(從 - 到)1-10
期刊Information Processing Letters
出版狀態Published - 2010 十二月 15

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 訊號處理
  • 資訊系統
  • 電腦科學應用


深入研究「An efficient approach to cyclic reference counting based on a coarse-grained search」主題。共同形成了獨特的指紋。