Region inference

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

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

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

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 1976 the PL/I standard included the AREA data type. 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 Server, which calls them pools, 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.

...
Wikipedia