Вопрос: Почему многопоточность медленнее?


Поэтому я пытаюсь написать программу, которая находит простые числа. Реальная цель проекта - просто узнать многопоточность. Сначала я написал программу с одним потоком и обнаружил до 13 633 943 за 1 минуту. Моя многопоточная версия только дошла до 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;
}

Что-то, что меня особенно смущает, - это то, что системный монитор сообщает о 25% использовании ЦП для одного потока и 100% использовании для многопоточности. Разве это не значит, что он делает в 4 раза больше расчётов?


12


источник


Ответы:


Я уверен 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,76 с, но time команда на моем компьютере Linux показывает общее время выполнения 12.792s, поэтому, очевидно, немного времени, когда все потоки не работают - или некоторые ошибки учета ...


12



Я думаю, что большая часть вашей текущей проблемы заключается в том, что вы принимаете участие, которое действительно может работать многопоточным (нахождение простых чисел) и хоронить его в шуме (время для вывода вывода на консоль).

Чтобы получить представление о том, как много эффекта это имеет, я немного переписал вашу основную часть, чтобы отделить печать простых чисел от поиска простых чисел. Чтобы облегчить синхронизацию, мне также потребовалось лимит из командной строки вместо интерактивного, давая следующее:

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 из 0,6 секунды, даже если мы можем только удвоить скорость, мы должны увидеть значительную разницу в общем времени ,

Отделение вывода от первичного поиска также дает нам гораздо лучшую основу для написания многопоточной версии кода. С каждым потоком, записывающим свои результаты в отдельный вектор, мы можем получить значимый (не чередующийся) вывод без необходимости блокировки 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 все еще вычисляют и записывают данные из потока 3, пока поток 4 все еще вычисляет).

Полагаю, я должен добавить, что улучшения, которые мы видим, достаточно малы, что также может быть простым шумом в сроках. Тем не менее, я выполнял как одно-, так и многопоточные версии, и, несмотря на некоторые различия в обеих версиях, многопоточная версия постоянно быстрее, чем должно учитываться улучшение скорости вычислений.

Я почти забыл: чтобы понять, насколько сильно это происходит в общей скорости, я проверил тест, чтобы узнать, сколько времени потребуется, чтобы найти простые цифры до 13 633 943, которые ваша оригинальная версия обнаружила за одну минуту. Несмотря на то, что я почти наверняка использую более медленный процессор (7-летний Athlon 64 X2 5200+), эта версия кода делает это за 12,7 секунды.

Одно последнее замечание: по крайней мере на данный момент я не использовал прописку, которую вы вставили, чтобы предотвратить ложный обмен. В зависимости от времени, которое я получаю, они не кажутся необходимыми (или полезными).


6



Это зависит скорее от того, сколько процессоров получает ваш код для запуска ОС. Каждый из этих потоков связан с ЦП, поэтому, если у вас есть только один процессор, он будет запускать один поток для бит, использовать его в один поток, запускать следующий поток и т. Д., Который не будет быстрее и может быть медленнее, в зависимости от накладные расходы на обмен нитями. И, по крайней мере, на Solaris стоит сказать, что вы хотите, чтобы все потоки запускались сразу.

Я не сталкивался с реализацией, где вывод сериализуется, как это предлагает другой плакат. Обычно вы получаете выход, как

235 iisi s  ppprririimmme
ee

поэтому ваш вывод может указывать на то, что O / S не выделяет вам несколько потоков.

Другая проблема, которую вы могли бы поразить, заключается в том, что вывод на консоль невероятно медленный по сравнению с выходом в файл. Возможно, стоит отправить вывод из вашей программы в файл и посмотреть, как быстро это происходит.


1



Я считаю, что Оли Чарльзворт ударил его по голове с проблемой гиперпотока. Я думал, что гиперпоточность похожа на двух ядер. Это не. Я изменил его, чтобы использовать только два потока, и я добрался до 22 227 421, что почти вдвое быстрее.


1



Хотя @MatsPetersson является правильным (по крайней мере для системы на основе POSIX, stdout является общим ресурсом), он не предоставляет способ фиксировать  эта проблема, вот как вы можете устранить эти досадные блокировки от происходящего.

POSIX C определяет функцию, putc_unlocked, который будет делать то же самое, что и putc, но без блокировки (сюрприз). Используя это, мы можем определить нашу собственную функцию, которая будет печатать целое число без блокировки и быть быстрее, чем cout или printf в многопоточных сценариях:

void printint_unlocked(FILE *fptr, int i) {
    static int digits[] = {
        1,
        10,
        100,
        1000,
        10000,
        100000,
        1000000,
        10000000,
        100000000,
        1000000000,
    };

    if (i < 0) {
        putc_unlocked('-', fptr);
        i = -i;
    }

    int ndigits = (int) log10(i);
    while (ndigits >= 0) {
        int digit = (i / (digits[ndigits])) % 10;

        putc_unlocked('0' + digit, fptr);

        --ndigits;
    }
}

Обратите внимание, что вполне возможно, что с этим методом будут условия гонки, в результате чего числа будут сталкиваться в вашем выходе. Если ваш алгоритм не заканчивается столкновениями, вы все равно должны получать повышение производительности многопоточного кода.

Третий и последний вариант (и, вероятно, один из них слишком сложный для вашего случая использования) - это создать очередь событий на еще одном потоке и выполнить всю печать из этого потока, что приведет к отсутствию условий гонки и отсутствия проблем с блокировкой между потоками.


-2