NSArray怎么会这么慢？

Question

我来自C++/STL世界,我想检查Objective-c容器与stl相比如何.

我想比较一个数字数组,但是添加一个数字的唯一方法NSArray是使用NSNumber,这是非常慢,并且我的ram空了,所以我想我需要手动解除它们.但我不想测试副作用,所以我只是添加[NSNull null]到数组中.

将10k内容添加到阵列1k次的结果:
NSArray- 0.923411秒
vector<int>- 0.129984秒

我认为它可能是分配和解除分配所以我将数组的数量(imax在代码中)设置为1和添加数量为10000000(jmax)但它甚至更慢
NSArray- 2.19859秒
vector<int>- 0.223471秒

编辑:
正如在评论中提到的阵列的不断增加的大小可能是问题,所以我做了NSArray使用arrayWithCapacity,但vector用reserve(!),也和它比以前更慢(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;
}

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.你可以NSNumber通过使用非保留来避免这种情况(而不是坚持实数CFMutableArray).这将使附加时间达到约2倍vector.

  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

Answer 2

简短的回答:是的,NSArray确实比C++的STL集合类慢得多.这与编译时间与运行时行为,编译器的优化机会以及众多实现细节有很大关系.

(而且,正如Rob指出的那样,NSMutableArray针对随机插入进行了优化,并且表现优于C++ ...)

真正的答案:

微基准测试对于优化面向用户的应用程序毫无用处.

使用微基准来做出实施决策是过早优化的定义.

您很难找到针对iOS或Mac OS X的Objective-C应用程序,其中CPU分析将显示在与NSArray相关的代码路径中花费的任何重要时间,但绝大多数应用程序使用NS*集合类几乎只.

当然,有些情况下NS*的性能不可行,为此,你转向C++/STL.

这些都不意味着您的问题无效.如果没有更多的情况下,这是很难说,如果观察到的性能差异真正重要的(但是,以我的经验,只是开发商已要求基于微基准测试中的问题,它已经误导每次).

哦 - 阅读本文,因为它对*Array的实现提供了一些见解.

Answer 3

它是一个完全成熟的Objective-C对象,这意味着每次添加对象时都会产生开销,因为Cocoa的消息查找算法是实现正确动态绑定所必需的.

还有一点是,NSArrays不一定是内部结构化的连续指针集.对于非常大的数组,NSArray比C++向量执行得更好(即具有更好的大O时间复杂度).阅读有关该主题的权威Ridiculous Fish博客.