Как NSArray может быть таким медленным?

Ответ 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). Это приведет к тому, что время добавления составит примерно 2x из 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 уверен медленно. Как Apple могла быть такой глупой, верно? Я имею в виду, действительно... подождите... Интересно, если что-то 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

Ответ 2

Короткий ответ: Да, NSArray действительно довольно медленнее, чем классы коллекции С++ STL. Это имеет большое значение для времени компиляции и поведения во время выполнения, возможностей оптимизации со стороны компилятора и многочисленных деталей реализации.

(И, как указывает Rob, NSMutableArray оптимизирован для случайной вставки и работает лучше, чем С++ для этого...)

Реальный ответ:

Микро-бенчмарки бесполезны для оптимизации приложений, ориентированных на пользователей.

Использование микро-бенчмарка для принятия решений по внедрению - это само определение преждевременной оптимизации.

Вам будет сложно найти приложение Objective-C, ориентированное на iOS или Mac OS X, где профилирование ЦП будет показывать значительное время, потраченное на пути кода, связанные с NSArray, однако подавляющее большинство этих приложений использует коллекцию NS * классы в значительной степени исключительно.

Конечно, бывают случаи, когда производительность NS * не жизнеспособна и для этого вы переходите к С++/STL.

Ничто из этого не означает, что ваш вопрос недействителен. Без особого контекста трудно сказать, действительно ли наблюдается наблюдаемая разница в производительности (однако, по моему опыту, почти каждый раз, когда разработчик задавал вопрос на основе микро-теста, он был ошибочным).

Oh - и читайте это, поскольку он дает представление о реализации * Array.

Ответ 3

Это полноценный объект Objective-C, который означает, что каждый раз, когда вы добавляете объект из-за Cocoa алгоритма поиска сообщений, который необходим для правильной динамической привязки, есть накладные расходы каждый раз.

Также существует точка, в которой NSArrays не обязательно внутренне структурированы как непрерывный набор указателей. Для очень больших массивов NSArray работает намного лучше (т.е. Имеет намного лучшую большую временную сложность O), чем векторы С++. Почитайте это окончательный Смешной блог о рыбах на эту тему.

Ответ 4

По крайней мере, часть времени потребляется при многократном увеличении емкости NSArray. Это должно быть быстрее инициализировать NSArray вправо (или, по крайней мере, лучшую) емкость изначально с помощью

[NSMutableArray arrayWithCapacity:10000];

Ответ 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