NSMutableDictionary比Java Map慢得多......为什么？

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?).

以下代码将简单值持有者映射到一个对象,使用XCode 7 beta3,“最快,最具侵略性的优化[-Ofast]”,在Java中运行速度比Objective-C快15倍。我可以在Java中获得超过280M的查找/秒,但在objc示例中只有大约19M。 (我在这里发布了相应的Java代码,因为这开始是一个Swift比较:Swift Dictionary甚至在优化时缓慢:执行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.

这是我的实际代码的简化版本,它肯定受哈希查找时间的约束,并且也展示了这种整体性能差异。在下面的测试中,我正在测试null的值,只是为了确保编译器不会优化掉查找,但在真实的应用程序中,我会在大多数情况下使用该值。

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.

当我查看乐器时,我发现在保留/释放,msgSend以及一些我不理解的锁定调用上花费了大量时间。

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.

任何可以解释这个问题的想法比Java或任何变通方法慢10-15倍,我们将不胜感激。我实际上可以像下面那样实现一个完美的哈希,所以我可以使用一个快速的int-object字典用于iOS,如果我找到一个。

@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]);
    }

2 个解决方案

#1

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

您可以重新实现这样的-isEqual:方法以避免属性访问器:

- (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.

如果您的MyKey类可能是子类,那是不可接受的,但我从Java代码中看到那里的类是final。

#2

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

NSMutableDictionary的计算复杂性是下一个(来自CFDictionary.h文件):

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.

意味着,几乎所有的时间都应该具有O(1)访问/插入/删除的复杂性。对于Java HashMap,你应该得到几乎相同的东西。

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

根据这项研究,使用dictionaryWithCapacity:便利初始化器没有任何好处。

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.

在这个WWDC会话中,他们解释了objc_msgSend性能问题以及如何处理它们。第一种解决方案是使用C ++和STL容器。第二个是使用Swift,因为与Objective-C不同,它只是在注意到它时才是动态的。

#1