Region-based memory management
Encyclopedia
In computer science
, region-based memory management is a type of memory management
in which each allocated object is assigned to a region. A region, also called a zone, arena, or memory context, is a collection of allocated objects that can be efficiently deallocated all at once. Like stack allocation, regions facilitate allocation and deallocation of memory with low overhead; but they are more flexible, allowing objects to live longer than the activation record in which they were allocated. In typical implementations, all objects in a region are allocated in a single contiguous range of memory addresses.
As a simple example, consider the following pseudocode which allocates and then deallocates a linked list
data structure:
r ← createRegion
ListNode head ← null
for i from 1 to 1000
newNode ← allocateFromRegion(r, sizeof(ListNode))
newNode.next ← head
head ← newNode
destroyRegion(r)
Although it required many operations to construct the linked list, it can be destroyed quickly in a single operation by destroying the region in which the nodes were allocated. There is no need to traverse the list.
of large blocks of memory; each block should be large enough to serve many allocations. The current block maintains a pointer to the next free position in the block, and if the block is filled, a new one is allocated and added to the list. When the region is deallocated, the next-free-position pointer is reset to the beginning of the first block, and the list of blocks can be reused for the next region to be created. Alternatively, when a region is deallocated, its list of blocks can be appended to a global freelist from which other regions may later allocate new blocks. With this simple scheme, it is not possible to deallocate individual objects in regions.
The overall cost per allocated byte of this scheme is very low; almost all allocations involve only a comparison and an update to the next-free-position pointer. Deallocating a region is a constant-time operation, and is done rarely. Unlike in typical garbage collection
systems, there is no need to tag data with its type.
, which calls them arenas, and the PostgreSQL
database management system, which calls them memory contexts. Like traditional heap allocation, these schemes do not provide memory safety
; it is possible for a programmer to access a region after it is deallocated through a dangling pointer
, or to forget to deallocate a region, causing a memory leak
.
In an early work by Ruggieri and Murtagh, a region is created at the beginning of each function and deallocated at the end. They then use data flow analysis to determine a lifetime for each static allocation expression, and assign it to the youngest region that contains its entire lifetime.
In 1994 this work was generalized in a seminal work by Tofte and Talpin to support type polymorphism
and higher-order function
s in Standard ML
, a functional programming
language, using a different algorithm based on type inference
and the theoretical concepts of polymorphic region types and the region calculus. Their work introduced an extension of the lambda calculus
including regions, adding two constructs:
Due to this syntactic structure, regions are nested, meaning that if r2 is created after r1, it must also be deallocated before r1; the result is a stack of regions. Moreover, regions must be deallocated in the same function in which they are created. These restrictions were relaxed by Aiken et al.
This extended lambda calculus was intended to serve as a provably memory-safe intermediate representation for compiling Standard ML programs into machine code, but building a translator that would produce good results on large programs faced a number of practical limitations which had to be resolved with new analyses, including dealing with recursive calls, tail recursive calls, and eliminating regions which contained only a single value. This work was completed in 1995 and integrated into the ML Kit, a version of ML based on region allocation in place of garbage collection. This permitted a direct comparison between the two on medium-sized test programs, yielding widely varying results ("between 10 times faster and four times slower") depending on how "region-friendly" the program was; compile times, however, were on the order of minutes. The ML Kit was eventually scaled to large applications with two additions: a scheme for separate compilation of modules, and a hybrid technique combining region inference with tracing garbage collection.
Region-based memory management works best when the number of regions is relatively small and each contains many objects; programs that contain many sparse regions will exhibit internal fragmentation, leading to wasted memory and a time overhead for region management. Again, in the presence of region inference this problem can be more difficult to diagnose.
, limiting the overhead of reference counting since references internal to regions don't require counts to be updated when they're modified. Similarly, some mark-region hybrid methods combine tracing garbage collection
with regions; these function by dividing the heap into regions, performing a mark-sweep pass in which any regions containing live objects are marked, and then freeing any unmarked regions. These require continual defragmentation to remain effective.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, region-based memory management is a type of memory management
Memory management
Memory management is the act of managing computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed. This is critical to the computer system.Several...
in which each allocated object is assigned to a region. A region, also called a zone, arena, or memory context, is a collection of allocated objects that can be efficiently deallocated all at once. Like stack allocation, regions facilitate allocation and deallocation of memory with low overhead; but they are more flexible, allowing objects to live longer than the activation record in which they were allocated. In typical implementations, all objects in a region are allocated in a single contiguous range of memory addresses.
As a simple example, consider the following pseudocode which allocates and then deallocates a linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
data structure:
r ← createRegion
ListNode head ← null
for i from 1 to 1000
newNode ← allocateFromRegion(r, sizeof(ListNode))
newNode.next ← head
head ← newNode
destroyRegion(r)
Although it required many operations to construct the linked list, it can be destroyed quickly in a single operation by destroying the region in which the nodes were allocated. There is no need to traverse the list.
Implementation
Simple explicit regions are straightforward to implement; the following description is based on Hanson. Each region is implemented as a linked listLinked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
of large blocks of memory; each block should be large enough to serve many allocations. The current block maintains a pointer to the next free position in the block, and if the block is filled, a new one is allocated and added to the list. When the region is deallocated, the next-free-position pointer is reset to the beginning of the first block, and the list of blocks can be reused for the next region to be created. Alternatively, when a region is deallocated, its list of blocks can be appended to a global freelist from which other regions may later allocate new blocks. With this simple scheme, it is not possible to deallocate individual objects in regions.
The overall cost per allocated byte of this scheme is very low; almost all allocations involve only a comparison and an update to the next-free-position pointer. Deallocating a region is a constant-time operation, and is done rarely. Unlike in typical garbage collection
Garbage collection (computer science)
In computer science, garbage collection is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program...
systems, there is no need to tag data with its type.
History and concepts
The basic concept of regions is very old, first appearing as early as 1967 in Douglas T. Ross's AED Free Storage Package, in which memory was partitioned into a hierarchy of zones; each zone had its own allocator, and a zone could be freed all-at-once, making zones usable as regions. In 1990, Hanson demonstrated that explicit regions in C (which he called arenas) could achieve time performance per allocated byte superior to even the fastest-known heap allocation mechanism. Explicit regions were instrumental in the design of a number of early C-based software projects, including the Apache HTTP ServerApache HTTP Server
The Apache HTTP Server, commonly referred to as Apache , is web server software notable for playing a key role in the initial growth of the World Wide Web. In 2009 it became the first web server software to surpass the 100 million website milestone...
, which calls them arenas, and the PostgreSQL
PostgreSQL
PostgreSQL, often simply Postgres, is an object-relational database management system available for many platforms including Linux, FreeBSD, Solaris, MS Windows and Mac OS X. It is released under the PostgreSQL License, which is an MIT-style license, and is thus free and open source software...
database management system, which calls them memory contexts. Like traditional heap allocation, these schemes do not provide memory safety
Memory safety
Memory safety is a concern in software development that aims to avoid software bugs that cause security vulnerabilities dealing with random-access memory access, such as buffer overflows and dangling pointers....
; it is possible for a programmer to access a region after it is deallocated through a dangling pointer
Dangling pointer
Dangling pointers and wild pointers in computer programming are pointers that do not point to a valid object of the appropriate type. These are special cases of memory safety violations....
, or to forget to deallocate a region, causing a memory leak
Memory leak
A memory leak, in computer science , occurs when a computer program consumes memory but is unable to release it back to the operating system. In object-oriented programming, a memory leak happens when an object is stored in memory but cannot be accessed by the running code...
.
Region inference
In 1988, researchers began investigating how to use regions for safe memory allocation by introducing the concept of region inference, where the creation and deallocation of regions, as well as the assignment of individual static allocation expressions to particular regions, is inserted by the compiler at compile-time. The compiler is able to do this in such a way that it can guarantee dangling pointers and leaks do not occur.In an early work by Ruggieri and Murtagh, a region is created at the beginning of each function and deallocated at the end. They then use data flow analysis to determine a lifetime for each static allocation expression, and assign it to the youngest region that contains its entire lifetime.
In 1994 this work was generalized in a seminal work by Tofte and Talpin to support type polymorphism
Type polymorphism
In computer science, polymorphism is a programming language feature that allows values of different data types to be handled using a uniform interface. The concept of parametric polymorphism applies to both data types and functions...
and higher-order function
Higher-order function
In mathematics and computer science, higher-order functions, functional forms, or functionals are functions which do at least one of the following:*take one or more functions as an input*output a function...
s in Standard ML
Standard ML
Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
, a functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
language, using a different algorithm based on type inference
Type inference
Type inference refers to the automatic deduction of the type of an expression in a programming language. If some, but not all, type annotations are already present it is referred to as type reconstruction....
and the theoretical concepts of polymorphic region types and the region calculus. Their work introduced an extension of the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
including regions, adding two constructs:
- e1 at ρ: Compute the result of the expression e1 and store it in region ρ;
- letregion ρ in e2 end: Create a region and bind it to ρ; evaluate e2; then deallocate the region.
Due to this syntactic structure, regions are nested, meaning that if r2 is created after r1, it must also be deallocated before r1; the result is a stack of regions. Moreover, regions must be deallocated in the same function in which they are created. These restrictions were relaxed by Aiken et al.
This extended lambda calculus was intended to serve as a provably memory-safe intermediate representation for compiling Standard ML programs into machine code, but building a translator that would produce good results on large programs faced a number of practical limitations which had to be resolved with new analyses, including dealing with recursive calls, tail recursive calls, and eliminating regions which contained only a single value. This work was completed in 1995 and integrated into the ML Kit, a version of ML based on region allocation in place of garbage collection. This permitted a direct comparison between the two on medium-sized test programs, yielding widely varying results ("between 10 times faster and four times slower") depending on how "region-friendly" the program was; compile times, however, were on the order of minutes. The ML Kit was eventually scaled to large applications with two additions: a scheme for separate compilation of modules, and a hybrid technique combining region inference with tracing garbage collection.
Generalization to new language environments
Following the development of ML Kit, regions began to be generalized to other language environments:- Various extensions to the C programming language:
- The safe C dialect Cyclone, which among many other features adds support for explicit regions, and evaluates the impact of migrating existing C applications to use them.
- An extension to C called RC was implemented that uses explicitly-managed regions, but also uses reference countingReference countingIn computer science, reference counting is a technique of storing the number of references, pointers, or handles to a resource such as an object, block of memory, disk space or other resource...
on regions to guarantee memory safety by ensuring that no region is freed prematurely. Regions decrease the overhead of reference counting, since references internal to regions don't require counts to be updated when they're modified. RC includes an explicit static type system for regions that allows some reference count updates to be eliminated. - A restriction of C called Control-C limits programs to use regions (and only a single region at a time), as part of its design to statically ensure memory safety.
- Regions were implemented for a subset of Java, and became a critical component of memory management in Real time JavaReal time JavaReal time Java is a catch-all term for a combination of technologies that allows programmers to write programs that meet the demands of Real time systems in the Java programming language....
, which combines them with ownership types to demonstrate object encapsulation and eliminate runtime checks on region deallocation. More recently, a semi-automatic system was proposed for inferring regions in embedded real-time Java applications, combining a compile-time static analysis, a runtime region allocation policy, and programmer hints. Regions are a good fit for real-time computingReal-time computingIn computer science, real-time computing , or reactive computing, is the study of hardware and software systems that are subject to a "real-time constraint"— e.g. operational deadlines from event to system response. Real-time programs must guarantee response within strict time constraints...
because their time overhead is statically predictable, without the complexity of incremental garbage collection. - They were implemented for the logic programmingLogic programmingLogic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
languages PrologPrologProlog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
and MercuryMercury programming languageMercury is a functional logic programming language geared towards real-world applications. It is developed at the University Of Melbourne Computer Science department under the supervision of Zoltan Somogyi. The first version was developed by Fergus Henderson, Thomas Conway and Zoltan Somogyi and...
by extending Tofte and Talpin's region inference model to support backtracking and cuts.
Disadvantages
Systems using regions may experience issues where regions become very large before they are deallocated and contain a large proportion of dead data; these are commonly called "leaks" (even though they are eventually freed). Eliminating leaks may involve restructuring the program, typically by introducing new, shorter-lifetime regions. Debugging this type of problem is especially difficult in systems using region inference, where the programmer must understand the underlying inference algorithm, or examine the verbose intermediate representation, to diagnose the issue. Tracing garbage collectors are more effective at deallocating this type of data in a timely manner without program changes; this was one justification for hybrid region/GC systems. On the other hand, tracing garbage collectors can also exhibit subtle leaks, if references are retained to data which will never be used again.Region-based memory management works best when the number of regions is relatively small and each contains many objects; programs that contain many sparse regions will exhibit internal fragmentation, leading to wasted memory and a time overhead for region management. Again, in the presence of region inference this problem can be more difficult to diagnose.
Hybrid methods
As mentioned above, RC uses a hybrid of regions and reference countingReference counting
In computer science, reference counting is a technique of storing the number of references, pointers, or handles to a resource such as an object, block of memory, disk space or other resource...
, limiting the overhead of reference counting since references internal to regions don't require counts to be updated when they're modified. Similarly, some mark-region hybrid methods combine tracing garbage collection
Garbage collection (computer science)
In computer science, garbage collection is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program...
with regions; these function by dividing the heap into regions, performing a mark-sweep pass in which any regions containing live objects are marked, and then freeing any unmarked regions. These require continual defragmentation to remain effective.