Std::vector fill time goes from 0ms to 16ms after a certain threshold?

Question

Here is what I'm doing. My application takes points from the user while dragging and in real time displays a filled polygon.

It basically adds the mouse position on MouseMove. This point is a USERPOINT and has bezier handles because eventually I will do bezier and this is why I must transfer them into a vector.

So basically MousePos -> USERPOINT. USERPOINT gets added to a std::vector<USERPOINT> . Then in my UpdateShape() function, I do this:

DrawingPoints is defined like this:

std::vector<std::vector<GLdouble>> DrawingPoints;


Contour[i].DrawingPoints.clear();



 for(unsigned int x = 0; x < Contour[i].UserPoints.size() - 1; ++x)
         SetCubicBezier(
             Contour[i].UserPoints[x],
             Contour[i].UserPoints[x + 1],
             i);

SetCubicBezier() currently looks like this:

void OGLSHAPE::SetCubicBezier(USERFPOINT &a,USERFPOINT &b, int &currentcontour )
{
std::vector<GLdouble> temp(2);

    if(a.RightHandle.x == a.UserPoint.x && a.RightHandle.y == a.UserPoint.y 
        && b.LeftHandle.x == b.UserPoint.x && b.LeftHandle.y == b.UserPoint.y )
    {

        temp[0] = (GLdouble)a.UserPoint.x;
        temp[1] = (GLdouble)a.UserPoint.y;

        Contour[currentcontour].DrawingPoints.push_back(temp);

        temp[0] = (GLdouble)b.UserPoint.x;
        temp[1] = (GLdouble)b.UserPoint.y;


        Contour[currentcontour].DrawingPoints.push_back(temp);

    }
    else
    {
         //do cubic bezier calculation
        }

So for the reason of cubic bezier, I need to make USERPOINTS into GlDouble[2] (since GLUTesselator takes in a static array of double.

So I did some profiling. At ~ 100 points, the code:

 for(unsigned int x = 0; x < Contour[i].UserPoints.size() - 1; ++x)
         SetCubicBezier(
             Contour[i].UserPoints[x],
             Contour[i].UserPoints[x + 1],
             i);

Took 0 ms to execute. then around 120, it jumps to 16ms and never looks back. I'm positive this is due to std::vector. What can I do to make it stay at 0ms. I don't mind using lots of memory while generating the shape then removing the excess when the shape is finalized, or something like this.

Answer 1

0ms is no time...nothing executes in no time. This should be your first indicator that you might want to check your timing methods over timing results.

Namely, timers typically don't have good resolution. Your pre-16ms results are probably just actually 1ms - 15ms being incorrectly reported at 0ms. In any case, if we could tell you how to keep it at 0ms, we'd be rich and famous.

Instead, find out which parts of the loop take the longest, and optimize those. Don't work towards an arbitrary time measure. I'd recommend getting a good profiler to get accurate results. Then you don't need to guess what's slow (something in the loop), but can actually see what part is slow.

Answer 2

You could use vector::reserve() to avoid unnecessary reallocations in DrawingPoints:

Contour[i].DrawingPoints.reserve(Contour[i].size());    
for(unsigned int x = 0; x < Contour[i].UserPoints.size() - 1; ++x) {
   ...
}

Answer 3

If you actually timed the second code snippet only (as you stated in your post), then you're probably just reading from the vector. This means, the cause can not be the re-allocation cost of the vector. In that case, it may due to cache issues of the CPU (i.e. the small datasets can be read in lightning speed from cpu cache, but whenever the dataset is larger than the cache [or when alternately reading from different memory locations], the cpu has to access ram, which is distinctly slower than cache access).

If the part of the code, which you profiled, appends data to the vector, then use std::vector::reserve() with an appropriate capacity (number of expected entries in vector) before filling it.

However, regard two general rules for profiling/benchmarking:

1) Use time measurement methods with high resolution precision (as others stated, the resolution of your timer IS too low)

2) In any case, run the code snippet more than once (e.g. 100 times), get the total time of all runs and divide it by number of runs. This will give you some REAL numbers.

Answer 4

There's a lot of guessing going on here. Good guesses, I imagine, but guesses nevertheless. And when you try to measure the time functions take, that doesn't tell you how they take it. You can see if you try different things that the time will change, and from that you can have some suggestion of what was taking the time, but you can't really be certain.

If you really want to know what's taking the time, you need to catch it when it's taking that time, and find out for certain what it's doing. One way is to single-step it at the instruction level through that code, but I suspect that's out of the question. The next best way is to get stack samples. You can find profilers that are based on stack samples. Personally, I rely on the manual technique, for the reasons given here.

Notice that it's not really about measuring time. It's about finding out why that extra time is being spent, which is a very different question.