Random slowdown when inserting elements at random into vectors

Question

EDIT: I've fixed the insertion. As Blastfurnace kindly mentioned the insertion invalidated the iterators. The loop is needed I believe to compare performance (see my comment on Blastfurnance's answer). My code is updated. I have completely similar code for the list just with vector replaced by list. However, with the code I find that the list performs better than the vector both for small and large datatypes and even for linear search (if I remove the insertion). According to http://java.dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs and other sites that should not be the case. Any clues to how that can be?

I am taking a course on programming of mathematical software (exam on monday) and for that I would like to present a graph that compares performance between random insertion of elements into a vector and a list. However, when I'm testing the code I get random slowdowns. For instance I might have 2 iterations where inserting 10 elements at random into a vector of size 500 takes 0.01 seconds and then 3 similar iterations that each take roughly 12 seconds. This is my code:

    void AddRandomPlaceVector(vector<FillSize> &myContainer, int place)  {
    int i = 0;

    vector<FillSize>::iterator iter = myContainer.begin();

    while (iter != myContainer.end())
    {
        if (i == place)
        {
            FillSize myFill;
            iter = myContainer.insert(iter, myFill);
        }
        else
            ++iter;

        ++i;
    }

    //cout << i << endl;
}

double testVector(int containerSize, int iterRand)
{
    cout << endl;
    cout << "Size: " << containerSize << endl << "Random inserts: " << iterRand << endl;

    vector<FillSize> myContainer(containerSize);
    boost::timer::auto_cpu_timer tid;

    for (int i = 0; i != iterRand; i++)
    {
        double randNumber = (int)(myContainer.size()*((double)rand()/RAND_MAX));
        AddRandomPlaceVector(myContainer, randNumber);
    }

    double wallTime = tid.elapsed().wall/1e9;

    cout << "New size: " << myContainer.size();

    return wallTime;
}

int main()
{
    int testSize = 500;
    int measurementIters = 20;
    int numRand = 1000;
    int repetionIters = 100;


    ofstream tidOutput1_sum("VectorTid_8bit_sum.txt");
    ofstream tidOutput2_sum("ListTid_8bit_sum.txt");

    for (int i = 0; i != measurementIters; i++)
    {
        double time = 0;

        for (int j = 0; j != repetionIters; j++) {
            time += testVector((i+1)*testSize, numRand);
        }

        std::ostringstream strs;
        strs << double(time/repetionIters);
        tidOutput1_sum << ((i+1)*testSize) << "," << strs.str() << endl;
    }

    for (int i = 0; i != measurementIters; i++)
    {
        double time = 0;

        for (int j = 0; j != repetionIters; j++) {
            time += testList((i+1)*testSize, numRand);
        }

        std::ostringstream strs;
        strs << double(time/repetionIters);
        tidOutput2_sum << ((i+1)*testSize) << "," << strs.str() << endl;
    }
    return 0;
}

struct FillSize
{
    double fill1;
};

The struct is just for me to easily add more values so I can test for elements with different size. I know that this code is probably not perfect concerning performance-testing, but they would rather have me make a simple example than simply reference to something I found.

I've tested this code on two computers now, both having the same issues. How can that be? And can you help me with a fix so I can graph it and present it Monday? Perhaps adding some seconds of wait time between each iteration will help?

Kind regards, Bjarke

Answer 1

Your AddRandomPlaceVector function has a serious flaw. Using insert() will invalidate iterators so the for loop is invalid code.

If you know the desired insertion point there's no reason to iterate over the vector at all.

void AddRandomPlaceVector(vector<FillSize> &myContainer, int place)
{
    FillSize myFill;
    myContainer.insert(myContainer.begin() + place, myFill);
}