Measuring Time Spent Executing Function

Question

edit: I've figured it out. The 2nd algorithm was running so efficiently that the time wasn't even being recorded with an input < 100,000

I'm trying to measure how long a certain algorithm that I have implemented in a function takes to execute. I've included <time.h> and I'm surrounding the function around time_t variables. It works great for my first implementation, but not my second.

Do I need to close the clock stream (can't think of a better work)between uses? Kind of like how you close the Scanner stream in a Java program. Here's my code in case I am not explaining it well.

switch(choice) { case 1: printf("Beginning prefixAverages1\n"); clock_t begin1 = clock(); int *a1 = prefixAverages1(input); clock_t end1 = clock(); double time_spent1 = (double)(end1 - begin1) * 1000.0 / CLOCKS_PER_SEC; free(a1); printf("Algorithm took %f milliseconds to execute \n", time_spent1); break; case 2: printf("Beginning prefixAverages2\n"); clock_t begin2 = clock(); int *a2 = prefixAverages2(input); clock_t end2 = clock(); double time_spent2 = (double)(end2 - begin2) * 1000.0 / CLOCKS_PER_SEC; free(a2); printf("Algorithm took %f milliseconds to execute \n", time_spent2); break; default: printf("Invalid input!"); break; }

Time is displayed properly in my 1st case, but not in the second. I've tried doing some research but I can't find anything particular to my scenario.

When running case 1, depending on the input, I get a time between 600-1000 ms to run (which sounds about right). When I run case 2, regardless of the input, I get 00.000

Here are my functions if that helps:

int* prefixAverages1(int input) { int x[input]; int *a = malloc(input*sizeof(*a)); srand(time(NULL)); for(int i = 0; i < input; i++) { int sum = 0; for(int j = 0; j < i; j++) { int r = rand() % 100; x[j] = r; sum = sum + x[j]; } a[i] = sum / (i+1); } return a; } int* prefixAverages2(int input) { int sum = 0; int x[input]; int *a = malloc(input*sizeof(*a)); srand(time(NULL)); for(int i = 0; i < input; i++) { int r = rand() % 100; x[i] = r; sum = sum + x[i]; a[i] = sum / (i+1); } return a; }

How do you know the time is improper in the second case? What do you get from the first and second? How long do the functions actually take to run? If they're under a number in the 50 ms range, the timing is likely to be unreliable, IMO — and longer than that would be better. But you really need to show what it is that you're getting. — Jonathan Leffler
– Jonathan Leffler, Commented May 23, 2018 at 0:18
@JonathanLeffler You're right. Sorry about that. I've edited the post. — InfoSecNick
– InfoSecNick, Commented May 23, 2018 at 0:21
Looks like the measurements should be accurate. Have you tried executing the 2nd choice and THEN the first? en.wikipedia.org/wiki/CPU_cache#CPU_stalls. Although 600ms worth of memory time is far more than a modern CPU can cache as far as I know (generally speaking) — zzxyz
– zzxyz, Commented May 23, 2018 at 0:32
Add a sleep between begin2 and end2 - that will tell you if timing is a problem or the 2nd algorithm is really fast... — John3136
– John3136, Commented May 23, 2018 at 0:34
@InfoSecNick I mean optimized to the point where the compiler eliminates the call to prefixAverages2 completely. Since the code never uses the return value (except to free it), if prefixAverages2 has no side-effects the compiler might eliminate the call completely. Try compiling with and without optimizations. Or do something with the contents of a2, like printing them. Maybe you should show us prefixAverages2. — Schwern
– Schwern, Commented May 23, 2018 at 0:48

Schwern · Accepted Answer · 2018-05-23 05:46:08Z

While I don't know why the second choice might be 0, since the two functions have the same signature you can eliminate the redundant code by using function pointers.

void do_benchmark( const char *name, int*(*functionPtr)(int), int input ) { printf("Beginning %s\n", name); clock_t begin = clock(); int *ret = (*functionPtr)(input); clock_t end = clock(); double time_spent = (double)(end - begin) * 1000.0 / CLOCKS_PER_SEC; free(ret); printf("Algorithm took %f milliseconds to execute \n", time_spent); }

Then both functions are run with the same timing code, eliminating differences in the benchmarking code as the culprit.

switch(choice) { case 1: do_benchmark("prefixAverages1", &prefixAverages1, input); break; case 2: do_benchmark("prefixAverages2", &prefixAverages2, input); break; default: printf("Invalid input!"); break; }

Note that clock can fail.

If the processor time used is not available or its value cannot be represented, the function returns the value (clock_t)(-1).

You'll want to check for that failure.

if( begin == (clock_t)-1 ) { fprintf(stderr, "Begin time not available.\n"); } else if( end == (clock_t)-1 ) { fprintf(stderr, "End time not available.\n"); } else { double time_spent = (double)(end - begin) * 1000.0 / CLOCKS_PER_SEC; printf("Algorithm took %f milliseconds to execute \n", time_spent); }

zzxyz · Accepted Answer · 2018-05-23 02:19:33Z

I'm more familiar with doing this on Windows using QueryPerformanceCounter, so I'm probably doing all sorts of bad stuff here, but the basic idea for measuring short loops:

int main() { printf("Beginning prefixAverages2\n"); timespec begin, end; clock_gettime(CLOCK_REALTIME, &begin); int *a1 = prefixAverages2(50000); clock_gettime(CLOCK_REALTIME, &end); double time_spent = (end.tv_nsec - begin.tv_nsec) / 1000; time_spent += (end.tv_sec - begin.tv_sec) *1000000; free(a1); printf ("Time spent %f microseconds", time_spent); }

Output:

Beginning prefixAverages2 Time spent 427.000000 microseconds

PS--It turns out clock() doesn't do wall time: Calculate execution time when sleep() is used

Collectives™ on Stack Overflow

Measuring Time Spent Executing Function

2 Answers 2

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Linked

Related