views:

373

answers:

2
+2  Q: 

GCC performance

Hello,

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.

+5  A: 

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.

Didier Trosset
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.
ZeKoU
@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: http://stackoverflow.com/questions/1108780/why-do-i-always-get-the-same-sequence-of-random-numbers-with-rand
John Paulett
didn't it occur to you that int randPrime() {return srand(rand()), rand();}?
ima
@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?
unwind
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.
Steve Jessop
+1  A: 

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.

Scottie T