Memory Management in Lobster

This is a more in-depth explanation of how memory management in Lobster works, and is typically not needed to be understood fully to use the language.

It may be interesting to those wanting to implement a similar scheme in another language.

Introduction

Memory management is an aspect of a language that has one of the biggest influences on how a language turns out: it affects the type system and the kinds of types you can have, it affects efficiency in both time and space, it affects the cognitive model of the programmer in what data structures can be represented, it affects latency, interoperability, and much more.

Yet, it is often ignored and almost invisible at the same time. Many consider it to be a "solved" problem with probably 95% of programming languages out there using some form of garbage collection: allocate, then worry about reclaiming unreachable objects later.

I think it is far from solved. If I'd have to make a top-10 of "least elegant algorithms in computer science", the #1 would be an easy pick. The idea that just because "who is pointing to this object" is a hard question we are not going to even try to track it, and instead repeatedly scan large parts of the heap to recover that information later, really makes me cringe.

The problem is maybe that for the longest time, the alternatives have not been great. Low level languages would use manual memory management (efficient but error prone), and some have used reference counting. Then there were languages based on linear types or regions, but those never entered the mainstream.

I've personally always thought of reference counting as the "least bad" solution, which is why it was initially used for Lobster. Many people dismiss it out-right because it can't collect cycles, but I've found that, in practical use, getting a "cycle report" at program exit that helps the programmer know where to break those cycles, is largely sufficient.

I mentioned linearity (every object can only have one pointer to it) and regions (every object is assigned a memory pool that outlives them all), and I have implemented languages in the past that implemented both of those strategies. While viable, I felt at the time they required too much programmer assistance to be mainstream.

Ownership models

There is a memory management design space which I'll collectively call "Ownership" which is a generalization of the linearity models: one pointer always owns an object (and is responsible for its deallocation), and others merely "borrow" it.

This now poses new questions: How do we determine who is the owner? When is borrowing allowed? How do we detect a borrower that outlives an owner? What about an owner being modified while there are borrowers? Do we check any of these at compile time, runtime, or a mix?

There have been many ownership models in the past, but only recently they are becoming more mainstream:

Rust is the poster child, which tries to solve all of the above questions at compile time, at the cost of much programmer assistance.
Modern C++ with std::unique_ptr is essentially an ownership model, except one that answers questions like "How do we detect that a borrower outlives an owner" with "We don't". But even with such caveats, it largely works well, and is a huge improvement over the manual memory management of C and even the manual RAII of earlier C++.
Swift, one of the few languages that uses reference counting (inherited from objective C) has intentions to (optionally) move to ownership.
Nim has intention to move away from GC to ownership (see post 1, 2) with a model that is partially programmer assisted and partially runtime.
D has plans.
Many more research-y or less known languages, e.g. Gel, Dyon, CoSy, ParaSail, Cone, Scopes, Pure RC GC, Mitten.

I personally think this general direction is the future of memory management. It just needs to be made more friendly than Rust for most programmers to want to come on board. Lobster offers a possible direction.

Lobster's Memory Management Strategy

This has two parts, its by-value model and ownership analysis.

In-line, by-value structs

The best memory management is.. not to have to manage it at all! You can make an incredibly fast memory manager, but it will never beat simply having less objects to manage. This is the thinking behind Lobster's by-value structs, which offer similar "zero abstraction cost" objects to ones available in C/C++, Rust, and even C#, but surprisingly not in most other languages. It is the most effective and cheapest way towards more efficient memory use that frankly every language should have.

Essentially, you declare an object with the struct keyword instead of the usual class, which causes Lobster to always allocate this object inline in the parent, where "parent" can be another struct or class, a vector, or simply the stack (as a local variable). On an implementation level, it is as if you added all the fields of the struct as fields/variables to the parent, so writing s.x (where s is a struct) is just as cheap as writing x. The struct disappears.

This of course has limitations, in that you're completely dependent on the lifetime of the parent, and that you assign these kinds of struct by copy, rather than by pointer. That means it is not great for large objects, but usually up to 4 fields or so this is still more efficient than heap allocation.

Currently, such structs are immutable, since that simply makes sense for small, copied objects. This is likely to be relaxed in the future to also allow mutation.

There are situations where rather than copying the implementation could use a short-lived reference instead, like is common in C++. This is however not actually faster in many cases, and more importantly, a reference would be subject to the ownership analysis below. By making them copies, we essentially "reduce pressure" on that algorithm, meaning it is more likely to produce optimal ownership assignments and less errors.

Having these by-value structs is especially important in a language like Lobster that has so far focussed on the areas of games and computer graphics, which make intensive use of 2D/3D vectors. Having such types be as cheap as possible is important.

Ownership Analysis

Lobster combines its original (runtime) reference counting with a ownership analysis algorithm, to get "compile time reference counting".

This is a fully automatic algorithm that mostly does not require programmer intervention. In my personal testing, working with several dozens of Lobster programs (many of which medium sized game prototypes) I needed to make minor changes in only 2 locations when transitioning from runtime to compile-time reference counting, the rest "just worked". Or rather, I was able to make the algorithm jump through hoops such that code changes weren't necessary.

Essentially, the algorithm picks a single owner for each new heap allocation, which is usually the first variable, field, or vector element it gets assigned to, and then tries as best as possible to make all uses from there on "borrows". The initial ownership and all borrows do not require any runtime reference counting. If somewhere else in the code something wants to own that same value, it will insert a reference count increase only for this particular use (in Rust, this would cause an error instead). Using this analysis was able to remove around 95% of runtime reference count operations.

This is the default behavior, since it is "good enough" of an optimisation for most code, and very convenient for the programmer. For those cases where the programmer wants maximum control however, they can opt-in to a more Rust-like model on a per variable basis, which will guarantee there will only be one owner ever, and error out if the analysis is not able to guarantee this. This will also be able to remove the reference count field from objects entirely, a further optimisation. This has not been implemented at the time of writing, however.

Errors

These are errors that may happen as a consequence of ownership analysis, though all of them have proven to be very rare.

cannot modify x while y borrows it

Consider code like:

var x = "hello"
def f(y):
    x = "world"
    print y
f(x)

Here, y borrows x, then f overwrites x while it is still borrowed, which would deallocate "hello" while y is still pointing at it. When the borrowed value is an argument of a call, like here, the caller is made to keep the value alive for the rest of its scope (a reference count increase for that call only), so this compiles and prints hello. The error remains for a borrow that no call can be made responsible for, typically an argument that is still being evaluated when a later argument modifies what it was borrowed from, like f(v[0], v.pop()). It is pretty rare for code that uses a borrowed value to be modifying the original value also, and easy to avoid.

cannot assign to borrowed argument: x

This typically never triggers, as arguments that are assigned to are typically forced to be owners, but there are currently some exceptions related to dynamic dispatch where this may still happen. Likely will be eliminated entirely in the future.

variable x still has 1 borrowers

x used in <feature> without being borrowed

These two I've never even seen happen, they largely exist because I am not smart enough to write a formal proof that they can't happen, and then ensure that my code matches the proof :)

The algorithm in detail

The "ground truth" for how the algorithm is to be found in typecheck.h, this section is merely a description of it. If you were hoping for pages of equations like the typical PL paper, I am going to have to disappoint.

AST ownership matching

The ownership analysis works differently from most other languages in that rather than working just on variables and other storage locations, it works on all values in the language.

To be more precise, every AST node has a ownership "kind" it expects of its children, and an ownership kind it passes to its parent. The core of the algorithm is thus the matching that takes place between child and parent:

When the two agree, nothing happens. This is most of the time. For example in let a = [ 1, 2, 3 ] the vector wants to be owned, and the variable wants to own, everybody is happy. No Reference counts touched.
When the parent wants to own, but the child wants to borrow, then either a a reference count increase has to be inserted (by default), or it is an error (optionally). For example, in let a = b, b wants to borrow (lend) itself, but a wants to own, so this has to be reconciled.
When a parent wants to borrow, but a child wants to be owned, we insert an anonymous variable in the current scope that will delete the value later, much like what happens to R-values in C++. For example in print [ 1, 2, 3 ] like most built-in functions print defaults to only wanting to borrow the value, and the vector wants to be owned. So instead it gets held on to and deleted at the end of the scope.

L-value borrowing

Owned values are simple.. these are values that someone needs to be responsible for at all times.

Borrowed values are a little more complicated. Whenever an expression returns the value of a variable, field or vector element we want to default to borrowing these values, since the L-value already owns it. We have a stack of currently active L-values, and the ownership kind returned by the expression refers to these stack elements. These stack values are also reference counted, as multiple borrows may be active at once. This reference count decreases as borrowed values get "consumed". Mutating a borrowed L-value with a reference count > 0 produces the above error. The reference count not being 0 at the end is a bug in the ownership analysis :)

Variables that are assigned to always own. A variable that is never assigned to (a let, or a for loop element) and is initialized from a variable, field or vector element borrows it instead, for the rest of its scope: it holds a borrow of that L-value, so no reference count is touched when it is defined or goes out of scope. If something then writes to that L-value while the variable is alive, the analysis does not error like it does for other borrows, but retroactively makes the variable own (its initializer gets the reference count increase, and it gets the decrease at the end of its scope), so the program means the same either way, and only the cost differs. This is what makes the old := cur pattern work, where cur gets overwritten while old hangs on to the previous value. Such a variable is also another name for what it borrows, so a write through it is checked against borrows of the original.

The same applies to a borrowed function argument: it is another name for the variable or field path the caller passed (when it passed one), and writes through it, in that function or the ones it calls, are checked against what the callers have borrowed or have flow-type promoted. Vector elements are locations too: writing an element, or calling a builtin that can drop elements (pop, remove, truncate, ..), is a write to the elements of that vector, which conflicts with a borrow of any element (or of the same constant index). What the analysis still cannot see is aliasing through a variable that owns a reference of its own and is reassigned, e.g. var c = a followed later by a write through c while a field of a is borrowed.

The end of a variable's lifetime is typically the end of the scope, though making it its "last use" is being worked on, see return below.

Function specialization by ownership.

Function ownership specialization is probably quite unique to Lobster, and solves an important problem: if different callers to a function have different ownership kinds that would be ideal for their arguments, the compiler (or worse, the programmer) would have to pick one, and let the others be suboptimal. Not only does this produce unnecessary reference counting, it reduces the amount of code that could otherwise work error-free in the context of strict ownership. For example:

def f(x): print x
f([ 1, 2, 3 ])
f(a)

If x had been fixed to own because of the first call, the second call would have been less efficient, or even an error. Now they both get to be maximally efficient because of specialization. Now in this simple example it is easy to see that x should really borrow, but it isn't always that trivial, and would need a more complex ownership analysis that employs "logical variables" much like type inference currently does (assuming you want to do this without help of the programmer).

There are currently some exceptions to this:

Arguments that are assigned to are always owned.
Big functions (and all functions in a dynamic dispatch, which must agree) get a single specialization with all arguments that allow it borrowing: that costs a caller passing a variable nothing, and a caller passing an owned value the same as an owning argument would.
The return value of a function is currently always owned.

Much like variables, some of these could be relaxed/improved in the future.

Ownership kinds for AST types

These are currently how the different AST types interact lifetime wise with their children (wants) and parent (results).

Note that most of code also uses a ownership kind of "any", which means either that the ownership doesn't matter (for e.g. scalars) or that the recipient is cool with any kind of ownership.

Assignment wants to own, and results in borrow.
if results in the union of the ownership kinds of both branches. The union is simple if both are equal or either side doesn't care. If they differ, it defaults to own. It has specialized code to detect if one of the branches never returns (has a return statement in it that escapes the if) in which the ownership kind is that of the other branch. The condition wants to borrow. if with one branch of course does not result in anything.
switch is similar to if, but currently always defaults to owning the value returned by the cases, since doing a correct ownership kind union between many cases in the context of branches not returning is harder. This should be improved.
and and or are again similar to if, but have some special cases because sometimes a value is guaranteed ignored (a and b or c never results in a) or values are coerced to bool when they are incompatible ("a" or "b" results in a string that wants to be owned, but [ 1 ] or "hello" results in a bool with the values immediately deleted).
while borrows its condition and doesn't care about the body.
for borrows what it iterates over and doesn't care about its body. Its element variable borrows the elements of the vector (see above), unless the body writes to them, in which case it owns each element in turn.
String constants result in a borrow. This is because strings are most frequently passed to contexts that would prefer to borrow (like + or many builtin functions) and thus would produce a lot of reference count churn if they were owned. Each distinct string constant is an object in the generated code itself (static data, not the heap), emitted holding a reference of its own that is never given up, so its count never drops to 0 and it can safely be borrowed from. Or more simply: it's as if there exists an anonymous global variable for each string constant that's actually used, and which you borrow from. Such an object is marked by a type table entry of its own, so the builtins that write into a string in place (write_int8_le and friends) can copy it first rather than change the constant.
s += x (and s = s + x) appends in place when s is the only reference to a dynamic string and its allocation has the room (a string that had to grow got as much room again as it took), so building a string up in a loop costs what is appended rather than what has been built. A shared or constant string is copied instead, as it always was: the append never changes what another reference sees. The right hand side is appended piece by piece rather than made into a string first: the operands of a concatenation, an int, float or struct of scalars written out as it goes on (a call the optimizer inlined down to its value counts as that value, and so does an explicit string(x)), and the text substring or number_to_string would have made. All operands are evaluated before any of them is appended, and a piece that is the string itself (s += "x" + s, or a substring of it) is read as it was: for the appends the string then keeps a reference of its own, so it is copied rather than grown in place. The byte-writing builtins (write_int8_le and friends, ensure_size) grow a string into the same room, but in place whether it is shared or not, since a string used as a byte buffer is written in place by design; string_with_capacity makes an empty string with room to grow.
+ on strings wants to borrow, and returns owned. This is the same in principle for all binary operators, but thanks to "inline structs" this doesn't matter for most of them anymore.
Built-in functions by default want to borrow all their args, and return an owned value. There are exceptions to this rule, which can be marked when declaring a built-in, mainly for functions that directly operate on a vector or other data structure. For example push wants to own its second argument, and top returns a borrowed value.
As noted above, return typically wants to own what it is returning, but currently makes an exception for the frequent case of returning a single variable, where it pretends to borrow it. This is because otherwise it would typically cause a reference count increase followed by a decrease as the variable goes out of scope. Extending the cases where this happens, and also generally allowing the last use of a variable to be owned by its last use rather than waiting for the end of the scope, is planned as a future improvement.
Any data structure constructors (objects, vectors) of course result in own.
Any L-value results in borrow.