Garbage collector working

I pushed up the first working implementation of the new garbage collector last night. It’s a tracing copy collector, designed to efficiently compact small heaps. Radian has a branching generational memory model: a subtask can operate in its own allocation zone, with read-only access to objects from other zones. When the task completes, we can copy its live set into the parent zone, then release the subtask zone as a whole block.

By running tasks in separate allocation zones, we can avoid the cost of mutex locking, as threads no longer need to contend for access to the same allocator. Further, since allocation zones operate on a page-level granularity, tasks running on separate processors need not touch the same cache lines. Only at the point when subtask results are reintegrated into the parent do we need a lock – but we already have to lock that operation anyway.

This allocator/collector project has been a lot of work, and I really hope it turns out to have been worth the engineering time. Radian’s semantics are not very much like those of a conventional object-oriented language, and I believe that a memory management system designed around its needs will perform much better than a generic allocator & collector ever could have. The whole point of this project is to maximize processor throughput, after all – the fancy loop splitting stuff is not going to do us any good if the cores spend all their time contending over allocator locks.

Relaxed radix balanced trees: efficient immutable vectors

Immutable vectors are a convenient data structure for func-
tional programming and part of the standard library of modern languages
like Clojure and Scala. The common implementation is based on wide
trees with a xed number of children per node, which allows fast in-
dexed lookup and update operations. In this paper we extend the vector
data type with a new underlying data structure, Relaxed Radix Balanced
Trees (RRB-Trees), and show how this structure allows immutable vector
concatenation, insert-at and splits in O(logN) time while maintaining the
index, update and iteration speeds of the original vector data structure.

They compare this new structure to finger trees, which I used for Radian’s array container:

2-3 finger trees achieve a lgN time for indexing and update while at the sametime maintaining an amortized constant time for adding items to the vector. Concatenation can be accomplished in lgN time too. Although attractive, using this data structure for vectors does compromise the 1/5 lgN time for index, making it theoretically 5 times slower.