Подтвердить что ты не робот

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

Я из мира С++/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 секунд

Edit:
Как уже упоминалось в комментариях, постоянный увеличивающий размер массива может быть проблемой, поэтому я сделал 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;
}
4b9b3361

ОТВЕТЫ

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