Performance hit incurred using NSMutableDictionary vs. NSMutableArray>

Question

I am considering using an NSMutableDictionary in place of my current NSMutableArray. This is primarily for KVC/KVO reasons. The collection will undergo heavy mutation within the inner loop of my drawing method. Can I expect to incur a significant performance hit if I go ahead with this replacement?

Cheers, Doug

Answer 1

The only way to be sure is to measure. None of us have enough knowledge about how NSMutableDictionary's and NSMutableArray's implementations work, so there's little point asking.

Granted, you could probably expect some hit since the dictionary has to do additional hashing that a simple array would not. Whether or not that is "significant" is hard to say.

Again, measure.

Answer 2

When you say "primarily for KVC/KVO reasons", can you elaborate?

If you're seeing performance problems due to excessive KVO firing under heavy mutation, consider firing the KVO notifications yourself once you're done:

[self willChangeValueForKey: @"myArray"];

// loop and mutate

[self didChangeValueForKey: @"myArray"];

Answer 3

As they say you need to test these things. But... the following simple test was instructive for me to get an idea of the relative difference in speed between the NSMutableDictionary and NSMutableArray collection classes in the case of small size high allocation rate examples.

Running the following program the times were: (with garbage collection on) (on a recent quad core machine)

NSMutableDictionary 4.624478 seconds NSMutableArray 1.806365 seconds

int main (int argc, const char * argv[])
{
    NSLog(@"Hello, World!");

    LNCStopwatch* stopwatch = [[LNCStopwatch alloc] init];
    [stopwatch start];
    for (int i = 1; i< 1000000; i++)
    {
        NSMutableDictionary* dict = [[NSMutableDictionary alloc]init];
        [dict setObject:@"a" forKey:@"a"];
        [dict setObject:@"b" forKey:@"b"];
        [dict setObject:@"c" forKey:@"c"];
        [dict setObject:@"d" forKey:@"d"];
        [dict setObject:@"e" forKey:@"e"];
        [dict setObject:@"y" forKey:@"a"];
        [dict setObject:@"x" forKey:@"d"];
    }
    [stopwatch stopAndLogTimeAndReset];
    [stopwatch start];
    for (int i = 1; i< 1000000; i++)
    {
        NSMutableArray* arr = [[NSMutableArray alloc]init];
        [arr addObject:@"a"];
        [arr addObject:@"b"];
        [arr addObject:@"c"];
        [arr addObject:@"d"];
        [arr addObject:@"e"];
        [arr replaceObjectAtIndex:[arr indexOfObject:@"a"] withObject:@"y"];
        [arr replaceObjectAtIndex:[arr indexOfObject:@"d"] withObject:@"x"];
    }
    [stopwatch stopAndLogTimeAndReset];

    return 0;
}

(The absolute times I don't think are really all that important, its just the relative times which are more important for these small size classes. For larger size classes of corse the nature of the collection class will dominate, eg NSMutableDictionary should be O(1) to find an element, etc... )