Reference counting take 2

I think of the current implementation of reference counting in Cyclone as a first draft. It’s usable and it’s useful, but it needs at least one more redesign. Here are some ideas.

Unique pointers, which are the basis of our implementation of reference counting, are too hard to use. The swap operator, unique paths, etc., can be used by experts, but I don’t think your average programmer is ready for them, at least in their present incarnation.

Two things save the day: temporary (and usually implicit) aliasing, and autorelease for reference counted objects. These features allow us to use reference counted objects anywhere that we can use objects allocated in lexical regions, which is just about everywhere.

Autorelease is particularly interesting. It takes a pointer to a reference counted object and passes on the responsibility of decrementing the count to a region: the count will be decremented when the region is deallocated. Until then, the pointer can be used just like a pointer into the region itself.

The advantage over lexical regions is that the count can be incremented, if you need to hold on to the object beyond the lifetime of the region. The disadvantage is that you lose the efficiency of bulk deallocation that lexical regions give you.

Autorelease is great

I find in my programming that I almost never want a non-autoreleased, reference-counted object. I usually autorelease a reference-counted object as soon as I get my hands on it. A lot of machinery could be pruned if we just got rid of the intermediate, non-autoreleased state. So, here’s a proposal. Say that

`t *@lifetime(`r)

is the type of a pointer to a `t that lives at least as long as region `r. Then we provide a function

`t *@lifetime(`r, `s) extend(region_t<`s>, `t *@lifetime(`r));

that ensures the object lives as long as `r and `s. This can be implemented by reference counting.

It would be even better if extend operated by side-effect, changing the type of its argument rather than returning a new copy of the pointer.

Bulk extend

One of the most difficult issues to solve with the current scheme is to take a complex autoreleased data structure, such as a list, and extend its lifetime. We need the ability to do a bulk extend.

As usual, we can solve this with one more layer of indirection. Let’s have reference-counted regions: when the count of the region goes to zero, everything in the region is deallocated. Then we can autorelease the region; this relates two regions, one region `r that lives as long as a second region `s.

What’s missing

First, we really need finalizers. Notice that for my bulk extend proposal I’m essentially using a finalizer that deallocates all data in region `r when its count goes to zero. Finalizers are generally useful for memory management: when you deallocate an object its useful to decrement the counts of objects it points to. Finalizers are expensive in this case, but, doing this by hand in Cyclone right now is quite painful.

Second, my proposal simply does not handle some kinds of memory management. For example, if you want to have a graph in memory with node objects pointing at each other, and the ability to deallocate individual nodes as needed, you are pretty much stuck with the current reference counting scheme.

13 April 2006 by trevor #