44

I'm trying around on the new C++11 threads, but my simple test has abysmal multicore performance. As a simple example, this program adds up some squared random numbers.

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

Compiled with 'g++ -std=c++11 -pthread test.cpp' on Linux and a 3core machine, a typical result is

time single: 33
time multi: 565

So the multi threaded version is more than an order of magnitude slower. I've used random numbers and a sqrt to make the example less trivial and prone to compiler optimizations, so I'm out of ideas.

edit:

  1. This problem scales for larger N, so the problem is not the short runtime
  2. The time for creating the threads is not the problem. Excluding it does not change the result significantly

Wow I found the problem. It was indeed rand(). I replaced it with an C++11 equivalent and now the runtime scales perfectly. Thanks everyone!

13
  • 9
    You're measuring algorithm + time of creating threads which is slow due to system calls. Move the timer after creation of threads and then run threads.
    – masoud
    Commented May 23, 2013 at 14:06
  • 17
    rand() is not a multi-tread safe function generally. Use rand_r(). Commented May 23, 2013 at 14:06
  • 7
    +1 for well-composed question. Nice sscce and compiler instructions appreciated. Commented May 23, 2013 at 14:08
  • 5
    To expand on @MM.'s comment: 500ms is not significant enough to be relevant, the thread creation time is much more than your algorithm's running time. Run it with a much higher N (eg. N = 1000000000) and give us the results. ;)
    – syam
    Commented May 23, 2013 at 14:10
  • 7
    @MaximYegorushkin: Better still, use C++11 random engines like std::minstd_rand. Commented May 23, 2013 at 14:11

4 Answers 4

27

On my system the behavior is same, but as Maxim mentioned, rand is not thread safe. When I change rand to rand_r, then the multi threaded code is faster as expected.

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;
}
6
  • 11
    Seems to me that the issue is actually that rand is thread-safe, and there is a great deal of lock contention when multiple threads are all calling rand. With rand_r each call has its own data, so there is no contention. Commented May 23, 2013 at 19:16
  • @PeteBecker I also thought like you, but rand man page states The function rand() is not reentrant or thread-safe, since it uses hidden state that is modified on each call.
    – Étienne
    Commented May 23, 2013 at 22:07
  • @Étienne - using hidden state means it's not re-entrant. It does not mean that it's not thread-safe. If changing rand to rand_r makes it much faster, that pretty much establishes that rand is synchronizing its internal state. Commented May 24, 2013 at 2:49
  • 4
    "The function rand() is not reentrant or thread-safe" doesn't mean rand is not thread-safe?
    – Étienne
    Commented May 24, 2013 at 7:29
  • 2
    @PeteBecker It's possible that your particular implementation of rand chooses to be thread-safe (as evidenced by the timing data). But if the documentation explicitly says it's not thread-safe, then relying on that is a Bad Idea -- future versions would be free to change without warning and break your code in very-difficult-to-debug ways. Commented May 24, 2013 at 18:25
22

As you discovered, rand is the culprit here.

For those who are curious, it's possible that this behavior comes from your implementation of rand using a mutex for thread safety.

For example, eglibc defines rand in terms of __random, which 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;
}

This kind of locking would force multiple threads to run serially, resulting in lower performance.

8

The time needed to execute the program is very small (33msec). This means that the overhead to create and handle several threads may be more than the real benefit. Try using programs that need longer times for the execution (e.g., 10 sec).

4
  • he's only creating 3 threads. It doesn't explain the 565ms. And I can't reproduce the results on VS2012 so i suspect something else is wrong here.
    – Timo
    Commented May 23, 2013 at 14:55
  • As stated in the edit, the problem scales. Same or comparable result with much higher N's
    – Basti
    Commented May 23, 2013 at 15:06
  • On my Linux system with g++ 4.7 and -O3 I had comparable results.
    – Claudio
    Commented May 23, 2013 at 15:23
  • This is a suggestion and does not answer the actual question.
    – iammilind
    Commented Dec 18, 2014 at 14:12
3

To make this faster, use a thread pool pattern.

This will let you enqueue tasks in other threads without the overhead of creating a std::thread each time you want to use more than one thread.

Don't count the overhead of setting up the queue in your performance metrics, just the time to enqueue and extract the results.

Create a set of threads and a queue of tasks (a structure containing a std::function<void()>) to feed them. The threads wait on the queue for new tasks to do, do them, then wait on new tasks.

The tasks are responsible for communicating their "done-ness" back to the calling context, such as via a std::future<>. The code that lets you enqueue functions into the task queue might do this wrapping for you, ie this signature:

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

which turns a naked std::function returning R into a nullary packaged_task, then adds that to the tasks queue. Note that the tasks queue needs be move-aware, because packaged_task is move-only.

Note 1: I am not all that familiar with std::future, so the above could be in error.

Note 2: If tasks put into the above described queue are dependent on each other for intermediate results, the queue could deadlock, because no provision to "reclaim" threads that are blocked and execute new code is described. However, "naked computation" non-blocking tasks should work fine with the above model.

2
  • You could replace your shared_ptr<promise<R>> and lambda expression with packaged_task<R()>, it would make enqueue much simpler Commented May 23, 2013 at 16:03
  • @JonathanWakely I think that did it. Commented May 23, 2013 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.