News

Another Day, Another Runtime

Posted on 10 November 2007 by David Chisnall

After spending a little while poking at the GNU runtime, I came to two conclusions:

• It was at least twice as complicated as it needed to be.
• GNU coding style really hurts my eyes.

I've spent a little while thinking about what I want from a runtime. One of my recent projects has been writing a Smalltalk JIT that targets the GNU runtime (still quite work-in-progress) and so I know the GNU runtime can support Smalltalk as well as Objective-C. Quentin, meanwhile, has been working on the Io bridge. While this works, it is a bit ugly because the Io object model doesn't really mesh well with the Smalltalk object model that the GNU runtime uses. More on this later.

Beyond better being able to support Io, I read a few interesting papers recently. The first was on Polymorphic Inline Caching. This is quite a neat idea, and allows you to eliminate the cost of dynamic method lookups in a number of cases. Unfortunately, this is quite hard to get right. Consider the simple Objective-C line:

[object message];

With the Apple runtime, this will be translated roughly into something like this:

objc_msgSend(object, @selector(message));

I'm cheating a bit here, and skimming over how the @selector() directive is expanded. In contrast, the GNU runtime does this:

IMP method = objc_msg_lookup(object, @selector(message));
method(object, @selector(message));

This is quite nice, since it means that a small compiler change is all that's needed to cache the method. We could replace this with something like this:

static IMP cached_method = NULL;
static Class cached_class = Nil;
if(cached_class != object->isa)
{
    cached_method = objc_msg_lookup(object, @selector(message));
}
cached_method(object, @selector(message));

Now you only need to bother with the (expensive) method lookup if you reach this bit of code with two different object types. There are a lot of places in code where you will get the same kind of object all of the time, and this can give a huge speed boost. In other cases, you get a number of different ones and this is where polymorphic inline caching comes in. Rather than keeping a single (class, method) pair cached, you keep a few. Profiling can determine the optimal size for this cache relatively easily.

Nice and easy? Well, there's a catch. Objective-C is a dynamic language. You can load bundles which will replace methods at runtime and languages like Io allow even different objects to have different methods. This means that you need to check that the cache is valid before you use it. A problem.

This, and the difficulty in supporting Objective-C 2.0 on the GNU runtime caused me to write a new one from scratch. This took just under 48 hours (after which I ate and went out to a well-earned salsa class). What's new?

First, inline caching can now be done safely. Rather than looking up methods, the runtime looks up slots. The slot contains (among other things) an IMP and a version. How does the version help? Consider two classes, A and B. A inherits from B, which implements a -foo method. Somewhere in my code, I call this method on an instance of A and cache the result. Two things can cause this cache to become invalid:

• B's implementation of the method being modified / replaced.
• A having an implementation of the method added.

The first case Just Works™ since a pointer to the the slot (which contains a pointer to the method) is cached. You can modify the method without any problems (great for debuggers and runtime optimisations). The second case is more tricky. When you add a method to A, it first performs a lookup on the selector. If this returns a non-NULL slot, then the version of the located slot is incremented. Any time you cache a slot, you should also cache the version; if there is a version mismatch with the cached slot then you need to perform the lookup again.

The slots also contain an optional offset. This can be used to implement very fast set/get methods. A lot of the time you wrap instance variables up in set/get methods to insulate users of the code from changes to the instance variable layout. This comes with a speed penalty. I can't make this go away completely, but the new runtime allows you to avoid the method call and just access the ivar directly, while maintaining the dynamic lookup. This can make things like KVO faster, since you can do direct ivar access while there are no observers and then switch to indirect access when there are some.

I said the new runtime was simpler (no exaggeration; it's roughly 10% of the code size of the GNU runtime). That's partly because it works in a slightly different way to other Objective-C runtimes. While the GNU runtime provides the functionality required to implement Smalltalk in C, the new one provides the functionality required to implement Self in C, and then implements Smalltalk in Self (which is very easy).
Every object has (or, rather, can have) its own dispatch table and its own lookup function. Classes really are just objects. Anything you do with classes, you can also do with objects; for example you can add a method to a single object at runtime (say hello to closures, prototypes, and all of the things Io and Lisp programmers have been mocking you for having to do without).

The class model contains a nod to that used by Animorphic Smalltalk. This used mixins as a base type. That's effectively what I'm doing although they're called classes so as not to scare off the old Objective-C programmers. Classes can be composed as mixins are, which is how concrete protocols are supported (the only difference between a concrete protocol and a mixin is that the compiler does type checking for a concrete protocol. From the perspective of the runtime they are the same).

Oh, and every object has an associated recursive mutex, so @synchronized can now be generated easily.

To get an idea of how the runtime is used, take a look at example.c, which contains some simple example Objective-C code in comments and the equivalent code the compiler should be producing. I'd love to see this supported in LLVM, so anyone familiar with that codebase who feels like lending a hand please let me know.

You can also find more information in the release announcement email, including a more detailed overview and the API docs.

None of the interfaces are set in stone yet, so any suggestions are welcome. You can grab a copy of the code by doing:

svn co http://svn.gna.org/svn/etoile/branches/libobjc_tr/

Labels: libobjc, Objective-C, runtime, shiny