Objective-c:块和NSEnumerationConcurrent的问题

Question

我有一个字典,其中包含第二个包含1000个条目的字典.这些条目都是类型为key =的NSStrings key XXX,而value = element XXXwhere 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...

苹果公司的NSEnumerationConcurrent州文件:

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

我认为这可能是问题所在,但是我的代码或块的问题是什么KVC_access4对并发调用不安全？

编辑和结论

感谢BJ Homer的出色解决方案,我得到了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倍.大小的交叉点大约是我的测试元素100,000的字典.更多的字典和交叉点可能更高,可能是因为设置时间.

Answer 1

使用并发枚举,您将在多个线程上同时运行该块.这意味着多个线程同时访问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来控制访问,但如果此操作实际上是一个重要的性能瓶颈,那么您可能需要最高性能的选项,即使是以一点清晰度为代价.如果这感觉有点矫枉过正,那么我怀疑启用并发枚举并不会真正影响你的表现.