How can NSArray be this slow?

@JeremyP provides an excellent link and information. Always read the fish. Here's some breakdown of what's eating time, though, and what you might do about it.

First, there's the many calls to objc_msgSend() for dynamic dispatch. These can be avoided and you'll save some of the time (though not as much as you'd think. objc_msgSend() is crazy optimized). But you'll knock maybe 5% off 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 eaten up with retain/release. You can avoid that (and stick real numbers in rather than NSNumber) by using a non-retaining CFMutableArray). This will get the append times to about 2x of 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 of this one is the calls to memmove() (or the collectable version of it on the Mac).

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

Try swapping out these lines for their 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 the NSNumber, not just using NSNull.)

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

  CFArrayInsertValueAtIndex(v, 0, &j);

In my tests I get:

Vector insertions7.83188 secondsNSArray insertions2.66572 secondsNon-retaining0.310126 seconds

The short answer: Yes, NSArray really is quite a bit slower than C++'s STL collection classes. This has much to do with compile time vs. runtime behaviors, optimization opportunities on the part of the compiler, and numerous implementation details.

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

The real answer:

Micro-benchmarks are useless for optimizing user facing applications.

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

You would be hard pressed to find an Objective-C app targeted to iOS or Mac OS X where CPU profiling would show any significant time spent in code paths related to NSArray, yet the vast majority of those apps use the NS* collection classes pretty much exclusively.

Certainly, there are cases where the performance of NS* aren't viable and, for that, you turn to C++/STL.

None of this is to imply that your question is invalid. Without more context, it is difficult to say if the observed performance difference really matters (however, in my experience, just about every time a developer has asked a question based on a micro-benchmark, it has been misguided).

Oh -- and read this as it gives a bit of insight into the implementation of *Array.

It's a fully fledged Objective-C object which means there is an overhead each time you add an object due to Cocoa's message lookup algorithm which is necessary to implement properly dynamic binding.

There's also the point that NSArrays are not necessarily internally structured as a contiguous set of pointers. For very large arrays, NSArray performs much better (i.e. has much better big O time complexity) than C++ vectors. Have a read of this the definitive Ridiculous Fish Blog on the topic.