Parallel Generational-Copying Garbage Collection with a Block-Structured Heap
📜 Abstract
We present a parallel generational-copying garbage collector implemented for the Glasgow Haskell Compiler. We use a block-structured memory allocator, which provides a natural granularity for dividing the work of GC between many threads, leading to a simple yet effective method for parallelising copying GC. The results are encouraging: we demonstrate wall-clock speedups of on average a factor of 2 in GC time on a commodity 4-core machine with no programmer intervention, compared to our best sequential GC.
✨ Summary
Summary
The paper presents a stop-the-world, parallel generational copying garbage collector for the Glasgow Haskell Compiler (GHC). Its central design choice is a heap divided into fixed-size blocks, each with a descriptor recording metadata such as generation, aging step, allocation state, and garbage-collection scan state. This organization allows generations and steps to be resized independently, supports non-contiguous regions, simplifies large-object management, and provides a convenient unit of work for parallel collection.
During collection, each garbage-collection thread maintains a scan block and an allocation block. Evacuated objects are copied into private allocation blocks, while blocks containing pending objects are placed in a shared pending-block set. Threads claim source objects with atomic compare-and-swap operations to prevent duplicate evacuation, and global termination is detected by coordinating the set of active collector threads. When work is scarce, partially filled blocks are exported so that otherwise idle threads can participate; the chunk size controls the trade-off between load balance and synchronization overhead.
The design is extended to multiple generations and aging steps. The paper introduces eager promotion, which promotes an object directly to the generation of an immutable object that references it. This is particularly suitable for Haskell thunks because they are updated at most once. In the measurements, eager promotion reduced garbage-collection time by 6.8% geometrically on average, although one benchmark was adversely affected by collection-timing sensitivity.
Experiments on Haskell benchmarks, including GHC itself, show meaningful but sublinear scaling. The implementation reports approximately 20% lower garbage-collection time on dual-core systems and approximately 45% lower time on quad-core systems, with benchmark speedups ranging from 1.5 to 3.2 on a four-processor machine. The principal costs are per-object synchronization, which adds roughly 20–30% overhead in the single-processor parallel configuration, and workload imbalance caused both by the collector’s scheduling decisions and by inherently sequential heap structures. Measured fragmentation remained below 1% of runtime-allocated memory across the benchmarks.
Subsequent influence and use
The work formed part of the development trajectory of multicore garbage collection in GHC. GHC’s current documentation describes parallel garbage collection as enabled by multicore execution and provides runtime controls for selecting the generations collected in parallel, demonstrating that parallel GC remains an exposed feature of the GHC runtime. (ghc.gitlab.haskell.org)
A later paper by Marlow and Peyton Jones, Multicore Garbage Collection with Local Heaps (ISMM 2011), cites this work and develops local per-processor heaps to reduce global synchronization and improve scaling. (researchgate.net) The available sources establish direct continuity in GHC runtime research and implementation, but do not provide sufficient evidence to attribute adoption of the specific block-level algorithm or eager-promotion policy to unrelated industrial garbage collectors.