Daily Archives: June 27, 2005

Code Timing functions

When it comes to timing your code, there are a lot of options, and depending on what you need to do, not all of them make sense. There are timing functions which utilize callbacks and other ways to periodically call a designated function at a regular interval–I’m not going to discuss those types of timers.

Instead, I’ll focus on the kinds of timing you can do to assess code performance.

To illustrate the differences between these methods, let’s have a simple C++ program:

[code lang=”cpp”]
#include
#include

using namespace std;

int main(int argc, char** argv)
{
//begin timing

//test code
const int nLimit = 10000000;
double sum = 0;

for (int i=0;i {
double rt = sqrt(static_cast(i));
sum+=rt;
}

//end timing

cout << “sum: “<

cout << elapsed << ” second(s) total”< cout << avg << ” second(s) average iteration”<

return 0;
}[/code]

I deliberately chose something simple and fast. Here’s why: if you’re timing something that always takes an hour–a second doesn’t matter, and the first option will work perfectly fine. On the other hand, if you need to time something small that will potentially be repeated dozens, hundreds, thousands, or millions of times, every microsecond can matter.

time_t and CTime

time() is the good old C standby. It’s simple, it’s easy, it’s historic, and it’ll break after 19:14:07, January 18, 2038, UTC.

To remedy this, Microsoft has the _time64() function, which uses the type __time64_t. It improves the lifespan, but not the precision.

Our code is now:
[code lang=”cpp”]
#include
#include
#include

using namespace std;

int main(int argc, char** argv)
{
//begin timing
time_t start = time(NULL);

//test code
const int nLimit = 10000000;
double sum = 0;

for (int i=0;i {
double rt = sqrt(static_cast(i));
sum+=rt;
}

//end timing
time_t end = time(NULL);
cout << “sum: “< long elapsed = static_cast(end – start);
double avg = (double)elapsed / nLimit;
cout << elapsed << ” second(s) total”< cout << avg << ” second(s) average iteration”<

return 0;
}[/code]

Output:
sum: 2.10819e+013
16 second(s) total
0 second(s) average iteration

MFC’s CTime is just a wrapper for time_t (VC++6.0) or __time64_t (VC++7), so nothing new here.

time_t is good when you don’t need very precise measurements, when you’re just interested in the date and/or time, as in wall-clock time, or when it’s your only option.

For timing code, this is not a great option.

GetTickCount

Windows contains a function called GetTickCount which returns the number of milliseconds since the machine was turned on. This gives us 1,000 times better accuracy then time().

[code lang=”cpp”]
#include
#include
#include

using namespace std;

int main(int argc, char** argv)
{
//begin timing
DWORD start = GetTickCount();

//test code
const int nLimit = 10000000;
double sum = 0;

for (int i=0;i {
double rt = sqrt(static_cast(i));
sum+=rt;
}

//end timing
DWORD end = GetTickCount();
cout << “sum: “< double elapsed = (end – start) / 1000.0;//ms –> s
double avg = ((double)elapsed)/ nLimit;
cout << elapsed << ” second(s) total”< cout << avg << ” second(s) average iteration”<

return 0;
}[/code]

Output:
sum: 2.10818e+010
0.172 second(s) total
1.72e-008 second(s) average iteration

As seen above, this value is returned in a DWORD, which is 32-bits wide. 232 milliseconds comes out to about 49 days, at which time the counter rolls over to 0. If you’re timing very short intervals, this probably won’t be a problem. The MSDN documentation has a code example to detect timer wrap-around.

GetTickCount provides much more precision than time_t, but with processor speeds at multiple gigahertz, a lot can happen in a millisecond. Enter…

QueryPerformanceCounter and QueryPerformanceFrequency

This set of functions is also available in the Win32 API and they are much more accurate than time_t and GetTickCount.

Their usage is often paired. QueryPerformanceCounter returns the current count on the timer, and QueryPerformanceFrequency returns how many counts per second there are. The documentation makes clear that timer frequency is not the same as processor clock frequency. This timer is hardware-based, however, and if your computer doesn’t have a timing device, then calling QueryPerformanceCounter returns the same thing as GetTickCount above, and QueryPerformanceFrequency returns 1000 (1000 ms = 1 s).

The code reads:

[code lang=”cpp”]
#include
#include
#include

using namespace std;

int main(int argc, char** argv)
{
//begin timing
LARGE_INTEGER start;
::QueryPerformanceCounter(&start);

//test code
const int nLimit = 10000000;
double sum = 0;

for (int i=0;i {
double rt = sqrt(static_cast(i));
sum+=rt;
}

//end timing
LARGE_INTEGER end;
LARGE_INTEGER countsPerSecond;
::QueryPerformanceCounter(&end);
::QueryPerformanceFrequency(&countsPerSecond);

double elapsed = (double)(end.QuadPart – start.QuadPart) / countsPerSecond.QuadPart;
double avg = elapsed / nLimit;
cout << “sum: “< cout << elapsed << ” second(s) total”< cout << avg << ” second(s) average iteration”<

return 0;
}[/code]

Output:
sum: 2.10818e+010
0.165298 second(s) total
1.65298e-008 second(s) average iteration

You can easily see the much improved precision.

OK, well these are all well and good if you have Windows, but what if you don’t have Windows, or the time isn’t as important as the number of cycles required to compute something?

Here’s…

GetMachineCycleCount

…a function to read the current CPU clock cycle. Note that there aren’t any API or standard library functions to do this so we need to use assembly. Note also that this wasn’t possible until the Pentium came along, so don’t run this code on a pre-Pentium computer. 🙂

[code lang=”cpp”]
#include
#include

using namespace std;

inline __int64 GetMachineCycleCount()
{
__int64 cycles; //64-bit int

_asm rdtsc; // won’t work on 486 or below – only pentium or above
_asm lea ebx,cycles; //ebx = &cycles
_asm mov [ebx],eax; //get low-order dword
_asm mov [ebx+4],edx; //get hi-order dword

return cycles;
}

int main(int argc, char** argv)
{
//begin timing

__int64 start = GetMachineCycleCount();

//test code
const int nLimit = 10000000;
double sum = 0;

for (int i=0;i {
double rt = sqrt(static_cast(i));
sum+=rt;
}

//end timing
__int64 end = GetMachineCycleCount();

cout << “sum: “< __int64 elapsed = end – start;
double avg = (double)elapsed / nLimit;
cout << elapsed << ” cycles total”< cout << avg << ” cycles average iteration”<

return 0;
}[/code]

Output:
sum: 2.10818e+010
263631085 cycles total
26.3631 cycles average iteration

What are some situations where this is useful? If you want to make a piece of code absolutely the fastest on any piece of hardware, regardless of clock-time, this can give you a truer reflection of the effectiveness of your algorithm. If you don’t have a high-performance timer API (and you don’t want to write one), then this is a quick-and-dirty, but effective, solution.

So what about discovering the speed of your processor? Well, there’s no machine instruction to do this. Basically, you have to combine the cycle count with the performance timers and run through a lot of loops to calculate an average.

I hope this has helped some people wade through the various options of timing performance-critical code.