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

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.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Runtime environments

      • Source code generation

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection