多线程实现导致性能下降

Question

我用C语言实现了一个小程序，使用蒙特卡洛方法计算圆周率（主要是出于个人兴趣和培训目的）。在实现基本代码结构之后，我添加了一个命令行选项，允许通过线程执行计算。我原以为能够有显著的加速，但结果让我失望了。命令行概述应该很清楚。用于近似圆周率的最终迭代次数是通过命令行传递的-iterations和-threads相乘的结果。将-threads留空会默认为1线程，在主线程中执行。下面的测试总共进行了8000万次迭代。

在Windows 7 64位（Intel Core2Duo机器）上：

使用Cygwin GCC 4.5.3编译：gcc-4 pi.c -o pi.exe -O3

在Ubuntu/Linaro 12.04 (8Core AMD)上：

使用GCC 4.6.3编译：gcc pi.c -lm -lpthread -O3 -o pi

性能

在Windows上，使用线程版本比未线程化版本快几毫秒。说实话，我原以为会有更好的表现。在Linux上，呃！怎么回事？为什么要慢2000%？当然这很大程度上取决于实现方式，所以在这里阐述一下。在命令行参数解析完成并开始计算之后的摘录如下：

    // Begin computation.
    clock_t t_start, t_delta;
    double pi = 0;

    if (args.threads == 1) {
        t_start = clock();
        pi = pi_mc(args.iterations);
        t_delta = clock() - t_start;
    }
    else {
        pthread_t* threads = malloc(sizeof(pthread_t) * args.threads);
        if (!threads) {
            return alloc_failed();
        }

        struct PIThreadData* values = malloc(sizeof(struct PIThreadData) * args.threads);
        if (!values) {
            free(threads);
            return alloc_failed();
        }

        t_start = clock();
        for (i=0; i < args.threads; i++) {
            values[i].iterations = args.iterations;
            values[i].out = 0.0;
            pthread_create(threads + i, NULL, pi_mc_threaded, values + i);
        }
        for (i=0; i < args.threads; i++) {
            pthread_join(threads[i], NULL);
            pi += values[i].out;
        }
        t_delta = clock() - t_start;

        free(threads);
        threads = NULL;
        free(values);
        values = NULL;

        pi /= (double) args.threads;
    }

虽然 pi_mc_threaded() 的实现方式为:

struct PIThreadData {
    int iterations;
    double out;
};

void* pi_mc_threaded(void* ptr) {
    struct PIThreadData* data = ptr;
    data->out = pi_mc(data->iterations);
}

你可以在http://pastebin.com/jptBTgwr找到完整的源代码。

问题

为什么会出现这种情况？为什么在Linux上存在如此巨大的差异？我原本期望计算所需的时间至少是原始时间的3/4。当然，可能是我没有正确使用pthread库。希望能够得到关于在这种情况下正确使用的澄清。

- Niklas R

Answer 1

问题在于，在glibc的实现中，rand()调用了__random()函数。

long int
__random ()
{
  int32_t retval;

  __libc_lock_lock (lock);

  (void) __random_r (&unsafe_state, &retval);

  __libc_lock_unlock (lock);

  return retval;
}

对于实际操作的函数__random_r，必须在每次调用时加锁。

因此，当您有多个线程使用rand()时，几乎每次调用rand()都会使每个线程等待其他线程。直接在每个线程中使用自己的缓冲区使用random_r()应该更快。

- Daniel Fischer

Answer 2

为了比较，我刚刚在Windows Vista上使用Borland C++编译了您的应用程序，并且双线程版本的性能几乎是单线程的两倍。

pi.exe -iterations 20000000 -stats -threads 1
3.141167

Number of iterations:  20000000
Method:                Monte Carlo
Evaluation time:       12.511000 sec
Threads:               Main


pi.exe -iterations 10000000 -stats -threads 2
3.142397

Number of iterations:  20000000
Method:                Monte Carlo
Evaluation time:       6.584000 sec
Threads:               2

该程序是使用线程安全运行时库编译的。如果使用单线程库，两个版本都可以以其线程安全速度的两倍运行。

pi.exe -iterations 20000000 -stats -threads 1
3.141167

Number of iterations:  20000000
Method:                Monte Carlo
Evaluation time:       6.458000 sec
Threads:               Main


pi.exe -iterations 10000000 -stats -threads 2
3.141314

Number of iterations:  20000000
Method:                Monte Carlo
Evaluation time:       3.978000 sec
Threads:               2

所以，两线程版本仍然比单线程库的一线程版本快两倍，但使用线程安全库的一线程版本实际上比两线程版本更快。

看看Borland的rand实现，他们在线程安全实现中使用线程本地存储来存储种子，因此不会像glibc的锁一样对线程代码产生负面影响，但线程安全实现显然比单线程实现慢。

但归根结底，编译器的rand实现可能是两种情况下的主要性能问题。

更新

我刚刚尝试用Borland的rand函数的内联实现替换了您的rand_01调用，并使用本地变量作为种子，结果在两线程情况下始终快两倍。

更新后的代码如下：

#define MULTIPLIER      0x015a4e35L
#define INCREMENT       1

double pi_mc(int iterations) {
    unsigned seed = 1;
    long long inner = 0;
    long long outer = 0;
    int i;
    for (i=0; i < iterations; i++) {
        seed = MULTIPLIER * seed + INCREMENT;
        double x = ((int)(seed >> 16) & 0x7fff) / (double) RAND_MAX;

        seed = MULTIPLIER * seed + INCREMENT;
        double y = ((int)(seed >> 16) & 0x7fff) / (double) RAND_MAX;

        double d = sqrt(pow(x, 2.0) + pow(y, 2.0));
        if (d <= 1.0) {
            inner++;
        }
        else {
            outer++;
        }
    }

    return ((double) inner / (double) iterations) * 4;
}

我不知道这个rand实现的好坏如何，但至少在Linux上尝试一下是否会对性能产生影响是值得的。

- James Holderness

Answer 3

性能和线程是黑魔法。答案取决于编译器和用于线程的库的具体细节，内核处理得有多好等等。基本上，如果*nix的库在切换、移动对象等方面不高效，则线程实际上会变慢。这就是为什么我们现在大部分做线程工作的人都使用JVM或类似JVM的语言之一的原因之一。我们可以信任运行时JVM的行为，它的整体速度可能因平台而异，但在该平台上始终如一。此外，由于时间问题可能在Windows上并不会出现的一些隐藏的等待/竞争条件可能会被揭示出来。

如果您有更改语言的能力，请考虑Scala或D。 Scala是Java的Actor驱动模型继承者，而D是C的继承者。这两种语言都显示了它们的根源——如果您可以编写C代码，那么使用D应该没有问题。然而，这两种语言都实现了Actor模型。无需再使用线程池，也无需担心竞争条件等！！！！

- user500123