Region-based memory management (RBMM) is a form of compile time memory management, well-known from the functional programming world. In this paper we describe our work on implementing RBMM for the logic programming language Mercury. One interesting point about Mercury is that it is designed with strong type, mode, and determinism systems. These systems not only provide Mercury programmers with several direct software engineering benefits, such as self-documenting code and clear program logic, but also give language implementors a large amount of information that is useful for program analyses. In this work, we make use of this information to develop program analyses that determine the distribution of data into regions and transform Mercury programs by inserting into them the necessary region operations. We prove the correctness of our program analyses and transformation. To execute the annotated programs, we have implemented runtime support that tackles the two main challenges posed by backtracking. First, backtracking can require regions removed during forward execution to be "resurrected"; and second, any memory allocated during a computation that has been backtracked over must be recovered promptly and without waiting for the regions involved to come to the end of their life. We describe in detail our solution of both these problems. We study in detail how our RBMM system performs on a selection of benchmark programs, including some well-known difficult cases for RBMM. Even with these difficult cases, our RBMM-enabled Mercury system obtains clearly faster runtimes for 15 out of 18 benchmarks compared to the base Mercury system with its Boehm runtime garbage collector, with an average runtime speedup of 24 , and an average reduction in memory requirements of 95 . In fact, our system achieves optimal memory consumption in some programs.
While also used a stack in their inference algorithm, they nevertheless thought that forcing stack discipline on the lifetimes of regions is too strict @cite_13 , and they decoupled region creation and removal, allowing regions to have arbitrarily overlapped lifetimes. Going even further in this direction, Henglein, Makholm, and Niss in @cite_0 proposed an imperative sublanguage on regions. In their system, regions are allowed not only to have arbitrary lifetimes but also to change their bindings. Their regions also contain reference counters that can give their system more flexibility in controlling their lifetimes. The most complete functional programming system with RBMM is the MLKit @cite_12 , which manages storage solely by RBMM. This system, while still using stack discipline for the lifetimes of regions, supports both resetting regions to zero size and runtime garbage collection within regions. Its performance is competitive with other state-of-the-art SML compilers.
@cite_0 @cite_13 @cite_12
2074003683 2040070287
Region-based memory management can be used to control dynamic memory allocations and deallocations safely and efficiently. Existing (direct-style) region systems that statically guarantee region safety---no dereferencing of dangling pointers---are based on refinements of Tofte and Talpin's seminal work on region inference for managing heap memory in stacks of regions.We present a unified Floyd-Hoare Logic inspired region type system for reasoning about and inferring region-based memory management, using a sublanguage of imperative region commands. Our system expresses and performs control-sensitive region management without requiring a stack discipline for allocating and deallocating regions. Furthermore, it captures storage mode analysis and late allocation early deallocation analysis in a single, expressive, unified logical framework. Explicit region aliasing in combination with reference-counted regions provides flexible, context-sensitive early memory deallocation and simultaneously dispenses with the need for an integrated region alias analysis.In this paper we present the design of our region type system, illustrate its practical expressiveness, compare it to existing region analyses, demonstrate how this eliminates the need for previously required source code rewritings for good memory performance, and describe automatic inference of region commands that give consistently better (or at least equally good) memory performance as existing inference techniques. Static memory management replaces runtime garbage collection with compile-time annotations that make all memory allocation and deallocation explicit in a program. We improve upon the Tofte Talpin region-based scheme for compile-time memory management[TT94]. In the Tofte Talpin approach, all values, including closures, are stored in regions. Region lifetimes coincide with lexical scope, thus forming a runtime stack of regions and eliminating the need for garbage collection. We relax the requirement that region lifetimes be lexical. Rather, regions are allocated late and deallocated as early as possible by explicit memory operations. The placement of allocation and deallocation annotations is determined by solving a system of constraints that expresses all possible annotations. Experiments show that our approach reduces memory requirements significantly, in some cases asymptotically.