NSArray vs. C Array performance comparison

The classes provided by Cocoa for handling data sets (NSDictionary, NSArray, NSSet etc.) provide a very nice interface for managing information, without having to worry about the bureaucracy of memory management, reallocation etc. Of course this does come at a cost though. I think it's pretty obvious that say using an NSArray of NSNumbers is going to be slower than a C Array of floats for simple iterations, so I decided to do some tests, and the results were pretty shocking! I wasn't expecting it to be this bad. Note: these tests are conducted on an iPhone 3G as that's the target platform I was interested in.

In this test I do a very simple random access performance comparison between a C float* and NSArray of NSNumbers. In Part II I compare performance of using NSArray of CustomObjects containing floats and not using NSNumber, and faster enumeration method aimed at linear iteration.

I create a simple loop to sum up the contents of each array and time them using mach_absolute_time(). The NSMutableArray takes on average 400 times longer!! (not 400 percent, just 400 times longer! thats 40,000% longer!).

// process using NSArray
-(IBAction) doNSArray:(id)sender {
    NSLog(@"doNSArray: %@", sender);
 
    uint64_t startTime = mach_absolute_time();
    float total = 0;
    for(int i=0; i<numberOfItems; i++) {
        total += [[nsArray objectAtIndex:i] floatValue];
    }
    [self displayResult:mach_absolute_time() - startTime];
}
 
 
 
// process using C Array
-(IBAction) doCArray:(id)sender {
    NSLog(@"doCArray: %@", sender);
 
    uint64_t start = mach_absolute_time();
    float total = 0;
    for(int i=0; i<numberOfItems; i++) {
        total += cArray[i];
    }
    [self displayResult:mach_absolute_time() - start];
}

The results of the test and source code are below (you can set the number of iterations in the app). The time is in milliseconds, and each entry is an average result of running the test 5-10 times. I found that generally it is accurate to 2-3 significant digits and after that it would vary with each run. That gives a margin of error of less than 1%. The test was running on an iPhone 3G as that's the target platform I was interested in.

numberOfItems	NSArray (ms)	C Array (ms)	Ratio
100	0.39	0.0025	156
191	0.61	0.0028	218
3,256	12.5	0.026	481
4,789	16	0.037	432
6,794	21	0.050	420
10,919	36	0.081	444
19,731	64	0.15	427
22,030	75	0.162	463
32,758	109	0.24	454
77,969	258	0.57	453
100,000	390	0.73	534

Of course this example is extra slow because it also has the overheads of NSNumber, and it is random access (Even though the for loop is linear, I'm using the objectAtIndex:i method to test accessing elements by index). In Part II I look at faster alternatives for linear enumeraton and not using NSNumbers.

Source code below (I used Obj C++ & new/delete instead of malloc/free to provide a simpler transition to the C++ class in Part II).

Header:

//
//  Array_Speed_TestViewController.h
//  Array Speed Test
//
//  Created by Mehmet Akten on 05/02/2009.
//  Copyright MSA Visuals Ltd. 2009. All rights reserved.
//
 
#import <UIKit/UIKit.h>
 
@interface Array_Speed_TestViewController : UIViewController {
    int                     numberOfItems;          // number of items in array
    float                   *cArray;                // normal c array
    NSMutableArray          *nsArray;               // ns array
    double                  machTimerMillisMult;    // multiplier to convert mach_absolute_time() to milliseconds
 
 
    IBOutlet    UISlider    *sliderCount;
    IBOutlet    UILabel     *labelCount;
 
    IBOutlet    UILabel     *labelResults;
}
 
-(IBAction) doNSArray:(id)sender;
-(IBAction) doCArray:(id)sender;
 
-(IBAction) sliderChanged:(id)sender;
 
@end

Implementation:

//
//  Array_Speed_TestViewController.m
//  Array Speed Test
//
//  Created by Mehmet Akten on 05/02/2009.
//  Copyright MSA Visuals Ltd. 2009. All rights reserved.
//
 
#import "Array_Speed_TestViewController.h"
 
#include <mach/mach.h>
#include <mach/mach_time.h>
 
 
 
@implementation Array_Speed_TestViewController
 
 
// Implement viewDidLoad to do additional setup after loading the view, typically from a nib.
- (void)viewDidLoad {
    NSLog(@"viewDidLoad");
 
    [super viewDidLoad];
 
    cArray      = NULL;
    nsArray     = NULL;
 
    // read initial slider value setup accordingly
    [self sliderChanged:sliderCount];
 
    // get mach timer unit size and calculater millisecond factor
    mach_timebase_info_data_t info;
    mach_timebase_info(&info);
    machTimerMillisMult = (double)info.numer / ((double)info.denom * 1000000.0);
    NSLog(@"machTimerMillisMult = %f", machTimerMillisMult);
}
 
 
// pass in results of mach_absolute_time()
// this converts to milliseconds and outputs to the label
-(void)displayResult:(uint64_t)duration {
    double millis = duration * machTimerMillisMult;
 
    NSLog(@"displayResult: %f milliseconds", millis);
 
    NSString *str = [[NSString alloc] initWithFormat:@"%f milliseconds", millis];
    [labelResults setText:str];
    [str release];
}
 
 
 
// process using NSArray
-(IBAction) doNSArray:(id)sender {
    NSLog(@"doNSArray: %@", sender);
 
    uint64_t startTime = mach_absolute_time();
    float total = 0;
    for(int i=0; i<numberOfItems; i++) {
        total += [[nsArray objectAtIndex:i] floatValue];
    }
    [self displayResult:mach_absolute_time() - startTime];
}
 
 
 
// process using C Array
-(IBAction) doCArray:(id)sender {
    NSLog(@"doCArray: %@", sender);
 
    uint64_t start = mach_absolute_time();
    float total = 0;
    for(int i=0; i<numberOfItems; i++) {
        total += cArray[i];
    }
    [self displayResult:mach_absolute_time() - start];
}
 
 
// allocate NSArray and C Array 
-(void) allocateArrays {
    NSLog(@"allocateArrays");
 
    // allocate c array
    if(cArray) delete cArray;
    cArray = new float[numberOfItems];
 
    // allocate NSArray
    [nsArray release];
    nsArray = [[NSMutableArray alloc] initWithCapacity:numberOfItems];
 
 
    // fill with random values
    for(int i=0; i<numberOfItems; i++) {
        // add number to c array
        cArray[i] = random() * 1.0f/(RAND_MAX+1);
 
        // add number to NSArray
        NSNumber *number = [[NSNumber alloc] initWithFloat:cArray[i]];
        [nsArray addObject:number];
        [number release];
    }
 
}
 
 
// callback for when slider is changed
-(IBAction) sliderChanged:(id)sender {
    numberOfItems = sliderCount.value;
    NSLog(@"sliderChanged: %@, %i", sender, numberOfItems);
 
    NSString *str = [[NSString alloc] initWithFormat:@"%i items", numberOfItems];
    [labelCount setText:str];
    [str release];
 
    [self allocateArrays];
}
 
 
//cleanup
- (void)dealloc {
    [nsArray release];
    if(cArray) delete cArray;
 
    [super dealloc];
}
 
@end