On my Thinkpad, I'm working on a different line of development, involving garbage collection. I'm trying to modify LLVM to be able to generate stack frame descriptors that handle local variables that aren't just primitive types. This turns out to be somewhat easier than I was afraid of, now that I have taken the time to actually understand the LLVM code for generating stack roots.
Tracer Tables
One issue that I am still pondering is the generation of tracer tables. A tracer table is simply an array of the offsets of all of the traceable pointers within a data structure. The idea is that the garbage collector has a base pointer to an object, and then obtains a tracer table for that object, which it can then use to locate all of the pointers. For user-defined classes, the object's TIB (TypeInfoBlock) contains a pointer to the tracer table:
class Object {
const TypeInfoBlock * __tib;
// (more members follow)
};
class TypeInfoBlock {
const long ** __tracerTable;
// (more members follow)
};
(I'm writing these examples in C++ for clarity.)
In the case of struct types, there's no TIB pointer, so the compiler needs to determine which tracer table to use at compile time. Fortunately this is easy to do, since structs are always contained within a context - either they are local variables or they are embedded within another object type.
Tracer Functions
An alternative to tracer tables is to generate a tracer function for each type. A tracer function is simply a compiler-generated function that iterates through all of the pointers in the data structure and performs some garbage-collection action on each one.
Let's take a simple mark-and-sweep collector as an example. During the mark phase, we need to trace through all of the pointers in the object and mark each object pointed to. So the compiler could generate code to do this, one tracer function for each data type.
One problem with this is that it means that the compiler has to know details about your garbage collection algorithm. Another problem is that for a sophisticated, multi-threaded collector, there will be more than one type of trace pass. Often there will be several passes, with the last being a "fix-up" pass which deals with mutations that have occurred while the collection cycle was underway. In order to avoid generating a different tracer function for each different trace pass, we would need to generalize the tracer function - have it take a parameter telling it what action to take, probably in the form of a functor argument that is used to process each pointer field.
Using a functor has a number of efficiency disadvantages: First, it means that you now have an extra pointer dereference (the functor pointer) for each and every pointer field processed. Secondly, some tracers need to actually modify the pointer values, while others can get by with merely reading the pointers but not changing them. The tracer function, unfortunately, would need to assume the worst - that the functor was always going to modify the pointer being traced.
From a caching and memory locality standpoint, using a tracer table is better (not to mention more compact) - the garbage collector can simply iterate through the table entries in a tight loop, and perform whatever action it wants in the body of that loop.
The one drawback of tracer tables is that the structure of the object must be known at compile time in order to generate the table. But that's not a big hardship, right?
Flexible Arrays
In C++ and other languages, the notion of a "variable-length" type is extremely useful. So useful, that in the case of Tart, there's a built-in data type designed to support this use case: FlexibleArray.
Here's an example of you you might use the FlexibleArray data type:
final class String {
var size:int;
@Unsafe var data:FlexibleArray[byte];
}
A FlexibleArray is simply a way to tell the compiler that the size of the member is unknown at compile time. It's similar to declaring a zero-length array in C++. It is illegal to declare a FlexibleArray-typed member that is not the last data member of the class, and the class must be declared 'final'. You also need to declare a custom allocator for the type:
final class String {
static def create(length:int) -> String {
let s:String = __flexAlloc(length);
s.size = length;
return s;
}
var size:int;
@Unsafe var data:FlexibleArray[byte];
}
The __flexAlloc function takes an integer length, and calculates how big of a memory block is needed to hold both the fixed fields of the type as well as the flexible array elements. It then allocates the memory, and fills in the TIB pointer.
(You may be wondering how __flexAlloc knew what type of object to allocate, in this case String. The answer is that the type inference engine deduced it from the type of the left hand side of the assignment statement. Cute, eh? We could have just as easily said "let s = __flexAlloc[String](length)").
Tracing Flexible-Sized Objects
So far, so good. However, we get back to the issue of garbage collection: How do we generate a tracer table for a variable-length object? The compiler doesn't know the length of the FlexibleArray, since that was determined at runtime.
You might think that the collector could cheat and look at the memory allocation header (which comes *before* the object), however this fails for two reasons: statically-allocated objects don't have a memory allocation header, and not all of the array elements may be initialized. A class might choose to use a FlexibleArray for "reserve capacity" - similar to what happens in an STL vector.
Really, the only entity who knows which elements of the array should be traced is the class itself. That means that we need to give some control of the tracing over to the class.
If we were using tracer functions, it would be relatively simple - we would just override the __trace() method. (Although even that doesn't entirely solve the problem as there's an interesting race condition. If our collector is operating on another thread, and we update the "size" field after writing additional elements to the FlexibleArray, the collector thread might get the older version of "size", which would mean that the newly written entry won't get traced. This is where the post-cycle fixups come in.)
Another drawback of using a tracer function is that now the class becomes responsible for tracing *all* of the fields in the class. You could use a combination of tracer tables and tracer functions, but that would mean implementing each tracer pass (as determined by the collection algorithm) twice - one version that works with tables and another version that works as a functor.
One (somewhat hacky) data-driven approach would be to use an annotation to tell the compiler which data field is used to store the size of the array:
final class String {
var size:int;
@Unsafe @SizeVar("size") var data:FlexibleArray[byte];
}
Essentially the compiler would see the annotation, look for a member variable named 'size', and use that to generate additional metadata. The compiler would need to generate four additional pieces of information:
- The offset of the 'size' variable.
- The integer type of the 'size' variable.
- The tracer table for an individual array element.
- The stride of an array element - that is, the difference in bytes of element N from element N-1.
Even this has problems. It means that the interpretation of 'size' is fixed by the compiler. You can't use begin/end pointers as is done in STL, you have to use integers.
Another example is array slice objects. Right now the Tart String class has a dual role: It can be used to represent a string of characters, or it can be use to represent a substring of another string. (For efficiency, the same class is used for both cases - otherwise String would have to be non-final, which would suck from a performance standpoint.) The 'size' field can mean either the size of the whole string, or the size of the substring. This is incompatible with a fixed interpretation of the field.
A third possibility is to have a special member function, say flexSize(), which returns the size of the flexible array and tells the collector how many entries in the array to trace.
final class String {
var size:int;
@Unsafe @FlexSize("flexSize") var data:FlexibleArray[byte];
def flexSize() -> int { return size; }
}
This is the best compromise solution I have come up with so far.
No comments:
Post a Comment