Message Analysis-Guided Allocation and Low-Pause Incremental Garbage Collection in a Concurrent Language
📜 Abstract
We present a memory management scheme for a concurrent programming language where communication occurs using message-passing with copying semantics. The runtime system is built around process-local heaps, which frees the memory manager from redundant synchronization in a multithreaded implementation and allows the memory reclamation of process-local heaps to be a private business and to often take place without garbage collection. The allocator is guided by a static analysis which speculatively allocates data possibly used as messages in a shared memory area. To respect the (soft) real-time requirements of the language, we develop a generational, incremental garbage collection scheme tailored to the characteristics of this runtime system. The collector imposes no overhead on the mutator, requires no costly barrier mechanisms, and has a relatively small space overhead. We have implemented these schemes in the context of an industrial-strength implementation of a concurrent functional language used to develop large-scale, highly concurrent, embedded applications. Our measurements across a range of applications indicate that the incremental collector substantially reduces pause times, imposes only very small overhead on the total runtime, and achieves a high degree of mutator utilization.
✨ Summary
The paper introduced a hybrid memory architecture for Erlang-style message-passing concurrency: process-local heaps are used by default, while statically identified potential messages are allocated in a shared message area. It paired this design with a generational incremental collector using copying collection for the young generation and incremental mark-and-sweep for the old generation. The design avoids per-object header words and costly read or write barriers, relying instead on pointer-directionality invariants, forwarding-pointer storage, remembered sets, and low-cost process activation checks.
The evaluation reported substantially shorter message-area collection pauses than a non-incremental collector, with comparatively small effects on total execution time for most benchmarks. The work-based collector supported fine-grained collection quanta, while the time-based collector demonstrated pauses targeted around a 1 ms quantum, subject to small deadline extensions.
The most clearly documented subsequent influence is a substantially extended journal version, “Efficient memory management for concurrent programs that use message passing,” published in Science of Computer Programming in 2006. That article explicitly identifies this ISMM paper as its conference predecessor and develops the memory-management architecture and collector in greater detail. (sciencedirect.com) The original work was also situated directly in the Erlang/OTP development context; contemporary bibliographic material records the hybrid architecture and associated techniques as part of the Erlang/OTP runtime-system research program. (user.it.uu.se) Subsequent publications cite the paper as work on incremental garbage collection for message-passing and concurrent systems, but the available sources do not establish broad adoption of this exact collector in commercial Erlang/OTP releases.