Like Tree1Likes

Measuring Run Time

This is a discussion on Measuring Run Time within the C Programming forums, part of the General Programming Boards category; Originally Posted by quzah Also, since you used Turbo C, you don't even have numbers as big as 100 million, ...

  1. #16
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by quzah View Post
    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.
    Quzah.
    Hey, my friend... Don't give up that day job!

  2. #17
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55
    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
    Last edited by BIOS; 09-13-2011 at 11:36 AM.

  3. #18
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Quote Originally Posted by BIOS View Post
    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.
    Last edited by anduril462; 09-13-2011 at 11:50 AM.

  4. #19
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55
    Quote Originally Posted by anduril462 View Post
    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.
    Gotcha. How come it still prints though?

    Quote Originally Posted by anduril462 View Post
    Books are not infallible.
    Indeed! My bad there. Thanks.

  5. #20
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Quote Originally Posted by megafiddle View Post
    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  6. #21
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Quote Originally Posted by BIOS View Post
    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.
    Last edited by anduril462; 09-13-2011 at 12:25 PM.

  7. #22
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    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.
    Last edited by Subsonics; 09-13-2011 at 12:27 PM.

  8. #23
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55
    Okay cool. So I just got lucky in this case :P Will make sure to read up on the library Thanks

  9. #24
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55
    Should the number of clock cycles per second change even if the input is the same between executions?

  10. #25
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    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.

  11. #26
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55
    I've got core i5's. Could you elaborate a bit more on relative time?

  12. #27
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    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.

  13. #28
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55
    Gotcha. Thanks for the pointers

  14. #29
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  15. #30
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    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.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. measuring function execution time
    By nik in forum C++ Programming
    Replies: 5
    Last Post: 03-12-2011, 09:21 PM
  2. measuring time in ms/us/ns
    By wanwan in forum C Programming
    Replies: 3
    Last Post: 04-29-2005, 02:42 PM
  3. measuring time of execution
    By KevBin in forum C Programming
    Replies: 6
    Last Post: 12-02-2004, 02:08 PM
  4. Measuring time
    By BruceLeroy in forum C++ Programming
    Replies: 20
    Last Post: 10-07-2004, 03:17 PM
  5. Measuring time of a reply
    By Zewu in forum C++ Programming
    Replies: 5
    Last Post: 10-27-2003, 12:37 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21