Article

An algorithm for parallel incremental compaction

Authors:

Victor LeikehmanAuthors Info & Claims

ISMM '02: Proceedings of the 3rd international symposium on Memory management

Pages 100 - 105

https://doi.org/10.1145/512429.512442

Published: 20 June 2002 Publication History

Get Access

Abstract

Garbage collectors of the mark-sweep family may suffer from memory fragmentation and require the use of compaction. Known compaction methods are expensive and work while program activity is stopped, so that compaction is often a major contributor to garbage collection pause times. We present a parallel incremental compaction algorithm that reduces pause times by working in parallel and evacuating a part of the heap when the program threads are stopped for garbage collection. Our algorithm works with collectors based on mark-sweep, including mostly concurrent collectors. We have implemented a prototype of our algorithm as part of the garbage collector in the IBM JVM. Measurements of our prototype show that even with the most simple-minded policies, e.g., for choosing the area to evacuate, parallel incremental compaction can successfully reduce maximum garbage collection pause times with a minimal performance penalty.

References

[1]

David F. Bacon, Ravi Konuru, Chet Murthy, and Mauricio Serrano. Thin locks: Featherweight synchronization for java. In Proceedings of SIGPLAN'98 Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices, pages 258--268, Montreal, June 1998. ACM Press

Digital Library

Google Scholar

[2]

Hans-Juergen Boehm, Alan J. Demers, and Scott Shenker. Mostly parallel garbage collection. ACM SIGPLAN Notices, 26(6):157--164, 1991

Digital Library

Google Scholar

[3]

Robert Dimpsey, Rajiv Arora, and Kean Kuiper. Java server performance: A case study of building efficient, scalable Jvms. IBM System Journal, 39(1):151--174, 2000

Digital Library

Google Scholar

[4]

Christine Flood, Dave Detlefs, Nir Shavit, and Catherine Zhang. Parallel garbage collection for shared memory multiprocessors. In Usenix Java Virtual Machine Research and Technology Symposium (JVM '01), Monterey, CA, April 2001

Digital Library

Google Scholar

[5]

Z/Architecture Principles of Operation (SA22-7832-01). Appendix A, 2000. Available at www.ibm.com

Google Scholar

[6]

Richard E. Jones. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, July 1996. With a chapter on Distributed Garbage Collection by R. Lins

Digital Library

Google Scholar

[7]

H. B. M. Jonkers. A fast garbage compaction algorithm. Information Processing Letters, 9(1):25--30, July 1979

Crossref

Google Scholar

[8]

Bernard Lang and Francis Dupont. Incremental incrementally compacting garbage collection. In SIGPLAN'87 Symposium on Interpreters and Interpretive Techniques, volume 22(7) of ACM SIGPLAN Notices, pages 253--263. ACM Press, 1987

Digital Library

Google Scholar

[9]

Martin Larose and Marc Feeley. A compacting incremental collector and its performance in a production quality compiler. In Richard Jones, editor, ISMM'98 Proceedings of the First International Symposium on Memory Management, volume 34(3) of ACM SIGPLAN Notices, pages 1--9, Vancouver, October 1998. ACM Press. ISMM is the successor to the IWMM series of workshops

Digital Library

Google Scholar

[10]

F. Lockwood Morris. A time- and space-efficient garbage compaction algorithm. Communications of the ACM, 21(8):662--5, 1978

Digital Library

Google Scholar

[11]

Yoav Ossia, Ori Ben-Yitzhak, Irit Goft, Elliot K. Kolodner, Victor Leikehman, and Avi Owshanko. A parallel, incremental and concurrent gc for servers. In Proceedings of SIGPLAN 2002 Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices, Berlin, June 2002. ACM Press

Digital Library

Google Scholar

[12]

Tony Printezis and David Detlefs. A generational mostly-concurrent garbage collector. In ISMM 2000 Proceedings of the Second International Symposium on Memory Management, volume 36(1) of ACM SIGPLAN Notices, Minneapolis, MN, October 2000. ACM Press

Digital Library

Google Scholar

[13]

Standard Performance Evaluation Corporation. Available at www.spec.org

Google Scholar

Cited By

View all

Cory TPetrank EBond MLee JPayer H(2024)The One Pass (OP) Compactor: An Intellectual AbstractProceedings of the 2024 ACM SIGPLAN International Symposium on Memory Management10.1145/3652024.3665513(108-120)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652024.3665513
Gamari BDietz LDing CMaas M(2020)Alligator collector: a latency-optimized garbage collector for functional programming languagesProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management10.1145/3381898.3397214(87-99)Online publication date: 16-Jun-2020
https://dl.acm.org/doi/10.1145/3381898.3397214
Cohen NPetrank E(2017)Limitations of Partial CompactionACM Transactions on Programming Languages and Systems10.1145/299459739:1(1-44)Online publication date: 6-Mar-2017
https://dl.acm.org/doi/10.1145/2994597
Show More Cited By

Index Terms

An algorithm for parallel incremental compaction
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

An algorithm for parallel incremental compaction
MSP 2002 and ISMM 2002

Garbage collectors of the mark-sweep family may suffer from memory fragmentation and require the use of compaction. Known compaction methods are expensive and work while program activity is stopped, so that compaction is often a major contributor to ...
A parallel, incremental and concurrent GC for servers
PLDI '02: Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementation

Multithreaded applications with multi-gigabyte heaps running on modern servers provide new challenges for garbage collection (GC). The challenges for "server-oriented" GC include: ensuring short pause times on a multi-gigabyte heap, while minimizing ...
A parallel, incremental and concurrent GC for servers

Multithreaded applications with multi-gigabyte heaps running on modern servers provide new challenges for garbage collection (GC). The challenges for "server-oriented" GC include: ensuring short pause times on a multi-gigabyte heap, while minimizing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISMM '02: Proceedings of the 3rd international symposium on Memory management

June 2002

192 pages

ISBN:1581135394

DOI:10.1145/512429

General Chair:
Hans-J. Boehm
Hewlett-Packard Labs, USA
,
Program Chair:
David Detlefs
Sun Microsystems Labs, USA

ACM SIGPLAN Notices Volume 38, Issue 2 supplement
MSP 2002 and ISMM 2002
February 2003
291 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/773039
Issue’s Table of Contents

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: 20 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISMM02

Sponsor:

SIGPLAN

ISMM02: 2002 International Symposium on Memory Management ( co-located with PLDI 2002 )

June 20 - 21, 2002

Berlin, Germany

Acceptance Rates

ISMM '02 Paper Acceptance Rate 17 of 41 submissions, 41%;

Overall Acceptance Rate 72 of 156 submissions, 46%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
514
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cory TPetrank EBond MLee JPayer H(2024)The One Pass (OP) Compactor: An Intellectual AbstractProceedings of the 2024 ACM SIGPLAN International Symposium on Memory Management10.1145/3652024.3665513(108-120)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652024.3665513
Gamari BDietz LDing CMaas M(2020)Alligator collector: a latency-optimized garbage collector for functional programming languagesProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management10.1145/3381898.3397214(87-99)Online publication date: 16-Jun-2020
https://dl.acm.org/doi/10.1145/3381898.3397214
Cohen NPetrank E(2017)Limitations of Partial CompactionACM Transactions on Programming Languages and Systems10.1145/299459739:1(1-44)Online publication date: 6-Mar-2017
https://dl.acm.org/doi/10.1145/2994597
Degenbaev UEisinger JErnst MMcIlroy RPayer H(2016)Idle time garbage collection schedulingACM SIGPLAN Notices10.1145/2980983.290810651:6(570-583)Online publication date: 2-Jun-2016
https://dl.acm.org/doi/10.1145/2980983.2908106
Degenbaev UEisinger JErnst MMcIlroy RPayer HKrintz CBerger E(2016)Idle time garbage collection schedulingProceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2908080.2908106(570-583)Online publication date: 2-Jun-2016
https://dl.acm.org/doi/10.1145/2908080.2908106
Bacon DCheng PRajan V(2013)POPL 2003ACM SIGPLAN Notices10.1145/2502508.250252348:4S(58-71)Online publication date: 9-Jul-2013
https://dl.acm.org/doi/10.1145/2502508.2502523
Cohen NPetrank E(2013)Limitations of partial compactionACM SIGPLAN Notices10.1145/2499370.249197348:6(309-320)Online publication date: 16-Jun-2013
https://dl.acm.org/doi/10.1145/2499370.2491973
Cohen NPetrank EBoehm HFlanagan C(2013)Limitations of partial compactionProceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2491956.2491973(309-320)Online publication date: 16-Jun-2013
https://dl.acm.org/doi/10.1145/2491956.2491973
Klock FClinger W(2011)Bounded-latency regional garbage collectionACM SIGPLAN Notices10.1145/2168696.204785947:2(73-84)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1145/2168696.2047859
Schatzl TDaynès LMössenböck HProbst CWimmer C(2011)Optimized memory management for class metadata in a JVMProceedings of the 9th International Conference on Principles and Practice of Programming in Java10.1145/2093157.2093182(151-160)Online publication date: 24-Aug-2011
https://dl.acm.org/doi/10.1145/2093157.2093182
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

An algorithm for parallel incremental compaction

A parallel, incremental and concurrent GC for servers

A parallel, incremental and concurrent GC for servers