Objective-c: проблемы с блоками и NSEnumerationConcurrent - PullRequest
Новая
       21

Objective-c: проблемы с блоками и NSEnumerationConcurrent

5 голосов
/ 02 мая 2011

У меня есть словарь, содержащий второй словарь с 1000 записями.Все записи являются NSStrings типа ключ = key XXX, а значение = element XXX, где XXX - это число между 0 - количество элементов - 1. (Несколько дней назад я спрашивал о словарях Objective-C, содержащихсловарь. Пожалуйста, обратитесь к этому вопросу , если вам нужен код, который создает словарь.)

Общая общая длина всех строк в под-словаре составляет 28 670 символов.то есть: 

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

Рассмотрим это очень простое хеш-значение в качестве индикатора, если метод перечислил каждую пару ключ + значение один раз и только один раз.

У меня есть одна подпрограмма, которая прекрасно работает (используя блоки) для доступа к отдельному ключу словаря и значениям: 

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

Если я попробую то же самое, используя параллельные блоки (на многопроцессорной машине), я получу число, близкое, но не совсем ожидаемое 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...

Документы Apple для NSEnumerationConcurrent состояния: 

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

Я думаю, что это, вероятно, проблема, но в чем проблема с моим кодом или блоком в KVC_access4что не безопасно для одновременного вызова?

Редактирование и заключение

Благодаря превосходному решению Б.Дж. Гомера, я получил работу NSEnumerationConcurrent.Я тщательно рассчитал оба метода.Код, приведенный выше в KVC_access3, быстрее и проще для небольших и средних словарей.Это намного быстрее на многих словарях.Однако, если у вас есть большой словарь mongo (миллионы или десятки миллионов пар ключ / значение), тогда этот код: 

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

        OSAtomicAdd64Barrier(workingLength, &ll); 
 }];

в 4 раза быстрее.Точка пересечения для размера составляет около 1 словаря из 100 000 моих тестовых элементов.Больше словарей и эта точка пересечения, вероятно, выше из-за времени настройки.

1 Ответ

13 голосов
/ 02 мая 2011

При одновременном перечислении блок будет запущен одновременно в нескольких потоках. Это означает, что несколько потоков обращаются к ll одновременно. Поскольку у вас нет синхронизации, вы склонны к условиям гонки.

Это проблема, потому что операция += не является атомарной операцией. Помните, что ll += x - это то же самое, что и ll = ll + x. Это включает чтение ll, добавление x к этому значению, а затем сохранение нового значения обратно в ll. В промежутке между считыванием ll в потоке X и его сохранением любые изменения, вызванные другими потоками, будут потеряны, когда поток X вернется к сохранению своих вычислений.

Вам необходимо добавить синхронизацию, чтобы несколько потоков не могли изменять значение одновременно. Наивное решение таково: 

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

Однако это исключает все преимущества, которые вы получаете от параллельного перечисления, так как все тело блока теперь заключено в синхронизированный блок - фактически только один экземпляр этого блока будет фактически работать одновременно.

Если параллелизм на самом деле является существенным требованием к производительности, я бы предложил следующее: 

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

Обратите внимание, что я использую OSAtomicAdd64Barrier, довольно низкоуровневую функцию, которая гарантированно увеличивает значение атомарно. Вы также можете использовать @synchronized для контроля доступа, но если эта операция на самом деле является существенным узким местом для производительности, то вам, вероятно, понадобится наиболее эффективный вариант, даже за счет некоторой ясности. Если это кажется излишним, то я подозреваю, что включение одновременного перечисления не сильно повлияет на вашу производительность.

...