Skip to content

A concurrent garbage collector for the old generation

This introduces a concurrent mark & sweep garbage collector to manage the old generation. The concurrent nature of this collector typically results in significantly reduced maximum and mean pause times in applications with large working sets.

Branch overview

The branch is split up into four sections, each of which consisting of a few logically atomic and buildable commits:

  1. preparation (wip/gc/preparation): Here we lay the groundwork for the collector by carrying out a few preparatory refactorings. These have been broken out into a variety of smaller MRs:

    • !411 (merged): Implements support for aligned allocations in the block allocator
    • !412 (merged): Factors out the large bitmap walking logic for reuse
    • !413 (merged): Various miscellany
    • !414 (merged): Allows sync to be requested by OS threads that do not hold a capability
    • !415 (merged): Unglobalized a bit of GC state to enable concurrent major and minor collections
  2. non-concurrent collection (wip/gc/nonmoving-nonconcurrent, !417 (closed)): Here we introduce the basic heap structure, the allocator, and implement non-concurrent mark & sweep collection.

  3. concurrent collection (wip/gc/nonmoving-concurrent, this MR): Here we extend the non-concurrent collector to allow both marking and sweeping to proceed concurrently with mutation.

  4. instrumentation (wip/gc/instrumentation, !973 (closed)): Here we introduce two useful bits of instrumentation for characterisation of the behavior of the new collector:

    • a heap utilization census, useful for measuring heap fragmentation
    • eventlog-based tracing support of various points in the concurrent collection cycle
  5. testsuite wibbles (wip/gc/test, !974 (closed)): Cleaning up the testsuite to reflect the various limitations of the nonmoving collector. These commits will either be folded into earlier commits or be dropped entirely before merging.

  6. aging support (wip/gc/aging, !975 (closed)): Allow aging of heap objects in the preparatory moving collection of a major GC.

  7. miscellaneous optimisations (wip/gc/optimize, !976 (closed)): A number of runtime performance improvements

  8. documentation (wip/gc/docs, !977 (closed)): Improve implementation Notes.

  9. compact region support (wip/gc/compact-nfdata, !1235 (closed)): Implement support for compact regions

  10. pause-time optimization (wip/gc/opt-pause, !1947 (closed) ): A variety of small optimisations to further reduce pause times.

Due to the large size of this patch it is recommended that review proceed commit-by-commit.

 * wip/gc/opt-pause:
 |   A variety of small optimisations to further reduce pause times.
 |
 * wip/gc/compact-nfdata: 
 |   Introduce support for compact regions into the non-moving
 |\  collector
 | \
 |  \
 | | * wip/gc/segment-header-to-bdescr:
 | | |   Another optimization that we are considering, pushing
 | | |   some segment metadata into the segment descriptor for
 | | |   the sake of locality during mark
 | | |
 | * | wip/gc/shortcutting:
 | | |   Support for indirection shortcutting and the selector optimization
 | | |   in the non-moving heap.
 | | |
 * | | wip/gc/docs:
 | |/    Work on implementation documentation.
 | /
 |/
 * wip/gc/everything:
 |   A roll-up of everything below.
 |\
 | \
 | |\
 | | \
 | | * wip/gc/optimize:
 | | |   A variety of optimizations, primarily to the mark loop.
 | | |   Some of these are microoptimizations but a few are quite
 | | |   significant. In particular, the prefetch patches have
 | | |   produced a nontrivial improvement in mark performance.
 | | |
 | | * wip/gc/aging:
 | | |   Enable support for aging in major collections.
 | | |
 | * | wip/gc/test:
 | | |   Fix up the testsuite to more or less pass.
 | | |
 * | | wip/gc/instrumentation:
 | | |   A variety of runtime instrumentation including statistics
 | | /   support, the nonmoving census, and eventlog support.
 | |/
 | /
 |/
 * wip/gc/nonmoving-concurrent:
 |   The concurrent write barriers.
 |
 * wip/gc/nonmoving-nonconcurrent:
 |   The nonmoving collector without the write barriers necessary
 |   for concurrent collection.
 |
 * wip/gc/preparation:
 |   A merge of the various preparatory patches that aren't directly
 |   implementing the GC.
 |
 |
 * GHC HEAD
 .
 .
 .

Collector design

The full design of the collector implemented here is described in detail in a technical note

B. Gamari. "A Concurrent Garbage Collector For the Glasgow Haskell Compiler" (2018)

This document can be requested from @bgamari.

The basic heap structure used in this design is heavily inspired by

K. Ueno & A. Ohori. "A fully concurrent garbage collector for functional programs on multicore processors." /ACM SIGPLAN Notices/ Vol. 51. No. 9 (presented at ICFP 2016)

This design is intended to allow both marking and sweeping concurrent to execution of a multi-core mutator. Unlike the Ueno design, which requires no global synchronization pauses, the collector introduced here requires a stop-the-world pause at the beginning and end of the mark phase.

To avoid heap fragmentation, the allocator consists of a number of fixed-size /sub-allocators/. Each of these sub-allocators allocators into its own set of /segments/, themselves allocated from the block allocator. Each segment is broken into a set of fixed-size allocation blocks (which back allocations) in addition to a bitmap (used to track the liveness of blocks) and some additional metadata (used also used to track liveness).

This heap structure enables collection via mark-and-sweep, which can be performed concurrently via a snapshot-at-the-beginning scheme (although concurrent collection is not implemented in this patch).

Implementation structure

The majority of the collector is implemented in a handful of files:

  • rts/Nonmoving.c is the heart of the beast. It implements the entry-point to the nonmoving collector (nonmoving_collect), as well as the allocator (nonmoving_allocate) and a number of utilities for manipulating the heap.

  • rts/NonmovingMark.c implements the mark queue functionality, update remembered set, and mark loop.

  • rts/NonmovingSweep.c implements the sweep loop.

  • rts/NonmovingScav.c implements the logic necessary to scavenge the nonmoving heap.

Usage

The non-moving collector can be run in two modes, both of which activated with the +RTS -xn runtime system flag (n for "non-moving"):

  • When compiled against the non-threaded runtime the non-moving heap is used for the oldest generation with non-concurrent mark & sweep for collection. We do not expect this will be a commonly used configuration but it has been invaluable for testing.

  • When compiled against the threaded runtime (e.g. using -threaded) the non-moving heap is used for the oldest generation with concurrent mark & sweep for collection.

The testsuite has been extended with two additional ways:

  • nonmoving exercises the non-concurrent collector by running all compile_and_run tests with +RTS -xn

  • nonmoving_thr exercises the concurrent collector by compiling all compile_and_run tests against the threaded RTS and running them with +RTS -xn

Performance characterisation

We have looked at the performance of the collector under a number of workloads.

TODO: Report more benchmarks

vector benchmarks

moving collector nonmoving collector
Mutator runtime, CPU (s) 61.484 64.89
Mutator runtime, elapsed (s) 61.88 64.979
Avg. gen0 pause (ms) 0 0.1
Max. gen0 pause (ms) 10.4 10.8
Avg. gen1 pause (ms) 4.5 0.8
Max. gen1 pause (ms) 277.6 20.5
Avg. sync pause (ms) N/A 8.4
Max. sync pause (ms) N/A 73.8

GHC compiling Cabal

moving collector nonmoving collector
Mutator runtime, elapsed (s) 210.9 219.6
Avg. gen0 pause (ms) 7.1 8.8
Max. gen0 pause (ms) 123.7 301.7
Avg. gen1 pause (ms) 236.9 6.6
Max. gen1 pause (ms) 693.2 31.7
Avg. sync pause (ms) N/A 4.8
Max. sync pause (ms) N/A 19.6

The Pusher benchmark

See this Stack Overflow question.

Small queue

  • queue size: 2e5
  • message count: 10e6
moving collector nonmoving collector
Mutator runtime, elapsed (s) 7.23 7.56
Avg. gen0 pause (ms) 0.1 0.1
Max. gen0 pause (ms) 3.0 2.3
Avg. gen1 pause (ms) 29.0 7.3
Max. gen1 pause (ms) 34.9 11.0
Avg. sync pause (ms) N/A 0.2
Max. sync pause (ms) N/A 2.0

Large queue

  • queue size: 2e6
  • message count: 10e6
moving collector nonmoving collector
Mutator runtime, elapsed (s) 9.086 8.99
Avg. gen0 pause (ms) 0.1 0.1
Max. gen0 pause (ms) 1.2 3.3
Avg. gen1 pause (ms) 132.4 21.5
Max. gen1 pause (ms) 420.8 79.8
Avg. sync pause (ms) N/A 0.4
Max. sync pause (ms) N/A 1.8

Status

There are a few things that remain left to be implemented:

  • Compact region support
  • Parallel marking
  • User guide documentation

The selector optimisation is implemented but not included in this branch.

Note that heap profiling is not implemented. We would also suggest that there are few compelling reasons to introduce heap profiling support in the non-moving collector: Profiling typically occurs only in a development environment where the low-latency provided by the non-moving collector is typically not needed. Furthermore, the concurrent nature of the collector means that profiles would at best be non-deterministic.

Edited by Ben Gamari

Merge request reports