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

Question

Так что я пытаюсь написать программу, которая находит простые числа. Реальная цель проекта - просто узнать многопоточность. Сначала я написал программу с одним потоком и обнаружил до 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 раза больше расчётов?

Answer 1

Я уверен, что cout действует совместно используемым ресурсом - и даже если он действительно правильно печатает каждое число и в правильном порядке, он замедляет работу ОЧЕНЬ много для этого.

Я сделал что-то подобное (он более гибкий и использует атомную операцию для «выбора следующего номера»), и это почти точно в 4 раза быстрее на моей четырехъядерной машине. Но это только если я ничего не печатаю. Если он печатает на консоли, это намного медленнее - потому что много времени используется, перетасовывая пиксели, а не вычисляя.

Комментарий из линии cout << i << endl;, и он будет работать намного быстрее.

Edit: с помощью моей тестовой программы, с печатью:

Single thread: 15.04s. 
Four threads: 11.25s 

Без печати:

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

3,69 * 4 = 14.76s, но time команда на моей машине Linux показывает 12.792s общее runtime, поэтому, очевидно, немного времени, когда все потоки не работают - или некоторые ошибки учета ...

Answer 2

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

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

235 iisi s ppprririimmme 
ee 

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

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

Answer 3

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

Answer 4

Хотя @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; 
    } 
} 

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

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

Answer 5

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

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

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; 
} 

Это, конечно, открыто для дополнительного улучшения (например, решето Эратосфена), но это просто, прямо и примерно в два-три раза быстрее (времена выше основаны на использовании этого 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 секунды.

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