Measuring algorithm speed.

[Chad]

Okay, after having a lot of brain farts regarding hashtables, I've come
to the general conclusion that it might be instructional if I could
'measure' how fast the algorithm executed. Question now becomes how do
I do this. I'm currently running both Suse Linux 9.1 and FreeBSD 4.8 on
a standard PC that I purchased from CompUSA a while back. I was
probably going to use either C or C++ for this demo.

I'm at a loss how to go about coding this. I was maybe thinking along
the lines of having an initial time (ie current time) before the loop
gets executed, then get the time after the loop gets executed. The
difference would be how long it took that portion of the program to
execute. I would maybe store these values in an separate file. Ideas?

Chad

[Chris McDonald]

"Chad" <cda...@gmail.com> writes:

>I'm at a loss how to go about coding this. I was maybe thinking along
>the lines of having an initial time (ie current time) before the loop
>gets executed, then get the time after the loop gets executed. The
>difference would be how long it took that portion of the program to
>execute. I would maybe store these values in an separate file. Ideas?

If coding in C, the following may help.

______________________________________________________________________________
Dr Chris McDonald E: ch...@csse.uwa.edu.au
Computer Science & Software Engineering W: http://www.csse.uwa.edu.au/~chris
The University of Western Australia, M002 T: +618 6488 2533
Crawley, Western Australia, 6009 F: +618 6488 1089

#include <stdio.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/time.h>
#include <sys/times.h>
#include <sys/resource.h>

static struct timeval startw, endw;
static struct rusage startt, endt;

static void time_taken(void)
{
printf("real=%ldms,",
((endw.tv_sec-startw.tv_sec)*1000 +
(endw.tv_usec-startw.tv_usec)/1000));
printf("usr=%ldms,",
((endt.ru_utime.tv_sec-startt.ru_utime.tv_sec)*1000 +
(endt.ru_utime.tv_usec-startt.ru_utime.tv_usec)/1000));
printf("sys=%ldms\n",
((endt.ru_stime.tv_sec-startt.ru_stime.tv_sec)*1000 +
(endt.ru_stime.tv_usec-startt.ru_stime.tv_usec)/1000));
}

static void do_something(void)
{
int i;

for(i=0 ; i<10000000 ; i++)
getpid();
}

int main(int argc, char *argv[])
{
gettimeofday(&startw, NULL);
getrusage(RUSAGE_SELF,&startt);

do_something();

gettimeofday(&endw, NULL);
getrusage(RUSAGE_SELF,&endt);

time_taken();

return(0);
}

[Chad]

Yes, that puts me in the right direction. I've never really tried to
benchmark an algorithm. I was probably going to write the code
(containing the algorithm) and run it a couple of times. I figure the
average time over a couple of runs would give me a reasonable
approximation.

Chad

[Russell Shaw]

You can use gprof or valgrind.

[CBFalconer]

The most important performance effect is that of the hash
function. Then comes the overflow treatment. By using a library
such as hashlib, you allow yourself to vary the functions and
measure the effects. Hashlib is also instrumented to show you the
probes and misses involved. It is written in purely ISO standard
C, and should port anywhere effortlessly. Under GPL.

<http://cbfalconer.home.att.net/download/hashlib.zip>

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>