Exploring the barrier to entry: incremental generational garbage collection for Haskell

ABSTRACT

We document the desi n and implementation of a "production" incremental garbage collector for GHC 6.2.It builds on our earlier work (Non-stop Haskell)that exploited GHC's dynamic dispatch mechanism to hijack object code pointers so that objects in to-space automatically scavenge themselves when the mutator attempts to "enter" them. This paper details various optimisations based on code specialisation that remove the dynamic space,and associated time, overheads that accompanied our earlier scheme.We detail important implementation issues and provide a detailed evaluation of a range of design alternatives in comparison with Non-stop Haskell and GHC's current generational collector.We also show how the same code specialisation techniques can be used to eliminate the write barrier in a enerational collector.

REFERENCES

• 1: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 2: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 3: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-298, January 15-17, 2003, New Orleans, Louisiana, USA
• 4: Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.104-117, May 01-04, 1999, Atlanta, Georgia, United States
• 5: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.125-136, June 2001, Snowbird, Utah, United States
• 6: G. L. Burn , S. L. Peyton Jones , J. D. Robson, The spineless G-machine, Proceedings of the 1988 ACM conference on LISP and functional programming, p.244-258, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62717]
• 7: A. M. Cheadle , A. J. Field , S. Marlow , S. L. Peyton Jones , R. L. While, Non-stop Haskell, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.257-267, September 2000
• 8: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 9: J. DeTreville. Experience with conncurrent garbage collectors for Modula-2+. Technical Report 64, DEC Systems Research Center, Palo Alto, CA, August 1990.
• 10: Barry Hayes, Using key object opportunism to collect old objects, Conference proceedings on Object-oriented programming systems, languages, and applications, p.33-46, October 06-11, 1991, Phoenix, Arizona, United States
• 11: Simon Marlow , Simon Peyton Jones, Making a fast curry: push/enter vs. eval/apply for higher-order languages, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, USA
• 12: Jan-Willem Maessen , Arvind, Hybrid eager and lazy evaluation for efficient compilation of haskell, 2002
• 13: Scott Nettles , James O'Toole , David Pierce, Replication-Based Incremental Copying Collection, Proceedings of the International Workshop on Memory Management, p.357-364, September 17-19, 1992
• 14: W. Partain. The nofib Benchmark Suite of Haskell Programs. Dept. of Computer Science, University of Glasgow, 1993.
• 15: PAPI: Performance Application Programming Interface http://icl.cs.utk.edu/papi/
• 16: Niklas Röjemo, Generational Garbage Collection without Temporary Space Leaks for Lazy Functional Languages, Proceedings of the International Workshop on Memory Management, p.145-162, September 27-29, 1995
• 17: Patrick M. Sansom , Simon L. Peyton Jones, Generational garbage collection for Haskell, Proceedings of the conference on Functional programming languages and computer architecture, p.106-116, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165195]
• 18: S. Peyton Jones. The Spineless Tagless g-machine: Second attempt. In Workshop on the Parallel Implementation of Functional Languages, volume CSTR 91-07, pages 147--91. University of Southampton, 1991.
• 19: S. Peyton Jones. Implementing lazy functional languages on stock hardware: the Spineless Tagless g-machine. In Journal of Functional Programming, pages 127--202, 1992.
• 20: S. Peyton Jones, S. Marlow, and A. Reid. The STG runtime system (revised). Draft paper, Microsoft Research Ltd, 1999.
• 21: Simon L. Peyton Jones , Jon Salkild, The spineless tagless G-machine, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.184-201, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99385]
• 22: Julian Seward, Generational Garbage Collection for Lazy Graph Reduction, Proceedings of the International Workshop on Memory Management, p.200-217, September 17-19, 1992
• 23: R.A. Shaw. Improving garbage collector performance in virtual memory. Technical Report CSL-TR-87-323, Stanford University, March 1987.
• 24: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 25: Valgrind, an open-source memory debugger for x86-linux. http://valgrind.kde.org.
• 26: Benjamin Goth Zorn, Comparative performance evaluation of garbage collection algorithms, 1989
• 27: Benjamin Zorn, The measured cost of conservative garbage collection, Software—Practice & Experience, v.23 n.7, p.733-756, July 1993 [doi>10.1002/spe.4380230704]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Preprocessors

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance

Keywords:
incremental garbage collection, non-stop haskell