Message Analysis for Concurrent Languages?
📜 Abstract
We describe an analysis-driven storage allocation scheme for concurrent languages that use message passing with copying semantics. The basic principle is that in such a language, data which is not part of any message does not need to be allocated in a shared data area. This allows for deallocation of thread-specific data without requiring global synchronization and often without even triggering garbage collection. On the other hand, data that is part of a message should preferably be allocated on a shared area, which allows for fast (O(1)) interprocess communication that does not require actual copying. In the context of a dynamically typed, higher-order, concurrent functional language, we present a static message analysis which guides the allocation. As shown by our performance evaluation, conducted using an industrial-strength language implementation, the analysis is effective enough to discover most data which is to be used as a message, and to allow the allocation scheme to combine the best performance characteristics of both a process-centric and a shared-heap memory architecture.
✨ Summary
The paper proposes a hybrid memory architecture for concurrent languages using asynchronous message passing with copying semantics, particularly Erlang. Each process retains a private heap for process-local data, while data likely to be shared through messages is allocated in a common area. This design aims to combine the short garbage-collection pauses and inexpensive reclamation of process-specific heaps with the constant-time communication and avoidance of repeated data replication associated with shared heaps.
The central contribution is a static message analysis for a dynamically typed, higher-order functional language. The analysis extends data-flow and closure-analysis techniques to identify values that may become messages, without depending on static type information. It also uses a specialized treatment of list constructors to preserve useful precision for recursive list processing. The paper additionally presents an escape analysis for identifying data that cannot leave its creating process.
The implementation integrates the analysis into the Erlang/OTP compiler and rewrites allocation sites so that probable message data is placed directly in shared memory. Values whose location is uncertain are protected by copy-on-demand operations, preserving the invariant that shared data cannot point into process-local heaps. The evaluated system reduced copying substantially: copying fell to zero for the life benchmark, from 81% to 34% of words for eddie, and to less than 0.02% for the large-message nag configurations. The analyzed hybrid system was approximately 10% faster than the process-centric baseline on life and generally outperformed it for larger messages in the nag benchmarks. Analysis overhead was modest in native-code compilation, remaining below 10% in the reported benchmarks.
The paper’s subsequent influence is directly documented in several follow-on publications. The authors extended the work into a 2004 ISMM paper that combined message-analysis-guided allocation with generational incremental garbage collection for low-pause concurrent systems. (researchgate.net) A substantially extended version appeared in ACM TOPLAS in 2006, expanding the treatment of message analysis and concurrent memory management. (doi.org) Bibliographic records identify the SAS paper as the original 2003 publication and the later TOPLAS article as a direct extended version. (link.springer.com) The available evidence supports a concrete influence on subsequent Erlang-oriented memory-management research; it does not establish broad adoption of the specific hybrid architecture in commercial Erlang/OTP implementations.