Calculating the runtime of a hash insertion?

Question

I need to calculated the runtime of a hash insertion. i have been using clock to do the time but i keep ending up with zero. Is there any certain way that would be the most efficient?

This is my code for it so far:

cout << "Testing chaining probing...\n";
    HashTable_chaining ChainingHT( ITEM_NOT_FOUND, 101 );
    int i = 0;
    while(i != DataArray.size())
    {
        clock_t tStart = clock();
        ChainingHT.insert(DataArray[i]);
        cout<<"Time taken:"<<(double)(clock() - tStart)/100000<<endl;
        if(i != NULL)
        {
            collision_count++;
        }
        i++;

    }

@user977154: It's what you divide the result of `clock()` by to get seconds. On some systems it's 100000. On other systems, it isn't. — Marcelo Cantos, Dec 03 '11 at 09:10
oh its pre defined, do u have any other suggestions? or do u think my clock is good? — user977154, Dec 03 '11 at 09:10

Basile Starynkevitch · Answer 1 · 2011-12-03T09:27:03.573

a single hash insert is too quick to be measured. Put

 clock_t tstart = clock();

at the start of your program, doing a million of insertions, and

 clock_t tend = clock();

at the end. Then compute in floating point:

 cout << "cpu time=" 
      << ((double)tend - (double)tstart) / CLOCKS_PER_SEC << endl;

Typical current computers do several billions elementary machine instructions per second (but with a clock resolution in milliseconds at best).

score 1 · Answer 2 · answered Dec 03 '11 at 09:08

My first guess it that insert is extremely fast so you get zeroes... I would never do what you try in this code. Instead I would make, say 10000 insertions, and then calculate how long it takes, and divide that number with 10000 to get average time it takes for insert.

score 0 · Answer 3 · edited May 23 '17 at 12:03

0

running a 10000 / 100000 / 1000000 insertion loop is ok (you need to play with the number of insertion until you get a value that doesn't take for ever to run).

If you are working in windows, consider using performance counters to getter a much better resolution (see code inside).

edited May 23 '17 at 12:03

Community

1
1

answered Dec 03 '11 at 09:58

OSH

2,847
3
25
46

But this solution is not cross-platform (it's win api call). – Yappie Dec 03 '11 at 10:02
true. OP didn't say if he needs cross platform, or not. I am guessing he is working on windows. – OSH Dec 03 '11 at 10:03
On linux, `clock_gettime` usually gives better precision, and there are some low level tricks for direct performance counter access. – Basile Starynkevitch Dec 03 '11 at 14:18

Calculating the runtime of a hash insertion?

3 Answers3

Linked