Почему этот код C++ 11, содержащий rand() медленнее с несколькими потоками, чем с одним?

Question

Я пытаюсь использовать новые потоки C++ 11, но мой простой тест имеет ужасную многоядерность. В качестве простого примера эта программа добавляет некоторые квадратные случайные числа.

#include <iostream> 
#include <thread> 
#include <vector> 
#include <cstdlib> 
#include <chrono> 
#include <cmath> 

double add_single(int N) { 
    double sum=0; 
    for (int i = 0; i < N; ++i){ 
     sum+= sqrt(1.0*rand()/RAND_MAX); 
    } 
    return sum/N; 
} 

void add_multi(int N, double& result) { 
    double sum=0; 
    for (int i = 0; i < N; ++i){ 
     sum+= sqrt(1.0*rand()/RAND_MAX); 
    } 
    result = sum/N; 
} 

int main() { 
    srand (time(NULL)); 
    int N = 1000000; 

    // single-threaded 
    auto t1 = std::chrono::high_resolution_clock::now(); 
    double result1 = add_single(N); 
    auto t2 = std::chrono::high_resolution_clock::now(); 
    auto time_elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count(); 
    std::cout << "time single: " << time_elapsed << std::endl; 

    // multi-threaded 
    std::vector<std::thread> th; 
    int nr_threads = 3; 
    double partual_results[] = {0,0,0}; 
    t1 = std::chrono::high_resolution_clock::now(); 
    for (int i = 0; i < nr_threads; ++i) 
     th.push_back(std::thread(add_multi, N/nr_threads, std::ref(partual_results[i]))); 
    for(auto &a : th) 
     a.join(); 
    double result_multicore = 0; 
    for(double result:partual_results) 
     result_multicore += result; 
    result_multicore /= nr_threads; 
    t2 = std::chrono::high_resolution_clock::now(); 
    time_elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count(); 
    std::cout << "time multi: " << time_elapsed << std::endl; 

    return 0; 
} 

Собран с 'г ++ -std = C++ 11 -pthread test.cpp' на Linux и 3core машины, типичный результат

time single: 33 
time multi: 565 

Так многопоточный версия больше на порядок медленнее. Я использовал случайные числа и sqrt, чтобы сделать пример менее тривиальным и подверженным оптимизации компилятора, поэтому у меня нет идей.

редактировать:

1. Эта проблема весы для больших N, так что проблема не короткое время выполнения
2. Время создания темы не проблема. Исключая его, это не меняет результат значительно

Ничего себе, я нашел проблему. Это был действительно rand(). Я заменил его эквивалентом C++ 11, и теперь он отлично работает. Всем спасибо!

Answer 1

Время, необходимое для выполнения программы, очень мало (33 мсек). Это означает, что накладные расходы для создания и обработки нескольких потоков могут быть больше, чем реальная выгода. Попробуйте использовать программы, которым требуется больше времени для выполнения (например, 10 секунд).

Answer 2

Чтобы сделать это быстрее, используйте шаблон пула потоков.

Это позволит вам ставить задачи в других потоках без накладных расходов при создании std::thread каждый раз, когда вы хотите использовать несколько потоков.

Не учитывайте накладные расходы на настройку очереди в ваших показателях производительности, а также время, в которое вы можете вывести и извлечь результаты.

Создайте набор потоков и очередь задач (структура, содержащая std::function<void()>), чтобы их кормить. Потоки ждут очереди для выполнения новых задач, выполняют их, а затем ждут новые задачи.

Задачи несут ответственность за передачу их «завершенности» обратно в вызывающий контекст, например, через std::future<>. Код, который позволяет вам Епдиеие функции в очередь задач может это сделать обертку для вас, то есть эта подпись:

template<typename R=void> 
std::future<R> enqueue(std::function<R()> f) { 
    std::packaged_task<R()> task(f); 
    std::future<R> retval = task.get_future(); 
    this->add_to_queue(std::move(task)); // if we had move semantics, could be easier 
    return retval; 
} 

который превращает голую std::function возвращающейся R в нульарную packaged_task, а затем добавляет, что в очередь задач. Обратите внимание, что очередь задач должна быть ориентирована на перенос, потому что packaged_task является только перемещением.

Примечание 1: Я не так хорошо знаком с std::future, поэтому приведенное выше может быть ошибкой.

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

Answer 3

В моей системе поведение такое же, но, как сказал Максим, rand не является потокобезопасным. Когда я меняю rand на rand_r, то многопоточный код работает быстрее, чем ожидалось.

void add_multi(int N, double& result) { 
double sum=0; 
unsigned int seed = time(NULL); 
for (int i = 0; i < N; ++i){ 
    sum+= sqrt(1.0*rand_r(&seed)/RAND_MAX); 
} 
result = sum/N; 
} 

Answer 4

Как вы обнаружили, rand является виновником здесь.

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

Например, eglibc определяет rand в терминах __random, который is defined as:

long int 
__random() 
{ 
    int32_t retval; 

    __libc_lock_lock (lock); 

    (void) __random_r (&unsafe_state, &retval); 

    __libc_lock_unlock (lock); 

    return retval; 
} 

Этот вид блокировки заставит несколько потоков запускать последовательно, что приводит к снижению производительности.