Abstract
A reference-counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference-counting collectors either use a backup tracing collector infrequently, or employ a cycle collector to reclaim cyclic structures. We propose a new concurrent cycle collector, i.e., one that runs concurrently with the program threads, imposing negligible pauses (of around 1ms) on a multiprocessor.
Our new collector combines the state-of-the-art cycle collector [5] with the sliding-views collectors [20, 2]. The use of sliding views for cycle collection yields two advantages. First, it drastically reduces the number of cycle candidates, which in turn, drastically reduces the work required to record and trace these candidates. Therefore, a large improvement in cycle collection efficiency is obtained. Second, it eliminates the theoretical termination problem that appeared in the previous concurrent cycle collector. There, a rare race may delay the reclamation of an unreachable cyclic structure forever. The sliding-views cycle collector guarantees reclamation of all unreachable cyclic structures.
The proposed collector was implemented on the Jikes RVM and we provide measurements including a comparison between the use of backup tracing and the use of cycle collection with reference counting. To the best of our knowledge, such a comparison has not been reported before.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alpern, B., Attanasio, C.R., Cocchi, A., Lieber, D., Smith, S., Ngo, T., Barton, J.J., Hummel, S.F., Sheperd, J.C., Mergen, M.: Implementing Jalapeño in Java. In: OOPSLA 1999 ACM Conference on Object-Oriented Systems, Languages and Applications. ACM SIGPLAN Notices, vol. 34(10), pp. 314–324 (1999)
Azatchi, H., Levanoni, Y., Paz, H., Petrank, E.: An on-the-fly mark and sweep garbage collector based on sliding view. In: OOPSLA [25]
Azatchi, H., Petrank, E.: Integrating generations with advanced reference counting garbage collectors. In: Hedin, G. (ed.) CC 2003. LNCS, vol. 2622, pp. 185–199. Springer, Heidelberg (2003)
Bacon, D.F., Attanasio, C.R., Lee, H.B., Rajan, V.T., Smith, S.: Java without the coffee breaks: A nonintrusive multiprocessor garbage collector. In: Proceedings of SIGPLAN 2001 Conference on Programming Languages Design and Implementation, Snowbird, Utah. ACM SIGPLAN Notices (June 2001)
Bacon, D.F., Rajan, V.T.: Concurrent cycle collection in reference counted systems. In: Knudsen, J.L. (ed.) ECOOP 2001. LNCS, vol. 2072, p. 207. Springer, Heidelberg (2001)
Baker, H.G.: List processing in real-time on a serial computer. Communications of the ACM 21(4), 280–294 (1978); Also AI Laboratory Working Paper 139, 1977
Blackburn, S.M., McKinley, K.S.: Ulterior reference counting: Fast garbage collection without a long wait. In: OOPSLA [25]
Bobrow, D.G.: Managing re-entrant structures using reference counts. ACM Transactions on Programming Languages and Systems 2(3), 269–273 (1980)
Boehm, H.-J., Demers, A.J., Shenker, S.: Mostly parallel garbage collection. ACM SIGPLAN Notices 26(6), 157–164 (1991)
Christopher, T.W.: Reference count garbage collection. Software Practice and Experience 14(6), 503–507 (1984)
Collins, G.E.: A method for overlapping and erasure of lists. Communications of the ACM 3(12), 655–657 (1960)
Dijkstra, E.W., Lamport, L., Martin, A.J., Scholten, C.S., Steffens, E.F.M.: On-the-fly garbage collection: An exercise in cooperation. Communications of the ACM 21(11), 965–975 (1978)
Domani, T., Kolodner, E., Petrank, E.: A generational on-the-fly garbage collector for Java. In: Proceedings of SIGPLAN 2000 Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices, Vancouver (June 2000)
Endo, T., Taura, K., Yonezawa, A.: A scalable mark-sweep garbage collector on large-scale shared-memory machines. In: Proceedings of High Performance Computing and Networking, SC 1997 (1997)
Flood, C., Detlefs, D., Shavit, N., Zhang, C.: Parallel garbage collection for shared memory multiprocessors. In: Usenix Java Virtual Machine Research and Technology Symposium (JVM 2001), Monterey, CA (April 2001)
Hosking, T. (ed.): ISMM 2000 Proceedings of the Second International Symposium on Memory Management ACM SIGPLAN Notices, vol. 36(1) (2000)
Hudson, R.L., Moss, J.E.B.: Sapphire: Copying GC without stopping the world. In: Joint ACM Java Grande — ISCOPE 2001 Conference, Stanford University, CA (2001)
Kolodner, E.K., Petrank, E.: Parallel copying garbage collection using delayed allocation. Parallel Processing Letters 14 (June 2004)
Levanoni, Y., Petrank, E.: A scalable reference counting garbage collector. Technical Report CS–0967, Technion — Israel Institute of Technology, Haifa, Israel (November 1999)
Levanoni, Y., Petrank, E.: An on-the-fly reference counting garbage collector for Java. In: OOPSLA 2001 ACM Conference on Object-Oriented Systems, Languages and Applications, Tampa, FL. ACM SIGPLAN Notices, vol. 36(10) (October 2001)
Lins, R.D.: Cyclic reference counting with lazy mark-scan. IPL 44(4), 215–220 (1992)
Lins, R.D.: An efficient algorithm for cyclic reference counting. IPL 83, 145–150 (2002)
Martinez, A.D., Wachenchauzer, R., Lins, R.D.: Cyclic reference counting with local mark-scan. Information Processing Letters 34, 31–35 (1990)
Harold McBeth, J.: On the reference counter method. CACM 6(9), 575 (1963)
OOPSLA 2003 ACM Conference on Object-Oriented Systems, Languages and Applications, ACM SIGPLAN Notices, Anaheim, CA (November 2003)
Paz, H., Bacon, D.F., Kolodner, E.K., Petrank, E., Rajan, V.T.: Efficient on-the-fly cycle collection. Technical Report CS–2003–10, Technion (2003)
Paz, H., Petrank, E., Blackburn, S.M.: Age-Oriented Concurrent Garbage Collection. In: Proceedings of the 14th Int. Conference on Compiler Construction (2005)
Printezis, T., Detlefs, D.: A generational mostly-concurrent garbage collector. In: Hosking [16]
SPEC Benchmarks. Standard Performance Evaluation Corporation (1998, 2000), http://www.spec.org/
Steele., G.L.: Multiprocessing compactifying garbage collection. Communications of the ACM 18(9), 495–508 (1975)
Steele, G.L.: Corrigendum: Multiprocessing compactifying garbage collection. Communications of the ACM 19(6), 354 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Paz, H., Petrank, E., Bacon, D.F., Kolodner, E.K., Rajan, V.T. (2005). An Efficient On-the-Fly Cycle Collection. In: Bodik, R. (eds) Compiler Construction. CC 2005. Lecture Notes in Computer Science, vol 3443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31985-6_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-31985-6_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25411-9
Online ISBN: 978-3-540-31985-6
eBook Packages: Computer ScienceComputer Science (R0)