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