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

You should be testing different data sizes (and running the test functions several times). This test with an enormous amount of integers probably doesn't represent a common use case and is rather unfavorable for vector (which in addition to everything else needs to get a contiguous block of that size). Therefore it doesn't properly represent the average cost of push_back.

It's just an edge case where vector doesn't shine (10 times slower when I tried it, but 2 times faster with reserving, which AFAIK is not available with deque).

Originally Posted by anon

This test with an enormous amount of integers probably doesn't represent a common use case and is rather unfavorable for vector

Well of course it is. That was just a quick test I wrote to give a demo of what sorts of things we can do. Here's something much better:

http://i169.photobucket.com/albums/u...rDequeSort.png

Code:

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <vector>

#include "stopwatch.hpp"

template <typename Container>
double TimeToSort(int elements, int repetitions, Stopwatch& sw);

int optimisationStopper = 0;

int main(int argc, char** argv)
{
    if (argc != 4)
    {
        std::cerr << "Usage: " << argv[0] << " maxElements increment repetitions" << std::endl;
        return 1;
    }

    int seedOffset = time(NULL);

    Stopwatch sw;

    int maxElements = atoi(argv[1]);
    int increment = atoi(argv[2]);
    int repetitions = atoi(argv[3]);

    std::cout << "size, vector, deque" << std::endl;
    for (int i = increment; i <= maxElements; i += increment)
    {
        std::cout << i << ", ";

        // Give the same numbers to vector and deque by seeding before the tests
        srand(i + seedOffset);
        std::cout << TimeToSort<std::vector<int> >(i, repetitions, sw) << ", ";

        srand(i + seedOffset);
        std::cout << TimeToSort<std::deque<int> >(i, repetitions, sw) << std::endl;
    }

    std::cout << ",,," << optimisationStopper << std::endl;

    return 0;
}

void ReserveIfVector(std::vector<int>& v, int n) { v.reserve(n); }
void ReserveIfVector(std::deque<int>& d, int n) { }

template <typename Container>
double TimeToSort(int elements, int repetitions, Stopwatch& sw)
{
    typename std::list<Container> cList(repetitions);
    for (typename std::list<Container>::iterator i = cList.begin(); i != cList.end(); ++i)
    {
        ReserveIfVector(*i, elements);

        for (int j = 0; j != elements; ++j)
            i->push_back(rand());
    }

    sw.Start();
    for (typename std::list<Container>::iterator i = cList.begin(); i != cList.end(); ++i)
    {
        sort(i->begin(), i->end());
        optimisationStopper += i->at(rand() % i->size());
    }
    sw.Stop();

    return sw.GetSeconds() / repetitions;
}

Output:

Code:

vectorVsDeque$ g++ sort.cpp stopwatch.cpp -O3 -march=pentium3 \
> -fomit-frame-pointer -fexpensive-optimizations
vectorVsDeque$ a.out 10000 500 10000
size, vector, deque
500, 2.5e-05, 3.1e-05
1000, 5.5e-05, 6.9e-05
1500, 8.5e-05, 0.000108
2000, 0.000119, 0.00015
2500, 0.000152, 0.000193
3000, 0.000185, 0.000236
3500, 0.000221, 0.000278
4000, 0.000256, 0.000323
4500, 0.00029, 0.000368
5000, 0.000325, 0.000415
5500, 0.000362, 0.00046
6000, 0.000398, 0.000506
6500, 0.000434, 0.000554
7000, 0.000473, 0.000599
7500, 0.000509, 0.000645
8000, 0.000547, 0.000695
8500, 0.000587, 0.000741
9000, 0.000623, 0.000791
9500, 0.000661, 0.000838
10000, 0.000699, 0.000887
,,,-588600934

Looks like this takes 25% longer with deque. That's with my machine and g++ 4.4.5 and -O3. I'd like to see someone else's output.