CODEWITHSUNDEEP
c++visual-c++-2010
NightSky
NightSky

Reputation: 13

Performance issues with C++ (using VC++ 2010): at runtime, my program seems to randomly wait for a while

I'm currently trying to code a certain dynamic programming approach for a vehicle routing problem. At a certain point, I have a partial route that I want to add to a minmaxheap in order to keep the best 100 partial routes at a same stage. Most of the program runs smooth but when I actually want to insert a partial route into the heap, things tend to go a bit slow. That particural code is shown below:

 clock_t insert_start, insert_finish, check1_finish, check2_finish;

insert_start = clock();
check2_finish = clock();

if(heap.get_vector_size() < 100) {
    check1_finish= clock();
    heap.insert(expansion);
    cout << "node added" << endl;
}
else {
    check1_finish = clock();
    if(expansion.get_cost() < heap.find_max().get_cost() ) {
        check2_finish = clock();
        heap.delete_max();
        heap.insert(expansion);
        cout<< "worst node deleted and better one added"   <<endl;
    }
    else {
        check2_finish = clock();
        cout << "cost too high check"<<endl;
    }
}

number_expansions++;

cout << "check 1 takes " << check1_finish - insert_start << " ms" << endl;
cout << "check 2 takes " << check2_finish - check1_finish << "ms " << endl;

insert_finish = clock();

cout << "Inserting an expanded state into the heap takes " << insert_finish - insert_start << " clocks" << endl;

A typical output is this:

cost too high check 
check1 takes 0 ms 
check2 takes 0ms 
Inserting an expanded state into the heap takes 0 clocks

cost too high check 
check1 takes 0 ms 
check2 takes 0ms 
Inserting an expanded state into the heap takes 16 clocks

cost too high check 
check1 takes 0 ms 
check2 takes 0ms 
Inserting an expanded state into the heap takes 0 clocks

I know it's hard to say something about the code when this block uses functions that are implemented elsewhere but I'm flabbergasted as to why this sometimes takes less than a ms and sometimes takes up to 16 ms. The program should execute this block thousands of times so these small hiccups are really slowing things down enormously.

My only guess is that something happens with the vector in the heap class that stores all these states but I reserve place for a 100 items in the constructor using vector::reserve so I don't see how this could still be a problem.

Thanks!

Upvotes: 1

Views: 297

Answers (4)

T.E.D.
T.E.D.

Reputation: 44794

It looks like you are measureing "wall time", not CPU time. Windows itself is not a realtime OS. Occasional large hiccups from high-priority things like device drivers is not at all uncommon.

On Windows if I'm manually trying to look for bottlenecks in code, I use RDTSC instead. Even better would be to not do it manually, but use a profiler.

Upvotes: 0

Zuljin
Zuljin

Reputation: 2640

Try to measure time using QueryPerformanceCounter, because I think that clock function could not be very accurate. Probably clock has the same accuracy as windows scheduler - 10 ms for single cpu and 15 or 16 ms for multicore cpu. QueryPerformanceCounter together with QueryPerformanceFreq can give you nanosecond resolution.

Upvotes: 0

Alessandro Teruzzi
Alessandro Teruzzi

Reputation: 3968

My only guess is that something happens with the vector in the heap class that stores all these states but I reserve place for a 100 items in the constructor using vector::reserve so I don't see how this could still be a problem.

Are you using std::vector to implement it? Insert is taking linear time for std::vector. Also delete max is can take time if you are not using a sorted container.

I will suggest you to use a std::set or std::multiset. Insert, delete and find take always ln(n).

Upvotes: 0

Tim
Tim

Reputation: 9172

Preempting. Your program may be preempted by the operating system, so some other program can run for a bit.

Also, it's not 16 ms. It's 16 clock ticks: http://www.cplusplus.com/reference/clibrary/ctime/clock/

If you want ms, you need to do:

cout << "Inserting an expanded state into the heap takes "
     << (insert_finish - insert_start) * 1000 / CLOCKS_PER_SEC
     << " ms " << endl;

Finally, you're setting insert_finish after printing out the other results. Try setting it immediately after your if/else block. The cout command is a good time to get preempted by another process.

Upvotes: 1

Related Questions