How does NSMutableArray achieve such high speed in fast enumeration

Question

Blue = My Linked List, Red = NSMutableArray

The y axis represents the the average access time (in ns) to each node in the list/array (total time to access all elements divided by the number of elements).

The x axis represents the number of elements in the array being iterated over.

Where red is an implementation of NSMutableArray and blue is my linked list (CHTape).

In each outer loop each list/array has a empty string @"" appended to it. In the inner loops each string in each list/array is retrieved, this is timed and recorded. After everything the times our outputted in a Wolfram Language output to produce a plot.

How does NSMutableArray achieve such amazing and consistent results? How can one achieve similar?

My NSFastEnumeration Implementation:

- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained [])stackBuffer count:(NSUInteger)len
{
    if (state->state == 0)
    {
        state->state = 1;
        state->mutationsPtr = &state->extra[1];
        state->extra[0] = (unsigned long)head;
    }

    CHTapeNode *cursor = (__bridge CHTapeNode *)((void *)state->extra[0]);

    NSUInteger i = 0;

    while ( cursor != nil && i < len )
    {
        stackBuffer[i] = cursor->payload;
        cursor = cursor->next;
        i++;
    }
    state->extra[0] = (unsigned long)cursor;

    state->itemsPtr = stackBuffer;

    return i;
}

Complete Testing Code:

NSMutableArray *array = [NSMutableArray array];
CHTape *tape = [CHTape tape];

unsigned long long start;

unsigned long long tapeDur;
unsigned long long arrayDur;

NSMutableString * tapeResult = [NSMutableString stringWithString:@"{"];
NSMutableString * arrayResult = [NSMutableString stringWithString:@"{"];

NSString *string;

int iterations = 10000;

for (int i = 0; i <= iterations; i++)
{
    [tape appendObject:@""];
    [array addObject:@""];

    // CHTape
    start = mach_absolute_time();
    for (string in tape){}
    tapeDur = mach_absolute_time() - start;


    // NSArray
    start = mach_absolute_time();
    for (string in array){}
    arrayDur = mach_absolute_time() - start;


    // Results

    [tapeResult appendFormat:@"{%d, %lld}", i, (tapeDur/[tape count])];
    [arrayResult appendFormat:@"{%d, %lld}", i, (arrayDur/[array count])];

    if ( i != iterations)
    {
        [tapeResult appendString:@","];
        [arrayResult appendString:@","];
    }
}

[tapeResult appendString:@"}"];
[arrayResult appendString:@"}"];

NSString *plot = [NSString stringWithFormat:@"ListPlot[{%@, %@}]", tapeResult, arrayResult];
NSLog(@"%@", plot);

NSMutableArray [changes it's internal implementation as its size grows](http://ridiculousfish.com/blog/posts/array.html) - chances are it's simply being implemented as a raw C array for the sizes you're using. — Richard J. Ross III, Feb 25 '14 at 21:22
It's also highly optimized for iteration, as that is one of the most commonly used operations on an array. — Richard J. Ross III, Feb 25 '14 at 21:22
You can probably also find all of you answers in the [open-sourced CFArray implementation](http://www.opensource.apple.com/source/CF/CF-368.18/Collections.subproj/CFArray.c), should you wish to dig through all of the source. — Richard J. Ross III, Feb 25 '14 at 21:25
See also http://stackoverflow.com/questions/20724712/how-for-in-loop-works-internally-objective-c-foundation: The `countByEnumeratingWithState:...` implementation need not copy the elements. — Martin R, Feb 25 '14 at 21:27
Is your -countByEnumeratingWithState... method implemented with ARC enabled? NSArray's implementation has ARC turned off so it avoids unnecessary retain/release calls. — Greg Parker, Feb 25 '14 at 22:47

score 1 · Accepted Answer · edited May 23 '17 at 12:30

Blue = My Linked List, Red = NSMutableArray

By forcing ARC off on the link list related files efficiency increased dramatically. It reduced access time from ~70ns to ~14ns. While this is still slower, on average, then NSArray its only, on average, about two times slower, as opposed to ten times slower.

While ARC can make some code faster, in iterative situations adds unnecessary release/retain calls.

Discovered thanks to Greg Parker's comment.

How does NSMutableArray achieve such high speed in fast enumeration

1 Answers1