Objective-C：块和NSEnumerationConcurrent的问题

Question

我有一个包含1000个条目的字典，每个条目都是一个包含NSString类型键和值的第二个字典，其中键为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...

NSEnumerationConcurrent的苹果文档中写道：

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

我认为这可能是问题所在，但是我的代码或者KVC_access4中的代码块对于并发调用来说不是安全的，这就是问题所在。

编辑和结论

感谢BJ Homer的优秀解决方案，我成功地使用了NSEnumerationConcurrent。我对两种方法进行了广泛的时间测试。我在KVC_access3中的代码在小型和中型字典中更快、更易于使用。它在许多字典中都更快。然而，如果你有一个非常大的字典（数百万或数千万个键/值对），那么这段代码：

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

        OSAtomicAdd64Barrier(workingLength, &ll); 
 }];

速度提高了4倍。尺寸的交叉点大约在我测试元素的100,000个字典中的1个字典。更多的字典，这个交叉点会更高，可能是因为设置时间。

- dawg

Answer 1

使用并发枚举时，块会同时在多个线程上运行。这意味着多个线程同时访问ll。由于没有同步，您容易遇到竞态条件。

这是一个问题，因为+=操作不是原子操作。记住，ll += x与ll = ll + x是相同的。这涉及读取ll，将x添加到该值中，然后将新值存储回ll。在线程X上读取ll和存储之间，由其他线程引起的任何更改都会在线程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来控制访问，但是如果此操作实际上是一个重要的性能瓶颈，那么您可能需要最具性能的选项，即使以一点清晰度为代价。如果这感觉过于复杂，请考虑启用并发枚举实际上不会对您的性能产生太大影响。

- BJ Homer