使用dispatch_group_async的并发代码的性能比单线程版本慢得多

最近我一直在做大量的随机数生成“正态分布”钟形曲线的实验。

方法很简单：

• 创build一个整数数组并将其归零。 （我使用2001整数）
• 重复计算该数组中的索引，并将该数组中的条目编入索引，如下所示
  • 循环999或1000次。 在每次迭代中：
    • 以中心值（1000）为数组索引
    • 生成一个随机数= + 1 / -1。 并将其添加到数组索引
    • 在循环结束时，在计算的数组索引处增加值。

由于随机值0/1倾向于频繁出现，因此上面内部循环的结束索引值倾向于保持接近中心值。 比起始值大得多/小得多的指标值越来越不寻常。

在大量重复之后，数组中的值呈现正态分布钟形曲线的形状。 然而，我使用的高质量的随机函数arc4random_uniform（）相当慢，并且需要很多迭代才能生成平滑的曲线。

我想计划10亿（十亿）点。 在主线程上运行，大约需要16个小时。

我决定重写计算代码来使用dispatch_async，并在我的8核心Mac Pro上运行它。

我结束了使用dispatch_group_async（）提交8个块，dispatch_group_notify（）在所有块完成处理时通知程序。

为了简化第一遍，所有8个块写入相同的NSUInteger数组。 在读取/修改写入数组条目时，出现竞争条件的可能性很小，但是在这种情况下，这只会导致一个值丢失。 我正打算在稍后添加一个锁到数组增量（或者甚至可以在每个块中创build单独的数组，然后将它们相加）。

无论如何，我重构代码使用dispatch_group_async（）并计算每个块中的总值的1/8，并设置我的代码运行。 对我来说，并发代码尽pipe最大化了我Mac上的所有内核，但运行速度比单线程代码慢。

单线程运行时，每秒可以得到大约17,800个点。 当使用dispatch_group_async运行时，性能下降到更像665点/秒，或约1/26的速度 。 我已经改变了我提交的块数 – 2,4或8，没关系。 性能是可怕的。 我也尝试使用dispatch_async提交所有8个块，没有dispatch_group。 这也没有关系。

目前没有阻塞/locking正在进行：所有块全速运行。 对于为什么并发代码运行速度慢，我感到十分困惑。

现在的代码有点混乱，因为我重构了它的单线程或同时工作，所以我可以testing。

以下是运行计算的代码：

randCount = 2; #define K_USE_ASYNC 1 #if K_USE_ASYNC dispatch_queue_t highQ = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0); //dispatch_group_async dispatch_group_t aGroup = dispatch_group_create(); int totalJobs = 8; for (int i = 0; i<totalJobs; i++) { dispatch_group_async(aGroup, highQ, ^{ [self calculateNArrayPoints: KNumberOfEntries /totalJobs usingRandCount: randCount]; }); } dispatch_group_notify(aGroup, dispatch_get_main_queue(), allTasksDoneBlock ); #else [self calculateNArrayPoints: KNumberOfEntries usingRandCount: randCount]; allTasksDoneBlock(); #endif 

以及单线程和并发版本都使用的常用计算方法：

 + (void) calculateNArrayPoints: (NSInteger) pointCount usingRandCount: (int) randCount; { int entry; int random_index; for (entry =0; entry<pointCount; entry++) { static int processed = 0; if (entry != 0 && entry%100000 == 0) { [self addTotTotalProcessed: processed]; processed = 0; } //Start with a value of 1000 (center value) int value = 0; //For each entry, add +/- 1 to the value 1000 times. int limit = KPinCount; if (randCount==2) if (arc4random_uniform(2) !=0) limit--; for (random_index = 0; random_index<limit; random_index++) { int random_value = arc4random_uniform(randCount); /* if 0, value-- if 1, no change if 2, value++ */ if (random_value == 0) value--; else if (random_value == randCount-1) value++; } value += 1000; _bellCurveData[value] += 1; //printf("\n\nfinal value = %d\n", value); processed++; } } 

这是一个快速而肮脏的学习项目。 它可以在Mac和iOS上运行，因此它使用共享实用程序类。 实用程序类是什么，但类方法。 没有创build实用程序方法的实例。 它有一个令人尴尬的全局variables。 如果我最终做了一些有用的代码，我将重构它来创build一个实用程序单例，并将所有全局variables转换为单例中的实例variables。

现在，它的工作原理，可怕的全球使用不影响结果，所以我要离开它。

使用“已处理”variables的代码只是计算在并发模式下运行时计算了多less个点的方法。 在发现并发版本的可怕performance之后，我添加了这个代码，所以我相信这不是放缓的原因。

我被困在这里 我写了大量的并发代码，这个任务是一个“ 令人尴尬的并行 ”问题，所以没有理由不应该在所有可用的内核上运行。

其他人是否看到任何可能导致这种情况的事情，或者是否有其他见解提供？

Answer 1

arc4random在修改状态时使用临界区域。 关键部分在非竞争情况下（当从未locking状态变为locking状态时）是超快的，但在争用的情况下（当试图locking已经locking的互斥体时），必须调用操作系统并将线程睡眠，这大大降低了性能。

 u_int32_t arc4random() { u_int32_t rnd; THREAD_LOCK(); arc4_check_init(); arc4_check_stir(); rnd = arc4_getword(&rs); THREAD_UNLOCK(); return (rnd); } 

THREAD_LOCK()被定义为

 #define THREAD_LOCK() \ do { \ if (__isthreaded) \ _pthread_mutex_lock(&arc4random_mtx); \ } while (0) 

来源： OpenBSD的Arc4随机数生成器

使其更快

您可以创build一个Arc4Random类，它是arc4random.c中静态arc4_ *函数的一个包装。 然后你有一个不再是线程安全的随机数生成器，但是你可以为每个线程创build一个生成器。

Answer 2

这是猜测，所以我不能以某种方式确认它，而不实际分析代码（因为它）。

也就是说， arc4random通过苹果的源代码集合来locking每个调用。 因为你在multithreading中使用arc4random_uniform ，所以你至less要调用一次，如果不是多次的话。 所以我最好猜测的是，每个任务都在等待所有其他任务对arc4random_uniform的调用（或者如果多个调用并行启动，并且需要对arc4random进行多次调用， arc4random可能继续等待自身）。

解决这个问题的最简单的方法可能是简单地将现有的arc4random.c源代码拉下来，并修改它，使其包装在一个类中，同时删除同步（正如我在聊天中所build议的那样，或者如Michael所build议的），或者利用线程本地存储（这可以解决线程安全问题，但可能同样缓慢 – 没有尝试过自己，所以盐山）。 请记住，如果你去任一路线，你将需要一个替代scheme来访问iOS上的/dev/random 。 在这种情况下，我build议使用SecRandomCopyBytes ，因为它应该产生与从/dev/random自己读取一样好的结果。

所以，当我非常确定这是arc4random ，我不能肯定地说没有分析，因为甚至在arc4random开始做它的事情之前可能会有其他事情导致性能问题。

Answer 3

好的，谢谢迈克尔和诺埃尔的深思。

实际上，arc4random（）和arc4random_uniform（）使用spin_lock的变体，在multithreading的使用中性能是可怕的。

在有很多冲突的情况下，自旋锁是一个非常不好的select，因为旋转锁会导致线程阻塞，直到锁释放，从而捆绑该内核。

理想的做法是创build我自己的arc4random版本，在实例variables中维护自己的状态数组，并且不是线程安全的，可能是最好的解决scheme。 然后，我会重构我的应用程序，为每个线程创build一个单独的我的随机生成器的实例。

但是，这是我自己研究的一个侧面项目。 如果我没有得到报酬，这比我准备花费更多的努力。

作为一个实验，我用rand（）replace了代码，而单线程的情况要快得多，因为rand（）是一个更简单，更快的algorithm。 随机数也不是很好。 从我读过的，rand（）在循环模式的低位有问题，所以不是使用典型的rand（）％2，而是使用rand（）％0x4000来代替使用第二个到最高的顺序而不是。

但是，当我尝试在我的multithreading代码中使用rand（）时，性能仍然显着下降。 它也必须在内部使用locking。

然后，我切换到rand_r（），它将一个指针指向一个种子值，假设由于它是无状态的，它可能不使用locking。

答对了。 我现在可以在我的8核Mac Pro上运行415,674点/秒。