Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership | k5 store

[P]
Precise timing in C (Diaries)

By llimllib
Wed Sep 3rd, 2003 at 01:55:54 PM EST

llimllib's Diary

So, I'm trying to time various sorts to test their performance on small, large, and medium data sets for my algorithms class. I found and used time.h and sys/time.h, but was only able to get my answers in seconds, when I need milliseconds. How does one get more precise timing in C? Is there a standard header to do this, or will I need to download a library?


Sponsors
Voxel dot net
o Managed Servers
o Managed Clusters
o Virtual Hosting


Collocated Linux/FreeBSD Server
As low as $45/month
o Root on your own FreeBSD or Linux server
o Very fast, triple-homed network
o NO hardware or setup fees, unlimited support
Testimonials from K5 Users

Login
Make a new account
Username:
Password:

Note: You must accept a cookie to log in.

Related Links
o llimllib's Diary


View: Display: Sort:
Precise timing in C | 31 comments (31 topical, 0 editorial, 0 hidden)
RDTSC (5.00 / 1) (#28)
by Bad Harmony on Thu Sep 4th, 2003 at 04:40:30 PM EST

If you are running on a reasonably modern Intel box, write a function in assembler that returns the value of the RDTSC instruction. The counter is driven by the CPU clock, so you will have to adjust for the system's clock speed to get normal units of time.

54º40' or Fight!

I'd love to (none / 0) (#29)
by llimllib on Thu Sep 4th, 2003 at 05:20:54 PM EST
(llimllib at f2o .. org)

but I don't have the skills. Care to point me to a tutorial/documentation that would make this conceivable?

Peace.
[ Parent ]
RDTSC (5.00 / 1) (#30)
by Bad Harmony on Thu Sep 4th, 2003 at 08:37:08 PM EST

What OS/compiler are you using? Here are a couple of examples that I grabbed from google:

unsigned long long read_timer() { _asm { rdtsc } }

inline __int64 __fastcall RDTSC( )
{
  _asm{
    rdtsc
  }
}

void
GetTimeNT( u64* t )
{
    u32 lo, hi;

    // Read the Time-Stamp Counter register into 'lo' and 'hi.
    __asm
    {
        // If this is the Metrowerks compiler.
#ifdef __MWERKS__

        rdtsc

#else // Visual C++ Compiler doesn't recognize the 'rdtsc'
      // instruction so the opcodes are used instead.

        __emit  0fh
        __emit  031h
#endif
        mov   lo, eax
        mov   hi, edx
    }

    // Combine the low and high 32-bit parts into a single
    // 64-bit number and return the result.
    *t = ( (u64) hi << 32 ) | (u64) lo;
}

The value returned is a 64-bit counter that is incremented by the system clock. So on a 500 MHz Pentium II, each tick is 2 nS.  To use, do something like:

int
main(int argc, char **argv)
{
  __int64 t1, t2;
  long elapsed;

  /* start measurement */
  t1 = RDTSC();

  /* call code under test */
  foo();

  /* stop measurement */
  t2 = RDTSC();

  /* compute elapsed time in microseconds, 500 MHz CPU */
  elapsed = (long) ((t2 - t1)/500);

  return 0;
};

54º40' or Fight!
[ Parent ]

myriad questions (none / 0) (#31)
by llimllib on Thu Sep 4th, 2003 at 08:54:33 PM EST
(llimllib at f2o .. org)

as for OS/compiler, I'm using linux 2.4/gcc.

  1. What is with the two types in the declaration of RDTSC() and read_timer()?
  2. Why is the GetTimeNT(...) function never called, as far as I can see?
  3. What does _asm{ rdtsc } do, and why is it in two seperate functions, each with different style, only one of which is called, as far as I can see? I assume that _asm{ ... } means execute in assembly code whatever is in the _asm block?
  4. What header file needs to be included, or is this a feature of the compiler?
  5. What does __fastcall mean?


Peace.
[ Parent ]
RDTSC (5.00 / 1) (#32)
by Bad Harmony on Thu Sep 4th, 2003 at 09:13:52 PM EST

This is supposed to work on Linux:

extern __inline__ unsigned long long int rdtsc()
   {
     unsigned long long int x;
     __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
     return x;
   }

1. Those were three different examples of reading the time-stamp counter, for different compilers. The code is compiler dependent.

2. It was just another example.

3. The _asm is a compiler directive to interpret the argument as assembly language instructions.

4. You shouldn't need any extra header files.

5. __fastcall is a keyword that tells the compiler what calling convention to use for the function. This is OS and compiler dependent.

54º40' or Fight!
[ Parent ]

gettimeofday (5.00 / 1) (#27)
by dn on Thu Sep 4th, 2003 at 01:39:30 AM EST
(k5 (at) teco (hypen) xaco (dot) com)

Use a computer that nobody else is using.

Find out what the granularity of the timer is, and make each pass through your loop take several times as long (say, 10X).

Run the measurement multiple times on identical data. Throw out the long-duration outliers: those are probably when you got preempted by something else. Average the remaining values.

Don't run anything else while it's working. Leave the mouse and keyboard alone. Pull the network plug if necessary.

Don't print the results to a terminal or file as you go: save them in memory and print them when you're through with all timing measurements. What can happen is that the next pass will get preempted by printing/saving the results for the previous pass, which breaks the numbers but you can't tell by looking.

    I ♥
 TOXIC
WASTE

Timing doesn't work in multiuser OSs (5.00 / 1) (#22)
by Stavr0 on Wed Sep 3rd, 2003 at 03:52:01 PM EST
(K5 Expendable Crewmember) http://www.kuro5hin.org/user/Stavr0/diary

If you're on anything than pure MS-DOS (not even Windows 98) all your timing (even at nanosec precision) will be broken because of the multitasking OS that takes away CPU time from your algorithm.

You'd probably want to count iterations instead. 'this while() loop was executed nnnn times, this compare was executed nnnnn times' and so on.
- - -
Pax Americana : Oderint Dum Metuant

"take away" how? (5.00 / 2) (#24)
by mikpos on Wed Sep 3rd, 2003 at 04:12:47 PM EST
(mikpos@shaw.ca)

If you mean other processes taking time away, then no problem. If you look at user time instead of real time (e.g. use setitimer()/getitimer() instead of gettimeofday()/clock()/other useless friends), you'll be close enough.

If you mean the OS itself taking time away, then MS-DOS will also take time away from the algorithm. Under MS-DOS, an ISR is called ~18 times per second to update the clock, which takes CPU time away from your algorithm. Probably quite insignificant, but then again I consider timer interrupts under other OSes to be quite insignificant as well.

Using a real-time OS might be an idea, though.

[ Parent ]

fair approximations are OK with me (5.00 / 1) (#23)
by llimllib on Wed Sep 3rd, 2003 at 03:55:19 PM EST
(llimllib at f2o .. org)

like ucblockhead suggested, I plan to run the code repeatedly, hoping to get a fair approximation of how quickly it runs.

Peace.
[ Parent ]
clock (5.00 / 2) (#16)
by ucblockhead on Wed Sep 3rd, 2003 at 03:00:01 PM EST
(ucblockhead at is.worsethanhitler.org) http://www.ucblockhead.org/journal

If you want millisecond accuracy, look at "clock()" and "CLOCKS_PER_SECOND", both of which are standard C. clock() returns the number of OS clock ticks. CLOCKS_PER_SECOND is a constant set to the number of clock ticks per second, obviously.

The accuracy depends on the OS. Under Windows, it's 10 milliseconds (I believe for Linux as well). (Though MSVC pretends to have 1 millesecond accuracy...it just always returns a multiple of ten. I believe this is for POSIX compliance.) It also starts the clock at 0 on program execution, but I believe that not all versions do that.

So you time something like this:

clock_t s = clock(); //stuff float delta = (float)(clock()-s)/(float)CLOCKS_PER_SEC;

You can get better accuracy by running a large number of times and averaging.
-----------------------
This is k5. We're all tools - duxup

Thought of using a profiler? (5.00 / 2) (#15)
by 5pectre on Wed Sep 3rd, 2003 at 02:47:42 PM EST
(spectre (at) thinkgeek (dot) co (dot) uk) http://www.thinkgeek.co.uk

I got a B for this piece of crap ;)

"Let us kill the English, their concept of individual rights might undermine the power of our beloved tyrants!!" - Lisa Simpson [ -1.50 / -7.74]

I like the Cartman quote (5.00 / 1) (#18)
by llimllib on Wed Sep 3rd, 2003 at 03:09:11 PM EST
(llimllib at f2o .. org)

and the goofy style of writing. What's with the underneath the line quotes, though?

Peace.
[ Parent ]
Underneath the line? (5.00 / 2) (#20)
by 5pectre on Wed Sep 3rd, 2003 at 03:32:13 PM EST
(spectre (at) thinkgeek (dot) co (dot) uk) http://www.thinkgeek.co.uk

Well, I mainly put the quotes in to fill out the report, it was supposed to be 6 pages and I only did three. The professor in question called the assignment "Find out the best sorting algorithm for Unnaturally Pneumatic Lady Relic Thief VI", so i guessed he wouldn't mind the humour ;)

This is the email I got from him:

Your grade was: B Comments (if any) that you may find useful: "Good C code let down by lack of code comments and dubious testing. All three sorts have near-identical results, which is wrong. The report was a little short of information and analysis, though it's always nice to see Eric Cartman playing his part in computer science. Sorry about the mark but remember, ""you will respect my authoritaah!"""



"Let us kill the English, their concept of individual rights might undermine the power of our beloved tyrants!!" - Lisa Simpson [ -1.50 / -7.74]

[ Parent ]

I need to have your professor (5.00 / 1) (#21)
by llimllib on Wed Sep 3rd, 2003 at 03:34:13 PM EST
(llimllib at f2o .. org)

seriously.

Peace.
[ Parent ]
Additional info. (5.00 / 2) (#12)
by i on Wed Sep 3rd, 2003 at 02:40:30 PM EST

Look up the introsort whitepaper and see how the authors measured performance of various algorithms.

People with sigs that reverse the reply line are gay

will do (none / 0) (#14)
by llimllib on Wed Sep 3rd, 2003 at 02:45:57 PM EST
(llimllib at f2o .. org)

plus, that sort looks cool, and I don't think it's in my book. I can't read the paper now, no .ps file reader on these computers. Thanks.

Peace.
[ Parent ]
Under BSD (5.00 / 1) (#10)
by omghax on Wed Sep 3rd, 2003 at 02:34:56 PM EST
(onlyihavehandle@hotmail.com)

There are function calls like getrusage(2) - I don't know the resolution but they could be helpful, check your documentation.

Consider compiling separate programs for each sort and using "time" or "timex" to get a measurement.

Additionally, you could write a small timer routine in assembly (80x86 and VAX are among the architectures that provide easy ways to do this) and use it in your program.

AHA (5.00 / 1) (#11)
by omghax on Wed Sep 3rd, 2003 at 02:38:55 PM EST
(onlyihavehandle@hotmail.com)

Look into clock_gettime(3) - nanosecond resolution and POSIX compliant to boot.

[ Parent ]
time structure (none / 0) (#13)
by llimllib on Wed Sep 3rd, 2003 at 02:43:23 PM EST
(llimllib at f2o .. org)

It appears that what I missed was the tv_usec or tv_nsec part of the timeval (or timespec) structure, which holds the milliseconds. Appreciate the help, I'll be done TAing this lab in 5 minutes, I'll go home and test it.

Peace.
[ Parent ]
be careful (5.00 / 1) (#17)
by ucblockhead on Wed Sep 3rd, 2003 at 03:06:16 PM EST
(ucblockhead at is.worsethanhitler.org) http://www.ucblockhead.org/journal

Just because it has a nanosecond field doesn't mean that it is accurate to one nanosecond.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]
understood (none / 0) (#19)
by llimllib on Wed Sep 3rd, 2003 at 03:10:38 PM EST
(llimllib at f2o .. org)

man page reading will wait until I am on my machine...the last kids haven't left yet...

Peace.
[ Parent ]
Template. (5.00 / 1) (#7)
by awgsilyari on Wed Sep 3rd, 2003 at 02:18:48 PM EST
(moc.wnlaruen@ttocs)

struct timeval begin_tv, end_tv;

void begin_timer()
{
    gettimeofday(&begin_tv);
}

double end_timer()
{
    double elapse;

    gettimeofday(&end_tv);
    elapse  = (double)end_tv.sec + (double)end.tv_usec * 1e-6;
    elapse -= (double)begin_tv.sec + (double)begin.tv_usec * 1e-6;
    return elapse;
}

--------
Please direct SPAM to john@neuralnw.com

GetTimeOfDay. (3.50 / 2) (#4)
by squigly on Wed Sep 3rd, 2003 at 02:11:40 PM EST
(squigs@postmaster.co.uk)

In <sys/time.h> under Unix, there's a GetTimeOfDay function that gives microsecond precision.  

Really, you shouldn't use these though since executionm time can vary depending on load.  Profilers (e.g. gprof) give a much better result.

Not necessarily (5.00 / 3) (#8)
by awgsilyari on Wed Sep 3rd, 2003 at 02:23:37 PM EST
(moc.wnlaruen@ttocs)

gprof is a sampling profiler, meaning it just examines the value of the program counter in small slices to see where execution is.

Anyone with a background in signal theory will tell you that this is prone to temporal aliasing. If a routine is being invoked at nearly the same frequency as the profiler, you'll see temporal "interference," with the function appearing to either take way more time than it really does, or way less.

gprof adds function prolog/epilog code to keep correct invocation counts. But the timings can be off massively in certain circumstances.

If you want to profile the execution time of a particular routine, the best way is to actually insert a timing call.

--------
Please direct SPAM to john@neuralnw.com
[ Parent ]

I've never done this sort of timing (none / 0) (#5)
by llimllib on Wed Sep 3rd, 2003 at 02:16:39 PM EST
(llimllib at f2o .. org)

And once I'm back on my machine, I'll try gprof. I guess it never struck me that there were tools to do this outside of code. duh.

Right now, I'm being a TA in a comp sci 1 class though, stupid windows lab machines.

Peace.
[ Parent ]
I have seen the light! (5.00 / 1) (#3)
by llimllib on Wed Sep 3rd, 2003 at 02:03:27 PM EST
(llimllib at f2o .. org)

Practical answers and empirical evidence be damned! Head for the high hills of theory, for that is where the only *real* work is! Math never lies!

Peace.
You are correct it never does lie [nt] (5.00 / 1) (#6)
by StormShadow on Wed Sep 3rd, 2003 at 02:17:30 PM EST
(Proud To Be An American:) Where At Least I Know I Am Free



-----------------
oderint dum metuant - Cicero
We aren't killing enough of our [America's] enemies. Re-elect Bush in 2004 - Me
12/2003: This account is now closed. Password scrambled. Its been a pleasure.


[ Parent ]
ehhh (none / 0) (#9)
by llimllib on Wed Sep 3rd, 2003 at 02:27:55 PM EST
(llimllib at f2o .. org)

Within its own system, it does not lie. Math, as a system, is based on logical consistency. As such, correct mathematical statements cannot technically lie. However, predicted results are often very different from actual ones, making the math appear to lie. So, IMHO, math both lies and doesn't.

Peace.
[ Parent ]
That is twisted logic... (none / 0) (#25)
by StormShadow on Wed Sep 3rd, 2003 at 08:00:55 PM EST
(Proud To Be An American:) Where At Least I Know I Am Free

...the experimental results differ from the theoretical because of uncertainties, errors, approximations or incomplete knowledge not because the mathematics "lies" -- a lie by definition is an attempt at deception. If you walk over to me and ask where is the local public library and I give you the wrong answer because I myself am misinformed, did I lie to you? Of course not.


-----------------
oderint dum metuant - Cicero
We aren't killing enough of our [America's] enemies. Re-elect Bush in 2004 - Me
12/2003: This account is now closed. Password scrambled. Its been a pleasure.


[ Parent ]
all I'm saying (5.00 / 1) (#26)
by llimllib on Wed Sep 3rd, 2003 at 10:32:38 PM EST
(llimllib at f2o .. org)

is that mathematics is not truth when it's translated to the world. Many people accept that a model is truth without considering that it may differ from the real world in reality.

Peace.
[ Parent ]
Check (5.00 / 2) (#2)
by jgerman on Wed Sep 3rd, 2003 at 02:01:34 PM EST
(jgermank5NO@SPAMyahoo.com)

setitimer(2) though there are some gotcha's if I recall.

Google around for high resolution timers in C and you shoudl turn something up.


if textbooks were a kuro5hin user, they would probably be Silent Chris. because textbooks piss me off. -- anaesthesis

Precise timing in C | 31 comments (31 topical, 0 editorial, 0 hidden)
View: Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest © 2000 - 2003 Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
Erik Benson is a deadbeat.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories! K5 Store by Jinx Hackwear Syndication Supported by NewsIsFree