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

Я пытаюсь использовать новые потоки С++ 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;
}

Скомпилированный с помощью "g++ -std = С++ 11 -pthread test.cpp" на Linux и 3core, типичный результат

time single: 33
time multi: 565

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

изменить

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

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

Ответ 1

В моей системе поведение такое же, но, как отметил Максим, 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;
}

Ответ 2

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

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

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

long int
__random ()
{
  int32_t retval;

  __libc_lock_lock (lock);

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

  __libc_lock_unlock (lock);

  return retval;
}

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

Ответ 3

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

Ответ 4

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

Это позволит вам ставить задачи в других потоках без накладных расходов на создание 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: Если задачи, поставленные в вышеописанную очередь, зависят друг от друга для промежуточных результатов, очередь может заходить в тупик, потому что не предусмотрено условие для "восстановления" потоков, которые заблокированы и выполняют новый код. Тем не менее, "нечеткие вычисления" неблокирующие задачи должны отлично работать с указанной выше моделью.