¿Cómo puede NSArray ser tan lento?

Question

Vengo de un mundo C++/STL y quería comprobar cómo son los contenedores object-c en comparación con stl.

Quería comparar una matriz de números, pero la única forma de agregar un número a NSArray es utilizando NSNumber, que es completamente lento y bebí mi memoria RAM vacía, así que supongo que debo desasignarlos manualmente. Pero no quiero probar los efectos secundarios, así que agregué [NSNull null] en la matriz.

Los resultados de la adición de 10k cosas en una matriz 1k veces:
NSArray - 0.923411 segundos
vector<int> - 0,129984 segundos

pensé que podría ser asignaciones y cancelaciones de asignación de modo fijo el número de matrices (imax en el código) a 1 y el número de adiciones a 10000000 (jmax) pero era aún más lento
NSArray - 2.19859 segundos
vector<int> - 0.223471 segundos

Editar:
Como se mencionó en los comentarios al creciente tamaño constante de la matriz podría ser el problema por lo que hizo NSArray usando arrayWithCapacity, pero vector con reserve demasiado y fue incluso más lento que antes (imax = 1, (!) jmax = 10000000).
NSArray - 2,55942
vector<int> - 0,19139
Fin de edición

Por qué es tan lento?

Mi código de referencia:

#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 proporciona un excelente enlace e información. Siempre lea el pez. Aquí hay un desglose de lo que es tiempo de comer, sin embargo, y lo que puede hacer al respecto.

Primero, hay muchas llamadas a objc_msgSend() para el envío dinámico. Esto se puede evitar y ahorrará algo de tiempo (aunque no tanto como podría pensar. objc_msgSend() es crazy optimized). Pero tal vez usted golpea 5% de descuento por su omisión:

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]; 
    } 

Una gran cantidad de tiempo se come con retain/release. Puede evitar eso (y pegar números reales en lugar de NSNumber) utilizando un CFMutableArray no retenido. Esto obtendrá los tiempos de adición a aproximadamente 2x de 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); 
} 

El mayor coste de ésta es las llamadas a memmove() (o la versión de colección de la misma en el Mac).

Hombre, NSMutableArray Seguro, es lento. ¿Cómo podría Apple ser tan estúpido, verdad? Quiero decir, realmente ... espera ... Me pregunto si hay algo que NSMutableArray sea mejor que vector?

Prueba a intercambiar a cabo estas líneas para sus contrapartes obvias:

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

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

(Sí, incluyendo la creación y la liberación de la NSNumber, no sólo usando NSNull.)

Ah, y usted puede tratar éste también para ver cuán rápido NSMutableArray y CFMutableArray realmente puede ser:

CFArrayInsertValueAtIndex(v, 0, &j); 

En mi te sts Obtengo:

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

Answer 2

Al menos una parte del tiempo se consume en el aumento de varias veces la capacidad de la NSArray. Debería ser más rápido para inicializar el NSArray hacia la derecha (o por lo menos una mejor) Capacidad inicialmente con:

[NSMutableArray arrayWithCapacity:10000]; 

Answer 3

Es un objeto de pleno derecho de Objective-C que significa que hay una sobrecarga cada vez que se agrega un objeto debido al algoritmo de búsqueda de mensajes de Cocoa, que es necesario para implementar una vinculación dinámica adecuada.

También se explica que los NSArrays no están necesariamente estructurados internamente como un conjunto contiguo de punteros. Para matrices muy grandes, NSArray tiene un rendimiento mucho mejor (es decir, tiene una complejidad de tiempo de O mucho mayor) que los vectores de C++. Lea esto, el definitivo Ridiculous Fish Blog sobre el tema.

Answer 4

#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; 
} 

salida en mi Core2Duo 2GHz iMac (compilado con LLVM):

0.000003 

Answer 5

La respuesta corta: Sí, NSArray realidad es un poco más lento que las clases de colección STL C++ 's. Esto tiene mucho que ver con el tiempo de compilación frente a los comportamientos de tiempo de ejecución, las oportunidades de optimización por parte del compilador y numerosos detalles de implementación.

(Y, como señala Rob, NSMutableArray está optimizado para la inserción aleatoria y tiene un rendimiento mejor que C++ para ese ...)

La verdadera respuesta:

micro-puntos de referencia son inútiles para la optimización de las aplicaciones de cara al usuario.

Usar una micro-referencia para tomar decisiones de implementación es la definición misma de la optimización prematura.

Sería difícil encontrar una aplicación Objective-C dirigida a iOS o Mac OS X donde los perfiles de CPU mostrarían un tiempo significativo en rutas de código relacionadas con NSArray, aunque la gran mayoría de esas aplicaciones usan NS * clases de colección casi exclusivamente.

Ciertamente, hay casos en los que el rendimiento de NS * no es viable y, para eso, se pasa a C++/STL.

Nada de esto implica que su pregunta es inválida. Sin más contexto, es difícil decir si la diferencia de rendimiento observada realmente importa (sin embargo, en mi experiencia, casi cada vez que un desarrollador hace una pregunta basada en un micro-punto de referencia, ha sido equivocada).

Ah, y lea this as it gives a bit of insight into the implementation of *Array.