C4: the continuously concurrent compacting collector

ABSTRACT

C4, the Continuously Concurrent Compacting Collector, an updated generational form of the Pauseless GC Algorithm [7], is introduced and described, along with details of its implementation on modern X86 hardware. It uses a read barrier to support concur- rent compaction, concurrent remapping, and concurrent incremental update tracing. C4 differentiates itself from other generational garbage collectors by supporting simultaneous-generational concurrency: the different generations are collected using concurrent (non stop-the-world) mechanisms that can be simultaneously and independently active. C4 is able to continuously perform concurrent young generation collections, even during long periods of concurrent full heap collection, allowing C4 to sustain high allocation rates and maintain the efficiency typical to generational collectors, without sacrificing response times or reverting to stop-the-world operation. Azul systems has been shipping a commercial implementation of the Pauseless GC mechanism, since 2005. Three successive generations of Azul's Vega series systems relied on custom multi-core processors and a custom OS kernel to deliver both the scale and features needed to support Pauseless GC. In 2010, Azul released its first software-only commercial implementation of C4 for modern commodity X86 hardware, using Linux kernel enhancements to support the required feature set. We discuss implementa- tion details of C4 on X86, including the Linux virtual and physical memory management enhancements that were used to support the high rate of virtual memory operations required for sustained pauseless operation. We discuss updates to the collector's manage- ment of the heap for efficient generational collection and provide throughput and pause time data while running sustained workloads.

References

1. A. W. Appel, J. R. Ellis, and K. Li. Real-time concurrent collection on stock multiprocessors. In Proceedings of the ACM SIGPLAN 1988 conference on Programming Language Design and Implementation, PLDI '88, pages 11--20, New York, NY, USA, 1988. ACM. ISBN 0-89791-269-1. http://doi.acm.org/10.1145/53990.53992. URL http://doi.acm.org/10.1145/53990.53992.
2. AzulMRIAzul Systems Inc. Managed Runtime Initiative. http://www.managedruntime.org/, 2010.
3. D. F. Bacon, P. Cheng, and V. T. Rajan. A real-time garbage collector with low overhead and consistent utilization. In Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '03, pages 285--298, New York, NY, USA, 2003. ACM. ISBN 1-58113-628-5. http://doi.acm.org/10.1145/604131.604155. URL http://doi.acm.org/10.1145/604131.604155.
4. H. G. Baker, Jr. List processing in real time on a serial computer. Commun. ACM, 21: 280--294, April 1978. ISSN 0001-0782. http://doi.acm.org/10.1145/359460.359470. URL http://doi.acm.org/10.1145/359460.359470.
5. S. M. Blackburn and K. S. McKinley. Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance. In Proceedings of the 2008 ACM SIGPLAN conference on Programming Language Design and Implementation, PLDI '08, pages 22--32, New York, NY, USA, 2008. ACM. ISBN 978-1-59593-860-2. http://doi.acm.org/10.1145/1375581.1375586. URL http://doi.acm.org/10.1145/1375581.1375586.
6. R. A. Brooks. Trading data space for reduced time and code space in real-time garbage collection on stock hardware. In Proceedings of the 1984 ACM Symposium on LISP and functional programming, LFP '84, pages 256--262, New York, NY, USA, 1984. ACM. ISBN 0-89791-142-3. http://doi.acm.org/10.1145/800055.802042. URL http://doi.acm.org/10.1145/800055.802042.
7. C. Click, G. Tene, and M. Wolf. The Pauseless GC algorithm. In Proceedings of the 1st ACM/USENIX International Conference on Virtual Execution Environments, VEE '05, pages 46--56, New York, NY, USA, 2005. ACM. ISBN 1-59593-047-7. http://doi.acm.org/10.1145/1064979.1064988. URL http://doi.acm.org/10.1145/1064979.1064988.
8. D. Detlefs and T. Printezis. A Generational Mostly-concurrent Garbage Collector. Technical report, Mountain View, CA, USA, 2000.
9. D. Detlefs, C. Flood, S. Heller, and T. Printezis. Garbage-first garbage collection. In Proceedings of the 4th International Symposium on Memory Management, ISMM '04, pages 37--48, New York, NY, USA, 2004. ACM. ISBN 1-58113-945-4. http://doi.acm.org/10.1145/1029873.1029879. URL http://doi.acm.org/10.1145/1029873.1029879.
10. D. Dice, A. Garthwaite, and D. White. Supporting per-processor local-allocation buffers using multi-processor restartable critical sections. Technical report, Mountain View, CA, USA, 2004.
11. D. Frampton, D. F. Bacon, P. Cheng, and D. Grove. Generational Real-Time Garbage Collection: A Three-Part Invention for Young Objects. ECOOP '07, pages 101--125.
12. U. Hölzle. A Fast Write Barrier for Generational Garbage Collectors. In OOPSLA/ECOOP '93 Workshop on Garbage Collection in Object-Oriented Systems, 1993.
13. H. Kermany and E. Petrank. The Compressor: concurrent, incremental, and parallel compaction. In Proceedings of the 2006 ACM SIGPLAN conference on Programming Language Design and Implementation, PLDI '06, pages 354--363, New York, NY, USA, 2006. ACM. ISBN 1-59593-320-4. http://doi.acm.org/10.1145/1133981.1134023. URL http://doi.acm.org/10.1145/1133981.1134023.
14. F. Pizlo, D. Frampton, E. Petrank, and B. Steensgaard. Stopless: a real-time garbage collector for multiprocessors. In Proceedings of the 6th International Symposium on Memory Management, ISMM '07, pages 159--172, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-893-0. http://doi.acm.org/10.1145/1296907.1296927. URL http://doi.acm.org/10.1145/1296907.1296927.
15. F. Pizlo, E. Petrank, and B. Steensgaard. A study of concurrent real-time garbage collectors. In Proceedings of the 2008 ACM SIGPLAN conference on Programming Language Design and Implementation, PLDI '08, pages 33--44, New York, NY, USA, 2008. ACM. ISBN 978-1-59593-860-2. http://doi.acm.org/10.1145/1375581.1375587. URL http://doi.acm.org/10.1145/1375581.1375587.
16. F. Pizlo, L. Ziarek, P. Maj, A. L. Hosking, E. Blanton, and J. Vitek. Schism: fragmentation-tolerant real-time garbage collection. In Proceedings of the 2010 ACM SIGPLAN conference on Programming Language Design and Implementation, PLDI '10, pages 146--159, New York, NY, USA, 2010. ACM. ISBN 978-1-4503-0019-3. http://doi.acm.org/10.1145/1806596.1806615. URL http://doi.acm.org/10.1145/1806596.1806615.
17. G. Tene, C. Click, M. Wolf, and I. Posva. Memory Management, 2006. US Patent 7,117,318.
18. D. Ungar. Generation Scavenging: A non-disruptive high performance storage reclamation algorithm. In Proceedings of the first ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, SDE 1, pages 157--167, New York, NY, USA, 1984. ACM. ISBN 0-89791-131-8. http://doi.acm.org/10.1145/800020.808261. URL http://doi.acm.org/10.1145/800020.808261.
19. M. T. Vechev, E. Yahav, and D. F. Bacon. Correctness-preserving derivation of concurrent garbage collection algorithms. In Proceedings of the 2006 ACM SIGPLAN conference on Programming Language Design and Implementation, PLDI '06, pages 341--353, New York, NY, USA, 2006. ACM. ISBN 1-59593-320-4. http://doi.acm.org/10.1145/1133981.1134022. URL http://doi.acm.org/10.1145/1133981.1134022.
20. P. R. Wilson. Uniprocessor Garbage Collection Techniques. In Proceedings of the International Workshop on Memory Management, IWMM '92, pages 1--42, London, UK, 1992. Springer-Verlag. ISBN 3-540-55940-X. URL http://portal.acm.org/citation.cfm?id=645648.664824.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Dynamic compilers

    • General programming languages

      • Language features

        • Concurrent programming structures

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection

          • Virtual memory