3

I have a C program which for the following number of inputs executes in the following amount of time:

23           0.001s            
100          0.001s

I tried finding a formula for this but was unsuccessful. As far as I can see, the time sometimes doubles sometimes it doesn't, that is why I couldn't find a formula for this.

Any thoughts?

NOTES

1) I am measuring this in CPU time (user+sys).

2) My program uses quicksort

2) The asymptotic run-time analysis/complexity of my program is O(NlogN)

Sarah
  • 313
  • 3
  • 10
  • 1
    Trying to determine a formula for runtime speed would be machine dependent, that's why it's more appropriate to do complexity analysis on the source code. – C.B. Nov 14 '13 at 20:23
  • Already did the complexity analysis. I am using quicksort for my program and my complexity is O(NlogN) – Sarah Nov 14 '13 at 20:24
  • N<1000 : thread start/stop overhead, maybe OS overheads too. Passing from 1000 to 10000 must have activated performance frequency of cpu. Rest of scaling is branchprediction, cache size and your program's complexity. – huseyin tugrul buyukisik Nov 14 '13 at 20:25
  • Can you provide more detail on how you measure execution time? Are you using CPU time used or like system time from start to end? And remember O(nlogn) is only a bounds to measure against. – C.B. Nov 14 '13 at 20:25
  • Ok, I have added more details on the program. – Sarah Nov 14 '13 at 20:28
  • You are not likely to come up with an exact and reliable formula for predicting the runtime of your application. Your performance can vary widely depending on the size of your input, how cache is used, branch prediction as others have noted and any other hardware specific issues. Have a look at [this question](http://stackoverflow.com/q/11413855/416627) for an interesting discussion about cache performance. – Dave Rager Nov 14 '13 at 20:32
  • Load on the machine; benchmarks are fickle. – Elliott Frisch Nov 14 '13 at 20:33
  • If an exact formula cannot be determined? what would be an approximate formula of this? – Sarah Nov 14 '13 at 20:55
  • 1
    Seems like `time = 0.35µs * n` does the job, right ? – Alexandre C. Nov 14 '13 at 21:30
  • @AlexandreC. How could the time be linear if the algorithm contains quicksort? It simply cannot. – HAL9000 Nov 28 '13 at 22:48

2 Answers2

2

Plotting this it looks very much like you are hitting a "cache cliff" - your data is big enough so that it doesn't all fit in a cpu cache level and so must swap data between cheaper and more expensive levels

The differences at lower levels are likely due to precission - if you increase loops inside the timer block - this might smooth out

generally when hitting a cache cliff the eprformace is something like plotting O*Q

where O is the average runtime -- Nlog(N) in your case

and Q is a step function that increases as you pass the allocated size for each cache. so Q=1 below L1 size, 10 above L1 size, 100 above L2 size, etc. (numbers only for example)

In fact, there are people that verify their cache sizes by plotting a O(1) function and looking for the memory used at performance cliffs the cliffs:

           ___
 _____-----
  L1 | L2 | L3
Glenn Teitelbaum
  • 10,108
  • 3
  • 36
  • 80
0

I always use this to get precise run time..

#include<stdio.h>

#include <time.h>

#include <stdlib.h>

`clock_t startm, stopm;

`#define START if ( (startm = clock()) == -1) {printf("Error calling clock");exit(1);}

`#define STOP if ( (stopm = clock()) == -1) {printf("Error calling clock");exit(1);}

#define PRINTTIME printf( "%6.3f seconds used by the processor.", ((double)stopm-startm)/CLOCKS_PER_SEC);

`int main() {

int i,x; START;

  scanf("%d",&x);
 for(i=0;i<10000;i++){
printf("%d\n",i);

}

 STOP;
 PRINTTIME;

}

Abhishek Kaushik
  • 1,121
  • 1
  • 13
  • 17