3

我用 C 语言实现了一个小程序，使用 Monte Carlo 方法计算 PI（主要是因为个人兴趣和培训）。在实现了基本的代码结构之后，我添加了一个命令行选项，允许执行线程计算。

我预计会大幅提速，但我感到失望。命令行概要应该清楚。近似 PI 的最终迭代次数是通过命令行传递的次数-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) 上：

Linux 统计

使用 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库。在这种情况下如何做正确的澄清会非常好。

4

3 回答 3

5

问题是在 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()您自己的缓冲区应该会快得多。

于 2013-05-26T15:08:36.757 回答
1

作为比较，我刚刚在 Windows Vista 上试用了您的应用程序，使用 Borland C++ 编译，2 线程版本的执行速度几乎是单线程版本的两倍。

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

所以2线程版本还是快一倍，但是单线程库的1线程版本其实比线程安全库上的2线程版本要快。

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

不过，最重要的是，您的编译器的rand实现可能是这两种情况下的主要性能问题。

更新

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

更新后的代码如下所示：

#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 上尝试一下，看看它是否会对性能产生影响。

于 2013-05-26T15:56:10.890 回答
1

性能和线程是一门黑色艺术。答案取决于用于执行线程的编译器和库的细节、内核处理它的能力等。基本上，如果您的 *nix 库在切换、移动对象等方面效率不高，那么线程实际上将是慢点 。这是我们现在很多线程工作都使用 JVM 或类似 JVM 的语言的原因之一。我们可以相信运行时 JVM 的行为——它的整体速度可能因平台而异，但在该平台上是一致的。此外，您可能会发现一些隐藏的等待/竞争条件，只是由于时间可能不会在 Windows 上显示。

如果您能够更改您的语言，请考虑使用 Scala 或 D。Scala 是 Java 的演员驱动模型的继承者，而 D 是 C 的继承者。这两种语言都有其根源——如果您可以用 C 编写，D 应该没问题。然而，这两种语言都实现了参与者模型。没有更多的线程池，没有更多的比赛条件等！！！！！！

于 2013-05-26T15:08:21.283 回答