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

Question

以下代码将简单的值保持者映射到一个对象，使用 XCode 7 beta3 的 Java 运行速度比 Objective-C 快了15倍以上，“最快，最激进的优化[-Ofast]”。在 Java 中，我可以获得超过280M的查找/秒，但在 objc 示例中只有大约19M（我在此发布了相应的 Java 代码，因为这是一个 Swift 比较：Swift Dictionary slow even with optimizations: doing uncessary retain/release?）。这是我的真实代码的简化版本，它明确受限于哈希查找时间，并展现了整体性能差异。在下面的测试中，我测试了 null 值，只是为了确保编译器不会优化掉查找，但在实际应用程序中，我大多数情况下会使用该值。当我查看工具时，我看到了很多时间花费在保留/释放、msgSend 和一些我不理解的锁定调用上。任何关于这个比 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]);
    }

- Pat Niemeyer

---

如果性能是一个问题，总有使用C++容器的选项。还有一种叫做Objective-C++（.mm扩展名）的东西。 - zaph

请添加您的Java代码，否则很难进行评判。但需要注意的是，当Java代码首次运行时，它将被即时编译为高度优化的本地代码，因此应该非常快。 - Sulthan

Java中的方法调用（一旦经过JIT编译）比Objective-C中的方法调用快得多。 - Hot Licks

我在想，尝试使用NSMapTable而不是NSDictionary会有所帮助吗？ - matt

你是否需要加锁是因为你没有将 xi 属性声明为 nonatomic 吗？你没有声明任何属性，这意味着该属性默认为 atomic。 - Ewan Mellor

Answer 1

您可以重新实现您的 -isEqual: 方法，避免使用属性访问器，例如：

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

如果您的MyKey类可能会被子类化，那么这是不可接受的，但从Java代码中可以看出该类是final的。

- Ken Thomases

Answer 2

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, 几乎所有时候，您应该对访问/插入/删除具有O(1)复杂度。对于Java HashMap，您应该得到几乎相同的结果。

根据this 的研究，使用dictionaryWithCapacity:便利初始化程序没有任何好处。

如果您将整数用作键，则可能可以使用数组替换字典。

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

- sgl0v

---

这并没有解释为什么Java在这个基准测试中比ObjC快10倍到15倍，或者为什么Swift又慢了近2倍。 - Ewan Mellor

1. 在Java中，你有字节码和JVM。将Java与Objective C / Swift性能进行比较是毫无意义的。
2. 测试取决于许多因素，如实现、编译器、优化级别等。根据这些基准测试，Swift的性能表现良好。

- sgl0v

当然比较这些内容是有意义的。尽管Java有JIT（即时编译器），但它被认为是主流编程语言中最慢的之一。Objective C和Swift都是静态编译的，并且具有强大的编译时优化功能。在这样一个紧密的微基准测试中，人们预计它们将毁掉Java，但它们没有，相差十倍。为什么会这样，为什么优化器如此严重地让我们失望，这些都是值得讨论的有趣问题。你的回答甚至没有触及表面。 - Ewan Mellor

对我来说，似乎使用ARC存在巨大的固有惩罚，而Swift设计人员则通过建议我们依赖于结构体和值语义来解决这个问题。但是这使得这些语言难以在高性能应用程序中使用。Java在这里的“不公平”优势在于，当使用固定对象池时，引用它们是“免费”的。但ARC（至少目前）无法知道它们的生命周期，并且必须执行所有这些额外的不必要的工作来进行引用计数。 - Pat Niemeyer