使用更多线程时,什么可以使程序运行得更慢？

这个问题与我之前询问的程序有关.回顾一下,我有一个循环结构的程序,如下所示:

for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1;

bin_index 对于这个问题而言,它是一个完全确定性的函数,它不会使用或改变任何共享状态 - 换句话说,它显然是可重入的.

我首先编写了这个程序来使用单个线程.然后我将它转换为使用多个线程,这样线程就n可以运行外部循环的所有迭代i1 % nthreads == n.所以在每个线程中运行的函数看起来像

for (int i1 = n; i1 < N; i1 += nthreads)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        thread_local_histogram[bin_index(i1, i2, i3, i4)] += 1;

并且最后将所有thread_local_histograms添加到主线程中.

这是奇怪的事情:当我用一个线程运行程序进行某些特定大小的计算时,大约需要6秒钟.当我使用2或3个线程运行它,执行完全相同的计算时,大约需要9秒.这是为什么？我希望使用2个线程比1个线程更快,因为我有一个双核CPU.该程序不使用任何互斥锁或其他同步原语,因此两个线程应该能够并行运行.

供参考:time一个线程的典型输出(这是在Linux上):

real    0m5.968s
user    0m5.856s
sys     0m0.064s

和两个线程:

real    0m9.128s
user    0m10.129s
sys     0m6.576s

代码位于http://static.ellipsix.net/ext-tmp/distintegral.ccs

PS我知道有一些图书馆专门设计用于这种可能有更好性能的东西,但这就是我的最后一个问题,所以我不需要再次听到这些建议.(另外我想用pthreads作为学习经验.)

为了避免对此有进一步的评论:当我写回复时,提问者还没有发布到他的来源的链接,所以我无法定制我对他的具体问题的回复.我只回答了一般问题"可以"导致这样的问题,我从未说过这一点必然适用于他的案子.当他发布一个链接到他的来源时,我写了另一个回复,这正是只关注他的问题(这是由于我在其他回复中解释的使用random()函数引起的).但是,由于这篇文章的问题仍然是"在使用更多线程时,什么可以使程序运行得更慢？" 而不是"是什么让我非常具体的应用程序运行得慢？",我认为没有必要改变我的相当一般的答复(一般问题 - >一般回答,具体问题 - >具体回答).

1)缓存中毒
所有线程都访问同一个数组,这是一个内存块.每个核心都有自己的缓存来加速内存访问.由于它们不只是从数组中读取而且还更改内容,因此内容实际上仅在缓存中更改,而不是在实际内存中更改(至少不是立即更改).问题是另一个核心上的另一个线程可能有缓存的内存重叠部分.如果现在核心1更改了缓存中的值,则必须告知核心2该值刚刚更改.它通过使核心2上的缓存内容无效来实现,核心2需要重新读取内存中的数据,这会减慢处理速度.缓存中毒只能在多核或多CPU机器上发生.如果你只有一个带有一个内核的CPU,这没问题.所以要弄清楚这是不是你的问题,只需禁用一个核心(大多数操作系统允许你这样做)并重复测试.如果现在几乎同样快,那就是你的问题.

2)防止内存突发
如果以突发顺序读取,则读取内存最快,就像从HD读取文件一样.解决内存中的某个点实际上非常慢(就像HD上的"寻道时间"),即使您的PC拥有市场上最好的内存.但是,一旦解决了这一问题,顺序读取就会很快.第一次寻址是通过发送行索引和列索引,并且在访问第一个数据之前始终具有等待时间.一旦这些数据存在,CPU就会开始爆发.虽然数据仍在发送,但它已经发送了下一次突发的请求.只要它保持突发(通过始终发送"请求下一行"请求),RAM将继续尽可能快地抽出数据(这实际上非常快!).只有在按顺序读取数据且仅在内存地址向上增长时(AFAIK,您不能从高地址突发到低地址),突发才有效.如果现在两个线程同时运行并且都保持读/写内存,但是两者都来自完全不同的内存地址,每次线程2需要读/写数据时,它必须中断线程1的可能突发,反之亦然.如果您有更多线程,这个问题会变得更糟,这个问题在只有一个单核CPU的系统上也是一个问题.它必须中断线程1的可能突发,反之亦然.如果您有更多线程,这个问题会变得更糟,这个问题在只有一个单核CPU的系统上也是一个问题.它必须中断线程1的可能突发,反之亦然.如果您有更多线程,这个问题会变得更糟,这个问题在只有一个单核CPU的系统上也是一个问题.

BTW运行比你拥有的核心更多的线程永远不会让你的进程更快(正如你提到的3个线程),它会慢下来(线程上下文切换有副作用,降低处理吞吐量) - 这与你运行更多的线程不同,因为某些线程正在休眠或阻塞某些事件,因此无法主动处理任何数据.在这种情况下,运行比核心更多的线程可能是有意义的.

到目前为止我在其他回复中说的所有内容在一般情况下都是正确的,因为你的问题是什么"可以"...但是现在我已经看到了你的实际代码,我的第一个赌注就是你对random的使用()功能会减慢一切.为什么？

请参阅随机在内存中保存一个全局变量,用于存储在那里计算的最后一个随机值.每次调用random()(并且在单个函数中调用它两次)时,它会读取此全局变量的值,执行计算(不是那么快;单独的random()是一个慢函数)并写入在返回之前返回那里.这个全局变量不是每个线程,它在所有线程之间共享.所以我写的有关缓存中毒的内容始终适用于此(即使你通过每个线程分离数组来避免数组;这对你来说非常聪明!).此值在任一核心的高速缓存中始终无效,必须从内存中重新获取.但是,如果你只有一个线程,就不会发生这样的事情,这个变量在最初读取之后永远不会离开缓存,因为它'

更糟糕的是,glibc有一个线程安全版本的random() - 我只是通过查看源代码来验证.虽然这在实践中似乎是一个好主意,但这意味着每次random()调用都会导致锁定互斥锁,访问内存以及解锁互斥锁.因此,在完全相同的时刻调用随机的两个线程将导致一个线程被阻塞几个CPU周期.但这是特定于实现的,因为AFAIK不要求random()是线程安全的.大多数标准的lib函数不需要是线程安全的,因为C标准首先不知道线程的概念.当他们没有在同一时刻调用它时,互斥锁对速度没有影响(因为即使是单个线程应用程序也必须锁定/解锁互斥锁),但是再次应用缓存中毒.

您可以为每个线程预先构建一个包含随机数的数组,其中包含每个线程所需的随机数.在生成线程之前在主线程中创建它,并将其引用添加到您移交给每个线程的结构指针.然后从那里得到随机数.

或者只是实现你自己的随机数生成器,如果你不需要地球上的"最佳"随机数,它与每线程内存一起用于保持其状态 - 一个可能比系统的内置生成器更快.

如果只有Linux解决方案适合您,您可以使用random_r.它允许您在每次调用时传递状态.只需为每个线程使用唯一的状态对象.但是这个函数是一个glibc扩展,它很可能不被其他平台支持(既不是C标准的一部分也不是POSIX标准的A​​FAIK--例如,Mac OS X上不存在此功能,它可能既不存在于Solaris中,也不存在于Solaris或FreeBSD的).

创建一个自己的随机数生成器实际上并不那么难.如果你需要真正的随机数,你不应该首先使用random().随机只创建伪随机数(看起来随机的数字,但如果你知道发生器的内部状态,则可以预测).这是产生良好uint32随机数的代码:

static uint32_t getRandom(uint32_t * m_z, uint32_t * m_w)
{
    *m_z = 36969 * (*m_z & 65535) + (*m_z >> 16);
    *m_w = 18000 * (*m_w & 65535) + (*m_w >> 16);
    return (*m_z << 16) + *m_w;
}

以某种方式以适当的方式"播种"m_z和m_w很重要,否则结果根本不是随机的.种子值本身应该已经是随机的,但在这里你可以使用系统随机数生成器.

uint32_t m_z = random();
uint32_t m_w = random();
uint32_t nextRandom;

for (...) {
    nextRandom = getRandom(&m_z, &m_w);
    // ...
}

这样每个线程只需要调用random()两次,然后使用自己的生成器.顺便说一句,如果你需要双重randoms(介于0和1之间),上面的函数可以很容易地包装:

static double getRandomDouble(uint32_t * m_z, uint32_t * m_w)
{
    // The magic number below is 1/(2^32 + 2).
    // The result is strictly between 0 and 1.
    return (getRandom(m_z, m_w) + 1) * 2.328306435454494e-10;
}

尝试在代码中进行此更改,并让我知道基准测试结果如何:-)