How does NSMutableArray achieve such high speed in fast enumeration

Question

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);

Answer 1

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.