Thread: Measuring Run Time

Okay so here is the starter code utilising the clock() function:

Code:

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


/* binary search algorithm */

int binsearch(int x, int v[], int n);

int main()
{
	int myarray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

	clock_t start = clock(); /* start clock */

	printf("%d\n", binsearch(3, myarray, 10));

	clock_t finish = clock(); /* stop clock */

	printf("It took %d seconds to execute the binary search.\n",
			(finish - start) / CLOCKS_PER_SEC);
	printf("It took %d clock cycles per second to 
        execute the binary search.\n", (finish - start));

	return 0;
}

int binsearch(int x, int v[], int n)
{
	int low, high, mid;

	low = 0;
	high = n -1;
	while (low <= high) {
		mid = (low+high)/ 2;
		if (x < v[mid])
			high = mid + 1;
		else if (x > v[mid])
			low = mid + 1;
		else	/* found match */
			return mid;
	}

	return -1; /* No Match */
}

I'm having two problems though:

1) I get the following error in relation to printing of the time:

Code:

"format '%d' expects type 'int', but argument 2 has type 'clock_t"

2) The binary search hangs with inputs of 4 and 6 for the key value 'x'. Strange considering the code has not yet been modified from the book :?

Any ideas?

Thanks as always

BIOS

Originally Posted by BIOS

1) I get the following error in relation to printing of the time:

Code:

"format '%d' expects type 'int', but argument 2 has type 'clock_t"

printf doesn't have a format specifier for clock_t variables. You either have to cast, or convert to a struct tm and use strftime, then printf that result.

2) The binary search hangs with inputs of 4 and 6 for the key value 'x'. Strange considering the code has not yet been modified from the book :?

Books are not infallible. Look at the following two lines:

Code:

high = mid + 1;
low = mid + 1;

Why are they both the same? high should be adjusted to mid - 1, moving it below the previous value of mid, which was too big.

Originally Posted by megafiddle

Well it does depend on the code under test.

But I was also including the loop counter increment and test. That's also done 100 million times.

Yeah but it's dirt cheep. A loop is essentially two instructions: increment and branch. Both are cheep for a loop, particularly a large one. Compare that to a function call which involves pushing all the arguments on the stack, adjusting the stack pointer twice, and two jumps.

Originally Posted by BIOS

Gotcha. How come it still prints though?

There's two distinct parts to calling printf with extra args. The first is what you pass in. You passed in a clock_t. It's probably just an int under the hood (but you don't know unless you rip your implementation apart), nor should you care. You told it to pass in a clock_t, so the compiler generated code to pass a clock_t to printf. Now, the guts of printf don't know what you passed it, they just have to trust your extra params match the % specifiers in the format string. You said %d, so printf assumes an int is next. But if it tries to take 8 bytes for that int, and you only gave it 4 for a clock_t, you'll end up with garbage. Like I said, in this case, an int and a clock_t are probably the same size, so you're getting away with it, but technically it's wrong, and might not work everywhere.

You can also time the entire process from the shell with time, for example:

$ time ./a.out


And on OS X you have mach_absolute_time(), and of course Instruments which has a time profiler among other things.

Relative time may be more precise for measuring improvements, but it won't provide the benchmark to tell you if the code needs improvement in the first place.