Region-based memory management

Last updated

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.

Contents

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(inti=1;i<=1000;i++){ListNode*newNode=allocateFromRegion(r,sizeof(ListNode));newNode->next=head;head=newNode;}// ...// (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. [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 allocated region. 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 either case of 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 PL/I standard included the AREA data type. [3] In 1990, Hanson demonstrated that explicit regions in C (which he called arenas[ clarification needed ]) could achieve time performance per allocated byte superior to even the fastest-known heap allocation mechanism. [1] Explicit regions were instrumental in the design some early C-based software projects, including the Apache HTTP Server, which calls them pools, and the PostgreSQL database management system, which calls them memory contexts. [4] 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.

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 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:

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. [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]

Related Research Articles

<span class="mw-page-title-main">Garbage collection (computer science)</span> Form of automatic memory management

In computer science, garbage collection (GC) is a form of automatic memory management. The garbage collector attempts to reclaim memory that was allocated by the program, but is no longer referenced; such memory is called garbage. Garbage collection was invented by American computer scientist John McCarthy around 1959 to simplify manual memory management in Lisp.

In computer science, reference counting is a programming technique of storing the number of references, pointers, or handles to a resource, such as an object, a block of memory, disk space, and others.

Java and C++ are two prominent object-oriented programming languages. By many language popularity metrics, the two languages have dominated object-oriented and high-performance software development for much of the 21st century, and are often directly compared and contrasted. Java's syntax was based on C/C++.

NewtonScript is a prototype-based programming language created to write programs for the Newton platform. It is heavily influenced by the Self programming language, but modified to be more suited to needs of mobile and embedded devices.

<span class="mw-page-title-main">Memory management</span> Computer memory management methodology

Memory management is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when no longer needed. This is critical to any advanced computer system where more than a single process might be underway at any time.

In object-oriented programming (OOP), the object lifetime of an object is the time between an object's creation and its destruction. Rules for object lifetime vary significantly between languages, in some cases between implementations of a given language, and lifetime of a particular object may vary from one run of the program to another.

In computer programming, tracing garbage collection is a form of automatic memory management that consists of determining which objects should be deallocated by tracing which objects are reachable by a chain of references from certain "root" objects, and considering the rest as "garbage" and collecting them. Tracing is the most common type of garbage collection – so much so that "garbage collection" often refers to the tracing method, rather than others such as reference counting – and there are a large number of algorithms used in implementation.

In computer science, type safety and type soundness are the extent to which a programming language discourages or prevents type errors. Type safety is sometimes alternatively considered to be a property of facilities of a computer language; that is, some facilities are type-safe and their usage will not result in type errors, while other facilities in the same language may be type-unsafe and a program using them may encounter type errors. The behaviors classified as type errors by a given programming language are usually those that result from attempts to perform operations on values that are not of the appropriate data type, e.g., adding a string to an integer when there's no definition on how to handle this case. This classification is partly based on opinion.

SIGPLAN is the Association for Computing Machinery's Special Interest Group on programming languages.

In the C++ programming language, new and delete are a pair of language constructs that perform dynamic memory allocation, object construction and object destruction.

In computer programming, unreachable memory is a block of dynamically allocated memory where the program that allocated the memory no longer has any reachable pointer that refers to it. Similarly, an unreachable object is a dynamically allocated object that has no reachable reference to it. Informally, unreachable memory is dynamic memory that the program cannot reach directly, nor get to by starting at an object it can reach directly, and then following a chain of pointer references.

In computer science, garbage includes data, objects, or other regions of the memory of a computer system, which will not be used in any future computation by the system, or by a program running on it. Because every computer system has a finite amount of memory, and most software produces garbage, it is frequently necessary to deallocate memory that is occupied by garbage and return it to the heap, or memory pool, for reuse.

In computer science, manual memory management refers to the usage of manual instructions by the programmer to identify and deallocate unused objects, or garbage. Up until the mid-1990s, the majority of programming languages used in industry supported manual memory management, though garbage collection has existed since 1959, when it was introduced with Lisp. Today, however, languages with garbage collection such as Java are increasingly popular and the languages Objective-C and Swift provide similar functionality through Automatic Reference Counting. The main manually managed languages still in widespread use today are C and C++ – see C dynamic memory allocation.

In compiler optimization, escape analysis is a method for determining the dynamic scope of pointers – where in the program a pointer can be accessed. It is related to pointer analysis and shape analysis.

In computer science, pointer analysis, or points-to analysis, is a static code analysis technique that establishes which pointers, or heap references, can point to which variables, or storage locations. It is often a component of more complex analyses such as escape analysis. A closely related technique is shape analysis.

In computer science, a mark–compact algorithm is a type of garbage collection algorithm used to reclaim unreachable memory. Mark–compact algorithms can be regarded as a combination of the mark–sweep algorithm and Cheney's copying algorithm. First, reachable objects are marked, then a compacting step relocates the reachable (marked) objects towards the beginning of the heap area. Compacting garbage collection is used by modern JVMs, Microsoft's Common Language Runtime and by the Glasgow Haskell Compiler.

Memory safety is the state of being protected from various software bugs and security vulnerabilities when dealing with memory access, such as buffer overflows and dangling pointers. For example, Java is said to be memory-safe because its runtime error detection checks array bounds and pointer dereferences. In contrast, C and C++ allow arbitrary pointer arithmetic with pointers implemented as direct memory addresses with no provision for bounds checking, and thus are potentially memory-unsafe.

Mads Tofte is a Danish computer scientist who has contributed in particular to functional programming and the Standard ML programming language.

In computer science, polymorphic recursion refers to a recursive parametrically polymorphic function where the type parameter changes with each recursive invocation made, instead of staying constant. Type inference for polymorphic recursion is equivalent to semi-unification and therefore undecidable and requires the use of a semi-algorithm or programmer-supplied type annotations.

<span class="mw-page-title-main">Kathryn S. McKinley</span> American computer scientist

Kathryn S. McKinley is an American computer scientist noted for her research on compilers, runtime systems, and computer architecture. She is also known for her leadership in broadening participation in computing. McKinley was co-chair of CRA-W from 2011 to 2014.

References

  1. 1 2 Hanson, David R. (1989). "Fast allocation and deallocation of memory based on object lifetimes". Software: Practice and Experience. 20 (1): 5–12. doi:10.1002/spe.4380200104. S2CID   8960945. Archived from the original on 2012-10-20.
  2. ↑ Ross, Douglas (1967). "The AED free storage package". Communications of the ACM. 10 (8): 481–492. doi: 10.1145/363534.363546 . S2CID   6572689.
  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.{{cite web}}: CS1 maint: numeric names: authors list (link)
  5. ↑ Ruggieri, Cristina; Murtagh, Thomas P. (1988). "Lifetime analysis of dynamically allocated objects". POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY, USA: ACM. doi: 10.1145/73560.73585 . Retrieved 22 February 2010.
  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. ↑ Tofte, Mads; Talpin, Jean-Pierre (1994). "Implementation of the Typed Call-by-Value λ-calculus using a Stack of Regions". POPL '94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY, USA: ACM. pp. 188–201. doi: 10.1145/174675.177855 . ISBN   0-89791-636-0 . Retrieved 15 April 2014.
  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. ↑ Birkedal, Lars; Tofte, Mads; Vejlstrup, Magnus (1996). "From region inference to von Neumann machines via region representation inference". POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY, USA: ACM. pp. 171–183. doi: 10.1145/237721.237771 . ISBN   0-89791-769-3 . Retrieved 22 February 2010.
  10. ↑ Tofte, Mads; Birkedal, Lars; Elsman, Martin; Hallenberg, Niels (2004). "A Retrospective on Region-Based Memory Management". Higher Order Symbolic Computing. 17 (3): 245–265. doi: 10.1023/B:LISP.0000029446.78563.a4 . ISSN   1388-3690.
  11. 1 2 Hallenberg, Niels; Elsman, Martin; Tofte, Mads (2003). "Combining region inference and garbage collection". SIGPLAN Notices. 37 (5): 141–152. doi:10.1145/543552.512547. ISSN   0362-1340.
  12. ↑ Elsman, Martin (2003). "Garbage collection safety for region-based memory management". SIGPLAN Notices. 38 (3): 123–134. CiteSeerX   10.1.1.57.8914 . doi:10.1145/640136.604190. ISSN   0362-1340.
  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. doi:10.1145/543552.512563.
  15. ↑ Hicks, Michael; Morrisett, Greg; Grossman, Dan (2004). "Experience with safe manual memory-management in cyclone". ISMM '04: Proceedings of the 4th international symposium on Memory management. New York, NY, USA: ACM. pp. 73–84. doi:10.1145/1029873.1029883. ISBN   1-58113-945-4 . Retrieved 22 February 2010.
  16. ↑ Gay, David (1999). "RC - Safe, region-based memory-management for C". David Gay's homepage. Intel Labs Berkeley. Archived from the original on February 26, 2009. Retrieved 22 February 2010.
  17. ↑ Gay, David; Aiken, Alex (1998). "Memory management with explicit regions". PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation. New York, NY, USA: ACM. pp. 313–323. doi:10.1145/277650.277748. ISBN   0-89791-987-4 . Retrieved 22 February 2010.
  18. ↑ Gay, David Edward (2001). Memory management with explicit regions (PDF) (PhD in Computer Science thesis). University of California at Berkeley. Retrieved 20 February 2010.
  19. ↑ Gay, David; Aiken, Alex (2001). "Language support for regions". SIGPLAN Notices. 36 (5): 70–80. CiteSeerX   10.1.1.650.721 . doi:10.1145/381694.378815. ISSN   0362-1340.
  20. ↑ Kowshik, Sumant; Dhurjati, Dinakar; Adve, Vikram (2002). "Ensuring code safety without runtime checks for real-time control systems". CASES '02: Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems. New York, NY, USA: ACM. pp. 288–297. doi:10.1145/581630.581678. ISBN   1-58113-575-0 . Retrieved 22 February 2010.
  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.[ permanent dead link ]
  22. ↑ Beebee, William S.; Rinard, Martin C. (2001). "An Implementation of Scoped Memory for Real-Time Java". EMSOFT '01: Proceedings of the First International Workshop on Embedded Software. London, UK: Springer-Verlag. pp. 289–305. ISBN   3-540-42673-6 . Retrieved 22 February 2010.[ permanent dead link ]
  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 (PDF) (Technical report). MIT Laboratory for Computer Science. MIT-LCS-TR-869.{{cite tech report}}: CS1 maint: multiple names: authors list (link)
  24. ↑ Boyapati, Chandrasekhar; Salcianu, Alexandru; Beebee, William Jr. (2003). "Ownership types for safe region-based memory management in real-time Java". PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation. New York, NY, USA: ACM. pp. 324–337. doi:10.1145/781131.781168. ISBN   1-58113-662-5 . Retrieved 22 February 2010.
  25. ↑ Nahkli, Chaker; Rippert, Christophe; Salagnac, Guillaume; Yovine, Sergio (2007). "Efficient region-based memory management for resource-limited real-time embedded systems" (PDF). Proceedings of "Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS'2006)". Retrieved 22 February 2010.
  26. ↑ Salagnac, Guillaume; Rippert, Christophe (2007). "Semi-Automatic Region-Based Memory Management for Real-Time Java Embedded Systems". RTCSA '07: Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Washington, DC, USA: IEEE Computer Society. pp. 73–80. doi:10.1109/RTCSA.2007.67. ISBN   978-0-7695-2975-2.
  27. ↑ Makholm, Henning (2000). Region-based memory management in Prolog (PDF) (Masters in Computer Science thesis). University of Copenhagen, Denmark. Archived from the original (PDF) on 5 June 2011. Retrieved 20 February 2010.
  28. ↑ Makholm, Henning (2000). "A region-based memory manager for prolog". ISMM '00: Proceedings of the 2nd international symposium on Memory management. New York, NY, USA: ACM. pp. 25–34. doi:10.1145/362422.362434. ISBN   1-58113-263-8 . Retrieved 22 February 2010.
  29. ↑ Phan, Quan; Janssens, Gerda (2007). Logic Programming. Lecture Notes in Computer Science. Vol. 4670/2007. Springer Berlin / Heidelberg. pp. 317–332. doi:10.1007/978-3-540-74610-2. ISBN   978-3-540-74608-9. ISSN   1611-3349.
  30. ↑ Phan, Quan; Somogyi, Zoltan (2008). "Runtime support for region-based memory management in Mercury". ISMM '08: Proceedings of the 7th international symposium on Memory management. New York, NY, USA: ACM. pp. 61–70. doi:10.1145/1375634.1375644. ISBN   978-1-60558-134-7 . Retrieved 15 April 2014.
  31. ↑ Taft, Tucker (2012). "A Pointer-Free path to Object Oriented Parallel Programming". ParaSail blog. Retrieved 14 September 2012.
  32. ↑ Blackburn, Stephen M.; McKinley, Kathryn S. (2008). "Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance". PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation. New York, NY, USA: ACM. pp. 22–32. doi:10.1145/1375581.1375586. ISBN   978-1-59593-860-2 . Retrieved 15 April 2014.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.