Concurrent, parallel garbage collection in linear time
Abstract
This paper presents a new concurrent garbage collection algorithm based on two types of reference, strong and weak, to link the graph of objects. Strong references connect the roots to all the nodes in the graph but do not contain cycles. Weak references may, however, contain cycles.
Advantages of this system include: (1) reduced processing, non-trivial garbage collection work is only required when the last strong reference is lost; (2) fewer memory traces to delete objects, a garbage cycle only needs to be traversed twice to be deleted; (3) fewer memory traces to retain objects, since the collector can often prove objects are reachable without fully tracing support cycles to which the objects belong; (4) concurrency, it can run in parallel with a live system without "stopping the world"; (5) parallel, because collection operations in different parts of the memory can proceed at the same time.
Previous variants of this technique required exponential cleanup time, but our algorithm is linear in total time, i.e. any changes in the graph take only O(N) time steps, where N is the number of edges in the affected subgraph (e.g. the subgraph whose strong support is affected by the operations).
References
[1]
URL https://github.com/stevenrbrandt/ MultiThreadBrownbridge.
[2]
D. F. Bacon and V. T. Rajan. Concurrent cycle collection in reference counted systems. In ECOOP, pages 207--235, 2001.
[3]
D. F. Bacon, C. R. Attanasio, H. B. Lee, V. T. Rajan, and S. Smith. Java without the coffee breaks: a nonintrusive multiprocessor garbage collector. SIGPLAN Not., 36(5):92--103, 2001.
[4]
D. F. Bacon, P. Cheng, and V. T. Rajan. A real-time garbage collector with low overhead and consistent utilization. SIGPLAN Not., 38(1): 285--298, 2003.
[5]
K. Barabash, O. Ben-Yitzhak, I. Goft, E. K. Kolodner, V. Leikehman, Y. Ossia, A. Owshanko, and E. Petrank. A parallel, incremental, mostly concurrent garbage collector for servers. ACM Trans. Program. Lang. Syst., 27(6):1097--1146, 2005.
[6]
M. Berzins, J. Luitjens, Q. Meng, T. Harman, C. A. Wight, and J. R. Peterson. Uintah: a scalable framework for hazard analysis. In TG, pages 3.1--3.8, 2010.
[7]
D. G. Bobrow. Managing reentrant structures using reference counts. ACM Trans. Program. Lang. Syst., 2(3):269--273, 1980.
[8]
D. Brownbridge. Cyclic reference counting for combinator machines. In J.-P. Jouannaud, editor, Functional Programming Languages and Computer Architecture, volume 201 of Lecture Notes in Computer Science, pages 273--288. 1985.
[9]
T. W. Christopher. Reference count garbage collection. Software: Practice and Experience, 14(6):503--507, 1984.
[10]
G. E. Collins. A method for overlapping and erasure of lists. Commun. ACM, 3(12):655--657, 1960.
[11]
D. Frampton. Garbage Collection and the Case for High-level Lowlevel Programming. PhD thesis, Australian National University, June 2010.
[12]
D. P. Friedman and D. S. Wise. Reference counting can manage the circular environments of mutual recursion. Inf. Process. Lett., 8(1): 41--45, 1979.
[13]
L. Huelsbergen and P. Winterbottom. Very concurrent mark-&-sweep garbage collection without fine-grain synchronization. SIGPLAN Not., 34(3):166--175, 1998.
[14]
R. Hughes. Managing reduction graphs with reference counts. Departmental Research Report CSC/87/R2, March 1987.
[15]
R. Jones and R. Lins. Garbage collection: algorithms for automatic dynamic memory management. John Wiley & Sons, Inc., New York, NY, USA, 1996. ISBN 0--471--94148--4.
[16]
H. Kaiser, M. Brodowicz, and T. Sterling. Parallex an advanced parallel execution model for scaling-impaired applications. In ICPPW, pages 394--401, 2009.
[17]
L. V. Kale and S. Krishnan. CHARM++: a portable concurrent object oriented system based on C++, volume 28. 1993.
[18]
C. Lauderdale and R. Khan. Towards a codelet-based runtime for exascale computing: position paper. In EXADAPT, pages 21--26, 2012.
[19]
Y. Levanoni and E. Petrank. An on-the-fly reference-counting garbage collector for java. ACM Trans. Program. Lang. Syst., 28(1):1--69, 2006.
[20]
R. D. Lins. Cyclic reference counting with lazy mark-scan. Inf. Process. Lett., 44(4):215--220, 1992.
[21]
R. D. Lins. An efficient algorithm for cyclic reference counting. Inf. Process. Lett., 83(3):145--150, 2002.
[22]
R. D. Lins. Cyclic reference counting. Inf. Process. Lett., 109(1):71--78, 2008.
[23]
J. H. McBeth. Letters to the editor: on the reference counter method. Commun. ACM, 6(9):575, 1963.
[24]
J. McCarthy. Recursive functions of symbolic expressions and their computation by machine, part i. Commun. ACM, 3(4):184--195, 1960.
[25]
J. Nieplocha, R. J. Harrison, and R. J. Littlefield. Global arrays: A portable shared-memory programming model for distributed memory computers. In SC, pages 340--349, 1994.
[26]
H. Paz, D. F. Bacon, E. K. Kolodner, E. Petrank, and V. T. Rajan. An efficient on-the-fly cycle collection. ACM Trans. Program. Lang. Syst., 29(4), 2007.
[27]
E. Pepels, M. Plasmeijer, C. van Eekelen, and M. Eekelen. A Cyclic Reference Counting Algorithm and Its Proof. Internal report 88--10. Department of Informatics, Faculty of Science, University of Nijmegen, 1988.
[28]
F. Pizlo, E. Petrank, and B. Steensgaard. A study of concurrent realtime garbage collectors. SIGPLAN Not., 43(6):33--44, 2008.
[29]
T. Printezis and D. Detlefs. A generational mostly-concurrent garbage collector. SIGPLAN Not., 36(1):143--154, 2000.
[30]
P. Roy, S. Seshadri, A. Silberschatz, S. Sudarshan, and S. Ashwin. Garbage collection in object-oriented databases using transactional cyclic reference counting. The VLDB Journal, 7(3):179--193, 1998.
[31]
J. Salkild. Implementation and analysis of two reference counting algorithms. Master thesis, University College, London, 1987.
[32]
R. Shahriyar, S. M. Blackburn, and D. Frampton. Down for the count' getting reference counting back in the ring. In ISMM, pages 73--84, 2012.
[33]
L. Veiga and P. Ferreira. Asynchronous complete distributed garbag collection. In IPDPS, pages 24.1--24.10, 2005.
Index Terms
- Concurrent, parallel garbage collection in linear time
Recommendations
Concurrent, parallel garbage collection in linear time
ISMM '14: Proceedings of the 2014 international symposium on Memory managementThis paper presents a new concurrent garbage collection algorithm based on two types of reference, strong and weak, to link the graph of objects. Strong references connect the roots to all the nodes in the graph but do not contain cycles. Weak ...
Concurrent, parallel, real-time garbage-collection
ISMM '10With the current developments in CPU implementations, it becomes obvious that ever more parallel multicore systems will be used even in embedded controllers that require real-time guarantees. When garbage collection is used in these systems, parallel ...
Concurrent, parallel, real-time garbage-collection
ISMM '10: Proceedings of the 2010 international symposium on Memory managementWith the current developments in CPU implementations, it becomes obvious that ever more parallel multicore systems will be used even in embedded controllers that require real-time guarantees. When garbage collection is used in these systems, parallel ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2014
121 pages
June 2014136 pages
Copyright © 2014 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 June 2014
Published in SIGPLAN Volume 49, Issue 11
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations3Total Citations
- 417Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)1
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in