Heap Architectures for Concurrent Languages using Message Passing

✨ Summary

Summary

The paper investigates three heap organizations for concurrent languages that communicate through asynchronous message passing, using an otherwise unchanged Erlang/OTP runtime as the experimental platform:

• Private heaps: Each process owns its stack and heap. Messages are copied from the sender’s heap to the receiver’s heap. This provides small garbage-collection root sets, direct reclamation when a process terminates, and straightforward per-process resource accounting, but incurs message-copying costs, requires additional memory, and can cause fragmentation.
• A shared heap: All processes allocate compound data and messages in one global heap. Sending a message requires only placing a pointer in the receiver’s mailbox, making communication independent of message size and reducing memory duplication. The tradeoff is that garbage collection must consider the stacks and mailboxes of all processes, potentially increasing pause times and collection costs.
• A hybrid architecture: Processes retain private heaps for local data, while messages are placed in a shared message area. Pointers may point from private areas into the shared area, but not in the reverse direction. This permits independent collection of private heaps while retaining non-copying message transfer. The design depends on escape analysis or programmer annotations to identify data that may leave a process.

The evaluation uses synthetic workloads and substantial Erlang applications, including the BEAM compiler and NETSim components. The shared-heap implementation generally uses less memory and often executes faster than the private-heap implementation because it avoids copying and fragmentation. In highly concurrent workloads, private heaps devote substantial execution time to interprocess communication, whereas the shared heap substantially reduces that cost. However, shared-heap garbage collection becomes a bottleneck when many processes have substantial live data, and its maximum collection pauses are somewhat longer in such cases. The private-heap design remains advantageous when applications have many processes with small heaps, exploit process termination for reclamation, or have been tuned specifically for copying-based message passing.

The hybrid prototype performs particularly well on workloads involving long-lived or repeatedly shared messages: it avoids message copying while keeping local garbage collections small and independent. Its broader evaluation was limited because compiler-integrated escape analysis was not yet available. The paper therefore does not identify a universally superior architecture; it presents the shared heap as the preferable default when a choice must be made without workload-specific information, while regarding the hybrid design as a promising combination of communication and garbage-collection benefits.

Influence and Subsequent Use

A subsequent paper by Carlsson, Sagonas, and Wilhelmsson, Message Analysis for Concurrent Languages (2003), cites this work and develops static message analysis to guide memory allocation in concurrent languages. That work preserves the central idea of separating process-local data from data that may be exchanged between processes, while adding analysis and incremental garbage-collection techniques intended to improve responsiveness. (user.it.uu.se)

The paper’s tradeoff remains visible in Erlang/OTP. Current Erlang documentation describes per-process stacks and heaps, copying generational garbage collection, and configurable handling of messages either on the process heap or in off-heap fragments. The modern implementation therefore retains the latency and isolation advantages associated with process-local heaps while providing an alternative for workloads with large message queues. (erlang.org)

Erlang/OTP’s engineering documentation also states that messages are copied before queue insertion and that earlier non-copying approaches were rejected as a poor fit for Erlang’s soft-real-time latency goals. This provides a concrete industry outcome consistent with the paper’s conclusion that communication throughput must be balanced against garbage-collection pause time rather than optimized in isolation. (erlang.org)

The paper was published as an ISMM’02 conference paper, pages 195–206 in bibliographic indexes, with the PDF version identifying the June 20–21, 2002 Berlin conference dates. (dblp.org)