Paper: Alligator Collector: A Latency-Optimized Garbage Collector for Functional Programming Languages

| tagged with
  • paper
  • garbage collection

As I have reported previously, over the past two years, I (along with my colleague Ömer Sinan Ağacan) have been working through the design and implementation of a concurrent garbage collector for the Glasgow Haskell Compiler. Happily, the result can be found in GHC 8.10.1 (with further improvements coming in future releases).

Further details (and some quantitative evaluation of the collector’s performance) can be found in our recently-accepted ISMM 2020 paper, Alligator Collector: A Latency-Optimized Garbage Collector for Functional Programming Languages (preprint):

Modern hardware and applications require runtime systems that can operate under large-heap and low-latency requirements. In particular, for many client/server or interactive applications, reducing average and maximum pause times is more important than maximizing throughput.

Since version 8.10.1, the GHC Haskell runtime system offers a new latency-optimized garbage collector as an alternative to the existing throughput-optimized copying garbage collector. This paper details the latency-optimized GC design, which is a generational collector integrates GHC’s existing collector and bump-pointer allocator with a non-moving collector and non-moving heap suggested by Ueno and Ohori. We provide an empirical analysis on the latency/throughput tradeoffs. We augment the established nofib micro benchmark with a response-time focused benchmark that simulates real-world applications such as LRU caches, web search, and key-value stores.

If you are curious about the name: don’t waste too much thought on it; I like reptiles and hate thinking of names.