multithreading - 使用更多线程时，什么会使程序运行速度变慢？

Question

这个问题是关于我之前问过的同一个程序。回顾一下，我有一个具有如下循环结构的程序：

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运行外部循环 where 的所有迭代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 都在最后添加到主线程中。

奇怪的是：当我只用 1 个线程运行程序以进行某些特定大小的计算时，大约需要 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 作为学习经验。）

score 13 · Accepted Answer

为避免对此发表进一步评论：当我写回复时，发问者尚未发布指向其来源的链接，因此我无法针对他的具体问题调整我的回复。我只是在回答一般问题是什么“可以”导致这样的问题，我从未说过这必然适用于他的情况。当他发布了指向他的来源的链接时，我写了另一个回复，这完全是针对他的问题（这是由我在另一个回复中解释的 random() 函数的使用引起的）。但是，由于这篇文章的问题仍然是“使用更多线程时，什么会使程序运行速度变慢？” 而不是“是什么让我的非常具体的应用程序运行得更慢？”，我认为没有必要更改我相当笼统的回复（一般问题 -> 一般回复，具体问题 -> 具体回复）。

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

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

顺便说一句，运行的线程数多于内核数永远不会使您的进程更快（正如您提到的 3 个线程），它反而会减慢它的速度（线程上下文切换具有降低处理吞吐量的副作用） - 这与您运行更多线程不同，因为某些线程在某些事件上处于休眠或阻塞状态，因此无法主动处理任何数据。在这种情况下，运行比核心更多的线程可能是有意义的。

score 5 · Accepted Answer

到目前为止，我在其他答复中所说的一切仍然普遍适用，因为您的问题是“可以”...但是现在我已经看到了您的实际代码，我的第一个赌注是您对 random() 的使用功能减慢一切。为什么？

看，random 在内存中保存了一个全局变量，该变量存储了在那里计算的最后一个随机值。每次你调用 random() （并且你在一个函数中调用它两次）它读取这个全局变量的值，执行计算（不是那么快；random() 单独是一个慢函数）并写入在返回之前返回那里。这个全局变量不是每个线程的，它在所有线程之间共享。所以我写的关于缓存中毒的内容一直都适用于这里（即使你通过为每个线程设置单独的数组来避免数组中毒；这真是太聪明了！）。该值在任一内核的缓存中不断失效，必须从内存中重新获取。但是，如果您只有一个线程，则不会发生类似的情况，此变量在最初读取后永远不会离开缓存，因为它'

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

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

或者，如果您不需要地球上“最好的”随机数，则只需实现您自己的随机数生成器，该随机数与每个线程内存一起工作以保持其状态 - 这可能比系统的内置生成器更快。

如果仅适用于 Linux 的解决方案适合您，则可以使用random_r。它允许您在每次调用时传递状态。只需为每个线程使用一个唯一的状态对象。然而这个函数是一个 glibc 扩展，它很可能不被其他平台支持（C 标准和 POSIX 标准 AFAIK 都不支持 - 例如，这个函数在 Mac OS X 上不存在，它可能不存在于 Solaris 或自由BSD）。

创建自己的随机数生成器实际上并不难。如果您需要真正的随机数，则不应首先使用 random() 。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() 两次，然后使用你自己的生成器。顺便说一句，如果您需要双随机数（介于 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;
}

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

score 2 · Accepted Answer

您正在看到缓存行弹跳。由于直方图桶上的竞争条件，您没有得到错误的结果，我真的很惊讶。

score 1 · Accepted Answer

一种可能性是创建线程所花费的时间超过了使用线程所节省的时间。如果 O(n^4) 操作的经过时间仅为 6 秒，我认为 N 不是很大。

也不能保证多个线程将在不同的内核或 CPU 上运行。我不确定 Linux 的默认线程亲和性是什么——可能两个线程都运行在一个内核上，这会抵消 CPU 密集型代码的好处，例如这样。

本文详细介绍了默认线程亲和性以及如何更改代码以确保线程在特定内核上运行。

score 1 · Accepted Answer

即使线程不会同时访问数组的相同元素，整个数组也可能位于几个内存页中。当一个核心/处理器写入该页面时，它必须使所有其他处理器的缓存无效。

避免让许多线程在相同的内存空间上工作。为每个线程分配单独的数据以进行处理，然后在计算完成时将它们连接在一起。

score 1 · Accepted Answer

在我的头顶上：

上下文切换
资源争用
CPU 争用（如果它们没有被拆分为多个 CPU）。
缓存抖动

score 0 · Accepted Answer

大卫，

你确定你运行一个支持多处理器的内核吗？如果您的系统中只使用一个处理器，则产生额外的 CPU 密集型线程会减慢您的程序。

And, are you sure support for threads in your system actually utilizes multiple processors? Does top, for example, show that both cores in your processor utilized when you run your program?

multithreading - 使用更多线程时，什么会使程序运行速度变慢？

7 回答 7

Related

Reference