为什么多线程会变慢？

Question

所以我正在尝试编写一个找到素数的程序.该项目的真正目的只是学习多线程.首先,我编写了一个单线程程序,它在1分钟内找到了最多13,633,943.我的多线程版本只有10,025,627.

这是我的单线程程序的代码

#include <iostream>

using namespace std;

bool isprime(long num)
{
    long lim = num/2;
    if(num == 1)
    {
        return 0;
    }
    for(long i = 2; i <= lim; i++)
    {
        if (num % i == 0)
        {
            return 0;
        }
        else{ lim = num/i; }
    }
    return 1;
}

int main()
{
    long lim;
    cout << "How many numbers should I test: ";
    cin >> lim;
    for(long i = 1; i <= lim || lim == 0; i++)
    {
        if(isprime(i))
        {
            cout << i << endl;
        }
    }
}

这是我的多线程程序的代码.

extern"C"
{
    #include <pthread.h>
    #include <unistd.h>
}
#include <iostream>

using namespace std;

bool isprime(long num);
void * iter1(void * arg);
void * iter2(void * arg);
void * iter3(void * arg);
void * iter4(void * arg);


int main()
{
    //long lim;
    //cout << "How many numbers should I test: ";
    //cin >> lim;
    pthread_t t1;
    char mem1[4096];//To avoid false sharing. Needed anywhere else?
    pthread_t t2;
    char mem2[4096];//These helped but did not solve problem.
    pthread_t t3;
    pthread_create(&t1, NULL, iter1, NULL);
    pthread_create(&t2, NULL, iter2, NULL);
    pthread_create(&t3, NULL, iter3, NULL);
    iter4(0);
}

bool isprime(long num)
{
    long lim = num/2;
    if(num == 1)
    {
        return 0;
    }
    for(long i = 2; i <= lim; i++)
    {
        if (num % i == 0)
        {
            return 0;
        }
        else{ lim = num/i; }
    }
    return 1;
}

void * iter1(void * arg)
{
    for(long i = 1;; i = i + 4)
    {
        if(isprime(i))
        {
            cout << i << endl;
        }
    }
return 0;
}

void * iter2(void * arg)
{
    for(long i = 2;; i = i + 4)
    {
        if(isprime(i))
        {
            cout << i << endl;
        }
    }
return 0;
}

void * iter3(void * arg)
{
    for(long i = 3;; i = i + 4)
    {
        if(isprime(i))
        {
            cout << i << endl;
        }
    }
return 0;
}

void * iter4(void * arg)
{
    for(long i = 4;; i = i + 4)
    {
        if(isprime(i))
        {
            cout << i << endl;
        }
    }
return 0;
}

让我特别困惑的是系统监视器报告单线程的CPU使用率为25%,多线程的使用率为100%.这不应该意味着它的计算量是4倍吗？

Answer 1

我相当确定cout它是一种共享资源 - 即使它实际上正确地按照正确的顺序打印每个数字,它也会使事情变得非常缓慢.

我做了类似的事情(它更灵活,并使用原子操作来"选择下一个数字"),而且在我的四核机器上几乎快了4倍.但那只是我不打印任何东西.如果它打印到控制台,它会慢很多 - 因为很多时候使用洗牌像素而不是实际计算.

注释掉这一cout << i << endl;行,它会更快地运行.

编辑:使用我的测试程序,打印:

Single thread: 15.04s. 
Four threads: 11.25s

没有打印:

Single threads: 12.63s.
Four threads: 3.69s.

3.69*4 = 14.76s,但是time我的Linux机器上的命令显示总运行时间为12.792秒,因此显然有一点时间所有线程都没有运行 - 或者一些会计错误......

Answer 2

我认为你目前的很多问题是你正在采用真正可以运行多线程(找到素数)并将其隐藏在噪声中的部分(将输出写入控制台的时间).

为了了解它有多大的影响,我重新编写了你的​​主要内容,分别打印素数与寻找素数.为了使计时更容易,我还从命令行而不是交互式获取限制,给出:

int main(int argc, char **argv) {
    if (argc != 2) {
        std::cerr << "Usage: bad_prime <limit:long>\n";
        return 1;
    }
    std::vector<unsigned long> primes;

    unsigned long lim = atol(argv[1]);

    clock_t start = clock();

    for(unsigned long i = 1; i <= lim; i++)
        if(isprime(i))
            primes.push_back(i);
    clock_t stop = clock();

    for (auto a : primes)
        std::cout << a << "\t";

    std::err << "\nTime to find primes: " << double(stop-start)/CLOCKS_PER_SEC << "\n";
}

跳过成千上万的素数本身,我得到这样的结果:

Time to find primes: 0.588


Real    48.206
User    1.68481
Sys     3.40082

所以 - 大约半秒钟找到素数,超过47秒打印它们.假设意图真的是将输出写入控制台,我们也可以在那里停止.即使多线程可以完全消除找到素数的时间,我们仍然只能将最终时间从~48.2秒改为~47.6秒 - 这不太可能是值得的.

因此,目前我认为真正的意图是将输出写入类似文件的内容.因为在编写多线程代码的过程中似乎没有意义,但是在每个线程中运行非常低效的代码,我认为我将优化(或者至少,去减少)单线程代码作为一个起点点.

首先,我删除了endl并替换它"\n".将输出定向到文件,这将运行时间从0.968秒减少到0.678秒 - endl除了写入换行符之外还刷新缓冲区,并且缓冲区刷新占程序整体所用时间的大约三分之一.

在同样的基础上,我冒昧地重写你isprime的东西,至少效率低一点:

bool isprime(unsigned long num) {
    if (num == 2)
        return true;

    if(num == 1 || num % 2 == 0)
        return false;

    unsigned long lim = sqrt(num);

    for(unsigned long i = 3; i <= lim; i+=2)
        if (num % i == 0)
            return false;

    return true;
}

这肯定是有待进一步改进的(例如,筛选Eratosthenes),但它简单,直接,快两到三倍(上面的时间是基于使用它isprime,而不是你的).

在这一点上,多线程的主要发现至少有一定意义:在主要发现大约0.5秒的情况下,即使我们只能加倍速度,我们也应该看到总体时间的显着差异.

将输出与主要发现分开也为编写多线程版本的代码提供了更好的基础.每个线程将其结果写入一个单独的向量,我们可以得到有意义的(不是交错的)输出而不必进行锁定cout等 - 我们分别计算每个块,然后按顺序打印出每个向量.

代码可能如下所示:

#include <iostream>
#include <vector>
#include <time.h>
#include <math.h>
#include <thread>

using namespace std;

bool isprime(unsigned long num) {
    // same as above
}

typedef unsigned long UL;

struct params { 
    unsigned long lower_lim;
    unsigned long upper_lim;
    std::vector<unsigned long> results;

    params(UL l, UL u) : lower_lim(l), upper_lim(u) {}
};

long thread_func(params *p) { 
    for (unsigned long i=p->lower_lim; i<p->upper_lim; i++)
        if (isprime(i))
            p->results.push_back(i);
    return 0;
}

int main(int argc, char **argv) {
    if (argc != 2) {
        std::cerr << "Usage: bad_prime <limit:long>\n";
        return 1;
    }

    unsigned long lim = atol(argv[1]);

    params p[] = {
        params(1, lim/4),
        params(lim/4, lim/2),
        params(lim/2, 3*lim/4),
        params(3*lim/4, lim)
    };

    std::thread threads[] = {
        std::thread(thread_func, p), 
        std::thread(thread_func, p+1),
        std::thread(thread_func, p+2),
        std::thread(thread_func, p+3)
    };

    for (int i=0; i<4; i++) {
        threads[i].join();
        for (UL p : p[i].results)
            std::cout << p << "\n";
    }
}

在以前的同一台机器上运行它(一个相当古老的双核处理器),我得到:

Real    0.35
User    0.639604
Sys     0

这看起来非常好.如果我们获得的是多核计算,我们期望看到时间找到素数除以2(我在双核处理器上运行)并且将数据写入磁盘的时间保持不变(多线程不会加速我的硬盘).基于此,完美缩放应该给我们0.59/2 + 0.1 = 0.40秒.

我们所看到的(不可否认的)小改进很可能源于这样一个事实:我们可以开始将数据从线程1写入磁盘,而线程2,3和4仍然可以找到素数(同样,开始编写来自线程2的数据,而3和4仍在计算,并且当线程4仍在计算时从线程3写入数据).

我想我应该补充一点,我们所看到的改进足够小,在时间上也可能是简单的噪音.但是,我做了多次运行单线程和多线程版本,虽然两者都有一些变化,但多线程版本始终比计算速度的改进应该更快.

我差点忘了:为了弄清楚它在整体速度上有多大差异,我进行了一项测试,看看需要多长时间才能找到13,633,943的素数,这是原始版本在一分钟内找到的.即使我几乎肯定使用较慢的CPU(一个~7岁的Athlon 64 X2 5200+),这个版本的代码在12.7秒内完成.

最后一点说明:至少在目前,我已经省去了你要插入的填充,以防止误共享.根据我所获得的时间,它们似乎没有必要(或有用).