多线程不会提高递归c ++程序的性能

Question

考虑这个递归的多线程程序:

#include <iostream>
#include <thread>

#define NUMTHREADS 4
using namespace std;

int g[NUMTHREADS];

thread t[NUMTHREADS];

void task1(int x)
{
    if(x+1<NUMTHREADS)
        t[x] = thread(task1, x+1);
    for(int i=0;i<100000000;i++)
        g[x]++;
    if(x+1<NUMTHREADS)
        t[x].join();
}

int main()
{
    task1(0);
    for(int i=0;i<NUMTHREADS;i++)
        cout<<g[i]<<" ";
}

我期望线程开销是微不足道的,但事实上程序的运行时间随着线程数的增加呈线性增长.

这是我的6核cpu的一些时间:

NUMTHREADS = 1:

$ time ./a
100000000
real    0m0.330s
user    0m0.312s
sys     0m0.015s

NUMTHREADS = 2:

$ time ./a
100000000 100000000
real    0m0.742s
user    0m1.404s
sys     0m0.015s

NUMTHREADS = 3:

$ time ./a
100000000 100000000 100000000
real    0m1.038s
user    0m2.792s
sys     0m0.000s

NUMTHREADS = 4:

$ time ./a
100000000 100000000 100000000 100000000
real    0m1.511s
user    0m5.616s
sys     0m0.015s

知道为什么会这样吗？

Answer 1

由于在访问元素时出现错误共享的极端情况,因此正在序列化线程程序的执行g.以下是程序的修改版本,它可以避免错误共享,并且可以使用不同数量的线程运行相同的时间,只要每个线程可以分配给不同的CPU核心:

#include <iostream>
#include <thread>

#define NUMTHREADS 4
using namespace std;

int g[NUMTHREADS*16];

thread t[NUMTHREADS];

void task1(int x)
{
    if(x+1<NUMTHREADS)
        t[x] = thread(task1, x+1);
    for(int i=0;i<100000000;i++)
        g[x*16]++;
    if(x+1<NUMTHREADS)
        t[x].join();
}

int main()
{
    task1(0);
    for(int i=0;i<NUMTHREADS;i++)
        cout<<g[i*16]<<" ";
}

运行时间为1和4个线程:

$ time ./a.out
100000000
./a.out  0.45s user 0.01s system 98% cpu 0.466 total
                                         ^^^^^^^^^^^
$ time ./a.out
100000000 100000000 100000000 100000000
./a.out  1.52s user 0.01s system 329% cpu 0.462 total
                                          ^^^^^^^^^^^

以下是对所发生情况的简短解释.现代x86 CPU以64字节为单位访问主存储器,称为高速缓存行(除非使用非时间存储或加载指令,但这不是这种情况).该大小的单个缓存行最多可容纳16个int数组元素:

|    single cache line      |  another cache line
|------+------+-----+-------|-------+-------+------
| g[0] | g[1] | ... | g[15] | g[16] | g[17] | ...
+------+------+-----+-------+-------+-------+------
    ^      ^
    |      |
    |      +------ thread 1 updates this element
    |
    +------------- thread 0 updates this element

x86是一种缓存一致的体系结构,这意味着当在单个内核中修改缓存行时,其他内核会被告知其相同缓存行的副本不再有效,必须从上层内存存储重新加载,例如共享L3缓存或主存储器.由于共享的最后一级缓存和主内存都比每个内核的私有缓存慢得多,这导致执行速度慢得多.

修改后的版本将索引乘以g16:

|     one cache line        |  another cache line
|------+------+-----+-------|-------+-------+------
| g[0] | g[1] | ... | g[15] | g[16] | g[17] | ...
+------+------+-----+-------+-------+-------+------
    ^                           ^
    |                           |
    |                           +------ thread 1 updates this element
    |
    +------------- thread 0 updates this element

现在很清楚,没有两个线程共享相同的高速缓存线,因此高速缓存一致性协议不参与该过程.

使用堆栈变量时可以获得相同的效果.线程堆栈通常很大(至少几个KiB)并在内存页边框上对齐,因此不同线程中的堆栈变量永远不会共享同一个缓存行.编译器还进一步优化了对堆栈变量的访问.

请参阅此答案以获得更详尽的解释和另一种防止错误共享的方法.虽然它与OpenMP有关,但这些概念也适用于您的案例.