为什么 N 个独立计算在 N 个线程上没有快 N 倍？

Question

我有一个 N 核处理器（在我的例子中是 4 个）。为什么 N 个线程上的 N 个完全独立的函数调用不是快 N 倍左右（当然创建线程会产生开销，但请进一步阅读）？

看下面的代码：

namespace ch = std::chrono;
namespace mp = boost::multiprecision;
constexpr static unsigned long long int num = 3555;

// mp_factorial uses boost/multiprecision/cpp_int, so I get legit results

    ch::steady_clock::time_point s1 = ch::steady_clock::now();
    auto fu1 = std::async(std::launch::async, mp_factorial, num);
    auto fu2 = std::async(std::launch::async, mp_factorial, num);
    auto fu3 = std::async(std::launch::async, mp_factorial, num);
    auto fu4 = std::async(std::launch::async, mp_factorial, num);
    fu1.get(); fu2.get(); fu3.get(); fu4.get();
    ch::steady_clock::time_point e1 = ch::steady_clock::now();

    ch::steady_clock::time_point s2 = ch::steady_clock::now();
    mp_factorial(num);
    mp_factorial(num);
    mp_factorial(num);
    mp_factorial(num);
    ch::steady_clock::time_point e2 = ch::steady_clock::now();

    auto t1 = ch::duration_cast<ch::microseconds>(e1 - s1).count();
    auto t2 = ch::duration_cast<ch::microseconds>(e2 - s2).count();

    cout << t1 << " " << t2 << endl;

我得到的结果如下：

11756 20317

大约快 2 倍。我也用大量数字尝试过这个，比如 num = 355555。我得到了非常相似的结果：

177462588 346575062

为什么会这样？ 我完全了解阿姆达尔定律，多核处理器并不总是快 number_of_cores 倍，但是当我有独立操作，我期待更好的结果。至少接近 number_of_cores.

更新：

如您所见，所有线程都按预期工作，所以这不是问题所在：

Answer 1

这里的问题是你肯定有一些大的块状数字，它们不适合你的处理器的 L1 和 L2 缓存，这意味着处理器坐着并转动它的小 ALU 手指，而内存控制器正在跳跃所有在尝试为每个处理器读取一点内存的地方。

当您运行在一个线程中时，该线程至少在很大程度上只在三个不同的内存区域上工作（a = b * c，从 b 和 c, 写入 a).

当你执行 4 个线程时，你有四个不同的 a = b * c;，每个线程有三个不同的数据流，导致缓存、内存控制器和 "open pages" [这里的页面是DRAM 术语，与 MMU 页面无关，但您可能还会发现 TLB 未命中也是一个因素]。

因此，您可以通过运行更多线程获得更好的性能，但不是 4 倍，因为每个线程消耗和产生大量数据，内存接口是瓶颈。除了让机器具有更高效的内存接口 [这可能不是那么容易]，您对此无能为力 - 只需接受对于这种特殊情况，内存比计算更多的限制因素。

使用多线程解决问题的理想示例是那些需要大量计算但不会占用太多内存的问题。我有一个简单的素数计算器和一个计算 "weird numbers" 的素数计算器，当运行在 N 核上时，两者几乎都提供了 Nx 性能改进 [但是我会开始将它们用于比 64 大很多倍的数字吗？位，它将停止提供相同的好处]

编辑：还有可能：

您的代码经常调用的一些函数是 locking/blocking 其他线程 [如果实现需要较短的等待时间，则可能以忙等待的方式调用 OS 等待几十个时钟周期是没有意义的] - new 和 malloc 之类的东西以及它们的释放对应物是合理的候选者。
错误共享为真 - 数据在 CPU 核心之间共享，导致缓存内容在处理器之间来回发送。从每个线程访问 [和更新] 的特别小的共享数组可能会导致此错误，即使更新是无锁地和原子操作完成的。

当你有这样的东西时，就用到了"false"分享这个词

 // Some global array. 
 int array[MAX_THREADS];
 ....
 // some function that updates the global array
 int my_id = thread_id();
 array[my_id]++;

虽然每个线程都有自己的数组条目，但同一个缓存行会从一个 CPU 跳转到另一个。我曾经有一个 SMP（在多核之前）dhrystone 基准测试，当运行在 2 个处理器上运行时，运行是一个处理器性能的 0.7 倍 - 因为经常访问的数据项之一被存储为一个 int array[MAX_THREADS]。这当然是一个比较极端的例子...

Answer 2

您的答案在某种程度上取决于用户线程或内核线程。如果您正在使用的线程是在用户 space 中实现的，则内核不知道它们，因此它们无法以真正的 "parallel" 方式跨多个物理 cpu 内核执行。

如果线程是在内核中实现的 space，那么内核会知道线程，并且可以跨多个物理 cpu 内核以并行方式处理它们。

还有线程创建、销毁和上下文切换的开销。每次线程上下文切换时，线程库都需要存储值和加载值等

为什么 N 个独立计算在 N 个线程上没有快 N 倍？

Why isn't N independent calculations N times faster on N threads?

c++

multithreading

multicore

cpu-cores

parallelism-amdahl