Need help finding the running time of a function in C

[cchen]

SO right now I'm programming some sorting algorithms and finding their actual running time....

To do this, I'm doing something like this:

time1=(clock()/CLOCKS_PER_SEC)*pow(10,3); // time in milliseconds
heapSort(temp,n);
time2=(clock()/CLOCKS_PER_SEC)*pow(10,3);
actualtime=time2-time1;
printf("This took %f\n",actualtime);

where actualtime, time2, and time1 are all floats

However, when I do this, I keep on getting 0 as the output. I think that my code is correct. Why would I get 0 as the running time?

 

[FatAlbo]

One run isn't necessarily the best indicator. Try doing multiple trials and then finding the average time per trial.

 

[cchen]

I understadn.... however my output is 0... once I get the value to at least print correctly I can do that....

 

[igowerf]

Make sure that in "clock()/CLOCKS_PER_SEC", at least one value is a float or double. If "clock()/CLOCKS_PER_SEC" divides to less than one and both values are ints, then you'll get 0.

Also, what happens when you printf() time1 and time2? What values do they have?

 

[cchen]

When I printf time1 and time2 I also get 0...

 

[igowerf]

What kind of value does clock() return and what value does CLOCKS_PER_SEC have?

 

[cchen]

CLOCKS_PER_SEC is system dependent
clock() returns a value in "clicks" which is related to CPU cycles....

clock()/CLOCKS_PER_SEC gives seconds...

 

[PrincessGuard]

1) You can use the constant 1000 instead of pow(10,3) to reduce that overhead.

2) Don't divide by CLOCKS_PER_SEC until you need to (i.e. in the printf()).

3) clock() returns clock_t. Make time1 and time2 type clock_t then cast to float when you need to.

 

[cchen]

I'm still getting 0....
This is what I changed

time1=clock();
heapSort(temp,n);
time2=clock();
actualtime=((float)((time2-time1)/CLOCKS_PER_SEC))*1000;
printf("This took %f\n",actualtime);
where time1 and time 2 are both time_t

 

[PrincessGuard]

Are time1 and time2 still 0 separately?

 

[cchen]

For some reason... clock is giving me the same time for time1 and time2.... ???????

 

[PrincessGuard]

Maybe your function is so fast that clock() can't catch it. CLOCKS_PER_SEC on my system is 1000, which gives me only millisecond resolution. That means any operation that takes less than 1ms (which is a long time in CPU terms) will show 0 clocks.

Stick a giant for() loop in there. Something like

long i;
for(i=0; i<100000000; i++);

should be noticible.

 

[cchen]

IF this is the case.... how else could I get the running time of the function?

 

[igowerf]

In my AP CS class, we used a prewritten StopWatchClass. Here's the code for the class:

/* Lawrenceville Press March 1998 */
/* Simple wrapper class to ease use of time facilties */
/* in dos.h for finding program times. */

// compiled if Microsoft compiler
#if defined (_MSC_VER)
#include <sys\types.h>
#include <sys\timeb.h>

class StopWatchClass {
public:
StopWatchClass(); // Creates and resets watch
void Reset(); // Resets watch to 0.00
double Reading(); // Returns current reading on watch
private:
struct _timeb MyTime;
};
//------------------------------------
StopWatchClass::StopWatchClass()
{
_ftime(&MyTime);
}
//------------------------------------
void StopWatchClass::Reset()
{
_ftime(&MyTime);
}
//------------------------------------
double StopWatchClass::Reading()
{
struct _timeb t2;
_ftime(&t2);
double diff = (t2.time - MyTime.time)+
(t2.millitm - MyTime.millitm)/1000.0;
return diff;
}

#endif

//-------------------------------------------------------------------
// compiled if not Microsoft compiler
#ifndef _MSC_VER
#include <dos.h>

class StopWatchClass {
public:
StopWatchClass(); // Creates and resets watch
void Reset(); // Resets watch to 0.00
double Reading(); // Returns current reading on watch
private:
struct time MyTime;
};
//------------------------------------
StopWatchClass::StopWatchClass()
{
gettime(&MyTime);
}
//------------------------------------
void StopWatchClass::Reset()
{
gettime(&MyTime);
}
//------------------------------------
double StopWatchClass::Reading()
{
struct time t2;
gettime(&t2);
double diff = 3600.0*(t2.ti_hour - MyTime.ti_hour)+
60.0*(t2.ti_min - MyTime.ti_min)+
(t2.ti_sec - MyTime.ti_sec)+
(t2.ti_hund - MyTime.ti_hund)/100.0;
return diff;
}

#endif

You can run it like this:

StopWatchClass Watch;
Watch.Reset();
myFunction();
myTime=Watch.Reading();

 

[glugglug]

Windows system clock only updates once every 15ms, or more accurately 1/64 s. (Which is an improvement from the 55ish ms resolution in DOS....)

If you want higher resolution, use QueryPerformanceCounter and QueryPerformanceFrequency.

QueryPerformanceCounter/QueryPerformanceFrequency = system up time in seconds. You only need to get the frequency once as this should be constant, but the overhead of getting either is really low so it doesn't matter too much.

use them like this:
double uptime()
{
__int64 perfFreq;
__int64 perfCount;
QueryPerformanceFrequency(&(LARGE_INTEGER*)&perfFreq);
QueryPerformanceCounter(&(LARGE_INTEGER*)&perfCount);
return 1.0*perfCount/perfFreq;
}

For a single CPU system only, look up RDTSC on google. There should be assembly examples somewhere that use this. It returns the CPU cycle counter on everything Pentium & up (not sure if AMD first implemented it in K6 or in K5). So if you have a 2 GHz processor the resolution is 0.5ns.

CLOCKS_PER_SEC returns 1000 in almost every implementation I've seen but its pretty much a lie (propagated by the GetTickCount API call I guess which also uses milliseconds as units, but similarly does NOT have millisecond resolution).

 

[cchen]

hmm, i guess i can try this implementation... but are you sure that large integer works in c?
btw.... this is going to be compiled using gcc... i think the implementation you showed me only works for windows?

 

[glugglug]

QueryPerformanceCounter is windows specific.

dunno what the equivalent API call in linux would be but you can get high resolution timing with this C/assembly function found

here which returns uptime in CPU-cycles (so you have to know what speed your machine is running at)

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

(long long is the same thing as __int64)

 

[Krakerjak]

I don't know of any other way of timing code, in C under dos, except for the 55msec method.

In the case of fast code you would have to run the code SEVERAL times to get a accurate timing measurement and divide down.