Does NSMutableArray actually count the items every time its count method is called?

Question

Because of cocoa design patterns, the name of the instance method count in NSMutableArray is ambiguous; it could either return a saved variable count, or it could count the items in the array each time it's called, and return that (cocoa dictates that a method that simply returns the value of a variable foo be foo, not getFoo). Does Objective C's NSMutableArray actually count the items every time its count method is called, or does it return the value of a pre-calculated variable? If this were Java, I'd look at the source code, but I can't find the source code for NSMutableArray. I looked at the API, and all it said was this:

Returns the number of objects currently in the array.

Since there was no context, I can't tell if that means it does any calculations inside it or not.

Answer 1

As you have correctly noted, there is no guarantee that it will behave one way or the other.

In practice, though, -[NSArray count] is a constant-time operation. You can confirm this yourself by creating a small array and a large array and benchmarking the time it takes to get their counts. It would be pretty silly to have an O(n) count method on the core array classes like this.

Answer 2

NSArray declares a private ivar _used that appears to hold the count of the array. Using object_getInstanceVariable() you can verify that in the case of the concrete subclass __NSArrayM, this variable is incremented and decremented as objects are added and removed.

I used the following program, a Mac OS X Foundation command-line tool, to verify this:

#import <Foundation/Foundation.h>
#import <objc/runtime.h>

int main(int argc, const char * argv[])
{

    @autoreleasepool {

        NSMutableArray *anArray = [NSMutableArray array];
        NSLog(@"anArray's concrete class is %@", [anArray class]);
        UInt64 used = 0;
        for (NSString *toAdd in @[@"o", @"m", @"g"]) {
            object_getInstanceVariable(anArray, "_used", (void **)&used);
            NSLog(@"array = %@, used = %lld", anArray, used);
            [anArray addObject:toAdd];
        }
        for (NSString *toRemove in [anArray copy]) {
            object_getInstanceVariable(anArray, "_used", (void **)&used);
            NSLog(@"array = %@, used = %lld", anArray, used);
            [anArray removeObject:toRemove];
        }
        object_getInstanceVariable(anArray, "_used", (void **)&used);
        NSLog(@"array = %@, used = %lld", anArray, used);
    }
    return 0;
}

This program produced the following output:

2013-01-31 17:40:15.376 Array[10173:303] anArray's concrete class is __NSArrayM
2013-01-31 17:40:15.378 Array[10173:303] array = (
), used = 0
2013-01-31 17:40:15.378 Array[10173:303] array = (
    o
), used = 1
2013-01-31 17:40:15.379 Array[10173:303] array = (
    o,
    m
), used = 2
2013-01-31 17:40:15.379 Array[10173:303] array = (
    o,
    m,
    g
), used = 3
2013-01-31 17:40:15.380 Array[10173:303] array = (
    m,
    g
), used = 2
2013-01-31 17:40:15.380 Array[10173:303] array = (
    g
), used = 1
2013-01-31 17:40:15.380 Array[10173:303] array = (
), used = 0