Confronto prestazioni NSArray vs array C

Question

Recentemente ho eseguito un piccolo progetto di ricerca sulle prestazioni dell'accesso sequenziale o casuale a un NSArray in relazione a un array C. La maggior parte dei casi di test si presentano come mi aspetterei, tuttavia alcuni non funzionano come pensavo che avrebbero fatto e spero che qualcuno possa spiegare il perché.

Fondamentalmente il test consiste nel riempire un array C con oggetti 50k, iterando su ciascuno di essi e chiamando un metodo (che internamente incrementa solo un float nell'oggetto), la seconda parte del test prevede la creazione di un ciclo che completa 50k iterazioni ma accede a un oggetto casuale nell'array. Fondamentalmente è piuttosto semplice.

Per eseguire il confronto sto inizializzando NSArray con C Array. Ogni test viene quindi eseguito tramite un blocco passato a un metodo che tiene traccia del tempo impiegato per eseguire il blocco. Il codice che sto usando è contenuto di seguito, ma mi piacerebbe coprire i risultati e le query che ho prima.

Questi test sono stati eseguiti su un iPhone 4 e racchiusi in un dispatch_after per attenuare eventuali operazioni di threading o non atomiche rimanenti a seguito dell'avvio dell'applicazione. I risultati di una singola esecuzione sono i seguenti, ogni esecuzione è essenzialmente la stessa con poche varianti:

===SEQUENCE=== 
NSARRAY FAST ENUMERATION: 12ms 
NSARRAY FAST ENUMERATION WEAK: 186ms 
NSARRAY BLOCK ENUMERATION: 31ms (258.3%) 
C ARRAY DIRECT: 7ms (58.3%) 
C ARRAY VARIABLE ASSIGN: 33ms (275.0%) 
C ARRAY VARIABLE ASSIGN WEAK: 200ms (1666.7%) 

===RANDOM=== 
NSARRAY RANDOM: 102ms (850.0%) *Relative to fast enumeration 
C ARRAY DIRECT RANDOM: 39ms (38.2%) *Relative to NSArray Random 
C ARRAY VARIABLE ASSIGN RANDOM: 82ms (80.4%) 

L'approccio più veloce sembra essere accedere direttamente gli elementi della matrice C con "* (CArray + idx)" , tuttavia, la cosa più sconcertante è che l'assegnazione del puntatore da C Array a una variabile ogg obiettiva "id object = * (carry + idx)" provoca un enorme successo in termini di prestazioni.

Inizialmente ho pensato che forse era un arco fare qualcosa con il conteggio dei riferimenti poiché la variabile era forte, quindi a questo punto l'ho cambiata a debole aspettando che la performance aumentasse "__weak id object = * (carry + idx)". Con mia sorpresa, in realtà è stato molto più lento.

I risultati di accesso casuale sono andati bene come mi sarei aspettato in base ai risultati della sequenza, quindi non ci sono sorprese per fortuna.

Come risultato di questo ci sono una serie di domande:

1. Perché l'assegnazione ad una variabile voluto così tanto tempo?
2. Perché l'assegnazione a una variabile debole richiede ancora più tempo? (Forse c'è qualcosa che non capisco succedendo qui)
3. Considerando quanto sopra, in che modo Apple ha ottenuto l'enumerazione standard rapida per funzionare così bene?

E per completezza ecco il codice. Così sto creando le matrici come segue:

__block id __strong *cArrayData = (id __strong *)malloc(sizeof(id) * ITEM_COUNT); 

for (NSUInteger idx = 0; idx < ITEM_COUNT; idx ++) { 
    NSTestObject *object = [[NSTestObject alloc] init]; 
    cArrayData[idx] = object; 
} 

__block NSArray *arrayData = [NSArray arrayWithObjects:cArrayData count:ITEM_COUNT]; 

E NSTestObject è definita in questo modo:

@interface NSTestObject : NSObject 

- (void)doSomething; 

@end 

@implementation NSTestObject 
{ 
    float f; 
} 

- (void)doSomething 
{ 
    f++; 
} 

E il metodo utilizzato al profilo il codice:

int machTimeToMS(uint64_t machTime) 
{ 
    const int64_t kOneMillion = 1000 * 1000; 
    static mach_timebase_info_data_t s_timebase_info; 

    if (s_timebase_info.denom == 0) { 
     (void) mach_timebase_info(&s_timebase_info); 
    } 
    return (int)((machTime * s_timebase_info.numer)/(kOneMillion * s_timebase_info.denom)); 
} 

- (int)profile:(dispatch_block_t)call name:(NSString *)name benchmark:(int)benchmark 
{ 

    uint64_t startTime, stopTime; 
    startTime = mach_absolute_time(); 

    call(); 

    stopTime = mach_absolute_time(); 

    int duration = machTimeToMS(stopTime - startTime); 

    if (benchmark > 0) { 
     NSLog(@"%@: %i (%0.1f%%)", name, duration, ((float)duration/(float)benchmark) * 100.0f); 
    } else { 
     NSLog(@"%@: %i", name, duration); 
    } 

    return duration; 

} 

Infine, questa è come sto eseguendo i test effettivi:

int benchmark = [self profile:^ { 
    for (NSTestObject *view in arrayData) { 
     [view doSomething]; 
    } 
} name:@"NSARRAY FAST ENUMERATION" benchmark:0]; 

[self profile:^ { 
    for (NSTestObject __weak *view in arrayData) { 
     [view doSomething]; 
    } 
} name:@"NSARRAY FAST ENUMERATION WEAK" benchmark:0]; 

[self profile:^ { 
    [arrayData enumerateObjectsUsingBlock:^(NSTestObject *view, NSUInteger idx, BOOL *stop) { 
     [view doSomething]; 
    }]; 
} name:@"NSARRAY BLOCK ENUMERATION" benchmark:benchmark]; 

[self profile:^ { 
    for (NSUInteger idx = 0; idx < ITEM_COUNT; idx ++) { 
     [*(cArrayData + idx) doSomething]; 
    } 
} name:@"C ARRAY DIRECT" benchmark:benchmark]; 

[self profile:^ { 
    id object = nil; 
    NSUInteger idx = 0; 
    while (idx < ITEM_COUNT) { 
     object = (id)*(cArrayData + idx); 
     [object doSomething]; 
     object = nil; 
     idx++; 
    } 
} name:@"C ARRAY VARIABLE ASSIGN" benchmark:benchmark]; 

[self profile:^ { 
    __weak id object = nil; 
    NSUInteger idx = 0; 
    while (idx < ITEM_COUNT) { 
     object = (id)*(cArrayData + idx); 
     [object doSomething]; 
     object = nil; 
     idx++; 
    } 
} name:@"C ARRAY VARIABLE ASSIGN WEAK" benchmark:benchmark]; 

NSLog(@"\n===RANDOM===\n"); 

benchmark = [self profile:^ { 
    id object = nil; 
    for (NSUInteger idx = 0; idx < ITEM_COUNT; idx ++) { 
     object = arrayData[arc4random()%ITEM_COUNT]; 
     [object doSomething]; 
    } 
} name:@"NSARRAY RANDOM" benchmark:benchmark]; 

[self profile:^ { 
    NSUInteger idx = 1; 
    while (idx < ITEM_COUNT) { 
     [*(cArrayData + arc4random()%ITEM_COUNT) doSomething]; 
     idx++; 
    } 
} name:@"C ARRAY DIRECT RANDOM" benchmark:benchmark]; 

[self profile:^ { 
    id object = nil; 
    NSUInteger idx = 0; 
    while (idx < ITEM_COUNT) { 
     object = (id)*(cArrayData + arc4random()%ITEM_COUNT); 
     [object doSomething]; 
     idx++; 
    } 
} name:@"C ARRAY VARIABLE ASSIGN RANDOM" benchmark:benchmark]; 

Answer 1

Perché l'assegnazione a una variabile richiede così tanto tempo?

La tua ipotesi era corretta: ARC chiama retain quando si assegna, e release quando si riassegnano, o quando id va fuori di portata.

Perché l'assegnazione a una variabile debole richiede ancora più tempo? (Forse c'è qualcosa che non capisco succedendo qui)

Ricordate che ARC promette di cancellare il vostro riferimento debole quando l'ultimo riferimento forte è andato. Questo è il motivo per cui i riferimenti deboli sono più costosi: per __weak id, __weak id, ARC registra l'indirizzo id con il runtime per ottenere una notifica dell'oggetto rilasciato. Questa registrazione richiede la scrittura in una tabella hash, molto più lenta del semplice mantenimento e rilascio.

Considerando quanto sopra, in che modo Apple ha ottenuto l'enumerazione rapida standard per funzionare così bene?

L'enumerazione rapida utilizza i blocchi dell'array che supporta direttamente NSArray. Essenzialmente, catturano un blocco di 30 elementi o giù di lì, e trattano l'accesso ad esso come un semplice array C. Quindi afferrano il blocco successivo, lo ripetono come se fosse un array C e così via. C'è qualche piccolo sovraccarico, ma è per blocco, non per elemento, quindi ottieni prestazioni piuttosto impressionanti.

Answer 2

2) perché non è possibile l'ottimizzazione. Debole variabili contenute nella memoria statica e accesso statico più lungo di dinamico