Objective-C Efficiency - C

On Thu, 4 Mar 2004, Laurent Deniau wrote:

> I am not an expert in Objective-C but I am interested by the features of
> this language and its runtime library. On the page
>
> http://www.dekorte.com/Objective-C/
>
> it is said that Objective-C is fast, with a time for message call of
> only 1.5 to 2 times the time of the C function call. I did a very simple
> quick and dirty benchmark which is showing that POC messages are >5
> times slower than C and gcc messages are >8 times slower than C. I put
> the code below (for POC).
>
> I can accept a factor of 2 but >5 is really too slow. So what is the
> reality about message efficiency?

Wow, I don't know what's going on with your tests. I tried this on my Mac
running OS X, so obviously with Apple's runtime. Here are my results:

Starting 0100000000 loops...
C = 9.60 sec
ObjC = 16.89 sec
Ratio = 1.76

Which is right in line with the quoted figure. (This is a 400MHz G4 for
anyone interested in the absolute times.) However, your inc() function is
not 100% equivalent to the -inc method. The ObjC equivalent has to add an
offset onto the pointer that's passed in, and it also returns self. The
return had no effect on my timings, but it turns out the offset did. I
wrote a different inc function and passed 'foo' to it:

id inc_func(id self)
{
long *ptr = (long *)self + 1;
(*ptr)++;
return self;
}

Using this instead, I got these timings:

Starting 0100000000 loops...
C = 10.86 sec
ObjC = 17.04 sec
Ratio = 1.57

I also tried the experiment using the IMP for -inc, and got about .2
seconds less on the C test than calling inc_func().

Of course, to really test overhead, you should use methods and functions
that really do nothing at all. But in any case, my results were in line
with the 1.5-2 figure. I'm curious to know why yours were so much worse.

Hmm, I just tried it with optimization turned on, and the C figures get a
whole lot better (1.5 seconds, ObjC goes down to 8.4 seconds, ratio 5.7),
in line with the figures you gave above. Is this result legitimate? Is the
optimizer doing something that it couldn't do in a more real-world test? I
don't have any answers to that one.

In article <c27e5g$3f1$1@sunnews.cern.ch>, Laurent.Deniau@cern.ch
says...
>
> it is said that Objective-C is fast, with a time for message call of
> only 1.5 to 2 times the time of the C function call. I did a very simple
> quick and dirty benchmark which is showing that POC messages are >5
> times slower than C and gcc messages are >8 times slower than C. I put
> the code below (for POC).
>
> I can accept a factor of 2 but >5 is really too slow. So what is the
> reality about message efficiency?
>

I had a go at your benchmark on Panther. I modified it to use NSObject
and stuck everything in one file.

I got:

james$ gcc -o objc objc.m -lobjc -framework Foundation
james$ ./objc
Starting 0100000000 loops...
C = 3.39 sec
ObjC = 8.75 sec
Ratio = 2.58

Not so bad...


However if we crank up the optimiser things go very pearshaped for objc
- I suspect such a simple C function in a tight loop has plenty of scope
for being optimised to hell.

james$ gcc -o objc objc.m -lobjc -O3 -framework Foundation
james$ ./objc
Starting 0100000000 loops...
C = 0.17 sec
ObjC = 5.55 sec
Ratio = 32.65 <- Ouch!

How did you compile your benchmark run?

Michael Ash wrote:
> On Thu, 4 Mar 2004, Laurent Deniau wrote:
>
>
>>I am not an expert in Objective-C but I am interested by the features of
>>this language and its runtime library. On the page
>>
>>http://www.dekorte.com/Objective-C/
>>
>>it is said that Objective-C is fast, with a time for message call of
>>only 1.5 to 2 times the time of the C function call. I did a very simple
>>quick and dirty benchmark which is showing that POC messages are >5
>>times slower than C and gcc messages are >8 times slower than C. I put
>>the code below (for POC).
>>
>>I can accept a factor of 2 but >5 is really too slow. So what is the
>>reality about message efficiency?
>
>
> Wow, I don't know what's going on with your tests. I tried this on my Mac
> running OS X, so obviously with Apple's runtime. Here are my results:
>
> Starting 0100000000 loops...
> C = 9.60 sec
> ObjC = 16.89 sec
> Ratio = 1.76
>
> Which is right in line with the quoted figure. (This is a 400MHz G4 for
> anyone interested in the absolute times.)

My results where on a 1.5Gz Pentium-M
Starting 0100000000 loops...
C = 0.65 sec
ObjC = 3.48 sec
Ratio = 5.35
with a reproducibility better than 5%.

> However, your inc() function is
> not 100% equivalent to the -inc method.

From the functionnality point of view it does and this is what is
interesting me.

> The ObjC equivalent has to add an
> offset onto the pointer that's passed in, and it also returns self.

As you point out later, the returned value does not take much. But about
the offset, I did not know that it was added to the pointer itself. I
thought that offsets were added to retrieve the arguments in the
arguments list using a va_arg like mecanism. As far as I have seen in
the Apple runtime description, the call is equivalent to id (*IMP)(id,
SEL, ...).

In gcc, I have seen in the code that they use some built-in stack
reference and size to propagate the arguments list into the method call.
So the mecanism seems to be equivalent.

In both cases, I don't think that the lost time (at least in my test) is
comming from the va_arg like mecanism.

> The return had no effect on my timings, but it turns out the offset did. I
> wrote a different inc function and passed 'foo' to it:
>
> id inc_func(id self)
> {
> long *ptr = (long *)self + 1;
> (*ptr)++;
> return self;
> }
>
> Using this instead, I got these timings:
>
> Starting 0100000000 loops...
> C = 10.86 sec
> ObjC = 17.04 sec
> Ratio = 1.57
>
> I also tried the experiment using the IMP for -inc, and got about .2
> seconds less on the C test than calling inc_func().

That's normal since this is equivalent to call the function directly
through the function pointer and the latter remains probably in a CPU
register inside the loop.

> Of course, to really test overhead, you should use methods and functions
> that really do nothing at all.

What do you mean? Incrementing the long is completely negligeable (<5%
of the overall time). You can even remove it if you want but let it as
an argument.

> But in any case, my results were in line
> with the 1.5-2 figure. I'm curious to know why yours were so much worse.

So do I. Gcc use 2-levels sparse arrays (3-levels code can be activated
with compilation flags) which normaly should be efficient, but they have
many internal function calls to make the machinery running.

> Hmm, I just tried it with optimization turned on, and the C figures get a
> whole lot better (1.5 seconds, ObjC goes down to 8.4 seconds, ratio 5.7),

Are you talking about the code I provided? In that case it is matching
my test (inc_func cannot be inlined). I was using -O3 in my compilation
and that is why I put the function inc in a separate file.

> in line with the figures you gave above. Is this result legitimate? Is the
> optimizer doing something that it couldn't do in a more real-world test? I
> don't have any answers to that one.

I thought that my "stupid" program was reflecting a common use of
message dispatch.

Thanks for you results.

ld.

James Weatherley wrote:
> In article <c27e5g$3f1$1@sunnews.cern.ch>, Laurent.Deniau@cern.ch
> says...
>
>>it is said that Objective-C is fast, with a time for message call of
>>only 1.5 to 2 times the time of the C function call. I did a very simple
>>quick and dirty benchmark which is showing that POC messages are >5
>>times slower than C and gcc messages are >8 times slower than C. I put
>>the code below (for POC).
>>
>>I can accept a factor of 2 but >5 is really too slow. So what is the
>>reality about message efficiency?
>>
>
>
> I had a go at your benchmark on Panther. I modified it to use NSObject
> and stuck everything in one file.

If you put everything in one file, you allow the compiler to do
(implicit) inlining and this is what I wanted to avoid, either in C or
ObjC, by spliting things into files.

> I got:
>
> james$ gcc -o objc objc.m -lobjc -framework Foundation
> james$ ./objc
> Starting 0100000000 loops...
> C = 3.39 sec
> ObjC = 8.75 sec
> Ratio = 2.58
>
> Not so bad...
>
>
> However if we crank up the optimiser things go very pearshaped for objc
> - I suspect such a simple C function in a tight loop has plenty of scope
> for being optimised to hell.
>
> james$ gcc -o objc objc.m -lobjc -O3 -framework Foundation
> james$ ./objc
> Starting 0100000000 loops...
> C = 0.17 sec
> ObjC = 5.55 sec
> Ratio = 32.65 <- Ouch!

Here the C function has probably be inlined...

> How did you compile your benchmark run?

As you but with things splited into files to avoid inlining.

ld.

In article <20040304111010.F39060@agamemnon.twistedsys.net>,
mikeash@mikeash.com says...
> Hmm, I just tried it with optimization turned on, and the C figures get a
> whole lot better (1.5 seconds, ObjC goes down to 8.4 seconds, ratio 5.7),
> in line with the figures you gave above. Is this result legitimate? Is the
> optimizer doing something that it couldn't do in a more real-world test? I
> don't have any answers to that one.
>
>

The optimised C version does not call inc() so it is making 0 function
calls within the loop. I don't know what it is up to because I don't
have m4d PPC asm skillz but this is what instructions are between the
two calls to clock() wrapping the call to inc():

;Start of main()
0x00004248 <main+0>: mflr r5
0x0000424c <main+4>: bcl- 20,4*cr7+so,0x4250 <main+8>
0x00004250 <main+8>: stmw r26,-32(r1)
0x00004254 <main+12>: mflr r31
0x00004258 <main+16>: mr r30,r4
0x0000425c <main+20>: addis r2,r31,0
0x00004260 <main+24>: addis r4,r31,0
0x00004264 <main+28>: mr r27,r3
0x00004268 <main+32>: lwz r3,7608(r4)
0x0000426c <main+36>: lis r28,1525
0x00004270 <main+40>: lwz r4,7600(r2)
0x00004274 <main+44>: stfd f31,-8(r1)
0x00004278 <main+48>: stw r5,8(r1)
0x0000427c <main+52>: stwu r1,-128(r1)
0x00004280 <main+56>: bl 0x45d4 <dyld_stub_objc_msgSend>
0x00004284 <main+60>: cmpwi r27,1
0x00004288 <main+64>: mr r26,r3
0x0000428c <main+68>: ori r27,r28,57600
0x00004290 <main+72>: ble+ 0x42a8 <main+96>
0x00004294 <main+76>: lwz r3,4(r30)
0x00004298 <main+80>: li r4,0
0x0000429c <main+84>: li r5,0
0x000042a0 <main+88>: bl 0x45b4 <dyld_stub_strtoul>
0x000042a4 <main+92>: mr r27,r3
0x000042a8 <main+96>: addis r8,r31,0
0x000042ac <main+100>: mr r4,r27
0x000042b0 <main+104>: addi r3,r8,1120
0x000042b4 <main+108>: bl 0x4594 <dyld_stub_printf>
0x000042b8 <main+112>: addis r7,r31,0
0x000042bc <main+116>: lwz r6,3620(r7)
0x000042c0 <main+120>: addi r3,r6,88
0x000042c4 <main+124>: bl 0x4574 <dyld_stub_fflush>

; C inc() function 'call'
0x000042c8 <main+128>: bl 0x4554 <dyld_stub_clock>
0x000042cc <main+132>: cmpwi r27,0
0x000042d0 <main+136>: mr r28,r3
0x000042d4 <main+140>: beq- 0x42e0 <main+152>
0x000042d8 <main+144>: mtctr r27
0x000042dc <main+148>: bdnz- 0x42dc <main+148>
0x000042e0 <main+152>: bl 0x4554 <dyld_stub_clock>

On Thu, 4 Mar 2004, Laurent Deniau wrote:

> Michael Ash wrote:
>
> > The ObjC equivalent has to add an
> > offset onto the pointer that's passed in, and it also returns self.
>
> As you point out later, the returned value does not take much. But about
> the offset, I did not know that it was added to the pointer itself. I
> thought that offsets were added to retrieve the arguments in the
> arguments list using a va_arg like mecanism. As far as I have seen in
> the Apple runtime description, the call is equivalent to id (*IMP)(id,
> SEL, ...).
>
> In gcc, I have seen in the code that they use some built-in stack
> reference and size to propagate the arguments list into the method call.
> So the mecanism seems to be equivalent.

You're confusing two different issues, here.

One issue is, how do the methods get arguments passed to them? Basically,
a method like:

- foobj1 barbj2;

Is translated into a function like this:

id FoobarIMP(id self, SEL _cmd, id obj1, id obj2);

While objc_msgSend is a varargs function, that is just for convenience.
For most methods (those that don't explicitly use varargs themselves),
varargs are not involved at all.

The other issue is, how do methods get to instance variables? They do it
by using the self pointer which is an implicit argument to every method.
'self' is a pointer to the object to which the message was sent. You use
fixed offsets from the self pointer to get to the various ivars. You are,
in effect, passing around a reference to a struct and getting variables
out of it. So for your -inc method to access the cnt ivar, it has to take
an offset off the 'self' argument. Apparently this offset takes a
significant amount of time to compute, at least on my computer.

> > Of course, to really test overhead, you should use methods and functions
> > that really do nothing at all.
>
> What do you mean? Incrementing the long is completely negligeable (<5%
> of the overall time). You can even remove it if you want but let it as
> an argument.

I took it out and got a ratio of 2.03. Not too significant, but not zero
either.

> > Hmm, I just tried it with optimization turned on, and the C figures get a
> > whole lot better (1.5 seconds, ObjC goes down to 8.4 seconds, ratio 5.7),
>
> Are you talking about the code I provided? In that case it is matching
> my test (inc_func cannot be inlined). I was using -O3 in my compilation
> and that is why I put the function inc in a separate file.

Yes, the code you provided. With only one change (the #include <objpak.h>
has to be changed to #include <objc/Object.h>) it compiles fine on OS X. I
was running the first tests without any -O flags at all.

> > in line with the figures you gave above. Is this result legitimate? Is the
> > optimizer doing something that it couldn't do in a more real-world test? I
> > don't have any answers to that one.
>
> I thought that my "stupid" program was reflecting a common use of
> message dispatch.

Message dispatch typically dispatches to something that is complicated or
not often called. If your program is doing the equivalent of incrementing
a counter a million times in a tight loop with an ObjC message, you're
probably doing something wrong. Normally, message-send overhead is very
small, because the contents of the methods take overwhelmingly more time
to execute than the message send itself.

On the other hand, I was wondering if a small program like this affords
the optimizer opportunities to improve the C function call speed that it
wouldn't get in a larger program. Obviously there is a lot of
function-call optimization going on in this program. My question is
whether this is a normal possibility, or whether it's only made possible
by the simple nature of the program.

Michael Ash wrote:
> On Thu, 4 Mar 2004, Laurent Deniau wrote:
>
>
>>Michael Ash wrote:
>>
>>
>>>The ObjC equivalent has to add an
>>>offset onto the pointer that's passed in, and it also returns self.
>>
>>As you point out later, the returned value does not take much. But about
>>the offset, I did not know that it was added to the pointer itself. I
>>thought that offsets were added to retrieve the arguments in the
>>arguments list using a va_arg like mecanism. As far as I have seen in
>>the Apple runtime description, the call is equivalent to id (*IMP)(id,
>>SEL, ...).
>>
>>In gcc, I have seen in the code that they use some built-in stack
>>reference and size to propagate the arguments list into the method call.
>>So the mecanism seems to be equivalent.
>
>
> You're confusing two different issues, here.

:-)

> One issue is, how do the methods get arguments passed to them? Basically,
> a method like:
>
> - foobj1 barbj2;
>
> Is translated into a function like this:
>
> id FoobarIMP(id self, SEL _cmd, id obj1, id obj2);

Here you are talking about the method invocation and I completely agree.
But how objc_msgSend converts its va_list into the method arguments list
which are usually two different things?

> While objc_msgSend is a varargs function, that is just for convenience.

Not only for convenience, this is probably the only way to do it in C if
you want a single interface for message call.

> For most methods (those that don't explicitly use varargs themselves),
> varargs are not involved at all.

In the method, I agree. In fact, when I saw the explanation, I was
thinking about an offset shift inside the object *before* calling the
method like it may happen in C++ for object build from multiple inheritence.

> The other issue is, how do methods get to instance variables? They do it
> by using the self pointer which is an implicit argument to every method.
> 'self' is a pointer to the object to which the message was sent. You use
> fixed offsets from the self pointer to get to the various ivars. You are,
> in effect, passing around a reference to a struct and getting variables
> out of it. So for your -inc method to access the cnt ivar, it has to take
> an offset off the 'self' argument. Apparently this offset takes a
> significant amount of time to compute, at least on my computer.

Clearly not (even on your computer ;-). C structures and C++ objects use
the same mecanism for computing members offset without penalty on recent
architectures. I modified the code (see below) to show up the influence
of returning a pointer and to add an offset to the object base and I
have the excatly same results:

Starting 0100000000 loops...
C = 0.65 sec
ObjC = 3.48 sec
Ratio = 5.35

>>>Of course, to really test overhead, you should use methods and functions
>>>that really do nothing at all.

In term relative load, they do nearly nothing except what I would like
to measure and to understand.

[...]

> Yes, the code you provided. With only one change (the #include <objpak.h>
> has to be changed to #include <objc/Object.h>) it compiles fine on OS X. I
> was running the first tests without any -O flags at all.

But you said that you put all the things in a single file (and your
compilation line is saying the same) and this is a big change which
breaks down what I wanted to measure. I want full code optimization but
no function inline to measure exclusively the time ratio between
function call and message call.

>>>in line with the figures you gave above. Is this result legitimate? Is the
>>>optimizer doing something that it couldn't do in a more real-world test? I
>>>don't have any answers to that one.
>>
>>I thought that my "stupid" program was reflecting a common use of
>>message dispatch.
>
>
> Message dispatch typically dispatches to something that is complicated or
> not often called. If your program is doing the equivalent of incrementing
> a counter a million times in a tight loop with an ObjC message, you're
> probably doing something wrong. Normally, message-send overhead is very
> small, because the contents of the methods take overwhelmingly more time
> to execute than the message send itself.

This not true for all applications. Numerical computation, data sorting
and many algorithms require to repeat millions of times a small set of
fast operations on objects of unknown type where only one of the super
class type is known.

That is why I was accepting up to a factor 2 in speed loss. But >5
becomes to much comparing to other polymorphic function call techniques.

> On the other hand, I was wondering if a small program like this affords
> the optimizer opportunities to improve the C function call speed that it
> wouldn't get in a larger program. Obviously there is a lot of
> function-call optimization going on in this program.

If you keep the things in separate files, the compiler cannot do any
optimisation on the function call since the function implementation is
not in the same compilation unit as the function call.

ld.

On Thu, 4 Mar 2004, Laurent Deniau wrote:

> > One issue is, how do the methods get arguments passed to them? Basically,
> > a method like:
> >
> > - foobj1 barbj2;
> >
> > Is translated into a function like this:
> >
> > id FoobarIMP(id self, SEL _cmd, id obj1, id obj2);
>
> Here you are talking about the method invocation and I completely agree.
> But how objc_msgSend converts its va_list into the method arguments list
> which are usually two different things?

It doesn't. Normally, objc_msgSend() will simply look up the correct
function to call, and then jump directly to it. It doesn't know anything
about other parameters past self and _cmd, but it keeps them in place so
that the 'real' function can get to them. objc_msgSend() is not a function
that calls a function, it's more like an extended prolog that happens to
be shared code. This is evident whenever you debug an ObjC program, in
that the objc_msgSend() calls don't show up on the stack unless you happen
to be stopped inside of one, and then only at the top.

> > While objc_msgSend is a varargs function, that is just for convenience.
>
> Not only for convenience, this is probably the only way to do it in C if
> you want a single interface for message call.

You could just as easily define objc_msgSend() like this:

id objc_msgSend(id self, SEL _cmd);

And then require that you cast for all methods that take arguments. It
wouldn't affect the compiled code at all, and it wouldn't even affect any
ObjC code that doesn't directly call objc_msgSend(). You already have to
cast it if your methods take non-id arguments or return non-id values.

> > The other issue is, how do methods get to instance variables? They do it
> > by using the self pointer which is an implicit argument to every method.
> > 'self' is a pointer to the object to which the message was sent. You use
> > fixed offsets from the self pointer to get to the various ivars. You are,
> > in effect, passing around a reference to a struct and getting variables
> > out of it. So for your -inc method to access the cnt ivar, it has to take
> > an offset off the 'self' argument. Apparently this offset takes a
> > significant amount of time to compute, at least on my computer.
>
> Clearly not (even on your computer ;-).

Looks like you're right. I modified the program slightly to test that and
I'm getting basically the same timings with or without the offset.

> > Yes, the code you provided. With only one change (the #include <objpak.h>
> > has to be changed to #include <objc/Object.h>) it compiles fine on OS X. I
> > was running the first tests without any -O flags at all.
>
> But you said that you put all the things in a single file (and your
> compilation line is saying the same) and this is a big change which
> breaks down what I wanted to measure.

No, that is not me, that was another poster. I began with your exact
files, except for the one change tho the #include line. That is all I
changed at the beginning.

> > Message dispatch typically dispatches to something that is complicated or
> > not often called. If your program is doing the equivalent of incrementing
> > a counter a million times in a tight loop with an ObjC message, you're
> > probably doing something wrong. Normally, message-send overhead is very
> > small, because the contents of the methods take overwhelmingly more time
> > to execute than the message send itself.
>
> This not true for all applications. Numerical computation, data sorting
> and many algorithms require to repeat millions of times a small set of
> fast operations on objects of unknown type where only one of the super
> class type is known.

Normally when you are implementing the inner loops of those kinds of
applications, you ditch dynamic dispatch and use straight C function
calls and inlined functions as much as possible. This is as true in ObjC
as it is in C++. The difference is that in C++, you can use techniques
like stack-allocated objects and non-virtual methods to gain speed while
still keeping some of the OO-aspects of the language. In ObjC, you have to
use IMP caching, structs, and C functions, which distance you from the OO
portions of the language. If you really are in a situation where you need
the full dynamic ObjC-style dispatch, I doubt if you'll find a faster way
of doing it than calling objc_msgSend(), because it is already about as
optimized as it's going to get.

> > On the other hand, I was wondering if a small program like this affords
> > the optimizer opportunities to improve the C function call speed that it
> > wouldn't get in a larger program. Obviously there is a lot of
> > function-call optimization going on in this program.
>
> If you keep the things in separate files, the compiler cannot do any
> optimisation on the function call since the function implementation is
> not in the same compilation unit as the function call.

Obviously that was not a problem. Is there anything else?

Laurent Deniau <Laurent.Deniau@cern.ch> wrote:
>
> I can accept a factor of 2 but >5 is really too slow. So what is the
> reality about message efficiency?

Did you compile with:

objc -inlineCache -O2 ?