mikeash.com pyblog/friday-qa-2009-04-24-code-generation-with-llvm-part-2-fast-objective-c-forwarding.html comments

Atii - 2013-04-16 06:42:55

Tue, 16 Apr 2013 06:42:55 GMT

Hi Mike,
Thnx for the wonderful post. Would you also do a tutorial about fast enumeration using LLVM code generation technique and also suggest some more use of it in objective C. That would be really great.. :)

mikeash - 2009-06-10 23:21:13

Wed, 10 Jun 2009 23:21:13 GMT

I searched around and found almost no information about the LLVM C API. What I did find indicated that it was incomplete, although that information was old.

In any case, I figure that if you don't know C++ and you want to do this kind of thing, you probably ought to just learn it. LLVM is not a beginners' library, and C++, while an ugly and horrible language in so many ways, is also an essential part of an advanced developer's toolkit.

wombat - 2009-06-10 14:57:09

Wed, 10 Jun 2009 14:57:09 GMT

Hi Mike,

thanks for this two-part series on how to use LLVM. Although it seems most of the posters have misunderstood the purpose of the example, I'd like to encourage you to do some more "LLVM how-to" in the future.

In particular, it would be interesting to see how the LLVM API's C-wrapper is used to call LLVM from C. Every Objective-C developer knows C of course, but not necessarily C++.

mikeash - 2009-04-26 11:22:10

Sun, 26 Apr 2009 11:22:10 GMT

I didn't bother to look into the amount of overhead, although it's definitely an interesting question. It seems to be pretty fast. In testing I dropped the timer to half a second instead of five seconds, and I couldn't see any startup delay with that. Whether that means it's 100ms or 100us, I don't know. If you decide to test it, please post your results!

As for the optimizations, it was pretty much just copy/paste from the tutorials for that section. Your best bet would be to read the LLVM documentation for the various stuff being passed to the FunctionPassManager.

Matt Gallagher - 2009-04-26 11:20:50

Sun, 26 Apr 2009 11:20:50 GMT

Wow, this is a huge post. Even if you had the code written, it must have taken a while to put together.

Thanks for taking the time!

david - 2009-04-26 10:10:23

Sun, 26 Apr 2009 10:10:23 GMT

nice post -- any perf metrics on the time needed to dynamically compile the code? what about memory foot print? what kind of optimizations are being performed during code gen?

mikeash - 2009-04-26 07:21:17

Sun, 26 Apr 2009 07:21:17 GMT

The LLVM voodoo can't go in resolveInstanceMethod: because you can't get the true method signature there, as it's a class method. (My original implementation used that, and cheated by stashing the "current proxy" in a global variable, but that's just plain ugly.) However it shouldn't matter speed-wise because forwardInvocation: only happens once. After the initial setup, method dispatch goes straight to the newly generated function and never passes through forwardInvocation: again. The setup cost is already huge due to building and compiling this dynamically-created function, so a bit of extra work doing forwardInvocation: isn't going to matter.

jason - 2009-04-26 06:58:54

Sun, 26 Apr 2009 06:58:54 GMT

Thanks Mr. Ash! I've been looking for just this for some time.

Harvey - 2009-04-26 06:47:51

Sun, 26 Apr 2009 06:47:51 GMT

Very nice! Does it get much faster if you implement the llvm voodoo in resolveInstanceMethod: instead of forwardInvocation:?

mikeash - 2009-04-26 04:09:06

Sun, 26 Apr 2009 04:09:06 GMT

It is true that there's a difference between lookup done by the standard for loop and the one done by the HOM implementation. But neither one is correct for a loop that contains distinct method signatures for the selector in question. Consider this code:

for(id obj in array) [obj foo:bar];

When the compiler generates the code for [obj foo:bar], it needs to know the method signature at compile time in order to generate the correct code. (If foo: returns a struct, it needs to generate a call to objc_msgSend_stret, if foo: takes a float, it needs to pass bar as a float, etc. In order to do this, is just looks at whatever declaration for a foo: method is in scope. If none is in scope, it assumes vararg calling conventions. If more than one is in scope, it picks one at random.

While different from using the last object's method signature, it works no better.

As for your second question, sure, both cases use bog-standard ObjC messaging to talk to the contents of the array and therefore do the exact same thing in terms of invoking forwarding methods.

Steve Wart - 2009-04-26 02:54:50

Sun, 26 Apr 2009 02:54:50 GMT

I think there's a difference between the dynamic method lookup done by the standard for loop and binding every object in an array to

[[_array lastObject] methodSignatureForSelector:sel];

if I have [NSArray arrayWithObjects:dog, cat, nil] and invoke @selector(bark) on each object, will the cat's forwardInvocation: method will be called in both the LLVM and the normal case? (assuming dog understands SEL(bark) but cat doesn't)

mikeash - 2009-04-26 01:48:35

Sun, 26 Apr 2009 01:48:35 GMT

The difference between the 6x speedup and the factor of 1000 comes about because of all the other work that's going on. The thousand times slower comes from doing forwardInvocation: and nothing else. Here, the program creates two objects (the proxy and the array) and then does some more work on them.

As for typing, this is just an inherent problem with Objective-C. Objective-C doesn't really tolerate having multiple methods in an application with the same selector but different signatures. It'll survive if you keep them well separated, but if you load them into an array and try to do something with them, you'll fall down. Even a standard for loop will break here. In practice, this problem does not occur very frequently. The array does not need to be homogenous, it just needs to have every object respond to that selector and use the same signature. In practice, the former will imply the latter.

For what it does, Objective-C messaging is basically as fast as it can possibly be. At 13 CPU cycles on i386 there's little to shave further. Smalltalk can go faster in some cases because it's actually doing something completely different. Namely, it's running a JIT compiler on the code at runtime, identifying places where dynamic dispatch can be eliminated due to proving what type of objects will be there, and doing a direct jump to the method in question or even inlining the implementation. That is, in fact, exactly the sort of "invoking the compiler" that you say you don't think are where performance gains lie.

One last note: since both comments so far seem to have missed this, it bears repeating. This example is not meant to be practical. This post is "how to integrate LLVM-generated code with your real code", not "how to make your Objective-C go faster". Faster is not the goal of this code, illustration is. That it's also several times faster than the simple implementation is a nice bonus, but it's not the point.

Steve Wart - 2009-04-26 01:17:02

Sun, 26 Apr 2009 01:17:02 GMT

Thanks for taking the time to put together this post. There are a couple of things I'm not comfortable with however.

It seems unfortunate that you can only get a 6x speedup with the LLVM implementation when you say that forwardInvocation: is "about a thousand times slower" than direct method invocation. I wonder if there's a better approach than invoking the compiler to create a method on an arbitrary class. Dynamic translation and inline caching is probably the "right" approach, although this requires runtime support (there are some interesting comments about an approach to doing this with LLVM here http://www.mirandabanda.org/cogblog/2008/06/06/cog/#comment-17).

The second issue pertains to typing. Both the normal and the LLVM implementations obtain the method signature from the last object in the array. Setting aside the case of an empty array, assuming that the binding for the last object applies to every other object is not safe unless there is some way to ensure the array is homogeneous.

Still, it's great to see these sorts of features being discussed for Objective-C. I was surprised to to come across some results indicating that Smalltalk message dispatching is still faster than the approach used in Objective-C (see the comment thread on this post http://ridiculousfish.com/blog/?p=22). Obviously that's more than made up for by the ability to include as much "raw" C as you need, but it suggests that a good runtime can be used to improve performance as well as to provide dynamic access to type information.

[I started building an equivalent test harness in Smalltalk but none of the implementations I am familiar with have a good quality microsecond timer. Eliot Miranda has some advice on how to do that so I might be able to cobble something together. I'll let you know how that goes :-)]

I suspect that the best opportunities for performance gains for dynamic Objective-C code will come from a smarter runtime than from invoking the compiler in this way. Nonetheless, it's useful to have such a realistic and detailed example about using LLVM with Objective-C.

mikeash - 2009-04-25 08:34:42

Sat, 25 Apr 2009 08:34:42 GMT

I really don't see how your code is easier than this:

NSArray *newArray = [[array map] stringByAppendingString:@"suffix"];

One line versus three. If you're counting the support code to implement map, well, don't. You don't count the support code to implement arrayWithCapacity: in your version....

As for your other one, that's nice and all, but falls apart the moment you want more parameters, or a parameter of a different type, which is most of the time.

Looking further, a more sophisticated HOM implementation can do something like this:

NSArray *newArray = [[prefixes map] stringByAppendingString:[suffixes each]];

To provide multi-array iteration.

Of course blocks will pretty much put HOM to rest for most people who are aware of it in the first place, but the whole point of this example was to show how you could use LLVM, not to show how you could use HOM.

Gwynne - 2009-04-25 06:41:58

Sat, 25 Apr 2009 06:41:58 GMT

The LLVM approach is elegant and powerful, but I feel that it's worth noting that the particular problem you were solving here could done with the rather this rather easier code:

NSMutableArray *result = [NSMutableArray arrayWithCapacity:[array count]];

for (NSString *str in array)
[result addObject:[str stringByAppendingString:@"suffix"]];

This code is less "Wow, look at the cool things I can do with Objective-C!"-ish, but it's simple, it works, and it doesn't incur the overhead of message forwarding. You could even generalize it with something like this:

@implementation NSArray (PerformSelector)
- (NSArray *)arrayByApplyingSelectorToObjects:(SEL)selector withObject:(id)argOrNil
{
    NSMutableArray *result = [NSMutableArray arrayWithCapacity:[self count]];

    for (id obj in self)
    {
        if (argOrNil)
            [result addObject:[obj performSelector:selector withObject:argOrNil]];
        else
            [result addObject:[obj performSelector:selector]];
    }
    return result; // Cast from mutable array to nonmutable array
}
@end

This doesn't have the flexibility implied by using full-fledged message forwarding, but it'll work for a lot of cases.