Non-stop Haskell: two papers on incremental garbage collection

Exploring the Barrier to Entry: Incremental Generational Garbage Collection for Haskell, Andy Cheadle, Tony Field, Simon Marlow, Simon Peyton Jones, and Lyndon While, International Symposium on Memory Management, Vancouver, 2004.

PDF.

We document the design and implementation of a "production" incremental garbage collector for GHC 6.02. 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 generational collector.


Non-stop Haskell, Andy Cheadle, Tony Field, Simon Marlow, Simon Peyton Jones, Lyndon While, International Conference on Functional Programming, Montreal, September 2000, pp. 257-267.

Postscript.

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.


Simon Peyton Jones, simonpj@microsoft.com