GetWiki

{{Short description|Memory allocation scheme}}{{Use American English|date = February 2019}}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 reallocated or deallocated all at once. Memory allocators using region-based managements are often called area allocators, and when they work by only “bumping” a single pointer, as bump allocators.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 stack frame in which they were allocated. In typical implementations, all objects in a region are allocated in a single contiguous range of memory addresses, similarly to how stack frames are typically allocated.

Example

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 next = head; }// ...// (use list here)// ...destroyRegion(r);Although it required many operations to construct the linked list, it can be quickly deallocated 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 the work of Hanson.JOURNAL, Hanson, David R., 1989, Fast allocation and deallocation of memory based on object lifetimes, Software: Practice and Experience, 20, 1, 5–12,www3.interscience.wiley.com/journal/113446436/abstract?CRETRY=1&SRETRY=0,www3.interscience.wiley.com/journal/113446436/abstract?CRETRY=1&SRETRY=0," title="archive.today/20121020025006www3.interscience.wiley.com/journal/113446436/abstract?CRETRY=1&SRETRY=0,">archive.today/20121020025006www3.interscience.wiley.com/journal/113446436/abstract?CRETRY=1&SRETRY=0, dead, 2012-10-20, 10.1002/spe.4380200104, 8960945, 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.JOURNAL, Ross, Douglas, 1967, The AED free storage package, Communications of the ACM, 10, 8, 481–492, 10.1145/363534.363546, 6572689, free, WEB,www.postgresql.org/docs/8.2/static/spi-memory.html, Section 41.3: Memory Management, 2010 PostgreSQL Global Development Group, 1996, PostgreSQL 8.2.15 Documentation, 22 February 2010,

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,CONFERENCE,portal.acm.org/citation.cfm?id=73585, Lifetime analysis of dynamically allocated objects, Ruggieri, Cristina, Murtagh, Thomas P., 1988, POPL ‘88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM, 22 February 2010, New York, NY, USA, 10.1145/73560.73585, free, 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.TECH REPORT, A Theory of Stack Allocation in Polymorphically Typed Languages, Tofte, Mads, Jean-Pierre Talpin, 93/15, Department of Computer Science, Copenhagen University, 1993, On CiteseerCONFERENCE, Implementation of the Typed Call-by-Value λ-calculus using a Stack of Regions, Tofte, Mads, Mads Tofte, Talpin, Jean-Pierre, Jean-Pierre Talpin, 1994, POPL ‘94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM, New York, NY, USA, 188–201, 0-89791-636-0, 10.1145/174675.177855,books.google.com/books?id=k-zHGxDf-HgC&q=POPL+%2794:+Proceedings+of+the+21st+ACM+SIGPLAN-SIGACT+symposium+on+Principles+of+programming+languages, 15 April 2014, free,

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.TECH REPORT, Better Static Memory Management: Improving Region-Based Analysis of Higher-Order Languages, Aiken, Alex, Manuel Fähndrich, Raph Levien, UCB/CSD-95-866, EECS Department, University of California, Berkeley, 1995, On CiteseerThis 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 calls, and eliminating regions which contained only a single value. This work was completed in 1995CONFERENCE,portal.acm.org/citation.cfm?id=237721.237771, From region inference to von Neumann machines via region representation inference, Birkedal, Lars, Lars Birkedal, Tofte, Mads, Mads Tofte, Vejlstrup, Magnus, Magnus Vejlstrup, 1996, POPL ‘96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM, 22 February 2010, 171–183, New York, NY, USA, 0-89791-769-3, 10.1145/237721.237771, free, JOURNAL, Tofte, Mads, Birkedal, Lars, Elsman, Martin, Hallenberg, Niels, 2004, A Retrospective on Region-Based Memory Management, Higher Order Symbolic Computing, 17, 3, 245–265, 1388-3690, 10.1023/B:LISP.0000029446.78563.a4, free, JOURNAL, Hallenberg, Niels, Elsman, Martin, Tofte, Mads, 2003, Combining region inference and garbage collection, SIGPLAN Notices, 37, 5, 141–152, 0362-1340, 10.1145/543552.512547, JOURNAL, Elsman, Martin, 2003, Garbage collection safety for region-based memory management, SIGPLAN Notices, 38, 3, 123–134, 0362-1340, 10.1145/640136.604190, 10.1.1.57.8914,

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.

WEB,cyclone.thelanguage.org/wiki/Introduction%20to%20Regions, Cyclone: Introduction to Regions, Cyclone User Manual, 22 February 2010, JOURNAL, Grossman, Dan, Morrisett, Greg, Jim, Trevor, Hicks, Michael, Wang, Yanling, 2002, Region-based memory management in cyclone, SIGPLAN Notices, 37, 5, 282–293, 10.1145/543552.512563, CONFERENCE,portal.acm.org/citation.cfm?id=1029883, Experience with safe manual memory-management in cyclone, Hicks, Michael, Morrisett, Greg, Greg Morrisett, Grossman, Dan, 2004, ACM, New York, NY, USA, 22 February 2010, ISMM ‘04: Proceedings of the 4th international symposium on Memory management, 73–84, 1-58113-945-4, 10.1145/1029873.1029883,

• An extension to C called RCWEB,berkeley.intel-research.net/dgay/rc/index.html, RC - Safe, region-based memory-management for C, Gay, David, 1999, David Gay’s homepage, Intel Labs Berkeley, 22 February 2010, dead,berkeley.intel-research.net/dgay/rc/index.html," title="web.archive.org/web/20090226070550berkeley.intel-research.net/dgay/rc/index.html,">web.archive.org/web/20090226070550berkeley.intel-research.net/dgay/rc/index.html, February 26, 2009,

CONFERENCE,portal.acm.org/citation.cfm?id=277650.277748, Memory management with explicit regions, Gay, David, David Gay (mathematician), Aiken, Alex, Alex Aiken, 1998, PLDI ‘98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, ACM, New York, NY, USA, 22 February 2010, 313–323, 0-89791-987-4, 10.1145/277650.277748, THESIS, PhD in Computer Science, Memory management with explicit regions,theory.stanford.edu/~aiken/publications/theses/gay.pdf, Gay, David Edward, 2001, University of California at Berkeley, 20 February 2010, JOURNAL, Language support for regions, Gay, David, David Gay (mathematician), Aiken, Alex, Alex Aiken, 2001, SIGPLAN Notices, 36, 5, 70–80, 0362-1340, 10.1145/381694.378815, 10.1.1.650.721,

• 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.

CONFERENCE,portal.acm.org/citation.cfm?id=581678, Ensuring code safety without runtime checks for real-time control systems, Kowshik, Sumant, Dhurjati, Dinakar, Adve, Vikram, 2002, ACM, New York, NY, USA, 22 February 2010, CASES ‘02: Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, 288–297, 1-58113-575-0, 10.1145/581630.581678,

• Regions were implemented for a subset of Java,

THESIS, Masters in Computer Science, Region-based memory management in Java,ftp.diku.dk/diku/semantics/papers/D-395.ps.gz, Christiansen, Morten V., 1998, Department of Computer Science (DIKU), University of Copenhagen, 20 February 2010, {{dead link|date=April 2018 |bot=InternetArchiveBot |fix-attempted=yes }} TECH REPORT, A type system for safe region-based memory management in Real-Time Java, Sălcianu, Alexandru, Chandrasekhar Boyapati, William Beebee, Jr., Martin Rinard, MIT-LCS-TR-869, MIT Laboratory for Computer Science, 2003,people.csail.mit.edu/rinard/techreport/MIT-LCS-TR-869.pdf, CONFERENCE,portal.acm.org/citation.cfm?id=781168, Ownership types for safe region-based memory management in real-time Java, Boyapati, Chandrasekhar, Chandrasekhar Boyapati, Salcianu, Alexandru, Alexandru Salcianu, Beebee, William Jr., William Beebee, Jr., 2003, ACM, New York, NY, USA, 22 February 2010, PLDI ‘03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, 324–337, 1-58113-662-5, 10.1145/781131.781168, CONFERENCE,hal.inria.fr/docs/00/30/96/88/PDF/06-Salagnac-ICOOOLPS.pdf, Efficient region-based memory management for resource-limited real-time embedded systems, Nahkli, Chaker, Guillaume Salagnac, Rippert, Christophe, Christophe Rippert, Salagnac, Guillaume, Guillaume Salagnac, Yovine, Sergio, 2007, 22 February 2010, Proceedings of “Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS’2006)”, CONFERENCE, Semi-Automatic Region-Based Memory Management for Real-Time Java Embedded Systems, Salagnac, Guillaume, Guillaume Salagnac, Rippert, Christophe, Christophe Rippert, 2007, IEEE Computer Society, Washington, DC, USA, RTCSA ‘07: Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 73–80, 978-0-7695-2975-2, 10.1109/RTCSA.2007.67,

• They were implemented for the logic programming languages Prolog

THESIS, Masters in Computer Science, Region-based memory management in Prolog,www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/00-09.pdf, Makholm, Henning, 2000, University of Copenhagen, Denmark, 20 February 2010, dead,www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/00-09.pdf," title="web.archive.org/web/20110605004034www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/00-09.pdf,">web.archive.org/web/20110605004034www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/00-09.pdf, 5 June 2011, CONFERENCE,portal.acm.org/citation.cfm?id=362422.362434, Makholm, Henning, A region-based memory manager for prolog, 2000, ACM, New York, NY, USA, 22 February 2010, ISMM ‘00: Proceedings of the 2nd international symposium on Memory management, 25–34, 1-58113-263-8, 10.1145/362422.362434, BOOK, Phan, Quan, Quan Phan, Janssens, Gerda, Logic Programming, Lecture Notes in Computer Science, Gerda Janssens, 2007, Springer Berlin / Heidelberg, 4670/2007, 317–332, 1611-3349, 10.1007/978-3-540-74610-2, 978-3-540-74608-9, CONFERENCE, Runtime support for region-based memory management in Mercury, Phan, Quan, Quan Phan, Somogyi, Zoltan, Zoltan Somogyi, 2008, ACM, New York, NY, USA, ISMM ‘08: Proceedings of the 7th international symposium on Memory management, 61–70, 978-1-60558-134-7, 10.1145/1375634.1375644,dl.acm.org/citation.cfm?doid=1375634.1375644, 15 April 2014,

• Region-based storage management is used throughout the parallel programming language ParaSail. Due to the lack of explicit pointers in ParaSail,

WEB,parasail-programming-language.blogspot.com/2012/08/a-pointer-free-path-to-object-oriented.html, A Pointer-Free path to Object Oriented Parallel Programming, Taft, Tucker, 2012, ParaSail blog, 14 September 2012, there is no need for reference counting.

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 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.CONFERENCE, Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance, Blackburn, Stephen M., Stephen M. Blackburn, McKinley, Kathryn S., Kathryn McKinley, 2008, ACM, New York, NY, USA, PLDI ‘08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, 22–32, 978-1-59593-860-2, 10.1145/1375581.1375586,dl.acm.org/citation.cfm?doid=1375581.1375586, 15 April 2014,

References

{{reflist|30em}}{{Memory management navbox}}