What is the data structure behind NSMutableArray?

Question

Usually, a "mutable array" class is implemented as a wrapper around a simple array. The wrapper allocates more memory when you add an element past the end. This is a common data structure and the performance of the various operations is well known. You get O(1) element access, O(N) insert and remove, or O(1) (on average) insert and remove at the end of the array. But NSMutableArray is something else. For example the docs say [emphasis mine]:

Note: Most operations on an array take constant time: accessing an element, adding or removing an element at either end, and replacing an element. Inserting an element into the middle of an array takes linear time.

So, what exactly is NSMutableArray? Is this documented somewhere?

Answer 1

It's a wrapper around a circular buffer.

This is neither documented nor open-sourced, but this blog post shows an amazing reverse-engineer job over NSMutableArray, which I think you'll find very interesting.

The NSMutableArray class cluster is backed by a concrete private subclass called __NSArrayM.

The greatest discovery is that NSMutableArray is not a thin wrapper around a CFArray, as one may reasonably think: CFArray is open-sourced and it doesn't use a circular buffer, whereas __NSArrayM does.

Reading through the comments of the article, it appears that it started to be this way since iOS 4, whereas in previous SDKs NSMutableArray actually used CFArray internally and __NSArrayM wasn't even there.

Straight from the blog post I mentioned above

Data Structure

As you might have guessed, __NSArrayM makes use of circular buffer. This data structure is extremely simple, but a little bit more sophisticated than regular array/buffer. The contents of circular buffer can wrap around when either end is reached.

Circular buffer has some very cool properties. Notably, unless the buffer is full, insertion/deletion from either end doesn’t require any memory to be moved.

The pseudo-code for objectAtIndex: goes as follows:

- (id)objectAtIndex:(NSUInteger)index {
    if (_used <= index) {
        goto ThrowException;
    }

    NSUInteger fetchOffset = _offset + index;
    NSUInteger realOffset = fetchOffset - (_size > fetchOffset ? 0 : _size);

    return _list[realOffset];

ThrowException:
    // exception throwing code
}

where the ivars are defined as

• _used: the number of elements the array holds
• _list: the pointer to the circular buffer
• _size: the size of the buffer
• _offset: the index of first element of array in the buffer

---

Again, I don't take any credit for all the information above, as they come straight from this amazing blog post by Bartosz Ciechanowski.

Answer 2

Did some measurements: Starting with an empty array, added @"Hello" 100,000 times, then removed it 100,000 times. Different patterns: Adding/removing at the end, at the start, in the middle, close to the start (at index 20 when possible), close to the end (20 indexes away from the end when possible), and one where I alternated between close to the start and the end. Here's the times for 100,000 objects (measured on Core 2 Duo):

Adding objects = 0.006593 seconds
Removing objects at the end = 0.004674 seconds
Adding objects at the start = 0.003577 seconds
Removing objects at the start = 0.002936 seconds
Adding objects in the middle = 3.057944 seconds
Removing objects in the middle = 3.059942 seconds
Adding objects close to the start = 0.010035 seconds
Removing objects close to the start = 0.007599 seconds
Adding objects close to the end = 0.008005 seconds
Removing objects close to the end = 0.008735 seconds
Adding objects close to the start / end = 0.008795 seconds
Removing objects close to the start / end = 0.008853 seconds

So the time for each add / remove is proportional the distance to the beginning or end of the array, whichever is closer. Adding things in the middle is expensive. You don't have to work exactly at the end; removing elements close to the start / end is also quite cheap.

The suggested implementation as a circular list omits an important detail: There is a gap of variable size between the location of the last and the first array element. As array elements are added / removed, the size of that gap changes. More memory needs to be allocated and object pointers need to be moved when the gap disappears and more objects are added; the array can be shrunk and object pointers need to be moved when the gap becomes too large. A simple change (allowing the gap to be located at any location, not just between last and first element) would allow changes at any location to be fast (as long as it is the same location), and would make operations that "thin out" the array faster.