A. M. Cheadle
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.
- 1.A. Appel, J. Ellis, and K. Li. Real-time concurrent collection on stock multiprocessors. In Conference on Programming Language Design and Implementation, pages 11-20, 1988.]] Google Scholar
Digital Library
- 2.L. Augustsson. Compiling Lazy Functional Languages, Part II. PhD thesis, Chalmers University, Sweden, 1987.]]Google Scholar
- 3.H. Baker. List-processing in real-time on a serial computer. In CACM 21(4), pages 280-94, 1978.]] Google Scholar
- 4.G. Blelloch and P. Cheng. One bounding time and space for multiprocessor garbage collection. In ACM SIGPLAN Symposium on Programming Language Design and Implementation (PLDI), 1999.]] Google ScholarDigital Library
- 5.G. Burn, S. Peyton-Jones, and J. Robson. The spineless g-machine. In Conference on Lisp and Functional Programming, pages 244-58, 1988.]] Google ScholarDigital Library
- 6.C. Cheney. A non-recursive list compacting algorithm. In CACM 13(11), pages 677-8, 1970.]] Google Scholar
- 7.R. Courts. Improving locality of reference in a garbagecollecting memory management system. In CACM 31(9), pages 1128-38, 1988.]] Google Scholar
- 8.D. Detlefs and O. Agesen. Inlining of virtual methods. In ECOOP, 1999.]] Google ScholarDigital Library
- 9.E. Dijkstra et al. On-the- y garbage collection: An exercise in cooperation. In CACM, 21, 11, pages 966- 975, 1978.]] Google ScholarDigital Library
- 10.D. Doligez and X. Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. In PoPL '93, pages 113-123, 1993.]] Google ScholarDigital Library
- 11.L. Huelsbergen and J. Larus. A concurrent copying garbage collector for languages that distinguish (im)mutable data. In 4th ACM Symposium on Principles and Practice of Parallel Programming, Vol. 28(7) of ACM SIGPLAN Notices, pages 73-82, 1993.]] Google ScholarDigital Library
- 12.D. Johnson. Trap architectures for lisp systems. In Conference on Lisp and Functional Programming, pages 79-86, 1990.]] Google ScholarDigital Library
- 13.D. Johnson. The case for a read barrier. In ASPLOS- IV, pages 279{87, 1991.]] Google ScholarDigital Library
- 14.T. Johnsson. Compiling Lazy Functional Languages. PhD thesis, Chalmers University, Sweden, 1987.]]Google Scholar
- 15.R. Jones and R. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, 1996.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 17.S. P. Jones. Implementing lazy functional languages on stock hardware: the Spineless Tagless g-machine. In Journal of Functional Programming, 1992.]]Google ScholarCross Ref
- 18.S. P. Jones, S. Marlow, and A. Reid. The STG runtime system (revised). draft paper, Microsoft Research Ltd, 1999.]]Google Scholar
- 19.S. P. Jones and J. Salkild. The Spineless Tagless G- machine. In Conference on Functional Programming Languages and Computer Architecture, pages 184-201, 1989.]] Google ScholarDigital Library
- 20.W. Partain. The nob Benchmark Suite of Haskell Programs. Dept. of Computer Science, University of Glasgow, 1993.]]Google Scholar
- 21.e. a. S.M. Nettles. Replication-based incremental copying collection. In Proceedings of the International Workshop on Memory Management, LNCS 637. Springer Verlag, 1992.]] Google ScholarDigital Library
- 22.B. Zorn. Comparative Performance Evaluation of Garbage Collection Algorithms. PhD thesis, University of California at Berkeley, 1989.]] Google ScholarDigital Library
Index Terms
- Non-stop Haskell
Recommendations
Non-stop Haskell
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 ...
A performance comparison between stop-the-world and multithreaded concurrent generational garbage collection for Java
PCC '02: Proceedings of the Performance, Computing, and Communications Conference, 2002. on 21st IEEE InternationalThe recent popularity of the Java programming language has brought automatic dynamic memory management (a.k.a., the garbage collection) into the mainstream. Traditional garbage collectors suffer from long garbage collection pauses (stop-the-world mark-...
A study of the scalability of stop-the-world garbage collectors on multicores
ASPLOS '13Large-scale multicore architectures create new challenges for garbage collectors (GCs). In particular, throughput-oriented stop-the-world algorithms demonstrate good performance with a small number of cores, but have been shown to degrade badly beyond ...
Comments