objective c - 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.