NSArray为什么这么慢？

Question

我来自C++/STL的世界，想要比较一下Objective-C容器和STL的差异。

我想比较一个数字数组，但是添加一个数字到NSArray中的唯一方法是使用NSNumber，这非常慢且会耗尽我的内存，所以我猜我需要手动释放它们。但我不想测试副作用，所以我只是往数组里添加了一个[NSNull null]。

将10k个元素添加到数组中1k次的结果如下：
NSArray - 0.923411秒
vector<int> - 0.129984秒

我认为可能是分配和释放内存的原因，所以我将数组数（代码中的imax）设置为1，将添加次数（jmax）设置为10000000，但速度甚至更慢了。
NSArray - 2.19859秒
vector<int> - 0.223471秒

编辑：
如评论中所提到的，数组大小的不断增加可能是问题所在，因此我使用了arrayWithCapacity创建了NSArray，但也使用了reserve创建了vector，结果比之前还要慢（imax=1，jmax=10000000）。
NSArray - 2.55942秒
vector<int> - 0.19139秒
编辑结束

为什么速度这么慢？

以下是我的参考代码：

#import <Foundation/Foundation.h>
#include <vector>
#include <iostream>
#include <time.h>

using namespace std;

int main (int argc, const char * argv[])
{
    int imax = 1000;
    int jmax = 10000;

    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

    cout << "Vector insertions" << endl;

    clock_t start = clock();

    for(int i = 0; i < imax; i++)
    {
        vector<int> *v = new vector<int>();
        for(int j = 0; j < jmax; j++)
        {
            v->push_back(j);
        }
        delete v;
    }

    double interval = (clock() - start) / (double)CLOCKS_PER_SEC;

    cout << interval << " seconds" << endl;

    cout << "NSArray insertions" << endl;

    start = clock();

    for(int i = 0; i < imax; i++)
    {
        NSMutableArray *v = [[NSMutableArray alloc] init];
        for(int j = 0; j < jmax; j++)
        {
            [v addObject:[NSNull null]];
        }
        [v dealloc];
    }

    interval = (clock() - start) / (double)CLOCKS_PER_SEC;

    cout << interval << " seconds" << endl;

    [pool drain];
    return 0;
}

- Daniel

---

如果你想要存储整数的速度，为什么不使用C数组呢？ - sidyll

存储任何东西，即使是空值，速度也会慢10倍。 - Daniel

Answer 1

@JeremyP提供了一个出色的链接和信息。一定要仔细阅读这篇文章。以下是关于时间消耗的一些详细说明，以及你可能采取的行动。

首先，有很多调用objc_msgSend()进行动态分派。虽然可以避免这些调用并节省一些时间（但你认为可以节省的时间并不多，因为objc_msgSend()已经被优化到了极致）。但是，跳过它可能会减少大约5%的时间：

  IMP addObject = class_getMethodImplementation([NSMutableArray class], @selector(addObject:));
  NSNull *null = [NSNull null];

  start = clock();

  for(int i = 0; i < imax; i++)
  {
    NSMutableArray *v = [[NSMutableArray alloc] init];
    for(int j = 0; j < jmax; j++)
    {
      addObject(v, @selector(addObject:), null);
    }
    [v release];
  }

很多时间都被retain/release占用了。你可以通过使用非保留的CFMutableArray（而不是NSNumber）来避免这个问题，这样可以将追加时间提高到大约是vector的2倍。

  CFArrayCallBacks cb = {0};
  for(int i = 0; i < imax; i++)
  {
    CFMutableArrayRef v = CFArrayCreateMutable(NULL, 0, &cb);
    for(int j = 0; j < jmax; j++)
    {
      CFArrayAppendValue(v, &j);
    }
    CFRelease(v);
}

这段代码最大的代价是调用 memmove()（或在 Mac 上的可回收版本）。

NSMutableArray 真的很慢。苹果怎么会这么愚蠢，对吧？我是说，真的...等等...我想知道 NSMutableArray 是不是比 vector 做得更好？

尝试将这些行替换为它们明显的对应项：

 v->insert(v->begin(), j);

  NSNumber *num = [[NSNumber alloc] initWithInt:j];
  [v insertObject:num atIndex:0];
  [num release];

（是的，包括创建和释放 NSNumber，而不仅仅是使用 NSNull。）

哦，你也可以尝试这个，看看 NSMutableArray 和 CFMutableArray 能有多快：

  CFArrayInsertValueAtIndex(v, 0, &j);

在我的测试中，我得到：

Vector insertions
7.83188 seconds
NSArray insertions
2.66572 seconds
Non-retaining
0.310126 seconds

- Rob Napier

---

这真是一个太棒的回答了。它真正抓住了问题的核心，即权衡取舍。在一个基准测试中发现缓慢不应使你想：“哇，这很慢！”而是应该让你想：“嗯，这是在做什么不同和为什么会这样呢？” - Chuck

Answer 2

简短回答：是的，NSArray确实比C++的STL集合类慢得多。这在很大程度上与编译时与运行时行为、编译器优化机会和众多实现细节有关。

（正如Rob所指出的，NSMutableArray针对随机插入进行了优化，并且在此方面的表现优于C++...）

真正的答案：

微基准测试对于优化面向用户的应用程序是无用的。

使用微基准测试来做出实现决策是过早优化的典型例子。

你很难找到一个针对iOS或Mac OS X的Objective-C应用程序，在CPU分析中显示任何与NSArray相关的代码路径占用了很大的时间，然而，绝大多数这些应用程序几乎完全使用NS*集合类。

当然，有些情况下，NS*的性能不可行，这时你就可以转向C++/STL。

这并不意味着你的问题是无效的。没有更多的上下文，很难说观察到的性能差异是否重要（然而，在我的经验中，每当开发人员根据微基准测试提出问题时，都是错误的）。

哦，还有阅读这篇文章，因为它可以给出一些关于*Array实现的见解。

- bbum

---

虽然我同意结论，但我的测试表明，如果你进行随机插入，NSMutableArray比vector快得多。我不会认为NSMutableArray在所有情况下都很慢。它只是在添加方面不太快。话虽如此，我追踪过的唯一一个真实世界的性能问题与NSMutableArray有关，那就是复制它，因为我不知道是否有写时复制的功能。 - Rob Napier

Answer 3

这是一个完全成熟的Objective-C对象，这意味着每次添加对象都会有开销，因为Cocoa的消息查找算法必须实现正确的动态绑定。

此外，NSArrays并不一定内部结构化为一组连续的指针。对于非常大的数组，NSArray的性能要比C++向量好得多（即具有更好的大O时间复杂度）。请阅读这篇关于该主题的权威Ridiculous Fish Blog。

- JeremyP

Answer 4

至少有一部分时间被用于反复增加NSArray的容量。更好的方法是在初始化NSArray时，将其容量设置为正确的（或至少更好的）容量：

[NSMutableArray arrayWithCapacity:10000];

- highlycaffeinated

---

你错了，arrayWithCapacity 比不用它还要慢，看看我的编辑。 - Daniel

@Dani - 同意。您可以通过预先分配NSArray和std :: vector并比较性能来从比较中删除扩展的成本。 - highlycaffeinated

正如@Dani所指出的，预分配可能比让它扩展更慢。我也看到了同样的情况。我的猜测是因为扩展的NSArray不是连续布局的，所以它可以重复使用许多已经分配的小块。但是当你预分配时，它可能会尝试在一个地方获取所有的内存，这可能对缓存系统来说是一个太大的块。这只是我的初步想法。但无论如何，在Foundation中，预分配并不是一定能赢，而且可能会输。 - Rob Napier

Answer 5

#include <stdio.h>
#include <time.h>

int main (int argc, char **argv)
{
    int imax = 1000;
    int jmax = 10000;

    clock_t start = clock();

    for(int i = 0; i < imax; i++)
    {
        int array[jmax];
        for(int j = 0; j < jmax; j++)
            j[array] = 0;
    }

    double interval = (clock() - start) / (double)CLOCKS_PER_SEC;

    printf("%f\n", interval);

    return 0;
}

在我的2GHz Core2Duo iMac上输出（使用LLVM编译）：

0.000003

- sidyll

---

“int array[jmax]”被编译器进行了优化（即使使用-O0），你在这里检查的是10000000个“mov”，而不是我要测试的内容。 - Daniel