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

Question

这个问题是关于同一个程序我previously asked about .回顾一下，我有一个具有如下循环结构的程序:

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_histogram s 最后在主线程中相加。

奇怪的是:当我仅用 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

附言我知道有些库正是为这种事情而设计的，它们可能会具有更好的性能，但这就是我的最后一个问题，所以我不需要再次听到这些建议。 (另外，我想使用 pthreads 作为学习经验。)

Answer 1

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

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

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

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