無法有效回收環狀垃圾(cyclic garbage)是參考計數式垃圾回收演算法(reference counting)的主要缺點。在支援參考計數之記憶體管理系統上，此問題有兩種普遍解法：(1) 整合基於追蹤法的全域型回收器(global tracing collector); (2) 採用基於追蹤法的區域型回收器(local tracing collector)。由於後者通常只需面對局部的物件而非整個堆積區(Heap)的物件，因此擴充性佳; 加上現今堆積區的空間普遍增加的趨勢，區域型回收器的優勢將逐漸明顯。
目前基於區域型回收器的相關研究幾乎都採用傳統的追蹤機制(稱為trial deletion)，由於此機制的運作一般需要追蹤(存取)物件三次，導致了許多額外的運算負擔; 儘管許多相關研究著眼於減少需要分析的物件數目來改善效能，卻鮮少有研究訴諸於回收環狀垃圾的演算法本身。
此研究提出一個適用於參考計數式記憶體管理系統之高效率環狀垃圾回收法，這包含一個新穎的環狀垃圾回收演算法，該演算法能以更簡單有效的方式來處理環狀垃圾(在此稱為輕量級演算法); 而關鍵在於此演算法降低了追蹤物件的次數。相較於傳統偵測環狀垃圾的方法，此方法只需追蹤物件一次，偵測環狀垃圾的複雜度因而從3O(n)降至O(n)。
此研究更針對如何增加該輕量級演算法的效率與實用性，提出兩個改善方法：(1) 透過演算程序與資料結構的改進，解決原演算法的最壞情況(worst case)，進而降低運算負擔; (2) 利用基於經驗式(heuristic)的混合演算法來解決輕量級演算法一個理論上的缺點，進而改善了整體效能。此外，相關的演算法虛擬碼以及其證明都被詳細陳述於此論文中。
為驗證在此所提之方法，此論文包括了一系列基於Jike虛擬機器 (Jikes Research Virtual Machine)以及SPECjvm98效能評估程式的實驗; 所有結果皆與另一個高效能的環狀垃圾回收器進行比較。根據實驗的結果，新提出之方法可改善約6–7%的整體程式執行時間，而且確實可有效解決真實應用程式的環狀垃圾問題。

The inability to collect cyclic garbage is generally considered the major weakness of reference counting. Reference counted systems handle this problem by incorporating either a global tracing collector or a local tracing collector that considers only the cycle candidates (i.e. objects that may contain cyclic garbage). Particularly, the latter has become a preferred one as it has better scalability and locality (i.e., there is no need to scan the entire heap).
Most of the local tracing collectors so far are based on a classical tracing scheme, called trial deletion. This scheme essentially requires three traversals over objects and thus may incur more tracing overhead and lower the potential for further developments. Lots of works have focused on improving the tracing cost by reducing the scope of cycle candidates, but few studies resort to the cycle collection procedure itself.
This research presents an efficient cyclic garbage reclamation approach for reference counted memory management systems. It includes a novel cycle collection algorithm, which is a local tracing algorithm but deals with the cycle problem in a simpler and more efficient way. The key is to minimize the number of traces over the cycle candidates; it can detect garbage cycles in a single traversal over objects, thereby significantly reducing the complexity from 3O(n) to O(n).
In addition, two further enhancements of the proposed algorithm are presented. The first introduces a data structure to increase the efficiency, solving the worst case of the proposed algorithm. The second is a heuristic-based hybrid approach for enhancing the practicability of the proposed algorithm. It not only addresses a theoretical problem of the algorithm, but also significantly improves the overall efficiency. Moreover, the pseudo-code of the algorithms and the correctness proofs are described in detail.
To evaluate the effectiveness of all of these methods, a set of experiments are conducted based on Jikes Research Virtual Machine and SPECjvm98 benchmarks. The results show that this approach can cope with the cycle problem for large programs and attain better application performance on average around 6–7% faster, when compared to a modern state-of-the-art cycle collector based on the trial deletion.

[1] Bowen Alpern, C. R. Attanasio, Anthony Cocchi, Derek Lieber, Stephen Smith, Ton Ngo, John J. Barton, Susan Flynn Hummel, Janice C. Sheperd, Mark Mergen, “Implementing Jalape˜no in Java,” Proc. of the ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, 1999, pp. 314-324.
[2] Hezi Azatchi, Erez Petrank, “Integrating generations with advanced reference counting garbage collectors,” Proc. of the 12th International Conference on Compiler Construction, Springer Verlag, LNCS 2622, 2003, pp. 185-199.
[3] David F. Bacon, Clement R. Attanasio, Han B. Lee, V. T. Rajan, Stephen Smith, “Java without the Coffee Breaks: A nonintrusive multiprocessor garbage collector,” Proc. of the SIGPLAN Conference on Programming Language Design and Implementation, 2001, pp. 92-103.
[4] David F. Bacon, V. T. Rajan, “Concurrent cycle collection in reference counted systems,” Proc. of European Conf. on Object-Oriented Programming, Springer Verlag, LNCS 2072, 2001, pp. 207-235.
[5] Stephen M. Blackburn, Perry Cheng, Kathryn S. McKinley, “Oil and water?High performance garbage collection in Java with MMTk,” Proc. of the 26th International Conference on Software Engineering, 2004, pp. 137-146.
[6] Stephen M. Blackburn, Kathryn S. McKinley, “Ulterior reference counting: Fast garbage collection without a long wait,” Proc. of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Anaheim, CA, Oct. 2003, pp. 244-358.
[7] Daniel G. Bobrow, “Managing re-entrant structures using reference counts,” ACM Trans. Program. Lang. Syst. 2 (3) (1980) 269-273.
[8] D. R. Brownbridge, “Cyclic reference counting for combinator machines,” In Functional Programming Languages and Computer Architecture, Springer Verlag, LNCS 201, 1985, pp. 273-288.
[9] T. W. Christopher, “Reference count garbage collection,” Software Practice and Experience, 14 (6) (1984) 503-507.
[10] George E. Collins, “A method for overlapping and erasure of lists,” Comm. ACM 3 (12) (1960) 655-657.
[11] John Detreville, “Experience with concurrent garbage collectors for Modula-2+. Tech. Rep. 64,” DEC Systems Research Center, 1990.
[12] L. Peter Deutsch, Daniel G. Bobrow, “An efficient incremental automatic garbage collector,” Comm. ACM 19 (9) (1976) 522-526.
[13] Sylvia Dieckmann, Urs Hölzle, “A study of the allocation behavior of the SPECjvm98 Java benchmarks,” Proc. of the 13th European Conference on Object-Oriented Programming (ECOOP’99), Springer Verlag, LNCS 1628, 1999, pp. 92-115.
[14] Edsger W. Djikstra, Leslie Lamport, A. J. Martin, C. S. Scholten, E. F. M. Steffens, “On-the-Fly Garbage Collection: An Exercise in Cooperation,” Comm. ACM 21 (11) (1978) 965-975.
[15] Daniel P. Friedman, David S. Wise, “Reference counting can manage the circular environments of mutual recursion,” Inform. Process. Lett. 8 (1979) 41-45.
[16] Ting-Wei Hou, Chin-Yang Lin, Tien-Yan Ma, “A single-trace cycle collection for reference counting systems,” Proc. of the 10th International Symposium on Pervasive Systems, Algorithms and Networks (I-SPAN 2009), Dec. 2009. (accepted)
[17] R. John, M. Hughes, “Managing reduction graphs with reference counts,” Departmental Research Report CSC/87/R2, University of Glasgow, March 1987.
[18] Richard E. Jones, Rafael D. Lins, “Cyclic weighted reference counting without delay,” Proc. of PARLE'93, Springer Verlag, LNCS 694, 1993, pp. 512-515.
[19] Richard E. Jones, Rafael D. Lins, Garbage Collection: Algorithms for Automatic Dynamic Memory Management, John Wiley & Sons, New York, 1996.
[20] Bernard Lang, Francis Dupont, “Incremental incrementally compacting garbage collection,” ACM SIGPLAN Notices 22 (7) (1987) 253-263.
[21] Yossi Levanoni, Erez Petrank, “A scalable reference counting garbage collector,” Technical Report CS-0967, Technion - Israel Institute of Technology, Haifa, Israel, November 1999.
[22] Yossi Levanoni, Erez Petrank, “An on-the-fly reference counting garbage collector for Java,” ACM Trans. Program. Lang. Syst. 28 (1) (2006) 1-69.
[23] Chin-Yang Lin, Ting-Wei Hou, “A lightweight cyclic reference counting algorithm,” Proc. of the International Conference on Grid and Pervasive Computing, Springer Verlag, LNCS 3947, 2006, pp. 346-359.
[24] Chin-Yang Lin, Ting-Wei Hou, “A simple and efficient algorithm for cycle collection,” ACM SIGPLAN Notices 42 (3) (2007) 7-13.
[25] Chin-Yang Lin, Ting-Wei Hou, “An efficient approach to cyclic reference counting based on a coarse-grained search,” Submitted to Information Processing Letters. (work in progress since 2008)
[26] Rafael D. Lins, “Cyclic Reference counting with lazy mark-scan,” Inform. Process. Lett. 44 (1992) 215-220.
[27] Rafael D. Lins, “Generational cyclic reference counting,” Inform. Process. Lett. 46 (1993) 19-20.
[28] Rafael D. Lins, “An efficient algorithm for cyclic reference counting,” Inform. Process. Lett. 83 (2002) 145-150.
[29] Rafael D. Lins, Richard E. Jones, “Cyclic weighted reference counting,” in:K. Boyanov (Ed.), Proc. of the International Workshop on Parallel and Distributed Processing, NH, May 1993, pp. 369-382.
[30] Rafael D. Lins, Francisco Heron de Carvalho Junior, Zanoni Dueire Lins, “Cyclic reference counting with permanent objects,” J. Univers. Comput. Sci. 13 (6) (2007) 830-838.
[31] Chia-Tien Dan Lo, Witawas Srisa-an, J. Morris Chang, “Who is collecting your Java garbage?,” IEEE IT Professional 5 (2) (2003) 44-50.
[32] Munenori Maeda, Hiroki Konaka, Yutaka Ishikawa, Takashi Tomokiyo, Atsushi Hori, Jörg Nolte, “On-the-fly global garbage collection based on partly mark-sweep,” Springer Verlag, LNCS 986, 1995, pp. 283-296.
[33] A.D. Martinez, R. Wachenchauzer, Rafael D. Lins, “Cyclic reference counting with local mark-scan,” Inform. Process. Lett. 34 (1990) 31-35.
[34] J. Harold McBeth, “On the reference counter method,” Comm. ACM 6 (9) (1963) 575.
[35] John McCarthy, “Recursive functions of symbolic expressions and their computation by machine,” Comm. ACM 3 (1960) 184-195.
[36] Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, V. T. Rajan, “An efficient on-the-fly cycle collection,” ACM Trans. Program. Lang. Syst. 29 (4):20, 2007.
[37] Harel Paz, Erez Petrank, “Using Prefetching to Improve Reference- Counting Garbage Collectors,” Proc. of the 16th International Conference on Compiler Construction, Springer Verlag, LNCS 4420, 2007, pp. 48-63.
[38] Harel Paz, Erez Petrank, David F. Bacon, V. T. Rajan, Elliot K. Kolodner, “Efficient on-the-fly cycle collection,” Proc. of the 14th International Conference on Compiler Construction, Springer Verlag, LNCS 3443, 2005, pp. 156-171.
[39] Harel Paz, Erez Petrank, Stephen M. Blackburn, “Age-Oriented Concurrent Garbage Collection,” Proc. of the 14th International Conference on Compiler Construction, Springer Verlag, LNCS 3443, 2005, pp. 121-136.
[40] E. J. H. Pepels, M. C. J. D. van Eekelen, M. J. Plasmeijer, “A cyclic reference counting algorithm and its proof,” Internal Rept. 88-10, University of Nijmegen, Nijmegen, 1988.
[41] Jon D. Salkild, “Implementation and analysis of two reference counting algorithms,” Master Thesis, University College, London, 1987.
[42] Standard Performance Evaluation Corporation, SPECjvm98 Documentation, Release 1.03, March, 1999. (Online version at http://www.spec.org/osg/jvm98/)
[43] Paul Watson, Ian Watson, “An efficient garbage collection scheme for parallel computer architecture,” Parallel Architectures and Languages Europe (PARLE’87), Springer Verlag, LNCS 259, June 1987, pp. 432-443.
[44] Xinfeng Ye, John Keane, “Collecting cyclic garbage in distributed systems,” In International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'97), Taipei, Taiwan, December 1997, pp. 227-231.