并行减少算法实现

Question

我一直在研究使用块在Objective-C中使用reduce [inject,fold,无论你想要什么称呼]函数的实现,并且想知道是否存在任何并行化计算的技术,其中所应用的函数是关联的(例如,a的总和)整数集合)？

也就是说,可以在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;
}

使用大中央调度？

编辑:我已经进行了第二次尝试,将数组划分为更小的块并在单独的调度队列中减少它们,但在我的测试中没有明显的性能提升:( 这里的要点)

Answer 1

您可以将dispatch_apply与Dispatch Global Queue一起使用来进行并行化,但是您的代码似乎对并发工作效率不高.因为累加器对象需要独占访问,并且它被块紧密使用,因此它将导致累加器对象的巨大锁定.

例如,即使将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);

您正在使用串行队列.串行队列一次执行一个块.因此,它可能是

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