Movatterモバイル変換

Welcome back to another shiny edition of Friday Q&A.Guy English suggested taking a look at implementing futures in Objective-C using blocks, and for this week's post I'm going to talk about the futures implementation that I built.

Futures
A future is, in short, an object which hides a calculation. When a future isresolved, the resolution blocks until the calculation has finished. My code involvesimplicit futures: a future is a proxy for the calculated result and, when messaged, transparently resolves the future and then passes the message on to the result. To code which uses it, a future is essentially indistinguishable from the object that it represents.

In Objective-C, it's natural to represent the calculation using a block. Futures are created by simply calling a function which takes a block representing the calculation. They return aproxy object which captures messages sent to that object and resolves the future as needed. My code has two kinds of futures.

Background futures begin the calculation immediately on a background thread as soon as the future is created. When the future is resolved, if the calculation is not yet complete, the call blocks until it's done. If the calculation finishes first, then resolution completes immediately. Background futures provide a way to write parallel code without needing to worry about details of synchronization. For example, if you're going to pass anNSData to another object that won't actually use thatNSData for a while, you can use a background future to allow other code to run concurrently with the disk access with very little effort:

NSString*filename=...;NSData*future=MABackgroundFuture(^{return[NSDatadataWithContentsOfFile:filename];});[objectdoSomethingLaterWithData:future];

NSString*filename=...;NSData*future=MALazyFuture(^{return[NSDatadataWithContentsOfFile:filename];});[objectdoSomethingOrNotWithData:future];

Getting the Code
As usual, I'm just going to cover the highlights of the code here, but the library is available from my subversion repository:

    svn cohttp://mikeash.com/svn/MAFuture/

A Custom Proxy Class
When building object proxies, Cocoa provides a convenient root proxy class to subclass in the form ofNSProxy. The idea is thatNSProxy provides a minimal implementation, which allows almost all messages to be captured and proxied.

Unfortunately,NSProxy doesn't quite live up to its promise. It implements a whole bunch of unnecessary methods, including important ones like-hash and-isEqual:. This is a problem because I don't wantNSProxy's implementations of these, I want the implementations in the proxied object. To make that happen, I'd have to either manually override these methods, or play runtime tricks to make them hit the forwarding path. Neither alternative is particularly appealing.

Instead, I chose a third route: implement my own proxy class.MAProxy is a true minimalistic proxy class. It implements memory management methods and-isProxy. It also implements+initialize, which the runtime requires to exist in every class. Theheader is really basic and theimplementation nearly as simple. The only tricky stuff at work is the inline reference count using atomic functions for thread safety.

Future Basics
To make implementing futures easier, I created a base class calledMABaseFuture which provides common facilities. A basic future needs to be able to store a value, to store whether the future has been resolved yet or not, and a condition variable to make it all thread safe:

@interfaceMABaseFuture :MAProxy{id_value;NSCondition*_lock;BOOL_resolved;}

-(id)init{_lock=[[NSConditionalloc]init];returnself;}-(void)dealloc{[_valuerelease];[_lockrelease];[superdealloc];}

-(void)setFutureValue:(id)value{[_locklock];[selfsetFutureValueUnlocked:value];[_lockunlock];}-(id)futureValue{// skip the usual retain/autorelease dance here// because the setter is never called more than// once, thus value lifetime is same as future// lifetime[_locklock];idvalue=_value;[_lockunlock];returnvalue;}-(void)setFutureValueUnlocked:(id)value{[valueretain];[_valuerelease];_value=value;_resolved=YES;[_lockbroadcast];}

-(BOOL)futureHasResolved{return_resolved;}

-(id)waitForFutureResolution{[_locklock];while(!_resolved)[_lockwait];[_lockunlock];return_value;}

-(id)resolveFuture{NSLog(@"-[MABaseFuture resolveFuture] called, this should never happen! Did you forget to implement -[%@ resolveFuture]?",NSStringFromClass(isa));NSParameterAssert(0);returnnil;}

The fix is simple, if bizarre. Get the real class, check to see if it starts withNSCF, and return the superclass if it does. If the real class isNSCFString, this will returnNSString, the code goes through the general equality path, and all is well. This is the implementation of-class:

-(Class)class{Classc=[[selfresolveFuture]class];if([NSStringFromClass(c)hasPrefix:@"NSCF"])return[csuperclass];elsereturnc;}

Deepening the Hierarchy
Building onMABaseFuture, I want to then create a tree of subclasses. First,_MASimpleFuture will contain some more common facilities for "simple" futures (futures which immediately resolve when accessed), then I'll create two subclasses of that for background and lazy futures.

_MASimpleFuture is very, well, simple. It implements-forwardingTargetForSelector: to resolve the future and return the object that resulted:

-(id)forwardingTargetForSelector:(SEL)sel{LOG(@"%p forwardingTargetForSelector: %@, resolving future",self,NSStringFromSelector(sel));return[selfresolveFuture];}

Forwarding tonil
There's a bad corner case here, which happens if the future returnsnil. Messagingnil is no problem, butforwardingTargetForSelector: takes anil return as meaning that there is no forwarding target, and the runtime should start on the slow forwarding path instead.

And here there's a major problem, because the slow forwarding path requires a method signature, but it's impossible to get one fromnil. I've partially solved this in an extremely brute-force fashion by writing a class calledMAMethodSignatureCache, which will check every class registered with the runtime for a selector and return whatever method signature it can dig up. (I didn't write it solely for this, there's more handy stuff to do with it in another post.) I can use this class to implement the slow forwarding path of_MASimpleFutureto return zero:

-(NSMethodSignature*)methodSignatureForSelector:(SEL)sel{return[[MAMethodSignatureCachesharedCache]cachedMethodSignatureForSelector:sel];}-(void)forwardInvocation:(NSInvocation*)inv{// this gets hit if the future resolves to nil// zero-fill the return valuecharreturnValue[[[invmethodSignature]methodReturnLength]];bzero(returnValue,sizeof(returnValue));[invsetReturnValue:returnValue];}

If that's not enough, there's another problem with futures that returnnil. This problem is quite simple: although the futured value may be nil, the future object itself is not nil. Any code which checks the object pointer for nil before using it will fail in weird ways. Imagine this code using an NSData:

NSData*data=...;if(data)[selfdoSomethingWithBytes:[databytes]];

Because of these two problems, you should avoid futuring any computation which might returnnil.

Background Futures
To implement background futures, I created a class called_MABackgroundBlockFuture. Since computation is supposed to begin immediately in the background, I create an initializer which takes the block to compute, and uses Grand Central Dispatch to execute it in the background. Once the computation is finished, it simply calls-setFutureValue: to set the computed value and mark the future as resolved:

-(id)initWithBlock:(id(^)(void))block{if((self=[selfinit])){dispatch_async(dispatch_get_global_queue(0,0),^{[selfsetFutureValue:block()];});}returnself;}

-(id)resolveFuture{return[selfwaitForFutureResolution];}

-(id)initWithBlock:(id(^)(void))block{if((self=[selfinit])){_block=[blockcopy];}returnself;}-(void)dealloc{[_blockrelease];[superdealloc];}

-(id)resolveFuture{[_locklock];if(![selffutureHasResolved]){[selfsetFutureValueUnlocked:_block()];[_blockrelease];_block=nil;}[_lockunlock];return_value;}

idMABackgroundFuture(id(^block)(void)){return[[[_MABackgroundBlockFuturealloc]initWithBlock:block]autorelease];}idMALazyFuture(id(^block)(void)){return[[[_MALazyBlockFuturealloc]initWithBlock:block]autorelease];}

NSArray*array=MALazyFuture(^{return[selfsomethingThatReturnsNSString];});

I worked around both of these problems by using two really scary-looking macros:

#defineMABackgroundFuture(...)((__typeof((__VA_ARGS__)()))MABackgroundFuture((id(^)(void))(__VA_ARGS__)))#defineMALazyFuture(...)((__typeof((__VA_ARGS__)()))MALazyFuture((id(^)(void))(__VA_ARGS__)))

First, they take variable arguments, because block syntax doesn't play completely nice with the preprocessor. If you write a block which contains a comma that isn't inside parentheses (which can be written completely legally), the preprocessor won't realize that it's inside a block, and will use that as an argument separator. The preprocessor will therefore see two (or more) arguments, and a single-argument macro will fail. By making the macros take..., that problem is avoided. Thus, the block parameter is represented in the macro by__VA_ARGS__.

__typeof is a gcc language extension which pretty much does what it says. You give it an expression, and it gives you the type of the expression.

The argument to__typeof is(__VA_ARGS__)(). Remember that__VA_ARGS__ is the block being passed to the macro. This expression calls the block. But since it's an argument being passed to__typeof, which is a compile-time construct, it doesn'treally call the block. Put the two together, and you get the return type of the block.

Next, the whole__typeof combination is wrapped in another set of parentheses and put right before the call through to the real function, which casts the return value of the function.

Finally, the function argument is cast toid (^)(void), because gcc is too stupid to understand that a block which returnsNSString * is compatible with a block type that returnsid.

Potential Uses
Background futures are useful any time you have computation which can happen asynchronously. In essence, you can think of the future as a synchronization mechanism, like a lock, which ensures that the job is completed before the result is used. Because these futures automatically forward requests, you can pass the future into code that doesn't know what it is, and it will be resolved automatically.

For example, let's say you're building a composite image by loading one image from disk, shrinking another image that already exists, and then putting the result into an image view:

NSImage*image1=[[NSImagealloc]initWithContentsOfFile:...];NSImage*image2=[selfshrinkImage:existingImage];NSImage*composite=[[NSImagealloc]initWithSize:...];[compositelockFocus];[image1drawAtPoint:NSZeroPointfromRect:NSZeroRectoperation:NSCompositeSourceOverfraction:1.0];[image2drawAtPoint:NSZeroPointfromRect:NSZeroRectoperation:NSCompositeSourceOverfraction:1.0];[compositeunlockFocus];[imageViewsetImage:composite];

NSImage*image1=MABackgroundFuture(^{return[[[NSImagealloc]initWithContentsOfFile:...]autorelease];});NSImage*image2=MABackgroundFuture(^{return[selfshrinkImage:existingImage];});NSImage*composite=MABackgroundFuture(^{NSImage*img=[[NSImagealloc]initWithSize:...];[imglockFocus];[image1drawAtPoint:NSZeroPointfromRect:NSZeroRectoperation:NSCompositeSourceOverfraction:1.0];[image2drawAtPoint:NSZeroPointfromRect:NSZeroRectoperation:NSCompositeSourceOverfraction:1.0];[imgunlockFocus];return[imgautorelease];});[imageViewsetImage:composite];

Lazy futures are useful any time you have objects that may never be needed, or simply may not be needed for a long time. Even if the object is used, deferring computation can spread out the load and improve responsiveness and startup times.

As an example, imagine some code which sets up a bunch of data file contents to be accessed through a dictionary:

gGlobalDictionary=[[NSDictionaryalloc]initWithObjectsAndKeys:[NSDatadataWithContentsOfFile:...],@"dataFile",[NSDatadataWithContentsOfFile:...],@"anotherDataFile",[NSDatadataWithContentsOfFile:...],@"moreDataFile",[NSDatadataWithContentsOfFile:...],@"fourthDataFile",nil];

gGlobalDictionary=[[NSDictionaryalloc]initWithObjectsAndKeys:MALazyFuture(^{return[NSDatadataWithContentsOfFile:...]}),@"dataFile",MALazyFuture(^{return[NSDatadataWithContentsOfFile:...]}),@"anotherDataFile",MALazyFuture(^{return[NSDatadataWithContentsOfFile:...]}),@"moreDataFile",MALazyFuture(^{return[NSDatadataWithContentsOfFile:...]}),@"fourthDataFile",nil];

Conclusion
Futures are an interesting technique which can make it much easier to use lazy evaluation and parallel computation. Futures make it easy to use lazy evaluation even when you have no control over (or no desire to change) the code that will eventually use the value in question. They also make for a handy synchronization mechanism for performing heterogeneous parallel computations. The dynamic nature of Objective-C makes it possible to mostly hide the existence of the future from code that isn't involved in creating it.

That's it for this week's edition. Come back in a week for the next one. As always, Friday Q&A is driven by user suggestions, so if you have a topic that you'd like to see covered here,send it in!

Add your thoughts, post a comment:

Spam and off-topic posts will be deleted without notice. Culprits may be publicly humiliated at my sole discretion.