How NSMutableArray achieves such high speed in fast enumeration

Question

The y axis represents 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 that are repeated.

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

In each outer loop, each list / array has an empty string @"" added to it. In inner loops, each row in each list / array is retrieved, it is synchronized and written. After all our data was output at the Wolfram Language output to create a graph.

How do NSMutableArray achieve such amazing and consistent results? How can this be achieved?

My implementation of NSFastEnumeration:

 - (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; } 

Full test 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

Forcibly disabling ARC in linked link list files, performance has increased significantly. This reduced access time from ~ 70 ns to ~ 14 ns. While it is still slower, on average, NSArray is, on average, about two times slower, and not ten times slower.

Although ARC can make code faster, iterative situations add unnecessary release / save calls.

Gratitude found for comments by Greg Parker .