Memory management in Unobtainabol

It’s been a while since I posted about Unobtainabol, the perfect (and therefore non-existent) programming language so here are some thoughts on perfect memory management.

There are two major categories of memory management: manual and automatic. Manual memory management is when the programmer does explicit allocation and freeing of memory as in C++. Automatic memory management includes garbage collection, reference counting, and other techniques where the computer does the memory management for you.

It is commonly believed that manual memory management is faster than automatic memory management, but that’s not true in general; some programs work better with manual memory management and some work better with automatic memory management. What is true is that there are certain use cases where a specially tailored manual memory management system can be much faster than a generic automatic system.

So should Unobtainabol have both manual and automatic memory management? Well, that’s a problem because Unobtainabol is a safe language--there is no undefined behavior--and I don’t know of any way to do safe manual memory management, except by adding a level of indirection and other overheads that would greatly reduce the benefits.

So instead, Unobtainabol has specially tailored automatic memory management that can be used to improve the performance of programs that do not do well with the generic memory management system.

Traditional Regions

There are two forms of automatic memory management that are used in practically every programming language and have been for decades because they are so simple, effective, and efficient. The first form is that all of the memory associated with a running process is reclaimed when the process exits. There is no need for the programmer to manually delete all of the objects allocated in the program; when the program exits, they will automatically be reclaimed by the operating system.

The second form is stack management. When a function is called, it pushes a frame onto the execution stack. It allocates local data on the frame, and when the function exits, everything in the frame is reclaimed at once. This is a very low overhead system because you can add as much local data as you want (within stack-size limits) and there is no additional cost per byte for the data.

In C++ you can allocate an object on the stack and then pass a reference to the object in a call to another function. However, this practice is not safe because there is no way for C++ to ensure that such a reference does not outlive the stack frame in which it is created. If the reference is a pointer for example, the pointer could be put into an object that is on the heap. That’s why safe languages like Java prevent references into the stack. In Java you cannot allocated objects on the stack, only local variables, and there is no way to get a reference to a local variable. But allocating objects on the stack can give a big performance win in some cases.

Generic Regions

The stack frame and the global process space are examples of regions. More generically, a region is an abstract place and time where objects live. What region an object lives in is determined by the way that the object is created. A region does not have to be a fixed location in memory; it is an abstraction. It is a sort of biosphere for objects; the objects can only live as long as their biosphere exists.

Every object and region has a lifespan, from the moment it is created until the moment it is destroyed. We say that one lifespan L1 bounds another lifespan L2 if the beginning of L1 is before the beginning of L2 or at the same time, and the end of L1 is after the end of L2 or at the same time. If an object O lives in a region R, then the lifespan of R bounds the lifespan of O.

Regions can contain other regions. If region R1 contains a region R2 then this means two things: first, every object that lives in R2 also lives in R1, and the lifespan of R2 is bounded by the lifespan of R1.

If r is a reference to an object O, and O lives in R, then we say that r is a reference into R. A reference into a region R cannot be stored anywhere that is not in region R. This includes ephemeral references such as register contents.

These rules have two important consequences for storage management. First, a region can be garbage collected independently from other regions. Since there can be no references into a region from outside, you can always garbage collect the objects in a region just by looking at the region. Second, when you are done with a region, you can just drop it, secure in the knowledge that there are no references outside the region that are still referencing objects inside the region. Of course you still have to run destructors if there are any.

To make regions practical, we need a few more things: we need a way to create regions, we need a way to use regions, and we need a way to ensure the safety of regions. Those issues are covered in the following sections.

Executing in a Region

Code can execute in one or more regions. This means that references to the region are allowed in that code and that the region’s lifespan cannot end as long as the code is executing in the region. When code first begins to execute in a region, we say that it enters the region. When it stops executing within the context of a particular region we say that it exits the region.

Every block that introduces a reference also introduces a new, unnamed region with a lifetime that is bounded by the execution of the block. We call this the local region. A local variable lives in the local region. It can hold references to the local region and to all other regions that the code is executing in.

Every program executes entirely within global, the region associated with the global process space. Every thread executes within thread, a region associated just with that thread. Every call to a function or most other routines executes within frame, a region dedicated just to that call.

We also treat the machine itself as another region, host, that contains all of the global regions for all processes, as well as persistent regions that can outlive any process. Unobtainabol has persistent objects and distributed network objects that look to the programmer just like regular objects --but that’s for another post.

A region can be explicitly entered:

enter <region-list> begin <block> end

The local region of <block> is contained in all of the regions in <region-list> as well as any regions that the enter statement itself executes in. A local variable in <block> lives in every region in <region-list>.

Creating a Region

A region is declared much like a function:

region <region-name> ( <region-attributes> ) ;

The scope of <region-name> is the same as any other name in the block. The lifespan of <region-name> is as long as any code can reference it. For example, if the block is a class body then there will be a different region for each object instantiated from the class, and the life of the region will be the same as the life of the object.

Every object automatically has a region associated with it named this.region. The object itself is not allocated in this.region, but this.region can be used to create internal objects. For example, if a class intended to implement a set using a balanced tree structure, then this.region could be used to allocate all of the tree nodes. When the set is deleted, the lifespan of this.region ends also, and all of the tree nodes are automatically deleted along with it.

Here are some possible region attributes:

1. Incremental garbage collection so there are no long interrupts.
2. Reference counting instead of garbage collection because you expect a small number of large objects with no cycles.
3. No recycling (such as garbage collection or reference counting) because most objects, once they are created, will be live for the remaining lifespan of the region.
4. A fixed list of type or block sizes to be allocated, so that we can use free lists. This makes storage management more efficient if we are using any recycling method that does not copy or compact because we don’t have the usual overheads that you get with general allocation strategies that need to worry about memory fragmentation.

Enforcing Safety

The restriction that a reference to an object in region R can only be stored in R is enforced statically by a form of type checking. In Unobtainabol, statically-checked types are optional and regions are no exception. However, if you don’t use explicit regions, then you will not get the performance benefits.

When you declare an object, you can declare the region that it lives in:

local TreeNode var: t1;   // stack frame

global TreeNode var: t2;  // global process space

“TreeNode” is the sort, “local” and “global” are the names of regions, and “var” says that we are declaring a traditional programming language variable rather than, say, a constant or something else. In Unobtainabol there is less need for variables than in languages like C++ or Java so the constant is the default. You have to specify if you want an assignable variable.

Unobtainabol separates the concerns of variable lifespan and variable scope (what code can see the variable). “local” and “global” refer to regions and therefore to lifespans, and have nothing to do with variable scope. In Unobtainabol, you use “global” much like you use “static” on local variables in C++. Of course we do have to be careful not to allow the scope of a variable to include code that can execute outside of the variable’s lifespan.

Declaring a variable as belonging to a certain region does not automatically let you pass that variable around and use it anywhere. In order for code to do anything with a reference into region R it first has to first enter R.

This comes up when you pass a reference to a function. If R is a region then you can declare a function using R references:

function f(R TreeNode var: t1) -> R TreeNode;

This says that f takes a single R parameter and returns an R result. The function f can only be called by code that is currently executing in R. Also, f automatically executes in every region needed to access its parameters and return value.

The local region is interesting because of the way that it interacts with function calls and therefore with parameters. Suppose you have a function

function f(local TreeNode t) -> local TreeNode;

The local region is a different region at the call site than it is in the function body. So which “local” are we referring to in the formal parameters list? Well, there isn’t much use to having “local” refer to the body of the called function because there can’t be any references in the called function’s region before or after the call.

Instead, we say that “local” in a parameter list or return value refers to the local region at the call site. This rule actually does have a useful application. It lets you write a function such as

function biggest(local List of TreeNode var ls) -> local TreeNode;

which returns a value from an aggregate, and you can safely pass in a local aggregate because the declarations prevent the function from doing anything unsafe like store it in a longer-lived region.

However, what you can’t do with this is return a list of objects from the list that was passed in, because you have no way to make a list in the same region as the objects. To allow this, we introduce a special region caller which is the same region as local in the parameter list. Any routine that has a return value or a returnable argument (such as call by var or call by value return) declared as “local”, has access to the special region caller. The called function can allocate space in this region and the caller is responsible for managing that space on return.