Foundation Objective-c: Dictionary with array; dict with dict

Suppose I have a NSDictionary with two sub collections of a NSArray and a NSDictionary:

NSMutableDictionary *mkDict(void){
    NSMutableDictionary *dict=[NSMutableDictionary dictionary];
    NSMutableDictionary *sub=[NSMutableDictionary dictionary];
    NSMutableArray *array= [NSMutableArray array];
    [dict setObject:array forKey:@"array_key"];
    [dict setObject:sub forKey:@"dict_key"];
    return dict;
}

There are a multitude of ways to access a single element of the sub-collection, and I choose to time three of them.

The first way is to indirectly access the subelements by accessing the key of the parent:

void KVC1(NSMutableDictionary *dict, int count){

    for(int i=0; i<count; i++){
        char buf1[40], buf2[sizeof buf1];
        snprintf(buf1,sizeof(buf1),"element %i", i);
        snprintf(buf2, sizeof buf2, "key %i", i);

        [[dict objectForKey:@"array_key"] 
          addObject:
             [NSString stringWithUTF8String:buf1]];
        [[dict objectForKey:@"dict_key"] 
          setObject:[NSString stringWithUTF8String:buf1] 
          forKey:[NSString stringWithUTF8String:buf2]];
    }
}

The second is to use KeyPath access:

void KVC2(NSMutableDictionary *dict, int count){

    for(int i=0; i<count; i++){
        char buf1[40], buf2[sizeof buf1], buf3[sizeof buf1];
        snprintf(buf1,sizeof(buf1),"element %i", i);
        snprintf(buf2, sizeof buf2, "key %i", i);
        snprintf(buf3, sizeof buf3, "dict_key.key %i",i);

        [dict insertValue:
             [NSString stringWithUTF8String:buf1] 
            atIndex:i inPropertyWithKey:@"array_key"];
        [dict set开发者_开发技巧Value:
             [NSString stringWithUTF8String:buf1] 
            forKeyPath:
             [NSString stringWithUTF8String:buf3]];
    }
}

And the third, similar to the first, is to access a pointer to the sub element, then use that pointer:

void KVC3(NSMutableDictionary *dict, int count){

    NSMutableArray *subArray = [dict objectForKey:@"array_key"];
    NSMutableDictionary *subDict = [dict objectForKey:@"dict_key"];

    for(int i=0; i<count; i++){
        char buf1[40], buf2[sizeof buf1];
        snprintf(buf1,sizeof(buf1),"element %i", i);
        snprintf(buf2, sizeof buf2, "key %i", i);

        [subArray addObject:[NSString stringWithUTF8String:buf1]];
        [subDict 
           setObject:
            [NSString stringWithUTF8String:buf1] 
           forKey:
            [NSString stringWithUTF8String:buf2]];
    }
}

Here is the timing code:

#import <Foundation/Foundation.h>
#import <mach/mach_time.h>

// KVC1, KVC2 and KVC3 from above...

#define TIME_THIS(func,times) \
({\
mach_timebase_info_data_t info; \
mach_timebase_info(&info); \
uint64_t start = mach_absolute_time(); \
for(int i=0; i<(int)times; i++) \
func ; \
uint64_t duration = mach_absolute_time() - start; \
duration *= info.numer; \
duration /= info.denom; \
duration /= 1000000; \
NSLog(@"%i executions of line %i took %lld milliseconds", times, __LINE__, duration); \
});

int main (int argc, const char * argv[]) {
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    NSMutableDictionary *dict=mkDict();
    NSMutableDictionary *dict2=mkDict();
    NSMutableDictionary *dict3=mkDict();

    TIME_THIS(KVC1(dict,1000),10);
    TIME_THIS(KVC2(dict2,1000),10);
    TIME_THIS(KVC3(dict3,1000),10);

    if([dict isEqualToDictionary:dict2])
        NSLog(@"And they are the same...");
    [pool drain];
    return 0;
}

Here are the results:

10 executions of line 256 took 57 milliseconds
10 executions of line 257 took 7930 milliseconds
10 executions of line 258 took 46 milliseconds
And they are the same...

Question: Why is the OS X Snow Leopard / Lion suggested method of using KeyPaths so stinking slow? If you increase the size of count to 10,000 or more, KVC2 becomes infinitely slow where the other two methods increase linearly.

Am I doing something wrong? Is there a better idiom to access a single element of a sub collection in a dictionary?

In KVC2(), you send

[dict insertValue:[NSString stringWithUTF8String:buf1] 
          atIndex:i
inPropertyWithKey:@"array_key"]; 

The documentation for that method states the following:

The method insertIn<Key>:atIndex: is invoked if it exists. If no corresponding scripting-KVC-compliant method (insertIn<Key>:atIndex:) is found, this method invokes mutableArrayValueForKey: and mutates the result.

Since the message is being sent to dict, an instance of NSDictionary, there is no -insertIn<Key>:atIndex: method, hence -mutableArrayValueForKey: is sent. The documentation for this method states the following:

Return Value A mutable array proxy that provides read-write access to the ordered to-many relationship specified by key.

Discussion Objects added to the mutable array become related to the receiver, and objects removed from the mutable array become unrelated. The default implementation recognizes the same simple accessor methods and array accessor methods as valueForKey:, and follows the same direct instance variable access policies, but always returns a mutable collection proxy object instead of the immutable collection that valueForKey: would return.

So what’s happening is that at each iteration:

1. A proxy mutable array is created as a mutable copy of the original array;
2. An object is added to the proxy array;
3. The proxy array adds the same object to the original array.

If you use Instruments to profile your program, you’ll notice that about 50% of the processing time is spent on -[NSKeyValueSlowMutableArray insertObject:atIndex:] — I think it’s safe to assume that NSKeyValueSlowMutableArray is the proxy array and its name should be a clue of its performance.

Because the framework needs to figure out how to get to the elements given a string access path: parsing of strings, error checking, creating more string instances and freeing them.

It is a preferred way because of key-value-observing, binding etc so that Cocoa can make a lot of its magic for you. And slow is relative: it may be slowlier than direct access, but is it too slow? Only profiling an real use-case can show you if it gets too slow and if you need to optimize. If you set a few variables using keypath on the UI then you probably won't notice the lack of speed, if you try to process a lot of data then keypath is probably not a best solution. As I said: profile you use case.

You have to make a compromise between ease of code, having access to all of the goodies Cocoa KVC provides and speed and you'll know the answer only when you see your code as part of the bigger picture.

1st and 3rd implementations have a "static" reference to the subelements which is definitely not evaluated a second time at the 3rd implementation. The variability of the 2nd implementation at accessing the subelements is probably causing the time issues... And [NSDictionary insertValue: atIndex: forPropertyKey:] has the issue of random access insertion in a not statically evaluated element (NSMutableArray) and is also a KVO procedure which might invoke a number of unknown side-effects... Try again without the KVO scripting insertValue:atIndex:forPropertyWithKey: and see if keyPath is that slow, I bet it is slower than the others but in different scales