Re: Objective-C and Smalltalk; speed of message send

[Alexander Malmberg]

Adrian Robert wrote:
> Incidentally, for those of us who _don't_ engage in front-lines
> modification of the ObjC compiler in our spare time, a nice "educated
> layman's" exposition on the nitty-gritty of message sending is:
> 
> http://www.mulle-kybernetik.com/artikel/Optimization/opti-3.html
> 
> Examples are from the Apple runtime on PPC, but most of the gist is the
> same, I'm assume.

Not really. :) The high-level stuff is similar, but the low-level
message passing (objc_msgSend on the next runtime) is very different.

To send a message using the GNU runtime, you first call objc_msg_lookup
with the receiver and selector as arguments. It will look up the
implementation and return a pointer to it. You then push all the
arguments and call this function pointer.

Using my patch (normal gcc is conceptually identical, but arguments are
passed on the stack, which is slower, and the lookup function isn't
hand-optimized for the common case), the code at the caller looks like:

  // Load the receiver
  movl    theReceiver@GOTOFF(%ebx), %edi

  // Load the selector
  leal    32+_OBJC_SELECTOR_TABLE@GOTOFF(%ebx), %esi

  // Copy arguments and call objc_msg_lookup
  movl    %esi, %edx
  movl    %edi, %eax
  call    objc_msg_lookup_fast@PLT

  // Push arguments for the message send and call the implementation
  movl    %esi, 4(%esp)
  movl    %edi, (%esp)
  call    *%eax

(For IMP caching, the three instructions in the middle are replaced by a
load of the function pointer. For a normal c call with two arguments,
the three instructions in the middle go away and the 'call *%eax'
changes to 'call function_name'.)

And the interesting parts of objc_msg_lookup_fast look like:

objc_msg_lookup_fast:
  // Check for a nil receiver (because I haven't gotten
  // around to handling that quickly yet)
  testl %eax,%eax
  jz .Lwont_handle1

  // Look up the selector in the dispatch tables
  pushl %eax
  movl (%eax),%eax
  movl 32(%eax),%eax
  movl (%edx),%ecx
  cmpl 24(%eax),%ecx
  jae .Lwont_handle2  // out-of-range selector

  movl (%eax),%eax
  shrl $16,%ecx
  movl (%eax,%ecx,4),%eax
  movl (%edx),%ecx
  andl $0xffff,%ecx

  movl (%eax,%ecx,4),%eax
  testl %eax,%eax
  jz .Lwont_handle2  // receiver doesn't respond to selector
  addl $4,%esp
  ret

Note that there are no loops, and no conditional handling in the common
case. The wont_handle:s pass the call along to the real, slow
objc_msg_lookup, but this only happens for nil receivers (something I
should fix since it's easy to handle), unimplemented methods (eg.
forwarding and stuff like that; message lookup isn't the bottleneck in
such cases), and the very first time a message is sent to a class
(before the dispatch tables for the class have been initialized).

Total: 18 cycles.

- Alexander Malmberg