Last time, I talked about my crazy hack that misuses the Objective-C message forwarding machinery to doblock proxying. This allows writing code that interposes in front of an arbitrary block to intercept its arguments, manipulate its return value, etc. Today, I want to present an exanmple of using this hack which almost verges on the practical. Specifically, I'm going to discuss how to use it to build a generalized block memoization facility.
What the Heck is Memoization?
In short, memoization is just a cache in front of a function. Imagine a pure function, which is to say, no side effects, and you always get the same result for the same arguments. Now imagine that this function is expensive to compute, and called multiple times with the same arguments. If the result is always the same with the same arguments, it's a waste to constantly recompute it.
The standard answer to this is a cache. Whenever the function computes a result, it can put that result into a dictionary that's keyed off the arguments. Whenever the function is called, it can check the dictionary first to see if the result is already in there. If it is, it can return the previously computed value.
Memoization is the process of performing this caching in a wrapper function. Instead of putting cache code into every function that fits this profile, you write the cache code once, as a wrapper around arbitrary functions. The wrapper has no idea how the function works, but it knows enough to cache return values and bypass the function if a particular set of arguments has already been computed.
Code
As before, the code is available on GitHub here:
https://github.com/mikeash/MABlockForwarding
Approach
The previous adventures eventually resulted in aMAForwardingBlock which takes a block and an interposer, and returns a new block. When the new block is called, the interposer is first called with anNSInvocation representing the call. The interposer can then manipulate theNSInvocation at will, optionally call through to the original block, and then give theNSInvocation's return value back to the caller.
The goal here is to write anMAMemoize function. This function takes a block, and returns a new block which wraps the original. The new block memoizes the original, caching values based on the arguments passed in.MAMemoize will useMAForwardingBlock to interpose in front of the original block, and use an interposer block to perform the memoization.
In order to accomplish this, the interposer needs to unpack all of the arguments of theNSInvocation into an object which can be used as a dictionary key. It also needs to be able to translate the return value to and from an object that can be used as a dictionary value.
Once it's able to do this, the rest is simple. Keep a dictionary which contains the memory. Unpack the arguments, and check to see if the dictionary has an entry for them. If it does, grab the value for those arguments and return it. Otherwise, call through to the original block, then fetch the return value and stash it in the memory dictionary before returning.
Implementation
To start out with, we'll define theMAMemoize function. It takes and returnid because it deals with arbitrary blocks, not just a particular type:
idMAMemoize(idblock){
Next up, create the memory dictionary. This is just a local variable, but it will be captured by the interposer block, so it ends up persisting. Blocks can be interesting like that. You can think of a block as being an object with just one method, where the captured variables are instance variables.
NSMutableDictionary*memory=[NSMutableDictionarydictionary];
Now we callMAForwardingBlock and give it our interposer. The interposer block takes anNSInvocation and a block that calls through to the original block. Here's the beginning of the call:
returnMAForwardingBlock(^(NSInvocation*inv,void(^call)(void)){
All of the code starting from here runs when the returned block is called. Theinv argument contains theNSInvocation of that call, and thecall block calls the original function.
The first thing to do is fetch the arguments into an object that can be used as a dictionary key. In this case, I chose to use anNSArray. Although this is probably not a very efficient dictionary key, this code isn't very efficient anyway and it does the job fine. The array will be filled out with objects representing each argument.
Fetching the arguments also requires knowing the invocation's method signature, so we grab that at the same time:
NSMethodSignature*sig=[invmethodSignature];NSMutableArray*args=[NSMutableArrayarray];
Now, loop through the arguments and add them to the array. Note that the loop starts at argument1, because argument0 is the implicit block pointer argument and doesn't need to be included in the cache:
for(unsignedi=1;i<[signumberOfArguments];i++){
For the case where the argument is an object, the task is easy: fetch it usinggetArgument:atIndex: and then stash it in the array. For non-object arguments, life gets more complicated. In fact, it's not possible to handle every possible type, since things like pointer types simply can't be introspected well enough to understand how they're being used.
My approach is to special-case C strings, since they seem like a common parameter type. For all other parameter types, fetch the raw argument into anNSData and treat that as the argument, not even making an attempt to interpret the meaning. In practice, this means that all primitive values will work, as will some structs and the rare pointers, likeSEL which can be compared using== and persist for the lifetime of the app.
To start with, I create anarg local variable which will hold the extracted object, whatever it is. I also grab the string describing the type of this argument:
idarg=nil;constchar*type=[siggetArgumentTypeAtIndex:i];
The first thing is to check to see if this argument is an object. We can do this by comparing the first character of 'type' with the first character of '@encode(id)':
if(type[0]==@encode(id)[0]){
For this case, just grab the argument intoarg. I add a small additional flourish where, if the argument conforms toNSCopying, it's copied before being placed into the array:
[invgetArgument:&argatIndex:i];if([argconformsToProtocol:@protocol(NSCopying)])arg=[argcopy];}
Next, check for a C string (anychar * parameter is assumed to be a C string) using the same technique. If it is one, pull its contents into anNSData:
elseif(type[0]==@encode(char*)[0]){char*str;[invgetArgument:&stratIndex:i];arg=[NSDatadataWithBytes:strlength:strlen(str)];}
Finally, for the fallback case, pull the argument directly into anNSData. TheNSGetSizeAndAlignment function can tell us how large the argument is and thus how large theNSData needs to be:
else{NSUIntegersize;NSGetSizeAndAlignment(type,&size,NULL);arg=[NSMutableDatadataWithLength:size];[invgetArgument:[argmutableBytes]atIndex:i];}
Now we have this argument inarg. Before adding it to the array, sinceNSArray doesn't likenil, check for that and useNSNull instead:
if(!arg)arg=[NSNullnull];
Now add the argument to the array and continue looping until all arguments are handled:
[argsaddObject:arg];}
Next, we checkmemory to see if the arguments are in it. If they are, we extract the return value and put it into theNSInvocation. If they aren't, we call the original block, then extract the return value from the `NSInvocation. In both cases, we need the method's return type, and we need to know if it's an object, a C string, or something else, so we precompute those:
constchar*type=[sigmethodReturnType];BOOLisObj=type[0]==@encode(id)[0];BOOLisCStr=type[0]==@encode(char*)[0];
Next up, checkmemory. This is done in a@synchronized block so that this code is thread safe:
idresult;@synchronized(memory){result=[[[memoryobjectForKey:args]retain]autorelease];}
If the arguments exist in the dictionary, thenresult will contain the object representation of the return value. Otherwise,result will benil. First, let's look at the case where there is no entry inmemory:
if(!result){
Since there's no saved value, the first thing to do is call the original block to compute the return value:
call();
Once this completes, the return value will be contained within theNSInvocation. We need to fetch it into an object so it can be stored inmemory. If the return value is an object, this is really easy. Just usegetReturnValue: and done:
if(isObj){[invgetReturnValue:&result];}
If it's a C string, then we need to fetch the string pointer, then convert that to anNSData. Note that unlike the argument saving code, I add1 to the length of the string in order to copy the string's terminatingNUL byte as well. Since this pointer needs to be returned to the caller, and the caller will expect the terminatingNUL, this saved additional redundant conversion:
elseif(isCStr){char*str;[invgetReturnValue:&str];result=str?[NSDatadataWithBytes:strlength:strlen(str)+1]:NULL;}
Finally, the fallback case. Like before, we fetch it into anNSData, usingNSGetSizeAndAlignment to figure out the necessary length:
else{NSUIntegersize;NSGetSizeAndAlignment(type,&size,NULL);result=[NSMutableDatadataWithLength:size];[invgetReturnValue:[resultmutableBytes]];}
And again, if the object isnil, replace it withNSNull:
if(!result)result=[NSNullnull];
Now that we have the result, store it inmemory. At this point, we're done with this particular code path. The proper return value is already in theNSInvocation and will be returned to the caller:
@synchronized(memory){[memorysetObject:resultforKey:args];}}
Now let's look at the case where a result was found inmemory. In that case, all we have to do is stuff the contents ofresult into theNSInvocation usingsetReturnValue:. Here, we do the reverse transformation fornil, checkingresult forNSNull and changing it tonil:
else{if(result==[NSNullnull])result=nil;
If the return type is an object, a direct call tosetReturnValue: gets the job done:
if(isObj){[invsetReturnValue:&result];}
If it's a C string, we have to fetch the string pointer into a local variable, then set that:
elseif(isCStr){constchar*str=[resultbytes];[invsetReturnValue:&str];}
Otherwise,result is anNSData of the appropriate length containing the return value. We can just pass the pointer straight into the invocation, and that's all there is to it!
else{[invsetReturnValue:[resultmutableBytes]];}}},block);}
For those of you who have lost track, theblock at the end of this is the original block which was passed intoMAMemoize, and tellsMABlockForwarding which block to wrap.
Example
As an example of memoization, let's look at a simple, computationally-expensive block:
__blockuint64_t(^fib)(int)=^uint64_t(intn){if(n<=1)return1;elsereturnfib(n-1)+fib(n-2);}
Thisfib block computes the well known Fibonacci function using recursion. This particular approach is extremely slow. The two recursive calls in theelse clause result in an exponential growth of computation. Each of the two recursive calls spawns two more recursive calls, which in turn each spawn two more recursive calls, etc.
However, almost all of the calls are redundant. If you analyze it, you'll see thatfib(5) callsfib(4) andfib(3), but thenfib(4) just callsfib(3) again. Memoizingfib will make it much faster, since subsequent calls tofib(3) will be cached rather than recomputed. There are, of course, much better ways compute the Fibonacci function altogether, but this still serves as an interesting example.
To memoizefib, we just callMAMemoize and assign the result back tofib:
fib=MAMemoize(fib);
Sincefib is declared as__block, the recursive calls pick up the memoized version, and the result is massively faster on large values than the original.
Conclusion
This memoization wrapper is not entirely useful. For one thing, it's based on my colossal block proxying hack, which really can't be used in code you intend to ship. Even ignoring that, all of the games played withNSInvocation are slow and this is a big problem for code that is, essentially, an optimization.
Despite this, it's a great learning experience. Even if it's not practical, this memoization wrapper illustrates how to deal withNSInvocation in complicated situations and deal with some of the variety of argument and return types that you're likely to encounter in the wild. Beyond that, this kind of hacking is just good fun.
That wraps things up for today. Keep those suggestions coming. Friday Q&A is (usually) driven by reader-submitted topics, so if you have a subject you'd like to see covered,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.