Tại sao mã C++ 11 này có chứa rand() chậm hơn với nhiều luồng hơn so với một?

Question

Tôi đang thử trên các chủ đề C++ 11 mới, nhưng bài kiểm tra đơn giản của tôi có hiệu năng đa lõi không hoạt động. Như một ví dụ đơn giản, chương trình này cho biết thêm một số số ngẫu nhiên bình phương.

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

Biên soạn với 'g ++ -std = C++ 11 -pthread test.cpp' trên Linux và một máy 3core, kết quả thu được là

time single: 33 
time multi: 565 

Vì vậy, đa phiên bản ren hơn một thứ tự cường độ chậm hơn. Tôi đã sử dụng số ngẫu nhiên và một sqrt để làm cho ví dụ ít tầm thường và dễ bị tối ưu hóa trình biên dịch, vì vậy tôi không có ý tưởng.

chỉnh sửa:

1. Vấn đề này quy mô lớn hơn cho N, vì vậy vấn đề không phải là thời gian chạy ngắn
2. Thời gian tạo chủ đề không phải là vấn đề. Việc loại trừ nó không làm thay đổi kết quả đáng kể

Tôi đã phát hiện ra vấn đề. Nó thực sự là rand(). Tôi đã thay thế nó bằng một tương đương C++ 11 và giờ đây quy mô thời gian chạy hoàn hảo. Cảm ơn mọi người!

Answer 1

Thời gian cần thiết để thực thi chương trình là rất nhỏ (33msec). Điều này có nghĩa rằng chi phí để tạo và xử lý một số luồng có thể nhiều hơn lợi ích thực sự. Hãy thử sử dụng các chương trình cần thời gian dài hơn để thực thi (ví dụ: 10 giây).

Answer 2

Để làm điều này nhanh hơn, hãy sử dụng mẫu hồ bơi chuỗi.

Điều này sẽ cho phép bạn enqueue nhiệm vụ trong các chủ đề khác mà không cần phải tạo ra một std::thread mỗi khi bạn muốn sử dụng nhiều hơn một sợi.

Đừng tính chi phí thiết lập hàng đợi trong chỉ số hiệu suất của bạn, chỉ cần thời gian để nạp và trích xuất kết quả.

Tạo một tập hợp các chủ đề và một chuỗi nhiệm vụ (một cấu trúc có chứa std::function<void()>) để nạp chúng. Các chủ đề chờ đợi trên hàng đợi để thực hiện các tác vụ mới, thực hiện chúng, sau đó đợi các tác vụ mới.

Nhiệm vụ có trách nhiệm truyền đạt "hoàn thành" của họ trở lại ngữ cảnh gọi điện, chẳng hạn như thông qua std::future<>. Các mã cho phép bạn chức năng enqueue vào hàng đợi công việc có thể làm gói này cho bạn, tức là chữ ký này:

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

mà biến một trần truồng std::function trở R thành một nullary packaged_task, sau đó nói thêm rằng vào hàng đợi công việc. Lưu ý rằng hàng đợi nhiệm vụ cần di chuyển, vì packaged_task chỉ di chuyển.

Lưu ý 1: Tôi không phải tất cả những gì quen thuộc với std::future, vì vậy, điều trên có thể do lỗi. Lưu ý 2: Nếu nhiệm vụ được đưa vào hàng đợi được mô tả ở trên phụ thuộc vào nhau cho kết quả trung gian, hàng đợi có thể bế tắc, vì không có quy định nào để "yêu cầu" chủ đề bị chặn và thực thi mã mới được mô tả. Tuy nhiên, các nhiệm vụ không chặn "tính toán trần truồng" sẽ hoạt động tốt với mô hình trên.

Answer 3

Trên hệ thống của tôi, hành vi là như nhau, nhưng như Maxim đã đề cập, rand không phải là chủ đề an toàn. Khi tôi thay đổi rand thành rand_r, thì mã đa luồng nhanh hơn như mong đợi.

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

Khi bạn phát hiện ra, rand là thủ phạm tại đây.

Đối với những người tò mò, có thể hành vi này xuất phát từ việc bạn triển khai rand bằng cách sử dụng mutex cho an toàn chủ đề.

Ví dụ, eglibc định nghĩa rand về __random, mà 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; 
} 

Đây là loại khóa sẽ buộc nhiều chủ đề để chạy serially, dẫn đến hiệu suất thấp hơn.