Wie NSMutableArray so hohe Geschwindigkeit in schnellen Auszählung erreichen

Question

Die y Achse stellt das die durchschnittliche Zugriffszeit (in ns) zu jedem Knoten in der Liste/array (Gesamtzeit alle Elemente durch unterteilt zuzugreifen die Anzahl der Elemente). Die Achse x repräsentiert die Anzahl der Elemente im Array, über die iteriert wird.

Wo rot ist eine Implementierung von NSMutableArray und blau ist meine verkettete Liste (CHTape).

In jeder äußeren Schleife ist jeder Liste/jedem Array eine leere Zeichenfolge @"" angehängt. In den inneren Schleifen wird jede Zeichenfolge in jeder Liste/jedem Array abgerufen, dies wird zeitlich festgelegt und aufgezeichnet. Nach all den Zeiten haben wir unsere Ausgabe in einer Wolfram Language ausgegeben, um eine Handlung zu erstellen.

Wie erzielt NSMutableArray so erstaunliche und konsistente Ergebnisse? Wie kann man Ähnliches erreichen?

My NSFastEnumeration Umsetzung:

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

komplette 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

von ARC zwingt auf der Linkliste bezogenen Dateien Effizienz off dramatisch zugenommen. Es reduziert die Zugriffszeit von ~ 70ns auf ~ 14ns. Während dies im Durchschnitt immer noch langsamer ist, ist NSArray im Durchschnitt nur etwa zweimal langsamer, im Gegensatz zu zehnmal langsamer.

Während ARC kann einige Code schneller machen, in iterativen Situationen fügt unnötige Freigabe/behalten Anrufe.

Entdeckt dank Greg Parker's Kommentar.