The mapping collector: virtual memory support for generational, parallel, and concurrent compaction
Pages 91 - 102
Abstract
Parallel and concurrent garbage collectors are increasingly employed by managed runtime environments (MREs) to maintain scalability, as multi-core architectures and multi-threaded applications become pervasive. Moreover, state-of-the-art MREs commonly implement compaction to eliminate heap fragmentation and enable fast linear object allocation.
Our empirical analysis of object demographics reveals that unreachable objects in the heap tend to form clusters large enough to be effectively managed at the granularity of virtual memory pages. Even though processes can manipulate the mapping of the virtual address space through the standard operating system (OS) interface on most platforms, extant parallel/concurrent compactors do not do so to exploit this clustering behavior and instead achieve compaction by performing, relatively expensive, object moving and pointer adjustment.
We introduce the Mapping Collector (MC), which leverages virtual memory operations to reclaim and consolidate free space without moving objects and updating pointers. MC is a nearly-single-phase compactor that is simpler and more efficient than previously reported compactors that comprise two to four phases. Through effective MRE-OS coordination, MC maintains the simplicity of a non-moving collector while providing efficient parallel and concurrent compaction.
We implement both stop-the-world and concurrent MC in a generational garbage collection framework within the open-source HotSpot Java Virtual Machine. Our experimental evaluation using a multiprocessor indicates that MC significantly increases throughput and scalability as well as reduces pause times, relative to state-of-the-art, parallel and concurrent compactors.
Supplementary Material
JPG File (1346294.jpg)
- Download
- 17.90 KB
Slides from the presentation
- Download
- .94 KB
Supplemental material for The mapping collector: virtual memory support for generational, parallel, and concurrent compaction
- Download
- 8.73 MB
Audio only (1346294.mp3)
- Download
- 10.08 MB
Video (1346294.mp4)
- Download
- 139.27 MB
References
[1]
D. Abuaiadh, Y. Ossia, E. Petrank, and U. Silbershtein. An efficient parallel heap compaction algorithm. In the ACM Conference on Object-Oriented Systems, Languages and Applications, 2004.
[2]
A.W. Appel, J.R. Ellis, and K. Li. Real-time concurrent collection on stock multiprocessors. ACM SIGPLAN Notices, 23(7):11--20, 1988.
[3]
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 Transactions on Programming Languages and Systems, 27(6):1097--1146, 2005.
[4]
K. Barabash, Y. Ossia, and E. Petrank. Mostly concurrent garbage collection revisited. In the ACM Conference on Object-Oriented Systems, Languages and Applications, 2003.
[5]
S.M. Blackburn and K.S. McKinley. Ulterior reference counting: Fast garbage collection without a long wait. In the ACM Conference on Object-Oriented Systems, Languages and Applications, 2003.
[6]
H.-J. Boehm. Reducing garbage collector cache misses. In Second International Symposium on Memory Management, ACM SIGPLAN Notices. ACM Press, 2000.
[7]
H.-J. Boehm, A.J. Demers, and S. Shenker. Mostly parallel garbage collection. ACM SIGPLAN Notices, 26(6), 1991.
[8]
H.-J. Boehm and M. Weiser. Garbage collection in an uncooperative environment. Software Practice and Experience, 18(9):807--820, 1988.
[9]
C.J. Cheney. A non-recursive list compacting algorithm. Communications of the ACM, 13(11):677--8, Nov. 1970.
[10]
P. Cheng and G. Blelloch. A parallel, real-time garbage collector. In the ACM Conference on Programming Languages Design and Implementation, 2001.
[11]
J. Cohen and A. Nicolau. Comparison of compacting algorithms for garbage collection. ACM Transactions on Programming Languages and Systems, 5(4):532--553, 1983.
[12]
The DaCapo Benchmark Suite. http://dacapobench.org.
[13]
D. Detlefs, C. Flood, S. Heller, and T. Printezis. Garbage-first garbage collection. In the ACM International Symposium on Memory Management, 2004.
[14]
C. Flood, D. Detlefs, N. Shavit, and C. Zhang. Parallel garbage collection for shared memory multiprocessors. In the USENIX Java Virtual Machine Symposium, 2001.
[15]
C. Grzegorczyk, S. Soman, C. Krintz, and R. Wolski. Isla Vista heap sizing: Using feedback to avoid paging. In the ACM Conference on Code Generation and Optimization, 2007.
[16]
M. Hertz, Y. Feng, and E.D. Berger. Garbage collection without paging. In the ACM Conference on Programming Languages Design and Implementation, 2005.
[17]
A.L. Hosking. Portable, mostly-concurrent and mostly-copying garbage collection for multi-processors. In the ACM International Symposium on Memory Management, 2004.
[18]
HotSpot Virtual Machine Garbage Collection. http://java.sun.com/javase/technologies/hotspot/gc/index.jsp.
[19]
R.E. Jones. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, July 1996.
[20]
H. Kermany and E. Petrank. The Compressor: Concurrent, incremental and parallel compaction. In the ACM Conference on Programming Languages Design and Implementation, 2006.
[21]
D. Lea. A memory allocator, 1997. http://gee.cs.oswego.edu/dl/html/malloc.html.
[22]
Open Source J2SE Implementation. http://openjdk.java.net.
[23]
Y. Ossia, O. Ben-Yitzhak, I. Goft, E.K. Kolodner, V. Leikehman, and A. Owshanko. A parallel, incremental and concurrent GC for servers. In the ACM Conference on Programming Languages Design and Implementation, 2002.
[24]
Y. Ossia, O. Ben-Yitzhak, and M. Segal. Mostly concurrent compaction for mark-sweep GC. In the ACM International Symposium on Memory Management, 2004.
[25]
T. Printezis and D. Detlefs. A generational mostly-concurrent garbage collector. In the ACM International Symposium on Memory Management, 2000.
[26]
R. Rashid, A. Tevanian, M. Young, et al. Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures. In the ACM Conference on Architectural Support for Programming Languages and Operating Systems, 1987.
[27]
N. Sachindran and E. Moss. MarkCopy: Fast copying GC with less space overhead. In the ACM Conference on Object-Oriented Systems, Languages and Applications, 2003.
[28]
K. Sagonas and J. Wilhelmsson. Mark and split. In the ACM International Symposium on Memory Management, 2006.
[29]
P. Sobalvarro. A lifetime-based garbage collector for Lisp systems on general-purpose computers. Technical Report AITR-1417, MIT AI Lab, Feb. 1988.
[30]
The SPEC Benchmarks. http://www.spec.org.
[31]
D.M. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. ACM SIGPLAN Notices, 19(5):157--167, Apr. 1984.
[32]
The VolanoMark Benchmark. http://www.volano.com/benchmarks.html.
[33]
P.R. Wilson, M.S. Johnstone, M. Neely, and D. Boles. Dynamic storage allocation: A survey and critical review. In the International Workshop on Memory Management, 1995.
[34]
T. Yang, E.D. Berger, M. Hertz, S.F. Kaplan, and J.E.B. Moss. Autonomic heap sizing: Taking real memory into account. In the ACM International Symposium on Memory Management, 2004.
[35]
T. Yang, E.D. Berger, S.F. Kaplan, and J.E.B. Moss. CRAMM: Virtual memory support for garbage-collected applications. In the ACM Conference on Operating Systems Design and Implementation, 2006.
[36]
C. Zhang, K. Kelsey, X. Shen, C. Ding, M. Hertz, and M. Ogihara. Program-level adaptive memory management. In the ACM International Symposium on Memory Management, 2006.
Index Terms
- The mapping collector: virtual memory support for generational, parallel, and concurrent compaction
Recommendations
The mapping collector: virtual memory support for generational, parallel, and concurrent compaction
ASPLOS '08Parallel and concurrent garbage collectors are increasingly employed by managed runtime environments (MREs) to maintain scalability, as multi-core architectures and multi-threaded applications become pervasive. Moreover, state-of-the-art MREs commonly ...
The mapping collector: virtual memory support for generational, parallel, and concurrent compaction
ASPLOS '08Parallel and concurrent garbage collectors are increasingly employed by managed runtime environments (MREs) to maintain scalability, as multi-core architectures and multi-threaded applications become pervasive. Moreover, state-of-the-art MREs commonly ...
The mapping collector: virtual memory support for generational, parallel, and concurrent compaction
ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systemsParallel and concurrent garbage collectors are increasingly employed by managed runtime environments (MREs) to maintain scalability, as multi-core architectures and multi-threaded applications become pervasive. Moreover, state-of-the-art MREs commonly ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2008352 pages
Copyright © 2008 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: 01 March 2008
Published in SIGARCH Volume 36, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations20Total Citations
- 1,008Total Downloads
- Downloads (Last 12 months)11
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Dec 2024
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