将工作分配给更多线程需要更多时间，为什么？

我有一个小的 C 程序可以计算pi用一个蒙特卡洛 http://en.wikipedia.org/wiki/Monte_Carlo_method#Introduction-模拟基本上只是测试随机点 [x,y] 是否在圆内部或外部。

近似pi我必须使用大量样本n其复杂度成正比O(n)。所以试图计算大量的样本n，我实现了POSIX 线程 http://en.wikipedia.org/wiki/POSIX_Threadsapi 来并行化计算能力。

我的代码如下所示：

pthread_t worker[nthreads]; /* creates workers for each thread */
struct param aparam[nthreads]; /* struct param{ long* hits; long rounds; }; */
long nrounds = nsamples / nthreads; /* divide samples to subsets of equal rounds per thread */

for (int i = 0; i < nthreads; ++i) { /* loop to create threads */
    aparam[i].hits = 0;
    aparam[i].rounds = nrounds;
    pthread_create(&worker[i], NULL, calc_pi, &aparam[i]); /* calls calc_pi(void* vparam){}  */ 
}

long nhits = 0;
for (int j = 0; j < nthreads; ++j) { /* collects results */
    pthread_join(worker[j], NULL);
    nhits += (long)aparam[j].hits; /* counts hits inside the cicrle */
}

这就是每个线程正在做的事情：

void* calc_pi(void* vparam)
{ /* counts hits inside a circle */
    struct param *iparam;
    iparam = (struct param *) vparam;
    long hits = 0;
    float x, y, z;
    for (long i = 0; i < iparam->rounds; ++i) {
        x = (float)rand()/RAND_MAX;
        y = (float)rand()/RAND_MAX;
        z = x * x + y * y;
        if (z <= 1.f) /* circle radius of 1 */
            ++hits;
    }
    iparam->hits = (long*)hits;
    return NULL;
}

现在我有一个奇怪的观察。使用同一组样本n并且随着线程数量的增加i这个程序需要更多的时间而不是更少的时间.

以下是一些平均运行时间（可重现）：

-------------------------------------------------
| Threads[1] | Samples[1] | Rounds[1] | Time[s] |
-------------------------------------------------
|        32  |  268435456 |   8388608 |    118  |
|        16  |  268435456 |  16777216 |    106  |
|         8  |  268435456 |  33554432 |    125  |
|         4  |  268435456 |  67108864 |    152  |
|         2  |  268435456 | 134217728 |     36  |
|         1  |  268435456 | 268435456 |     15  |
-------------------------------------------------

例如，为什么两个线程执行相同的工作所花费的时间是单个线程的两倍以上？我的假设是两个线程划分工作应该减少至少 50% 的时间。

使用 GCC 4.9.1 和以下标志编译：

gcc -O2 -std=gnu11 -pthread pipa.c -lpthread -o pipa

我的硬件是双 Intel Xeon E5520（2 个处理器，每个 4 核）@ 2.26 GHz，禁用超线程，运行具有 2.6.18 内核的 Scientific Linux。

有任何想法吗？

线程执行的最昂贵的操作是调用rand(). The rand()是一个简单、简单且通常不可 MT 可扩展的函数（因为它保证相同的种子产生相同的序列random数字）。我认为里面的锁rand()正在序列化所有线程。(*)

确认是否是问题的一个简单技巧是在调试器下启动程序，然后多次：暂停它，捕获线程的堆栈跟踪，然后继续。无论堆栈跟踪中最常出现什么，很可能就是瓶颈。

(*) 使它变得更慢的原因是锁争用会导致额外的性能损失。此外，许多线程增加了进程调度和上下文切换的额外开销。