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

Question

Я пришел из мира C ++ / STL и хотел проверить, насколько контейнеры Objective-C сравнимы с stl.

Я хотел сравнить массив чисел, но единственный способ добавить число к NSArray - это использовать NSNumber, который очень медленный и выпил мой баран пустым, так что я думаю, что мне нужно освободить их вручную,Но я не хочу проверять побочные эффекты, поэтому я просто добавил [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 конечно медленно. Как 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

Answer 2

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

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

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

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

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

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

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

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

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

Answer 3

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

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

Answer 4

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

[NSMutableArray arrayWithCapacity:10000];

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