GCC performance

Question

I am doing parallel programming with MPI on Beowulf cluster. We wrote parallel algorithm for simulated annealing. It works fine. We expect 15 time faster execution than with serial code. But we did some execution of serial C code on different architectures and operating systems just so we could have different data sets for performance measurement. We have used this Random function in our code. We use GCC on both windows and ubuntu linux. We figured out that execution takes much longer on linuxes, and we don't know why. Can someone compile this code on linux and windows with gcc and try to explain me.

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>

    int main (int argc, char** argv){
        double Random();

        int k,NUM_ITERATIONS = 10;
        clock_t start_time = clock();
        NUM_ITERATIONS=atoi(argv[1]);

        // iniciranje random generatora 
        srand(time(NULL));

        for(k=0; k<NUM_ITERATIONS; k++){
                double raa = Random();
        }
        clock_t end_time = clock();
    printf("Time of algorithm execution: %lf seconds\n",  ((double) (end_time - start_time)) / CLOCKS_PER_SEC);

    return 0;
    }

    // generate random number bettwen 0 and 1
    double Random(){
        srand(rand());
        double a = rand();
        return a/RAND_MAX; 
    }

If I execute it with 100 000 000 as argument for NUM_ITERATIONS, I get 20 times slower execution on linux than on windows. Tested on machine with same architecture with dual boot win + ubuntu linux. We need help as this Random function is bottleneck for what we want to show with our data.

Fieldpiece

What command line options are you passing to gcc when compiling this in linux, and what options are being used in windows. – Euphroe

"gcc -o rand rand.c -lm" On both systems. – Fieldpiece

Whatever random number generator you end up with, initialize it once per program run. ONCE ONLY! – Proudhon

Answer 1

I would investigate other random number generators available. Many exist that have been well tested and perform better than the standard library random functions, both in terms of speed of execution and in terms of pseudo-randomness. I have also implemented my own RNG for a graduate class, but I wouldn't use it in production code. Go with something that has been vetted by the community. Random.org is a good resource for testing whatever RNG you select.

Phylogeny

Answer 2

On Linux gcc, the call to srand(rand()); within the Random function accounts for more than 98 % of the time.

It is not needed for the generation of random numbers, at least not within the loop. You already call srand() once, it's enough.

Enkindle

We have need to change the seed all the time. void srand ( unsigned int seed ); The pseudo-random number generator is initialized using the argument passed as seed. For every different seed value used in a call to srand, the pseudo-random number generator can be expected to generate a different succession of results in the subsequent calls to rand. Two different initializations with the same seed, instructs the pseudo-random generator to generate the same succession of results for the subsequent calls to rand in both cases. – Fieldpiece

@ZeKoU - I'm not saying you're wrong, but this code smells quite fishy. I think (but am not sure) that you may be generating a deterministic or guessable sequence. The first call the rand inside the srand is always going to seed srand with the same value. From there, I think an attacker could re-run your could. I believe dtrosset is correct. Additionally, you may want to call srand(time(NULL)) instead: #1109280 – Fourlegged

didn't it occur to you that int randPrime() {return srand(rand()), rand();} ? – Lockjaw

@ZeKoU: Doesn't it follow from that that if you just seed it with the next pseudo-random number, the sequence as a whole is still just as pseudo-random? – Tarra

This is easy to test - print out the return from Random(), and replace srand(time(NULL)); in main() with srand(1);. Run it several times, and you will see the exact same sequence of outputs. Change it to srand(2);, you'll see a different sequence. Back to 1, same old sequence again. Re-seeding without adding any new information is literally a waste of time. – Fruition

"srand(rand());" is boneheaded. You've already seeded the random number generator, reseeding it with its own output is senseless. – Stonwin