Currently I'm studying from 'The C Programming Language' and it asks you to modify some code and then compare the run times. What is the best way to do this?
Printable View
Currently I'm studying from 'The C Programming Language' and it asks you to modify some code and then compare the run times. What is the best way to do this?
Code:#include <windows.h>
unsigned long int Time = GetTickCount();
// do whatever it is in here
printf("That took %ld milliseconds", GetTickCount() - Time);
Thanks for the reply. Any idea how I could do it on os x? :P
I'm sure they have equivalent functions... Google is your friend.Quote:
Originally Posted by BIOS
Can be pretty accurate.
gettimeofday
Portable.
clock
Anything sub-second needs a bit of care to make sure it is done well.
The accuracy and precision of any fast clock you can get at can vary from one machine to another.
Heck they can vary within the same machine... depending what else is running. But as a rule they're good enough for non-critical functions.Quote:
Originally Posted by Salem
Had a feeling you'd say this! :P I did actually google first but figured asking would be quicker than trawling.Quote:
Originally Posted by CommonTater
@salem Thanks. Clock seems perfect :)
Just in case anyone else digs up this thread in future. Here is some example code showing how to use clock():
outputs:Code:#include <stdio.h>
#include <time.h>
#include <math.h>
int main()
{
clock_t start = clock();
for (long i = 0; i < 100000000; ++i)
exp(log((double)i));
clock_t finish = clock();
printf("It took %d seconds to execute the for loop.\n",
(finish - start) / CLOCKS_PER_SEC);
return 0;
}
Code:It took 23 seconds to execute the for loop.
+1 for using the standard clock() function. Good job, BIOS.
If you're trying to measure something short, like a single statement, you should subtract off the
loop overhead, as it can be a significant part of the execution time.
Just run the same time measurement on the the same loop empty.
Then subtract that off the loop with the code under test in it.
And might as well convert the result to time per single pass also.
If the loop is empty, your compiler may optimize it out, throwing the loop out completely.
Quzah.
Also... compared to the time for 100 million floating point calculations, the loop overhead is probably trivial...Quote:
Originally Posted by quzah
Next actually assign the result to something... a = exp(log((double) i)); ... Optimization may have run an empty loop...Quote:
Originally Posted by BIOS
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.
Also, since you used Turbo C, you don't even have numbers as big as 100 million, so your loop didn't really run that many times. ;) :D :DQuote:
Originally Posted by CommonTater
Quzah.
Hey, my friend... Don't give up that day job! :tongue:Quote:
Originally Posted by quzah
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:
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 :?Code:"format '%d' expects type 'int', but argument 2 has type 'clock_t"
Any ideas?
Thanks as always
BIOS
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.Quote:
Originally Posted by BIOS
Books are not infallible. Look at the following two lines:Quote:
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 :?
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.Code:high = mid + 1;
low = mid + 1;
Gotcha. How come it still prints though?Quote:
Originally Posted by anduril462
Indeed! My bad there. Thanks.Quote:
Originally Posted by anduril462
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.Quote:
Originally Posted by megafiddle
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.Quote:
Originally Posted by BIOS
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.
Okay cool. So I just got lucky in this case :P Will make sure to read up on the library ;) Thanks
Should the number of clock cycles per second change even if the input is the same between executions?
What CPU do you have? The core i archtecture CPUs from intel can vary the clock based on work load. But runtime will vary from time to time, depending on what else is going on, if the process is still in memory and/or cache. Absolute runtime also depends on what machine you are running on, it's probably more interesting to look at relative time, what it is that takes time and so on.
I've got core i5's. Could you elaborate a bit more on relative time?
My point was that it's probably more interesting to look for what it is that takes time, and wether a change to the code gives an improved performance relative to the old time.
Gotcha. Thanks for the pointers ;)
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.
Wouldn't the indication of that be that you experience some kind of problem? Unless you are talking about some realtime process with a deadline. Otherwise it seems like a moving target.