Movatterモバイル変換

Collection classes are ubiquitous in Cocoa apps, but also fairly opaque. Today, at the suggestion of Matthew Elton, I'm going to take a look at howNSMutableArray works behind the scenes by building a replacement for it from scratch.

Concepts
SinceNSMutableArray is a class cluster, reimplementing it is fairly easy. By subclassing it and then implementing the primitive methods, you end up with a fully functionalNSMutableArray that supports all of the functionality of anyNSMutableArray. Here are the primitive methods:

-(NSUInteger)count;-(id)objectAtIndex:(NSUInteger)index;-(void)addObject:(id)anObject;-(void)insertObject:(id)anObjectatIndex:(NSUInteger)index;-(void)removeLastObject;-(void)removeObjectAtIndex:(NSUInteger)index;-(void)replaceObjectAtIndex:(NSUInteger)indexwithObject:(id)anObject;

It should be pretty clear how these primitive methods provide enough functionality for all the otherNSMutableArray methods to be built on. In fact, these primitive methods are already a bit excessive. For example,addObject: can be implemented in terms ofinsertObject:atIndex:, andremoveLastObject can be implemented in terms ofremoveObjectAtIndex:. I'm not entirely clear just why these extra primitive methods exist, but in any case, implementing this full set will give us a fully functionalNSMutableArray subclass.

The question is then,how do we implement these methods? The idea is to use a C array as the backing storage. Fundamentally, C arrays only support getting and setting values, whereasNSMutableArray allows for adding and removing values, which automatically shifts later values around. We'll handle this by copying array entries as necessary.NSMutableArray also allows for dynamic expansion of the array, which we'll handle by allocating a new C array and copying the old contents into it when necessary.

Code
As usual, the code for today's escapades is available on GitHub if you want to see it all in one place:

https://github.com/mikeash/MACollections

Implementation
The interface for this class is extremely simple:

@interfaceMAMutableArray :NSMutableArray@end

This subclass doesn't add anything new to the interface, so it's just a directNSMutableArray subclass.

Here are the instance variables that this class will use:

@implementationMAMutableArray{NSUInteger_count;NSUInteger_capacity;id*_objs;}

The C array is_objs, and_capacity holds the number of elements allocated for the array. The number of elements actually used is stored in_count. The capacity and count are stored separately so that the array doesn't need to be reallocated every time an object is added or removed, which would be extremely inefficient.

Next up is the initializer.NSMutableArray requires an implementation ofinitWithCapacity: in order for the class to work with built-in convenience methods like+array. As far as I know, this is not documented anywhere. For this class, all instance variables can be left at zero, so this initializer doesn't really need to do anything but callsuper:

-(id)initWithCapacity:(NSUInteger)capacity{return[superinit];}

Note that thecapacity argument is purely advisory, so it's safe to ignore like this.

Next comes the implementation ofdealloc. When the array is destroyed, it needs to release all of the objects it contains. While there are faster ways to implement this, I'll implement this by simply removing all of the objects. Besides that, the C array itself needs to be freed, and that's it:

-(void)dealloc{[selfremoveAllObjects];free(_objs);[superdealloc];}

Now we can move on to the implementation of the various primitive methods. The first one iscount, which is really easy since it can just return the_count instance variable:

-(NSUInteger)count{return_count;}

Next isobjectAtIndex:, which is nearly as simple. It simply fetches the element out of the C array and returns it:

-(id)objectAtIndex:(NSUInteger)index{return_objs[index];}

This code omits error checking in the interest of brevity and simplicity. A proper implementation of this method would first checkindex against_count and throw an exception if it's out of bounds. As it is here, a bad value forindex will cause this method to return junk or crash.

Insertion
As mentioned previously, theaddObject: method can be implemented in terms ofinsertObject:atIndex:, so that is what I do:

-(void)addObject:(id)anObject{[selfinsertObject:anObjectatIndex:[selfcount]];}

WithinsertObject:atIndex:, we finally get to some interesting code. The first thing this method needs to do is resize the backing C array if the current one is full, in order to make room for the new object:

-(void)insertObject:(id)anObjectatIndex:(NSUInteger)index{if(_count>=_capacity){

The code must calculate a new capacity to allocate. I use a minimum of16 elements, which is used for the very first allocation, and then increase the capacity by a factor of2 for each additional reallocation. Multiplying the capacity by a constant factor for each reallocation has some useful performance consequences which I'll discuss a little later. Here's the code that calculates the new capacity and then allocates the new array with this new capacity:

NSUIntegernewCapacity=MAX(_capacity*2,16);id*newObjs=malloc(newCapacity*sizeof(*newObjs));

Next, we need to copy the contents of the old array across. This is a simplememcpy:

memcpy(newObjs,_objs,_count*sizeof(*_objs));

Finally, the old storage is freed, and the instance variables reassigned to the new storage:

free(_objs);_objs=newObjs;_capacity=newCapacity;}

At this point, the array is guaranteed to have enough room for the new object. If the array was previously full, it has now been expanded. If it wasn't full, then it necessarily has room. With that condition satisfied, the next requirement is to move objects around to open up the slot atindex for the new object. All of the objects in the array afterindex need to shift down by one. This is done with a call tomemmove:

memmove(_objs+index+1,_objs+index,([selfcount]-index)*sizeof(*_objs));

For the unfamiliar,memmove is a potentially slower variant ofmemcpy which allows its arguments to overlap.memcpy is allowed to assume that its arguments are distinct, and can misbehave if that's not true. This code will have overlapping arguments nearly always, andmemmove allows that to work.

Let's unpack these arguments briefly._objs + index is the source address for thememmove, and is the beginning of the objects that need to be moved. The number of objects that need to be moved is[self count] - index, and multiplying that bysizeof(*_objs) gives the total size of these pointers in bytes. Finally, they need to be moved down by one slot, so the destination pointer is_objs + index + 1.

With room made for the new object, all that remains is to put it into the C array and increase the_count:

_objs[index]=[anObjectretain];_count++;}

Removal and Replacement
TheremoveLastObject primitive method is implemented by just callingremoveObjectAtIndex: and passing the last index in the array:

-(void)removeLastObject{[selfremoveObjectAtIndex:[selfcount]-1];}

The implementation ofremoveObjectAtIndex: is also relatively simple. The first thing is to release the object being removed:

-(void)removeObjectAtIndex:(NSUInteger)index{[_objs[index]release];

Next, shift all of the objects down withmemmove. This is essentially the same as the object shifting frominsertObject:atIndex:, but in the opposite direction:

memmove(_objs+index,_objs+index+1,([selfcount]-index-1)*sizeof(*_objs));

All that remains is to decrement the object count:

_count--;}

This method should also have some error checking in a real implementation to ensure thatindex is valid, but once again we skip it for this example.

A real implementation of this method would probably also shrink the C array if the count falls under some threshold. If you add a million objects to an array and then remove all of them, you don't want the array still holding memory for a million objects. However, since this isn't strictly necessary and is really just a memory-usage optimization, I have omitted it. The code would look much like the reallocation code ininsertObject:atIndex:.

The implementation ofreplaceObjectAtIndex:withObject: is also really simple. All it does is retain the new object, release the old object, and then place the new object into that index in the array:

-(void)replaceObjectAtIndex:(NSUInteger)indexwithObject:(id)anObject{[anObjectretain];[_objs[index]release];_objs[index]=anObject;}

And that's it! We now have a fully functionalNSMutableArray built from scratch.

Reallocation Cost
When reallocating the array, the code increases the capacity by a factor of two each time. This may be an unintuitive approach compared to, say, simply increasing the capacity by a fixed amount each time. Let's examine the performance consequences of these approaches to see why multiplying the capacity by a constant factor is generally better.

First, let's look at the cost incurred in performing a single array reallocation. We can assume that the allocation itself (and freeing the old array) take about the same amount of time no matter how big the array is. The only variable cost is copying the objects from the old array to the new array. Since copying doesn't do anything special, and just moves bytes around one by one, we can assume that if there are \(\mathrm{n}\) objects in the array, the copy will take an amount of time that's approximately proportionate to \(\mathrm{n}\), or in algorithmic complexity terms, this operation is \(\mathrm{O(n)}\). Knowing that each allocation is \(\mathrm{O(n)}\) in the size of the array so far, we can then figure out the complexity of different reallocation strategies.

Let's consider the case where we increase the array by a fixed amount each time. To make the analysis easy, let's say that the array's capacity is increased by \(\mathrm{1}\) each time. This is a pathological case, but it's easy to analyze, and the results carry over to more sane cases. Given this, let's look at the total cost of adding \(\mathrm{1000}\) elements to the array.

Every new element that's added requires a reallocation and incurs a cost proportional to the number of elements in the array so far. The first element costs approximately \(\mathrm{1}\), the second one approximately \(\mathrm{2}\), and so on. The total cost is then \(\mathrm{1 + 2 + 3 + \cdots + 999 + 1000}\), or \(\mathrm{500500}\).

More generally, the cost to add \(\mathrm{m}\) elements will be \(\mathrm{1 + 2 + 3 + \cdots + m}\), or: $$\frac{m * (m + 1)}{2}$$ In algorithmic complexity terms, this can be expressed simply as \(\mathrm{O(m^2)}\). In other words, the total cost to addm elements is proportional to the square ofm. Double the number of elements, and the time to add them will roughly quadruple. Adding a million elements will take roughly a trillion times longer than adding one element, which is not a very happy number.

Let's take a more realistic case, like increasing the capacity by \(\mathrm{1024}\) for each reallocation. In this case, adding \(\mathrm{m}\) elements will cost \(\mathrm{1024 + 2048 + 3076 + 4096 + \cdots + m}\). If you work it all out, this still turns out to beO(m2), although it's still much faster than before. The cost is still proportional to the square of the number of elements, but the cost is smaller by a large constant factor. This is a much more practical way to implement growing the array, but it still has poor asymptotic behavior.

Finally, let's look at the strategy implemented here of doubling the capacity for each reallocation. In this case, the total cost form elements will be approximately \(\mathrm{1 + 2 + 4 + 8 + 16 + \cdots + m}\), which is just \(\mathrm{2m - 1}\), or \(\mathrm{O(m)}\). In short, the cost to add elements is proportional to the total number of elements added. Add twice as many elements, and it takes about twice as much time.

Interestingly, this holds for other factors as well. For example, let's say that we increase the capacity by 10% each time. This is a little bit harder to work with, since the capacity can only be whole numbers. But if we put that aside for a moment and assume we can deal with fractions, then adding \(\mathrm{m}\) elements costs \(\mathrm{1 + 1.1 + 1.21 + \cdots + m}\), which works out to about \(\mathrm{11m}\), which is still \(\mathrm{O(m)}\), just with a larger constant factor. In general,any factor \(\mathrm{>1}\) will result in a net \(\mathrm{O(m)}\) cost to insert \(\mathrm{m}\) elements. However, the larger the factor, the lower the constant multiplier in front, so the faster the allocation will perform.

We end up with an interesting tradeoff. Using larger factors makes the array perform better, but wastes more space. When doubling the allocation, if the array holds \(\mathrm{m}\) elements, there may be space allocated for up to \(\mathrm{m - 2}\) additional elements that isn't being used. If the array continues to grow then it will eventually be used, but if it stops at that point, that space is perpetually wasted. With a 10% allocation increase, at most about \(\mathrm{\frac{m}{10}}\) space can be wasted, but the time spent in copying and reallocating becomes considerably greater.

Conclusion
The real implementation ofNSMutableArray isconsiderably more complicated that what's presented here, but the basic principles remain. Now that you see one simple implementation, I hope that this makes the whole concept more clear.

Next time, I'll take this a step further and show an implementation ofNSMutableDictionary based on a hash table. Until then, your ideas are always welcome for future articles, sosend them in!

Add your thoughts, post a comment:

Spam and off-topic posts will be deleted without notice. Culprits may be publicly humiliated at my sole discretion.