Performance decrease with threaded implementation

Question

I implemented a small program in C to calculate PI using a Monte Carlo method (mainly because of personal interest and training). After having implemented the basic code structure, I added a command-line option allowing to execute the calculations threaded.

I expected major speed ups, but I got disappointed. The command-line synopsis should be clear. The final number of iterations made to approximate PI is the product of the number of -iterations and -threads passed via the command-line. Leaving -threads blank defaults it to 1 thread resulting in execution in the main thread.

The tests below are tested with 80 Million iterations in total.

On Windows 7 64Bit (Intel Core2Duo Machine):

Compiled using Cygwin GCC 4.5.3: gcc-4 pi.c -o pi.exe -O3

On Ubuntu/Linaro 12.04 (8Core AMD):

Compiled using GCC 4.6.3: gcc pi.c -lm -lpthread -O3 -o pi

Performance

On Windows, the threaded version is a few milliseconds faster than the un-threaded. I expected a better performance, to be honest. On Linux, ew! What the heck? Why does it take even 2000% longer? Of course this is depending much on the implementation, so here it goes. An excerpt after the command-line argument parsing was done and the calculation is started:

    // Begin computation.
    clock_t t_start, t_delta;
    double pi = 0;

    if (args.threads == 1) {
        t_start = clock();
        pi = pi_mc(args.iterations);
        t_delta = clock() - t_start;
    }
    else {
        pthread_t* threads = malloc(sizeof(pthread_t) * args.threads);
        if (!threads) {
            return alloc_failed();
        }

        struct PIThreadData* values = malloc(sizeof(struct PIThreadData) * args.threads);
        if (!values) {
            free(threads);
            return alloc_failed();
        }

        t_start = clock();
        for (i=0; i < args.threads; i++) {
            values[i].iterations = args.iterations;
            values[i].out = 0.0;
            pthread_create(threads + i, NULL, pi_mc_threaded, values + i);
        }
        for (i=0; i < args.threads; i++) {
            pthread_join(threads[i], NULL);
            pi += values[i].out;
        }
        t_delta = clock() - t_start;

        free(threads);
        threads = NULL;
        free(values);
        values = NULL;

        pi /= (double) args.threads;
    }

While pi_mc_threaded() is implemented as:

struct PIThreadData {
    int iterations;
    double out;
};

void* pi_mc_threaded(void* ptr) {
    struct PIThreadData* data = ptr;
    data->out = pi_mc(data->iterations);
}

You can find the full source code at http://pastebin.com/jptBTgwr.

Question

Why is this? Why this extreme difference on Linux? I expected the anmount of time taken to calculate to be at least 3/4 of the original time. It would of course be possible that I simply made wrong use of the pthread library. A clarifcation on how to do correct in this case would be very nice.

Answer 1

The problem is that in glibc's implementation, rand() calls __random(), and that

long int
__random ()
{
  int32_t retval;

  __libc_lock_lock (lock);

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

  __libc_lock_unlock (lock);

  return retval;
}

locks around each call to the function __random_r that does the actual work.

Thus, as soon as you have more than one thread using rand(), you make each thread wait for the other(s) on almost every call to rand(). Directly using random_r() with your own buffers in each thread should be much faster.

Answer 2

Performance and threading is a black art. The answer depends on the specifics of the compiler and libraries used to do threading, how well the kernel handles it, etc. Basically, if your libraries for *nix are not efficient in switching, moving objects around etc, threading will in fact, be slower . THis is one of the reasons a lot us doing thread work now work with JVM or JVM-like languages. We can trust the runtime JVM's behavior -- it's overall speed may vary with platform, but it's consistent on that platform. In addition, you may have some hidden wait/race conditions that you uncovered just due to timing that may not show up on Windows.

If you are in a position to change your language, consider Scala or D. Scala is the actor driven model successor to Java, and D, the successor to C. Both languages show their roots -- if you can write in C, D should be no problem. Both languages however, implement the actor model. NO MORE THREAD POOLS, NO MORE RACE CONDITIONS ETC!!!!!!