Friday, January 20, 2012

Changes to support precise GC

When we originally designed MCI's ISA, we didn't consider the fact that precise garbage collection would require a more strict type system and well-defined memory layout. In order for precise garbage collection to work, all GC-tracked objects in the heap must carry some sort of type information. In the previous memory layout, objects would sometimes not carry a header (which contains type information and GC bits), thus forcing the GC to be conservative. This is clearly bad, since precise GC is one of the most important features of modern garbage-collected systems.

Other virtual machines, such as the CLR and the JVM, have a distinct object reference type. This type cannot be converted (e.g. to a pointer), nor can it be dereferenced. This is ideal, because with these two constraints, we can enforce that GC-tracked objects must always have a header. On the other hand, such a type severely limits what unsafe code can do. Whether this is a good or a bad thing is arguable, but it does nonetheless reduce the amount of languages that can target the MCI. For instance, the D programming language lets you cast an object to void* if you so desire. Such things are, of course, type-unsafe and cannot be expected to work with a precise GC. We don't see any immediate reason to support language features like this one.

So, the following changes have been made:
  • We've introduced the reference type. This is a type specification similar to a pointer. The difference is that it may have at most one indirection, and the element type must be a structure type. The object a reference refers to is guaranteed to have a header. If we have a structure type Foo, the syntax for a reference to it would be Foo&.
  • Arrays and vectors are now GC-tracked. This is another necessary change to avoid conservative scanning. If arrays and vectors would remain native data types, we wouldn't be able to scan them precisely. This means that, in practice, arrays and vectors work similarly to references, though they allow some more operations, like conversions.
  • Arrays now know their dynamic length. If we didn't make this change, we wouldn't be able to reliably scan arrays, as we couldn't possibly know their size. This would mean that any object inserted into an array would have to be pinned (more on pinning later), resulting in terrible GC performance and heap fragmentation (not to mention complex code).
The introduction of reference types means that field.get, field.set, and field.addr have been changed to accept these types. Additionally, we've introduced a new instruction, array.len, which fetches the length of an array. Perhaps more importantly, mem.* instructions have been completely revised: We've fused the mem.gcalloc, mem.gcnew, and mem.gcfree instructions with mem.alloc,, and Since references are now distinct, there's no longer a need for the GC variants of those instructions.

Now that arrays know their dynamic length, you might wonder if we're planning to allow using them in arithmetic and logic operations like vectors; after all, this seems like a natural thing to do, since optimizing these operations is relatively trivial. We haven't made up our minds about this just yet. The reason these things are allowed with vectors is that the compiler can statically unroll the operations because the vector's length is known. This cannot be done with arrays, and therefore, the benefits of allowing SIMD-style operations on them might not be worthwhile.

On to pinning. Pinning an object has two implications: The object will be considered reachable by the garbage collector until unpinned (i.e. it will never be collected until unpinned), and it cannot be moved by a copying or compacting GC. Both of these things are performance issues, but they are a necessary evil. When using a precise GC, we cannot pass an object to native code without pinning it. Since the GC has absolutely no knowledge of external code and its usage of managed objects, there is no way it would be able to do correct reachability analysis (not even conservatively). Another issue that copying and compacting collectors face is that after moving an object, they would have to update all external references. This is not practical at all, and again for the same reason: The collector has no knowledge about the external code's usage patterns. In other words, objects have to be pinned when passed to external code, and unpinned when the external code has finished running. This does, of course, require knowledge of the external code's implementation details, but there is no way around this.

The MCI provides two instructions for doing the above: and mem.unpin. Both work with references, arrays, and vectors.

Another reason that we had to make these changes is that the interpreter and the JIT compiler have to share the same memory layout. If they didn't, GCs would have to special-case execution with the interpreter, which is clearly horrible design.

Long story short: With these changes, we should be able to support precise garbage collection in the MCI, at the negligible cost of reducing the amount of type-unsafe operations that will work as "expected".

No comments:

Post a Comment