Objetivo-c: Problemas con bloques y NSEnumerationConcurrent

Question

Tengo un diccionario que contiene un segundo diccionario con 1000 entradas. Las entradas son todas NSStrings del tipo key = key XXX, y value = element XXX donde XXX es un número entre 0 - el número de elementos - 1. (Hace varios días, pregunté sobre los diccionarios Objective-C que contienen un diccionario. Por favor, refer to that question if desea el código que crea el diccionario.)

La longitud total de todas las cadenas del diccionario secundario es de 28,670 caracteres. es decir:

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

consideran este un valor hash muy simple como un indicador si un método ha enumerado cada par de claves valor + una vez y sólo una vez.

tengo una subrutina que funciona a la perfección (el uso de bloques) para acceder a la clave de diccionario individual y valores:

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... 

Si trato de los mismos utilizando bloques concurrentes (en una máquina multi procesadores), aparece un número cerca pero no exactamente el esperado 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... 

la documentación de Apple para NSEnumerationConcurrent estado:

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

Creo que ese es probablemente el problema, pero ¿cuál es el problema con mi código o el bloque en KVC_access4 que NO es seguro para la invocación concurrente?

Editar & Conclusión

Gracias a BJ Homero excellent solution, tengo NSEnumerationConcurrent de trabajo. Temporicé ambos métodos ampliamente. El código que tengo arriba en KVC_access3 es más rápido y más fácil para diccionarios pequeños y medianos. Es mucho más rápido en muchos diccionarios. Sin embargo, si usted tiene un gran diccionario mongo (millones o decenas de millones de pares clave/valor) entonces este código:

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

     OSAtomicAdd64Barrier(workingLength, &ll); 
}]; 

es hasta 4 veces más rápido. El punto de cruce para el tamaño es de aproximadamente 1 diccionario de 100,000 de mis elementos de prueba. Más diccionarios y ese punto de cruce es mayor presumiblemente debido al tiempo de configuración.

Answer 1

Con la enumeración simultánea, tendrá el bloque ejecutándose simultáneamente en varios hilos. Esto significa que varios hilos están accediendo al ll al mismo tiempo. Como no tienes sincronización, eres propenso a las condiciones de carrera.

Esto es un problema porque la operación += no es una operación atómica. Recuerde, ll += x es lo mismo que ll = ll + x. Esto implica leer ll, agregar x a ese valor, y luego almacenar el nuevo valor en ll. Entre el momento en que se lee ll en el Subproceso X y cuando se almacena, cualquier cambio causado por otros subprocesos se perderá cuando el Subproceso X vuelva a almacenar su cálculo.

Necesita agregar sincronización para que varios hilos no puedan modificar el valor al mismo tiempo.La solución ingenua es la siguiente:

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

Sin embargo, esto descarta todos los beneficios que obtiene de la enumeración simultánea, ya que todo el cuerpo del bloque está ahora encerrado en un sincronizado de bloques, en efecto, sólo una instancia de este bloque en realidad estaría funcionando a la vez.

Si la concurrencia es en realidad un requisito importante actuación aquí, me gustaría sugerir lo siguiente:

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

Tenga en cuenta que estoy usando OSAtomicAdd64Barrier, que es una función de bajo nivel bastante que está garantizado para incrementar una valor atómico. También puede usar @synchronized para controlar el acceso, pero si esta operación es en realidad un cuello de botella de rendimiento significativo, entonces es probable que desee la opción más eficiente, incluso a costa de un poco de claridad. Si esto parece exagerado, entonces sospecho que habilitar la enumeración concurrente realmente no afectará demasiado tu rendimiento.