Objective-c: Problemy z blokami i NSEnumerationConcurrent

Question

Mam słownik zawierający drugi słownik z 1000 wpisami. Wpisy są wszystkie NSStrings klucza typu = key XXX, a wartość = element XXX, gdzie XXX jest liczbą między 0 - liczba elementów - 1. (Kilka dni temu, zapytałem o słowniki Objective-C zawierające słownik. Please refer to that question if chcesz kod, który tworzy słownik.)

Suma całkowita długość wszystkich ciągów w podstronie jest 28 670 znaków. tj:

strlen("key 0")+strlen("element 0")+ 
//and so on up through 
strlen("key 999")+strlen("element 999") == 28670. 

Rozważ tę bardzo prostą wartość mieszania jako wskaźnik, jeśli metoda wyliczyła każdą parę klucz + wartość tylko raz.

Mam jeden podprogram, który działa doskonale (za pomocą bloków), aby uzyskać dostęp do indywidualnego klucza słownika i wartości:

NSUInteger KVC_access3(NSMutableDictionary *dict){ 
    __block NSUInteger ll=0; 
    NSMutableDictionary *subDict=[dict objectForKey:@"dict_key"]; 

    [subDict 
     enumerateKeysAndObjectsUsingBlock: 
      ^(id key, id object, BOOL *stop) { 
       ll+=[object length]; 
       ll+=[key length]; 
    }]; 
    return ll; 
} 
// will correctly return the expected length... 

Gdyby spróbować tego samego z wykorzystaniem bloków współbieżnych (na multi maszynie procesora), otrzymuję liczba blisko, ale nie do końca oczekiwany 28670:

NSUInteger KVC_access4(NSMutableDictionary *dict){ 
    __block NSUInteger ll=0; 
    NSMutableDictionary *subDict=[dict objectForKey:@"dict_key"]; 

    [subDict 
     enumerateKeysAndObjectsWithOptions: 
      NSEnumerationConcurrent 
     usingBlock: 
      ^(id key, id object, BOOL *stop) { 
       ll+=[object length]; 
       ll+=[key length]; 
    }]; 
    return ll; 
} 
// will return correct value sometimes; a shortfall value most of the time... 

Docs Jabłko dla NSEnumerationConcurrent stanie:

"the code of the Block must be safe against concurrent invocation." 

Myślę, że to prawdopodobnie problem, ale jaki jest problem z moim kodem lub blokiem w KVC_access4, który NIE jest bezpieczny dla współbieżnego wywoływania?

Edytuj & Wnioski

Dzięki BJ Homera excellent solution, mam NSEnumerationConcurrent pracy. Dokładnie zaplanowałem obie metody. Kod, który mam powyżej w KVC_access3 jest szybszy i łatwiejszy dla małych i średnich słowników. O wiele szybciej na wielu słownikach. Jednakże, jeśli masz Mongo duży słowniku (miliony lub dziesiątki milionów par klucz/wartość) wtedy ten kod:

[subDict 
    enumerateKeysAndObjectsWithOptions: 
     NSEnumerationConcurrent 
    usingBlock: 
     ^(id key, id object, BOOL *stop) { 
     NSUInteger workingLength = [object length]; 
     workingLength += [key length]; 

     OSAtomicAdd64Barrier(workingLength, &ll); 
}]; 

jest do 4x szybciej. Punktem przecięcia dla rozmiaru jest około 1 słownik 100 000 z moich elementów testowych. Więcej słowników i ten punkt zwrotny jest wyższy, prawdopodobnie z powodu czasu konfiguracji.

Answer 1

Przy równoczesnym wyliczaniu, blok będzie uruchamiany jednocześnie na wielu wątkach. Oznacza to, że wiele wątków ma dostęp do ll w tym samym czasie. Ponieważ nie masz synchronizacji, masz skłonność do wyścigów.

Jest to problem, ponieważ operacja += nie jest operacją atomową. Pamiętaj, że ll += x to to samo co ll = ll + x. Obejmuje to odczytanie ll, dodanie do tej wartości x, a następnie zapisanie nowej wartości z powrotem w ll. Między odczytem ll w wątku X i jego zapisaniem wszelkie zmiany spowodowane przez inne wątki zostaną utracone, gdy wątek X powróci do przechowywania swoich obliczeń.

Należy dodać synchronizację, aby wiele wątków nie mogła jednocześnie modyfikować wartości.Naiwny rozwiązanie to:

__block NSUInteger ll=0; 
NSMutableDictionary *subDict=[dict objectForKey:@"dict_key"]; 

[subDict 
    enumerateKeysAndObjectsWithOptions:NSEnumerationConcurrent 
    usingBlock: 
     ^(id key, id object, BOOL *stop) { 
      @synchronized(subDict) { // <-- Only one thread can be in this block at a time. 
       ll+=[object length]; 
       ll+=[key length]; 
      } 
}]; 
return ll; 

Jednak ta odrzuca wszystkie korzyści można uzyskać z równoczesnym wyliczenia, ponieważ całe ciało bloku jest teraz zamknięty w zsynchronizowany blokowo w efekcie tylko jedna instancja tego bloku będzie działać w danym momencie.

Jeśli współbieżności jest rzeczywiście istotny wymóg wydajność tutaj, polecam następujące:

__block uint64 ll = 0; // Note the change in type here; it needs to be a 64-bit type. 

^(id key, id object, BOOL *stop) { 
    NSUInteger workingLength = [object length]; 
    workingLength += [key length]; 

    OSAtomicAdd64Barrier(workingLength, &ll); 
} 

Zauważ, że używam OSAtomicAdd64Barrier, który jest dość funkcję niskiego poziomu gwarantowanego do zwiększania wartość atomowo. Możesz również użyć @synchronized, aby kontrolować dostęp, ale jeśli ta operacja jest rzeczywiście znaczącym wąskim gardłem wydajności, prawdopodobnie będziesz potrzebował najbardziej wydajnej opcji, nawet kosztem odrobiny przejrzystości. Jeśli to wydaje się być przesadą, to podejrzewam, że włączenie jednoczesnego wyliczania nie wpłynie tak naprawdę na twoją wydajność.