skip to main content
10.1145/1133956.1133963acmconferencesArticle/Chapter ViewAbstractPublication PagesismmConference Proceedingsconference-collections
Article

Portable, mostly-concurrent, mostly-copying garbage collection for multi-processors

Published: 10 June 2006 Publication History

Abstract

Modern commodity platforms increasingly support thread-level parallelism, which must be exploited by garbage collected applications. We describe the design and implementation of a portable mostly-concurrent mostly-copying garbage collector that exhibits scalable performance on multi-processors. We characterize its performance for heap-intensive workloads on two different multi-processor platforms, showing maximum pause times two orders of magnitude shorter than for fully stop-the-world collection at the cost of some total mutator throughput.

References

[1]
APPEL, A. W., ELLIS, J. R., AND LI, K. Realtime concurrent collection on stock multiprocessors. In Proceedings of the ACM Conference on Programming Language Design and Implementation (Atlanta, Georgia, June). ACM SIGPLAN Notices 23, 7 (July 1988), pp. 11--20.
[2]
APPEL, A. W., AND LI, K. Virtual memory primitives for user programs. In Proceedings of the ACM International Conference on Architectural Support for Programming Languages and Operating Systems (Santa Clara, California, Apr.). ACM SIGPLAN Notices 26, 4 (Apr. 1991), pp. 96--107.
[3]
AZATCHI, H., LEVANONI, Y., PAZ, H., AND PETRANK, E. An on-the-fly mark and sweep garbage collector based on sliding views. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Anaheim, California, Nov.). ACM SIGPLAN Notices 38, 11 (Nov. 2003), pp. 269--281.
[4]
BACON, D. F., ATTANASIO, C. R., LEE, H., RAJAN, V. T., AND SMITH, S. Java without the coffee breaks: A nonintrusive multiprocessor garbage collector. In PLDI'01 {39}, pp. 92--103.
[5]
BACON, D. F., CHENG, P., AND RAJAN, V. T. A real-time garbage collector with low overhead and consistent utilization. In Conference Record of the ACM Symposium on Principles of Programming Languages (New Orleans, Lousiana, Jan.). ACM SIGPLAN Notices 38, 1 (Jan. 2003), pp. 285--298.
[6]
BAKER, H. G. List processing in real time on a serial computer. Commun. ACM 21, 4 (Apr. 1978), 280--294.
[7]
BARABASH, K., BEN-YITZHAK, O., GOFT, I., KOLODNER, E. K., LEIKEHMAN, V., OSSIA, Y., OWSHANKO, A., AND PETRANK, E. A parallel, incremental, mostly concurrent garbage collector for servers. ACM Trans. Program. Lang. Syst. 27, 6 (Nov. 2005), 1097--1146.
[8]
BARTLETT, J. F. Compacting garbage collection with ambiguous roots. Research Report 88/2, Western Research Laboratory, Digital Equipment Corporation, Feb. 1988.
[9]
BARTLETT, J. F. Mostly-copying garbage collection picks up generations and C++. Technical Note TN-12, Western Research Laboratory, Digital Equipment Corporation, Oct. 1989.
[10]
BLACKBURN, S., AND MCKINLEY, K. S. In or out?: Putting write barriers in their place. In Proceedings of the ACM International Symposium on Memory Management (Berlin, Germany, Jun., 2002), D. Detlefs, Ed. ACM SIGPLAN Notices 38, 2 (Feb. 2003), pp. 281--290.
[11]
BLACKBURN, S. M., AND HOSKING, A. L. Barriers: Friend or foe? In Proceedings of the ACM International Symposium on Memory Management (Vancouver, Canada, Oct., 2004), D. F. Bacon and A. Diwan, Eds. ACM, 2004, pp. 143--151.
[12]
BOEHM, H.-J., DEMERS, A. J., AND SHENKER, S. Mostly parallel garbage collection. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Phoenix, Arizona, Oct.). ACM SIGPLAN Notices 26, 11 (Nov. 1991), pp. 157--164.
[13]
BOEHM, H.-J., AND WEISER, M. Garbage collection in an uncooperative environment. Software--Practice and Experience 18, 9 (Sept. 1988), 807--820.
[14]
CARDELLI, L., DONAHUE, J., GLASSMAN, L., JORDAN, M., KALSOW, B., AND NELSON, G. Modula-3 language definition. In Systems Programming with Modula-3, G. Nelson, Ed. Prentice Hall, 1991, ch. 2, pp. 11--66.
[15]
CHENEY, C. J. A nonrecursive list compacting algorithm. Commun. ACM 13, 11 (Nov. 1970), 677--678.
[16]
CHENG, P., AND BLELLOCH, G. A parallel, real-time garbage collector. In PLDI'01 {39}, pp. 125--136.
[17]
DETLEFS, D. L. Concurrent garbage collection in C++. Tech. Rep. CMU-CS-90-119, Carnegie Mellon University, Mar. 1990.
[18]
DETREVILLE, J. Experience with concurrent garbage collectors for Modula-2+. Tech. Rep. 64, Systems Research Center, Digital Equipment Corporation, Palo Alto, CA, Aug. 1990.
[19]
DIJKSTRA, E., LAMPORT, L., MARTIN, A., SCHOLTEN, C., AND STEFENS, E. On-the-fly garbage collection: An exercise in cooperation. Commun. ACM 21, 11 (Nov. 1978), 966--975.
[20]
DIWAN, A., MOSS, J. E. B., AND HUDSON, R. L. Compiler support for garbage collection in a statically typed language. In Proceedings of the ACM Conference on Programming Language Design and Implementation (San Francisco, California, June). ACM SIGPLAN Notices 27, 7 (July 1992), pp. 273--282.
[21]
DOLIGEZ, D., AND GONTHIER, G. Portable, unobtrusive garbage collection for multiprocessor systems. In Conference Record of the ACM Symposium on Principles of Programming Languages (Portland, Oregon, Jan.). 1994, pp. 70--83.
[22]
DOLIGEZ, D., AND LEROY, X. A concurrent, generational garbage collector for a multi threaded implementation of ML. In Conference Record of the ACM Symposium on Principles of Programming Languages (Charleston, South Carolina, Jan.). 1993, pp. 113--123.
[23]
DOMANI, T., KOLODNER, E. K., LEWIS, E., SALANT, E. E., BARABASH, K., LAHAN, I., LEVANONI, Y., PETRANK, E., AND YANOVER, I. Implementing an on-the-fly garbage collector for Java. In ISMM'00 {32}, pp. 155--166.
[24]
DOMANI, T., KOLODNER, E. K., AND PETRANK, E. A generational on-the-fly garbage collector for Java. In Proceedings of the ACM Conference on Programming Language Design and Implementation (Vancouver, Canada, June). ACM SIGPLAN Notices 35, 6 (June 2000), pp. 274--284.
[25]
FENICHEL, R. R., AND YOCHELSON, J. C. A LISP garbage-collector for virtual-memory computer systems. Commun. ACM 12, 11 (Nov. 1969), 611--612.
[26]
FLOOD, C. H., DETLEFS, D., SHAVIT, N., AND ZHANG, X. Parallel garbage collection for shared memory multiprocessors. In Proceedings of the Java Virtual Machine Research and Technology Symposium (Monterey, California, Apr.). USENIX, 2001.
[27]
FRASER, C. W., HANSON, D. R., AND PROEBSTING, T. A. Engineering a simple, efficient code generator generator. ACM Letters on Programming Languages and Systems 1, 3 (Sept. 1992), 213--226.
[28]
HOSKING, A. L., AND MOSS, J. E. B. Protection traps and alternatives for memory management of an object-oriented language. In Proceedings of the ACM Symposium on Operating Systems Principles (Asheville, North Carolina, Dec.). ACM Operating Systems Review 27, 5 (Dec. 1993), pp. 106--119.
[29]
HOSKING, A. L., MOSS, J. E. B., AND STEFANOVIć, D. A comparative performance evaluation of write barrier implementations. In Proceedings of the ACM Conference on Object-Oriented Program-ming Systems, Languages, and Applications (Vancouver, Canada, Oct.). ACM SIGPLAN Notices 27, 10 (Oct. 1992), pp. 92--109.
[30]
HUDSON, R. L., AND MOSS, J. E. B. Incremental collection of mature objects. In Proceedings of the International Workshop on Memory Management (Saint-Malo, France, Sept.), Y. Bekkers and J. Cohen, Eds. vol. 637 of Lecture Notes in Computer Science. Springer-Verlag, 1992, pp. 388--403.
[31]
HUDSON, R. L., AND MOSS, J. E. B. Sapphire: copying garbage collection without stopping the world. Concurrency and Computation--Practice and Experience 15, 3 (March 2003), 223--261.
[32]
Proceedings of the ACM International Symposium on Memory Management (Minneapolis, Minnesota, Oct., 2000). ACM SIGPLAN Notices 36, 1 (Jan. 2001).
[33]
Proceedings of the ACM International Symposium on Memory Management (Vancouver, Canada, Oct., 1998). ACM SIGPLAN Notices 34, 3 (Mar. 1999).
[34]
LEVANONI, Y., AND PETRANK, E. An on-the-fly reference counting garbage collector for Java. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Tampa, Florida, Oct.). ACM SIGPLAN Notices 36, 11 (Nov. 2001), pp. 367--380.
[35]
LIEBERMAN, H., AND HEWITT, C. A real-time garbage collector based on the lifetimes of objects. Commun. ACM 26, 6 (June 1983), 419--429.
[36]
MOON, D. Garbage collection in a large Lisp system. In Proceedings of the ACM Conference on Lisp and Functional Programming (Austin, Texas, Aug.). 1984, pp. 235--246.
[37]
NETTLES, S., AND O'TOOLE, J. Real-time replication garbage collection. In Proceedings of the ACM Conference on Programming Language Design and Implementation (Albuquerque, New Mexico,June). ACM SIGPLAN Notices 28, 6 (June 1993), pp. 217--226.
[38]
PIRINEN, P. P. Barrier techniques for incremental tracing. In ISMM'98 {33}, pp. 20--25.
[39]
Proceedings of the ACM Conference on Programming Language Design and Implementation (Snowbird, Utah, June). ACM SIGPLAN Notices 36, 5 (May 2001).
[40]
PRINTEZIS, T., AND DETLEFS, D. A generational mostly-concurrent garbage collector. In ISMM'00 {32}, pp. 143--154.
[41]
SMITH, F., AND MORRISETT, G. Comparing mostly-copying and mark-sweep conservative collection. In ISMM'98 {33}, pp. 68--78.
[42]
SOBALVARRO, P. G. A lifetime-based garbage collector for LISP systems on general-purpose computers, 1988. B.S. Thesis, Dept. of EECS, Massachusetts Institute of Technology, Cambridge.
[43]
SPOONHOWER, D., BLELLOCH, G., AND HARPER, R. Using page residency to balance trade offs in tracing garbage collection. In Proceedings of the ACM/USENIX Conference on Virtual Execution Environments (Chicago, Illinois, June). ACM, 2005, pp. 57--67.
[44]
STEELE, JR., G. L. Multiprocessing compactifying garbagecollection. Commun. ACM 18, 9 (Sept. 1975), 495--508.
[45]
STEELE,JR., G. L. Corrigendum: Multiprocessing compactifying garbage collection. Commun. ACM 19, 6 (June 1976), 354.
[46]
UNGAR, D. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In Proceedings of the ACM Symposium on Practical Software Development Environments (Pittsburgh, Pennsylvania, Apr.). 1984, pp. 157--167.

Cited By

View all
  • (2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
  • (2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
  • (2014)Fast conservative garbage collectionACM SIGPLAN Notices10.1145/2714064.266019849:10(121-139)Online publication date: 15-Oct-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ISMM '06: Proceedings of the 5th international symposium on Memory management
June 2006
202 pages
ISBN:1595932216
DOI:10.1145/1133956
  • General Chair:
  • Erez Petrank,
  • Program Chair:
  • Eliot Moss
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. ambiguous-roots
  2. concurrent
  3. conservative
  4. garbage collection
  5. incremental
  6. memory management
  7. mostly-concurrent
  8. mostly-copying
  9. portability

Qualifiers

  • Article

Conference

ISMM06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
  • (2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
  • (2014)Fast conservative garbage collectionACM SIGPLAN Notices10.1145/2714064.266019849:10(121-139)Online publication date: 15-Oct-2014
  • (2014)Fast conservative garbage collectionProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660198(121-139)Online publication date: 15-Oct-2014
  • (2009)The single-referent collectorACM Transactions on Architecture and Code Optimization10.1145/1596510.15965136:4(1-26)Online publication date: 29-Oct-2009
  • (2008)The mapping collectorACM SIGPLAN Notices10.1145/1353536.134629443:3(91-102)Online publication date: 1-Mar-2008
  • (2008)The mapping collectorACM SIGOPS Operating Systems Review10.1145/1353535.134629442:2(91-102)Online publication date: 1-Mar-2008
  • (2008)The mapping collectorACM SIGARCH Computer Architecture News10.1145/1353534.134629436:1(91-102)Online publication date: 1-Mar-2008
  • (2008)The mapping collectorProceedings of the 13th international conference on Architectural support for programming languages and operating systems10.1145/1346281.1346294(91-102)Online publication date: 1-Mar-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media