How can NSArray be so slow?

Question

I am from the C ++ / STL world, and I wanted to check how objective-c containers compare to stl.

I wanted to compare an array of numbers, but the only way to add a number to NSArray is to use NSNumber , which is extremely slow and drank my ram empty, so I think I need to delete them manually. But I don't want to test side effects, so I just added [NSNull null] to the array.

The results of adding 10k things to the array 1k times:
NSArray - 0.923411 seconds
vector<int> - 0.129984 seconds

I thought it could be allocations and deallocations, so I set the number of arrays ( imax in the code) to 1 and the number of additions to 10,000,000 ( jmax ), but it was even slower than NSArray - 2.19859 seconds
vector<int> - 0.223471 seconds

Edit:
As mentioned in the comments, constantly increasing the size of the array can be a problem, so I made NSArray with arrayWithCapacity , but vector with reserve too, and it was even slower than before (!) ( imax = 1, jmax = 10000000).
NSArray - 2.55942
vector<int> - 0.19139
End editing

Why is it so slow?

My code for reference:

 #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 provides an excellent link and information. Always read the fish. There is some breakdown of what time goes by and what you can do about it.

Firstly, there are many calls to objc_msgSend() to dynamically send. They can be avoided, and you will save some time (although not as much as you think. objc_msgSend() crazy optimized ), but you can bring it down by 5% by skipping it:

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

A lot of time is consumed with retain / release . You can avoid this (and stick with real numbers, not NSNumber ) by using a non-persistent CFMutableArray ). This will result in an add time of approximately 2x from 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); } 

The biggest cost to this is calls to memmove() (or its collector's version on Mac).

Man, NSMutableArray sure is slow. How could Apple be so stupid, right? I mean, really ... wait ... I wonder if something NSMutableArray better than vector ?

Try replacing these lines with your obvious counterparts:

  v->insert(v->begin(), j); NSNumber *num = [[NSNumber alloc] initWithInt:j]; [v insertObject:num atIndex:0]; [num release]; 

(Yes, including creating and releasing NSNumber , not just using NSNull .)

Oh, and you can try this too to see how fast NSMutableArray and CFMutableArray really can be:

  CFArrayInsertValueAtIndex(v, 0, &j); 

In my tests, I get:

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

Answer 2

Short answer: Yes, NSArray is really quite slower than the C ++ STL collection classes. This is important for compilation time and runtime behavior, compiler optimization options, and numerous implementation details.

(And, as Rob points out, NSMutableArray is optimized for random insertion and works better than C ++ for this ...)

The real answer is:

Micro benchmarks are useless for optimizing user-oriented applications.

Using a micro benchmark to make implementation decisions is the very definition of premature optimization.

It will be difficult for you to find an Objective-C application focused on iOS or Mac OS X, where CPU profiling will show significant time spent on code paths related to NSArray, however the vast majority of these applications use a collection of NS * classes to a large extent exclusively.

Of course, there are times when the performance of NS * is not viable and for this you go to C ++ / STL.

None of this means your question is invalid. Without a particular context, it is difficult to say whether the observed difference in performance is actually observed (however, in my experience, almost every time a developer asked a question based on a micro-test, it was erroneous).

Oh - and read this as it gives an idea of ​​the implementation of * Array .

Answer 3

This is a full-fledged Objective-C object, which means that every time you add an object due to Cocoa's message search algorithm, which is necessary for proper dynamic binding, there is an overhead every time.

There is also a point at which NSArrays are not necessarily internally structured as a continuous set of pointers. For very large arrays, NSArray works much better (i.e., has much better, greater O time complexity) than C ++ vectors. Check out this ultimate Funny Fish blog on the subject.

Answer 4

At least part of the time is consumed by repeatedly increasing the capacity of NSArray. It should be faster to initialize the NSArray to the right (or at least the best) capacity initially with

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

The output in my 2GHz Core2Duo iMac (compiled with LLVM):

 0.000003