NSMutableDictionary much slower than Java Map... why?

Question

The following code, which maps simple value holders to an object, runs over 15x faster in Java than Objective-C using XCode 7 beta3, "Fastest, Aggressive Optimizations [-Ofast]". I can get over 280M lookups/sec in Java but only about 19M in the objc example. (I posted the corresponding Java code here as this started as a Swift comparison: Swift Dictionary slow even with optimizations: doing uncessary retain/release?).

This is a simplified version of my real code which is definitely bound by hash lookup time and exhibits this overall performance difference as well. In the test below I'm testing the value for null just to make sure the compiler doesn't optimize away the lookup, but in the real app I'd be using the value in most cases.

When I look at instruments I see a lot of time spent in retain / release, msgSend, and some locking calls that I don't understand.

Any ideas on what could account for this being 10-15x slower than Java or any workarounds would be appreciated. I can actually implement a perfect hash like the one below so I could use a fast int-object dictionary for iOS if I could find one.

@interface MyKey : NSObject <NSCopying>
    @property int xi;
@end

@implementation MyKey
    - (NSUInteger)hash { return self.xi; }
    - (BOOL)isEqual:(id)object    { return ((MyKey *)object).xi == self.xi; }
    - (id)copyWithZone:(NSZone *)zone { return self; }

@end

    NSMutableDictionary *map = [NSMutableDictionary dictionaryWithCapacity:2501];
    NSObject *obj = [[NSObject alloc] init];

    int range = 2500;
    for (int x=0; x<range; x++) {
        MyKey *key = [[MyKey alloc] init];
        key.xi=x;
        [map setObject:obj forKey:key];
    }

    MyKey *key = [[MyKey alloc] init];
    int runs = 50;
    for (int run=0; run<runs; run++)
    {
        NSDate *start = [NSDate date];

        int reps = 10000;
        for(int rep=0; rep<reps; rep++)
        {
            for (int x=0; x<range; x++) {
                key.xi=x;
                if ( [map objectForKey:key] == nil ) { NSLog(@"missing key"); }
            }
        }

        NSLog(@"rate = %f", reps*range/[[NSDate date] timeIntervalSinceDate:start]);
    }

Answer 1

You could reimplement your -isEqual: method like this to avoid property accessors:

- (BOOL) isEqual:(id)other
{
    return _xi == ((MyKey*)other)->_xi;
}

That would not be acceptable if your MyKey class might be subclassed, but I see from the Java code that the class there is final.

Answer 2

The computational complexity of the NSMutableDictionary is the next (from CFDictionary.h file):

The access time for a value in the dictionary is guaranteed to be at
worst O(N) for any implementation, current and future, but will
often be O(1) (constant time). Insertion or deletion operations
will typically be constant time as well, but are O(N*N) in the
worst case in some implementations. Access of values through a key
is faster than accessing values directly (if there are any such
operations). Dictionaries will tend to use significantly more memory
than a array with the same number of values.

Means, almost all the time you should have O(1) complexity for access/insertion/deletion. For Java HashMap you should get pretty much the same.

According to this research there are no benefits in using dictionaryWithCapacity: convenience initializer.

In case you use integer as a key, probably it would be possible to replace dictionary with array.

In this WWDC session they explained objc_msgSend performance issues and how to deal with them. The first solution is to use C++ and STL containers. The second one is to use Swift, because unlike Objective-C it is only dynamic when it notes to be.