Perfomance slowdown with growth of operations number
I have next problem. My code performance depends on number of operation! How can it be? (I use gcc v 4.3.2 under openSuse 11.1)
Here is my code:
#define N_MAX 1000000
typedef unsigned int uint;
double a[N_MAX];
double b[N_MAX];
uint n;
int main(){
for (uint i=0; i<N_MAX; i++) {
a[i]=(double)rand()/RAND_MAX;
}
for (uint n=100000; n<500000; n+=5000) {
uint time1 = time(NULL);
for (uint i=0; i<n;++i)
for (uint j=0;j<n;++j)
b[j] = a[j];
uint time2 = time(NULL);
double time = double(time2-time1);
printf("%5d ", n);
printf("%5.2f %.3f\n", time, ((double)n*n/time)/1e9);
}
return 0;
}
And here is the log of results:
n-time-Gflops (=)
200000 23.00 1.739 205000 24.00 1.751 210000 25.00 1.764 215000 26.00 1.778 220000 27.00 1.793 225000 29.00 1.746 230000 30.00 1.763 235000 32.00 1.726 240000 32.00 1.800 245000 34.00 1.765 250000 36.00 1.736 255000 37.00 1.757 260000 38.00 1.779 265000 40.00 1.756 270000 42.00 1.736 275000 44.00 1.719 280000 46.00 1.704 285000 48.00 1.692 290000 49.00 1.716 295000 51.00 1.706 300000 54.00 1.667 305000 54.00 1.723 310000 59.00 1.629 315000 61.00 1.627 320000 66.00 1.552 325000 71.00 1.488 330000 76.00 1.433 335000 79.00 1.421 340000 84.00 1.376 345000 85.00 1.400 350000 89.00 1.376 355000 96.00 1.313 360000 102.00 1.271 365000 110.00 1.211 370000 121.00 1.131 375000 143.00 0.983 380000 156.00 0.926 385000 163.00 0.909There is also the image but I can't post it cause of new users restrictions. But here is the log plot.
What is the reason of开发者_StackOverflow社区 this slowdown? How to get rid of it? Please Help!
Your inner loops increase number of iterations every time - it is expected to take more time to do their job if there is more calculations to do. First time there are 100k operations to be done, second time 105k operations, and so on. It simply must take more and more time.
EDIT: To be clearer, I tried to say it looks to something that Spolsky called Shlemiel the painter's algorithm
Thank a lot for response!
My expectation bases on idea that operation number per time unit should remains the same. So if I increase number of operations, say twice, then computation time should increase also twice, therefore the ration of operations number and the computation time should be constant. This is something that i didn't meet. :(
精彩评论