as C++, the compiler maps the selec-tor-class pair to an offset in a vtable and then embeds the lookup at the call site. This is practical because the lookup is just a couple of instructions. In the GCC runtime, the sequence was to call objc _ msg _ lookup(), which would return a function pointer, and then call this function pointer. The NeXT/Apple runtime combined the two steps into one—a call to the objc _ msgSend() function.

Method lookup performance is critical for late-bound dynamic languages such as Smalltalk and Objective-C. It is common for 10%–20% of the total time on various runtimes to be used performing the lookups, so a small change in the lookup performance can be quite noticeable.

One of the biggest changes the Étoilé runtime made was the message-lookup mechanism. First, it made it possible for each object to have its own message-lookup function. Second, it made the lookup function return a slot structure, rather than a method. The point of the slot structure was to make safely caching lookups possible using a lockless algorithm.

The slot contained a version field, which could be incremented whenever a method lookup was invalidated. The basic update sequence was:

1. Look up the old slot.

2. If the slot is owned by the class you are modifying, then just modify the slot, no cache invalidations required.

3. If it is not, then add a new slot for the current class and increment the version of the old slot.

At each cached call site, you can then perform this sequence:

1. Read the cached slot.

2. Read the version from the cached slot.

3. Read the cached version.

4. Compare two and perform the full lookup if required.

This same mechanism is supported by the GNUstep runtime, along with some optimization passes that will automatically insert the caching based on some heuristics. For example, if you have a loop, then the compiler will cache method lookups within the loop between loop iterations. Testing this showed the cost of a message send dropped to around 50% more than the cost of a function call.

The cache checking is also cheaper in terms of TLB (translation lookaside buffer) and cache usage than the full lookup, so the improvement outside of microbenchmarks is likely to be even greater.

modifying the Lookup

One of the main motivations for allowing objects to have their own lookup mechanism was the desire to allow multiple object models to coexist. In practice this was rarely useful, and the extra overhead on every call was not worth it. Similar mechanisms can be implemented via the second-chance dispatch system, where a failed method lookup calls a standard method allowing forwarding and so on. We did, however, make one change to the lookup that could be shared among multiple languages: adding support for small objects.

Most Smalltalk implementations have a SmallInt class, which hides an integer inside an object pointer. The new runtime supports one such class on 32-bit systems and seven on 64-bit systems. The runtime does not define the semantics of these classes, but the method lookup simply loads the class from a table if the low bits are not 0.

The GNUstep runtime is designed with practical, measurable performance in mind, unlike the Étoilé runtime, which was designed for flexibility and theoretical performance. After some testing, we determined it was worth adopting NeXT’s approach of implementing a single-step objc _ msgSend() function. This is not possible to implement in C, because it must call the looked-up function with all of the arguments it is passed; therefore, it must be implemented in assembly.

This was avoided for the original GCC runtime because this assembly needs to be implemented for each combination of architecture and calling convention. This was a significant problem in the early 1990s when it meant upward of 30 different implementations. Now x86, x86-64, and ARM account for the vast number of users, so having the fast path for these and retaining the two-stage lookup for others are sufficient. Other platforms can be added as required.

Lessons Learned

The path from the research prototype (Étoilé runtime) to the shipping version (GNUstep runtime) involved a complete rewrite and redesign. This is not necessarily a bad thing: part of the point of building a prototype is to learn what makes sense and what does not, and to investigate what is feasible in a world where you control the entire system, but not necessarily in production.

The most important lesson was the relatively early discovery that no matter how adventurous developers claim to be, backward compatibility always wins over new features. Unless there is a simple migration path, the new system is doomed to failure. The new runtime can work with code compiled with old versions of GCC, but it requires a new compiler to use the more advanced features.

The second important lesson was that, while general solutions are nice for projects, products typically want good solutions to a subset of the general case. To the Objective-C runtime users, a more general object model was an interesting curiosity, while a slightly more general object model combined with significantly faster message sending was a compelling reason to switch.

 

Related articles
on queue.acm.org
hidden in Plain Sight

Bryan Cantrill

http://queue.acm.org/detail.cfm?id=1117401

A co-Relational Model of Data for Large Shared Data Banks

Erik Meijer, Gavin Bierman

http://queue.acm.org/detail.cfm?id=1961297

Code Spelunking Redux

George V. Neville-Neil

http://queue.acm.org/detail.cfm?id=1483108

References

1. Chisnall, D. a modern objective-C runtime. Journal of Object Technology 8, 1 (2009), 221-240; http://www. jot.fm/issues/issue_2009_01/article4/.

2. piumarta, I. and Warth, a. open, extensible object models. Viewpoints research Institute technical report tr-2006-003-a; http://www.vpri.org/pdf/ tr2006003a_objmod.pdf.

 

David Chisnall is a researcher at the university of Cambridge, where he works on programming language design and implementation. he spent several years consulting, during which time he also wrote books on Xen, the objective-C and go programming languages.

© 2012 aCM 0001-0782/12/09 $15.00