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

Question

我最近在使用大量随机数生成"正态分布"钟形曲线时做了一些实验.

方法很简单:

• 创建一个整数数组并将其归零.(我使用的是2001整数)
• 重复计算此数组中的索引并索引该数组中的条目,如下所示
  • 循环999或1000次.在每次迭代时:
    • 使用中心值(1000)对数组索引进行种子设定
    • 生成随机数= + 1/-1.并将其添加到数组索引中
    • 在循环结束时,递增计算的数组索引处的值.

由于随机值0/1倾向于频繁发生,因此来自上方内环的末端索引值倾向于保持接近中心值.比起始值大得多/小的索引值越来越不寻常.

在大量重复之后,阵列中的值呈现正态分布钟形曲线的形状.但是,我使用的高质量随机函数arc4random_uniform()相当慢,并且需要大量迭代才能生成平滑曲线.

我想绘制1,000,000,000(十亿)点.在主线程上运行,大约需要16个小时.

我决定重写计算代码以使用dispatch_async,并在我的8核Mac Pro上运行它.

我最终使用dispatch_group_async()提交了8个块,并使用dispatch_group_notify()在所有块都已完成处理时通知程序.

为了简化第一遍,所有8个块都写入相同的NSUInteger值数组.读取/修改写入其中一个数组条目的可能性很小,但在这种情况下,这只会导致一个值丢失.我打算稍后为数组增量添加一个锁(或者甚至可能在每个块中创建单独的数组,然后在它们之后对它们求和.)

无论如何,我重构了代码以使用dispatch_group_async()并计算每个块中总值的1/8,并将我的代码设置为运行.要我说出befuddlement,并发代码,而它马克塞斯所有我的Mac上的内核,运行MUCH比单线程代码慢.

当在单个线程上运行时,我每秒绘制大约17,800个点.使用dispatch_group_async运行时,性能下降到更接近665点/秒,或大约1/26的速度.我改变了我提交的块数--2,4或8,这没关系.表现很糟糕.我还尝试使用dispatch_async提交所有8个块而没有dispatch_group.这也无关紧要.

目前没有阻塞/锁定:所有块都以全速运行.关于为什么并发代码运行得慢,我完全不知所措.

代码现在有点混乱,因为我重构它可以单线程或同时工作,所以我可以测试.

这是运行计算的代码:

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上运行,因此它使用共享实用程序类.实用程序类只是类方法.没有创建实用程序方法的实例.它有一个令人尴尬的全球变量.如果我最终对代码执行任何有用的操作,我将重构它以创建实用程序单例,并将所有全局变量转换为单例上的实例变量.

就目前而言,它起作用,并且全局的可怕使用不会影响结果,所以我要离开它.

使用"已处理"变量的代码只是确定在并发模式下运行时计算了多少点的一种方法.在我发现并发版本的可怕性能之后我添加了代码,所以我相信它不是导致速度减慢的原因.

我在这里难过.我编写了大量的并发代码,这个任务是一个" 令人尴尬的并行 "问题,因此没有理由不应该在所有可用内核上全面运行.

是否有其他人看到可能导致此问题的任何内容,或者是否有任何其他见解？

Answer 1

arc4random在修改其状态时使用临界区.在非竞争情况下(当从解锁状态变为锁定状态时),关键部分是超快的,但在竞争情况下(当试图锁定已经锁定的互斥锁时),它必须调用操作系统并将线程放入睡觉,这会降低性能.

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随机数生成器

使它更快

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