Filling an NSMutableArray

It is estimated that there are over 6 billion people living on Earth. This staggering number raises many issues. For the Cocoa programmer, one of the issues is, can they all fit in an NSArray?

I’ve always wondered how many objects can fit in an NSArray. My first guess is one fewer than the number of grains in a heap of sand. According to the class reference for NSMutableArray, the method +[NSMutableArray arrayWithCapacity:] takes an unsigned int argument, so what’s the maximum value of an unsigned int? This should be defined in the standard headers by the macro UINT_MAX. We could easily learn the value of UINT_MAX by calling NSLog(@"UINT_MAX: %u", UINT_MAX); but instead let’s go on a wild goose chase! That would be much more fun. The natural place to start would be /usr/include/limits.h.

Nope, no dice. Ok, time to give up.

Wait! Near the top of the file we find #include <machine/limits.h> and #include <sys/syslimits.h>. The next stop on our goose chase is /usr/include/machine/limits.h. This file just tells you where to look depending on your architecture. If you have a PowerPC machine, it’s /usr/include/ppc/limits.h; I have an Intel machine, so I’m going to try /usr/include/i386/limits.h. Bingo!

#define UINT_MAX 0xffffffff /* max value for an unsigned int */

For those of you who don’t count in hexadecimal, that’s decimal 4,294,967,295. For those of you who don’t count in decimal, that’s 4 billion, give or take (actually, give). Unfortunately, an array with capacity UINT_MAX is not big enough to hold every person, or every Person, as the sample code usually goes. On the other hand, who pays attention to the stated capacity? Certainly not elevator riders. Maybe we can just keep stuffing an array with objects if we push really hard. After all, an NSMutableArray is supposed to be able to expand beyond its Capacity: argument.

Before we send our array to the all-you-can-eat object buffet, we should carefully consider the consequences. Will it have to go on an NSDiet afterward? Will we be able to find an object after it has been added to the array? The method -[NSArray indexOfObject:] returns an unsigned int. What index will the (UINT_MAX + 1)th object return? Another worry is that this method returns NSNotFound when the array does not contain the object. The file NSObjCRuntime.h defines NSNotFound:

enum {NSNotFound = 0x7fffffff};

That’s 2,147,483,647 for the hex-impaired. It turns out, then, that NSNotFound < UINT_MAX. (Note to self: link to the sound of a car slamming on its brakes and screeching to a halt.) If we add more than NSNotFound objects to an array, how will we know whether -[NSArray indexOfObject:] has found an object or not?

We’ve accumulated plenty of unanswered questions. It’s time to put up or shut up. (Note to self: stop talking to yourself.) Let’s test what actually happens when we add a large number of objects to an NSMutableArray. I decided to begin with NSNotFound before moving up to UINT_MAX. In the end, it didn’t make a difference.

#import <Foundation/Foundation.h>

int main(int argc, const char * argv[]) {
	NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

	unsigned int size = NSNotFound;
	NSMutableArray * array = [NSMutableArray arrayWithCapacity:size];
	NSNumber * number;
	unsigned int index;
	for (index = 0u; index < size; ++index) {
		number = [[NSNumber alloc] initWithUnsignedInt:index];
		[array addObject:number];
		[number release];
		if ((index % 1000000u) == 0u) {
			NSLog(@"Current index: %u", index);
		}
	}

	NSString * string = [[NSString alloc] initWithString:@"MAD_MAX"];
	[array addObject:string];
	NSLog(@"MAD_MAX index: %u", [array indexOfObject:string]);
	[string release];

    [pool release];
    return 0;
}

Can you say “SIGBUS”, children? Good! I knew you could! Yes, my test program crashed hard at somewhere between 115 and 116 million objects.

ArraySize(3780) malloc: *** vm_allocate(size=1069056) failed (error code=3)
ArraySize(3780) malloc: *** error: can't allocate region

Moral of the story: What’s the capacity of an NSMutableArray? I don’t know. Before it reaches any kind of limit, your computer will run out of memory. My iMac has 1 GB RAM; a Mac Pro has a maximum of 16 GB. Therefore, if you’re adding a completely unknown quantity of objects to an array, you might want to place your own limits. Or in other words, be excellent to each other, and party on dudes!

3 Responses to “Filling an NSMutableArray”

  1. Jeff says:

    I’m only guessing that a Mac Pro couldn’t handle it either. I’d be interested in hearing about real tests.

  2. Jeffstyr says:

    The amount of physical RAM you have shouldn’t matter–it’s the size of your virtual address space which does. For a 32-bit process, the limit is 4GB–you’re probably running into that limit (unless you run out of swap space first). You should be able to get to a higher number if you just add the same NSNumber instance to your array over-and-over, rather than creating a new one each time through the loop–those are probably eating up the majority of your memory.

  3. Jeff says:

    When I add the same object repeatedly, it makes it up to 536 million before dying. An array of that many 4-byte pointers would take up about 2GB; I have no idea what other overhead an NSArray has. The system and the app will also consume memory. Perhaps it’s reaching 4GB, though I’ve deliberately turned off everything else before the test. Anyway, NSNotFound is still safe.