World Library  
Flag as Inappropriate
Email this Article

Region-based memory management

Article Id: WHEBN0026294208
Reproduction Date:

Title: Region-based memory management  
Author: World Heritage Encyclopedia
Language: English
Subject: Memory management, ParaSail (programming language), International Symposium on Memory Management, Strong reference, Lapsed listener problem
Collection: Memory Management
Publisher: World Heritage Encyclopedia

Region-based memory management

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, area, 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.


  • Example 1
  • Implementation 2
  • History and concepts 3
    • Region inference 3.1
    • Generalization to new language environments 3.2
  • Disadvantages 4
  • Hybrid methods 5
  • References 6


As a simple example, consider the following C code which allocates and then deallocates a linked list data structure:

Region *r = createRegion();
ListNode *head = NULL;
for (int i = 1; i <= 1000; i++) {
    ListNode newNode = allocateFromRegion(r, sizeof(ListNode));
    newNode->next = head;
    head = newNode;
// ...
// (use list here)
// ...

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.


Simple explicit regions are straightforward to implement; the following description is based on Hanson.[1] Each region is implemented as a linked 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.

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.[2] In 1976 the memory leak.

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,[5] 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 functions 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.[6][7] Their work introduced an extension of the 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.[8]

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[9] 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.[10] 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.[11][12]

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.[13][14][15]
    • An extension to C called RC[16] was implemented that uses explicitly-managed regions, but also uses reference counting on regions to guarantee memory safety by ensuring that no region is freed prematurely.[17][18] 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.[19]
    • 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.[20]
  • Regions were implemented for a subset of Java,[21] and became a critical component of memory management in Real time Java, which combines them with ownership types to demonstrate object encapsulation and eliminate runtime checks on region deallocation.[22][23][24] 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.[25][26] Regions are a good fit for real-time computing because their time overhead is statically predictable, without the complexity of incremental garbage collection.
  • They were implemented for the logic programming languages Prolog[27][28] and Mercury[29][30] by extending Tofte and Talpin's region inference model to support backtracking and cuts.
  • Region-based storage management is used throughout the parallel programming language ParaSail. Due to the lack of explicit pointers in ParaSail,[31] there is no need for reference counting.


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.[11] 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 counting, 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.[32]


  1. ^ a b Hanson, David R. (1989). "Fast allocation and deallocation of memory based on object lifetimes". Software: Practice and Experience 20 (1): 5–12.  
  2. ^ Ross, Douglas (1967). "The AED free storage package". Communications of the ACM 10 (8): 481–492.  
  3. ^ American National Standards Institute, inc. (1976). American National Standard Programming Language PL/I. 
  4. ^ 2010 PostgreSQL Global Development Group (1996). "Section 41.3: Memory Management". PostgreSQL 8.2.15 Documentation. Retrieved 22 February 2010. 
  5. ^ Ruggieri, Cristina; Murtagh, Thomas P. (1988). "POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages". New York, NY, USA: ACM.  
  6. ^ Tofte, Mads; Jean-Pierre Talpin (1993). A Theory of Stack Allocation in Polymorphically Typed Languages (Technical report). Department of Computer Science, Copenhagen University. 93/15.  On Citeseer
  7. ^  
  8. ^ Aiken, Alex; Manuel Fähndrich, Raph Levien (1995). Better Static Memory Management: Improving Region-Based Analysis of Higher-Order Languages (Technical report). EECS Department, University of California, Berkeley. UCB/CSD-95-866.  On Citeseer
  9. ^  
  10. ^ Tofte, Mads; Birkedal, Lars; Elsman, Martin; Hallenberg, Niels (2004). "A Retrospective on Region-Based Memory Management". Higher Order Symbolic Computing (Hingham, MA, USA: Kluwer Academic Publishers) 17 (3): 245–265.  
  11. ^ a b Hallenberg, Niels; Elsman, Martin; Tofte, Mads (2003). "Combining region inference and garbage collection". SIGPLAN Notices (New York, NY, USA: ACM) 37 (5): 141–152.  
  12. ^ Elsman, Martin (2003). "Garbage collection safety for region-based memory management". SIGPLAN Notices (New York, NY, USA: ACM) 38 (3): 123–134.  
  13. ^ "Cyclone: Introduction to Regions". Cyclone User Manual. Retrieved 22 February 2010. 
  14. ^ Grossman, Dan; Morrisett, Greg; Jim, Trevor; Hicks, Michael; Wang, Yanling (2002). "Region-based memory management in cyclone". SIGPLAN Notices 37 (5): 282–293.  
  15. ^ Hicks, Michael;  
  16. ^ Gay, David (1999). "RC - Safe, region-based memory-management for C". David Gay's homepage. Intel Labs Berkeley. Retrieved 22 February 2010. 
  17. ^  
  18. ^ Gay, David Edward (2001). Memory management with explicit regions (PhD in Computer Science thesis). University of California at Berkeley. Retrieved 20 February 2010. 
  19. ^  
  20. ^ Kowshik, Sumant; Dhurjati, Dinakar; Adve, Vikram (2002). "CASES '02: Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems". New York, NY, USA: ACM. pp. 288–297.  
  21. ^ Christiansen, Morten V. (1998). Region-based memory management in Java (Masters in Computer Science thesis). Department of Computer Science (DIKU), University of Copenhagen. Retrieved 20 February 2010. 
  22. ^ Beebee, William S.; Rinard, Martin C. (2001). "EMSOFT '01: Proceedings of the First International Workshop on Embedded Software". London, UK: Springer-Verlag. pp. 289–305.  
  23. ^ Sălcianu, Alexandru; Chandrasekhar Boyapati, William Beebee, Jr., Martin Rinard (2003). A type system for safe region-based memory management in Real-Time Java (Technical report). MIT Laboratory for Computer Science. MIT-LCS-TR-869. 
  24. ^  
  25. ^  
  26. ^  
  27. ^ Makholm, Henning (2000). Region-based memory management in Prolog (Masters in Computer Science thesis). University of Copenhagen, Denmark. Retrieved 20 February 2010. 
  28. ^ Makholm, Henning (2000). "ISMM '00: Proceedings of the 2nd international symposium on Memory management". New York, NY, USA: ACM. pp. 25–34.  
  29. ^  
  30. ^  
  31. ^ Taft, Tucker (2012). "A Pointer-Free path to Object Oriented Parallel Programming". ParaSail blog. Retrieved 14 September 2012. 
  32. ^  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.