objective-c - 并行reduce算法实现

Question

我一直在研究使用 block 在 Objective-C 中实现 reduce [inject, fold, whatever you want to call it] 函数，并且想知道是否有任何技术可以并行化应用函数的计算 关联(例如，整数集合的总和)？

即是否有可能在 NSArray 上并行化或改进类似的东西:

- (id)reduceWithBlock:(id (^)(id memo, id obj))block andAccumulator:(id)accumulator
{
  id acc = [[accumulator copy] autorelease];

  for (id obj in self) {
    acc = block(acc, obj);
  }
  return acc;
}

使用大中央调度？

编辑:我做了第二次尝试，将数组分成更小的 block 并在单独的调度队列中减少它们，但在我的测试中没有明显的性能提升:(gist here)

Answer 1

您可以使用 dispatch_apply使用 Dispatch Global Queue 对其进行并行化，但您的代码似乎并发工作效率不高。因为accumulator对象需要独占访问，并且被block紧紧使用，所以会造成accumulator对象的巨型锁。

例如，即使将 dispatch_apply 与 Dispatch Global Queue 一起使用，此代码也几乎是非并发工作。

dispatch_semaphore_t sema = dispatch_semaphore_create(1);
dispatch_queue_t queue =
    dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
dispatch_apply([array count], queue, ^(size_t index) {
    dispatch_semaphore_wait(sema, DISPATCH_TIME_FOREVER);
    acc = block(acc, [array objectAtIndex:index]);
    dispatch_semaphore_signal(sema);
});
dispatch_release(sema);

您需要拆分块和累加器实现以实现高效并行化。

已编辑:

(我没有检查你代码的算法。)

dispatch_queue_t result_queue = dispatch_queue_create(NULL, NULL);

您正在使用串行队列。串行队列一次执行一个 block 。因此，它可能是

dispatch_queue_t result_queue =
    dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);

或

dispatch_queue_t result_queue = dispatch_queue_create(NULL, DISPATCH_QUEUE_CONCURRENT);
/* DISPATCH_QUEUE_CONCURRENT is only available OS X 10.7/iOS 4.3 or later. */