Non-stop Haskell

ABSTRACT

We describe an efficient technique for incorporating Baker's incremental garbage collection algorithm into the Spineless Tagless G-machine on stock hardware. This algorithm eliminates the stop/go execution associated with bulk copying collection algorithms, allowing the system to place an upper bound on the pauses due to garbage collection. The technique exploits the fact that objects are always accessed by jumping to code rather than being explicitly dereferenced. It works by modifying the entry code-pointer when an object is in the transient state of being evacuated but not scavenged. An attempt to enter it from the mutator causes the object to "self-scavenge" transparently before resetting its entry code pointer. We describe an implementation of the scheme in v4.01 of the Glasgow Haskell Compiler and report performance results obtained by executing a range of applications. These experiments show that the read barrier can be implemented in dynamic dispatching systems such as the STG-machine with very short mutator pause times and with negligible overhead on execution time.

REFERENCES

• 1: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• 2: L. Augustsson. Compiling Lazy Functional Languages, Part II. PhD thesis, Chalmers University, Sweden, 1987.
• 3: 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]
• 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: 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]
• 6: 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]
• 7: Robert Courts, Improving locality of reference in a garbage-collecting memory management system, Communications of the ACM, v.31 n.9, p.1128-1138, Sept. 1988 [doi>10.1145/48529.48536]
• 8: David Detlefs , Ole Agesen, Inlining of Virtual Methods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.258-278, June 14-18, 1999
• 9: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 10: Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158611]
• 11: Lorenz Huelsbergen , James R. Larus, A concurrent copying garbage collector for languages that distinguish (im)mutable data, ACM SIGPLAN Notices, v.28 n.7, p.73-82, July 1993
• 12: Douglas Johnson, Trap architectures for Lisp systems, Proceedings of the 1990 ACM conference on LISP and functional programming, p.79-86, June 27-29, 1990, Nice, France [doi>10.1145/91556.91595]
• 13: Douglas Johnson, The case for a read barrier, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.279-287, April 08-11, 1991, Santa Clara, California, United States
• 14: T. Johnsson. Compiling Lazy Functional Languages. PhD thesis, Chalmers University, Sweden, 1987.
• 15: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 16: S. P. Jones. The Spineless Tagless g-machine: Second attempt. In Workshop on the Parallel Implementation of Functional Languagesi, volume CSTR 91-07, pages 147-91. University of Southampton, 1991.
• 17: S. P. Jones. Implementing lazy functional languages on stock hardware: the Spineless Tagless g-machine. In Journal of Functional Programming, 1992.
• 18: S. P. Jones, S. Marlow, and A. Reid. The STG runtime system (revised). draft paper, Microsoft Research Ltd, 1999.
• 19: 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]
• 20: W. Partain. The nob Benchmark Suite of Haskell Programs. Dept. of Computer Science, University of Glasgow, 1993.
• 21: 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
• 22: Benjamin Goth Zorn, Comparative performance evaluation of garbage collection algorithms, 1989

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Haskell

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

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