c - 为什么多线程不能提高该程序中查找素数的性能？

Question

运行时间大致相同，与线程数无关。我很难弄清楚原因。我知道线程按预期并行运行，但我什至无法很好地猜测为什么没有性能改进。 (对于单线程和多线程，查找所有小于 800 万的素数大约需要 21 秒)这里发生了什么？

typedef struct prime_finder_vars {
    long from;
    long to;
    int idx;
} PrimeFinderVars;

int is_prime(long num) {
    int limit = round(sqrt(num));
    for (long i = 2; i <= limit; i++) {
        if (num % i == 0)
            return FALSE;
    }
    return TRUE;
}

void *prime_finder(void *pf) {

    PrimeFinderVars *pf_vars = (PrimeFinderVars *) pf;

    long next_cand = pf_vars->from;
    while (next_cand < pf_vars->to) {
        if (is_prime(next_cand)) {
            ++counts[pf_vars->idx];
        }
        next_cand += 2;
    }
    return pf;
}


int main(void) {

    struct timespec start;
    struct timespec end;
    double start_sec, end_sec, elapsed_sec;
    int sum = 0;

    clock_gettime(CLOCK_REALTIME, &start);

    pthread_t threads[NUM_THREADS];
    PrimeFinderVars vars[NUM_THREADS];

    int slice_size = SEARCH_RANGE / NUM_THREADS;

    for (int i = 0; i < NUM_THREADS; i++) {

        vars[i].from = i * slice_size + 1;
        vars[i].to = (i + 1) * slice_size;
        vars[i].idx = i;

        pthread_create(&threads[i], NULL, prime_finder, &vars[i]);

    }

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
        sum += counts[i];
    }

    clock_gettime(CLOCK_REALTIME, &end);

    start_sec = start.tv_sec + start.tv_nsec / NANO_PER_SEC;
    end_sec = end.tv_sec + end.tv_nsec / NANO_PER_SEC;
    elapsed_sec = end_sec - start_sec;
}

Answer 1

这是个有趣的问题。 Mikhail Vladimirov 所说的一切都是真的，但我决定在我的笔记本电脑上做一些测试，看看我得到了什么。我的笔记本电脑是配备八核 i9 的现代 MacBook Pro。我不确定它是否是超线程的，但这是我的结果:

我使用 1 到 50 之间变化的线程数和 10,000,000 的搜索范围进行了测试。
对于一个线程，它需要将近 11 秒，但是对于 16 个线程，这会迅速下降到大约 1.5 秒，并且此后没有任何好转。
我的结论是

我对 Mikhail 关于线程函数成本的回答的评论是错误的，至少在我的平台上是这样。我看到更多线程没有增加开销

您的线程库有问题。

我认为您可能需要让自己满意，线程确实在不同的内核上并行运行。您的结果的一种解释可能是它们都在竞争相同的 CPU。

只是为了好玩，我决定尝试分析该程序。

每一步都代表另一个核心 100%。我不确定为什么带有三个线程的 prt 没有达到 300%，但是您可以看到使用四个线程它会立即上升到 400%，但会以 100% 的步长下降。这是将任务分成相等的范围并且处理较低数字的线程更快完成的效果。

前 16 个数据点

Threads Time
1   11.893418
2   7.352520
3   5.117278
4   4.062026
5   3.511605
6   2.892274
7   2.401555
8   2.172573
9   1.910534
10  1.864023
11  1.860944
12  1.369277
13  1.628883
14  1.196646
15  1.626215
16  1.548878

我用来产生测试结果的代码(稍微修改了你的)。

#include <stdio.h>
#include <pthread.h>
#include <math.h>
#include <stdbool.h>

#define SEARCH_RANGE    10000000
#define NANO_PER_SEC    1000000000

typedef struct prime_finder_vars {
    long from;
    long to;
    int* count;
} PrimeFinderVars;

int is_prime(long num) {
    int limit = round(sqrt(num));
    for (long i = 2; i <= limit; i++) {
        if (num % i == 0)
            return false;
    }
    return true;
}


void *prime_finder(void *pf)
{

    PrimeFinderVars *pf_vars = (PrimeFinderVars *) pf;

    long next_cand = pf_vars->from;
    while (next_cand < pf_vars->to)
    {
        if (is_prime(next_cand))
        {
            (*pf_vars->count)++ ;
        }
        next_cand += 2;
    }
    return pf;
}


void trial(int numThreads)
{
    struct timespec start;
    struct timespec end;
    double start_sec, end_sec, elapsed_sec;
    int sum = 0;

    clock_gettime(CLOCK_REALTIME, &start);

    int counts[numThreads];
    pthread_t threads[numThreads];
    PrimeFinderVars vars[numThreads];

    int slice_size = SEARCH_RANGE / numThreads;

    for (int i = 0; i < numThreads; i++)
    {
        counts[i] = 0;
        vars[i].from = i * slice_size + 1;
        vars[i].to = (i + 1) * slice_size;
        vars[i].count = &counts[i];

        pthread_create(&threads[i], NULL, prime_finder, &vars[i]);

    }

    for (int i = 0; i < numThreads; i++)
    {
        pthread_join(threads[i], NULL);
        sum += counts[i];
    }

    clock_gettime(CLOCK_REALTIME, &end);

    start_sec = (double)start.tv_sec + (double)start.tv_nsec / NANO_PER_SEC;
    end_sec = (double)end.tv_sec + (double)end.tv_nsec / NANO_PER_SEC;
    elapsed_sec = end_sec - start_sec;
    printf("%d\t%f\n", numThreads, elapsed_sec);
}

int main()
{
    printf("Threads\tTime\n");
    for (int threads = 1 ; threads <= 50 ; ++threads)
    {
        trial(threads);
    }
}

在过去的一两天里，我更进一步地追求了这一点。首先，我很好奇为什么似乎有两条时间线:在大约 12 个线程之后，一次运行需要 1.5 秒或 1 秒。我在上面推测这是因为 Mikhail 提到的错误，所以我绘制了为每个线程数给出的实际答案并发现，虽然答案通常在 664,579 左右，但它通常会在一半左右，不出所料，当答案是一半时真正的答案，对应于两条时间线中较低的一条。

所以我修复了那个错误，双线效果消失了。但是，根据线程的数量，我仍然得到不止一个不同的答案。

这样做的原因是还有两个错误。

原始算法无法测试每个范围内的最高数字。

范围的大小是通过将搜索范围除以线程数来计算的。除非没有余数，否则不会检查搜索范围顶部的数字。

我修复了两个错误并进行了第三次运行。这并没有明显影响时间，但是对于使用的每个线程数，我得到了相同的答案。
为了比较，我写了一个 Eratosthenes 的筛子并计时。使用它和单个线程只需要 0.2 秒 - 比最快的内核数快约 7 倍。
我已经发布了一个 spreadsheet of the results 并且有一个 git repo of the code 。