Cloaca: A Concurrent Hardware Garbage Collector for Non-Strict Functional Languages
Most functional language runtime systems context switch between executing user code and a non-concurrent garbage collector (GC), exposing GC latency to overall wall-clock time. Recent concurrent software-based GCs reduce these latencies, but wall-clock times are instead increased due to their synchronisation and write barrier overheads, by as much as 21%. This GC overhead is exacerbated further for pure non-strict languages like Haskell, due to the abundance of allocations for storing immutable data structures and closures. This paper presents Cloaca, an FPGA-based hardware implementation of a concurrent, hybrid GC for a pure non-strict functional language. It combines mark-and-sweep tracing and one-bit reference counting. It traces live heap data using hardware-level synchronisation and write barriers, without damaging graph reduction performance. To ensure the correctness of Cloaca, three invariants of its Haskell-based implementation are verified with property-based testing. Despite GHC running on an Intel i7 CPU operating at a x25 higher clock frequency than Cloaca; Cloaca takes, on average, 8.6% of GHC’s GC wall-clock time across 14 of 15 benchmarks. Moreover, Cloaca’s small hardware footprint consumes under 4 Watts of power, compared with Intel i7 drawing between 5 and 20 Watts.
Sat 7 SepDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
14:00 - 15:30 | |||
14:00 30mTalk | Calculating Compilers Effectively Haskell Zac Garby University of Nottingham, Graham Hutton University of Nottingham, Patrick Bahr IT University of Copenhagen | ||
14:30 30mTalk | Cloaca: A Concurrent Hardware Garbage Collector for Non-Strict Functional Languages Haskell | ||
15:00 30mTalk | Functional Reactive Programming, Rearranged Haskell |