Thread: Let's collaborate on vector vs. deque performance

It's my perception that there is very little concensus about how to choose between vector and deque. It also seems that there is very little in the way of good publicly available performance data for vector and deque. The best one I know about is here. Contributions in the form of links to similar resources are welcome.

I imagine that with the combined talent we have here, through both tests and subsequent discussion of those tests, we can make this thread into a great resource for anyone who wants to understand when to use vector and when to use deque.

Please include the source code and compiler you're using when posting the results of any test results you share.

Here's my own test for push_back():

Code:

#include <cassert>
#include <ctime>
#include <iostream>
#include <deque>
#include <vector>

#include "stopwatch.hpp"

void VectorTest(Stopwatch& sw);
void DequeTest(Stopwatch& sw);

int main()
{
    std::cout << "Calibrating stopwatch: ";
    Stopwatch sw;
    std::cout << "resolution " << sw.GetResolution() << 's' << std::endl;

    VectorTest(sw);
    DequeTest(sw);

    return 0;
}

void VectorTest(Stopwatch& sw)
{
    std::vector<int> v;

    std::cout << "100,000,000 * vector<int>::push_back(): ";
    sw.Start();

    for (int i = 0; i != 100000000; ++i)
        v.push_back(i);

    sw.Stop();

    std::cout << sw.GetSeconds() << 's' << std::endl;
}

void DequeTest(Stopwatch& sw)
{
    std::deque<int> d;

    std::cout << "100,000,000 * deque<int>::push_back(): ";
    sw.Start();

    for (int i = 0; i != 100000000; ++i)
        d.push_back(i);

    sw.Stop();

    std::cout << sw.GetSeconds() << 's' << std::endl;
}

As you can see, I wrote a little stopwatch utility for high frequency timing. Feel free to use it. If you have something better, I'm actually quite skeptical of how valid the times it's giving me are so I'd be very interested. Here is its code:

stopwatch.hpp:

Code:

#ifndef STOPWATCH_HPP
#define STOPWATCH_HPP

#include <cassert>
#include <ctime>

class Stopwatch
{
private:
    bool mTimerRunning;
    clock_t mStart;
    clock_t mEnd;
    double mResolution;

public:
    Stopwatch();

    double GetResolution() { return mResolution; }

    void Start()
    {
        assert(mTimerRunning == false);
        mTimerRunning = true;
        mStart = clock();
    }

    void Stop()
    {
        mEnd = clock();
        assert(mTimerRunning == true);
        mTimerRunning = false;
    }

    double GetSeconds()
    {
        return (mEnd - mStart) * mResolution;
    }

    double GetMicroseconds()
    {
        return 1000 * 1000 * GetSeconds();
    }
};

#endif // STOPWATCH_HPP

stopwatch.cpp:

Code:

#include "stopwatch.hpp"

Stopwatch::Stopwatch()
:
    mTimerRunning(false),
    mStart(0),
    mEnd(0),
    mResolution(0.0)
{
    clock_t calibrationStart;
    clock_t calibrationEnd;

    time_t sec1 = time(NULL);
    time_t sec2 = sec1 + 1;
    time_t sec3 = sec2 + 1;

    // Wait until the start of the next second
    while (time(NULL) == sec1) { }

    calibrationStart = clock();

    assert(time(NULL) == sec2);

    // This should run for VERY close to one second
    while (time(NULL) == sec2) { }

    calibrationEnd = clock();

    assert(time(NULL) == sec3);

    mResolution = 1.0 / (calibrationEnd - calibrationStart);
}

I'm using gcc 4.4.5

Results:

Code:

vectorVsDeque$ g++ push_back.cpp stopwatch.cpp
vectorVsDeque$ a.out
Calibrating stopwatch: resolution 1.0101e-06s
100,000,000 * vector<int>::push_back(): 5.37374s
100,000,000 * deque<int>::push_back(): 3.22222s

vectorVsDeque$ g++ push_back.cpp stopwatch.cpp -O2
vectorVsDeque$ a.out
Calibrating stopwatch: resolution 1.0101e-06s
100,000,000 * vector<int>::push_back(): 4.28283s
100,000,000 * deque<int>::push_back(): 1.9697s