More Web Proxy on the site http://driver.im/

research-article

Concurrent, parallel garbage collection in linear time

Authors:

Steven R. Brandt,

Gokarna Sharma,

Costas BuschAuthors Info & Claims

ISMM '14: Proceedings of the 2014 international symposium on Memory management

Pages 47 - 58

https://doi.org/10.1145/2602988.2602990

Published: 12 June 2014 Publication History

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[7]

D. G. Bobrow. Managing reentrant structures using reference counts. ACM Trans. Program. Lang. Syst., 2(3):269--273, 1980.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[16]

H. Kaiser, M. Brodowicz, and T. Sterling. Parallex an advanced parallel execution model for scaling-impaired applications. In ICPPW, pages 394--401, 2009.

Digital Library

[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.

Digital Library

[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.

Digital Library

[20]

R. D. Lins. Cyclic reference counting with lazy mark-scan. Inf. Process. Lett., 44(4):215--220, 1992.

Digital Library

[21]

R. D. Lins. An efficient algorithm for cyclic reference counting. Inf. Process. Lett., 83(3):145--150, 2002.

Digital Library

[22]

R. D. Lins. Cyclic reference counting. Inf. Process. Lett., 109(1):71--78, 2008.

Digital Library

[23]

J. H. McBeth. Letters to the editor: on the reference counter method. Commun. ACM, 6(9):575, 1963.

Digital Library

[24]

J. McCarthy. Recursive functions of symbolic expressions and their computation by machine, part i. Commun. ACM, 3(4):184--195, 1960.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[29]

T. Printezis and D. Detlefs. A generational mostly-concurrent garbage collector. SIGPLAN Not., 36(1):143--154, 2000.

Digital Library

[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.

Digital Library

[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.

Digital Library

[33]

L. Veiga and P. Ferreira. Asynchronous complete distributed garbag collection. In IPDPS, pages 24.1--24.10, 2005.

Digital Library

Cited By

Brandt SKrishnan HBusch CSharma G(2018)Distributed garbage collection for general graphsACM SIGPLAN Notices10.1145/3299706.321057253:5(29-44)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3299706.3210572
Brandt SKrishnan HBusch CSharma GPayer HSartor J(2018)Distributed garbage collection for general graphsProceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management10.1145/3210563.3210572(29-44)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3210563.3210572
Bai JWang YLiu HHu S(2015)Automated resource release in device driversProceedings of the 2015 IEEE 26th International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE.2015.7381811(172-182)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.1109/ISSRE.2015.7381811

Index Terms

Concurrent, parallel garbage collection in linear time
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Concurrent, parallel garbage collection in linear time
ISMM '14

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 ...
Concurrent, parallel, real-time garbage-collection
ISMM '10

With 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 management

With 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

cover image ACM Conferences

ISMM '14: Proceedings of the 2014 international symposium on Memory management

June 2014

136 pages

ISBN:9781450329217

DOI:10.1145/2602988

General Chair:
David Grove
IBM Research, USA
,
Program Chair:
Samuel Z. Guyer
Tufts University, USA

ACM SIGPLAN Notices Volume 49, Issue 11
ISMM '14
November 2014
121 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2775049
Editor:
Andy Gill
University of Kansas, Lawrence, KS
Issue’s Table of Contents

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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ISMM '14

Sponsor:

SIGPLAN

ISMM '14: International Symposium on Memory Management

June 12, 2014

Edinburgh, United Kingdom

Acceptance Rates

ISMM '14 Paper Acceptance Rate 11 of 22 submissions, 50%;

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
417
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Brandt SKrishnan HBusch CSharma G(2018)Distributed garbage collection for general graphsACM SIGPLAN Notices10.1145/3299706.321057253:5(29-44)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3299706.3210572
Brandt SKrishnan HBusch CSharma GPayer HSartor J(2018)Distributed garbage collection for general graphsProceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management10.1145/3210563.3210572(29-44)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3210563.3210572
Bai JWang YLiu HHu S(2015)Automated resource release in device driversProceedings of the 2015 IEEE 26th International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE.2015.7381811(172-182)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.1109/ISSRE.2015.7381811

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten