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

  1. #1
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174

    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
    Last edited by Mozza314; 02-21-2011 at 07:56 AM.

  2. #2
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    This comparison is worthless. I haven't read all the code, but just looked at the command line. You tested it without the most important optimizations. -O2 does not even give inlining, which is very important here. You should turn on all CPU-specific ones.
    Do at least:
    Code:
    -O3
    -march=pentium3
    -fomit-frame-pointer
    -fexpensive-optimizations
    Deque is faster when you don't know how many you are going to push, vector is faster when you know this.
    Last edited by kmdv; 02-21-2011 at 08:26 AM.

  3. #3
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    let's collaborate on vector vs. deque performance
    Okay.

    Do you require that the arrangement of elements be truly continuous? Use `std::vector<???>' as `std::deque<???>' is not an option.

    Do you require a container with constant or amortized constant prepending of elements? Use `std::deque<???>' as `std::vector<???>' is not an option.

    Do you require a container of addressable boolean values? Use `std::deque<???>' as `std::vector<???>' is not an option.

    Otherwise, you require only the interface that `std::deque<???>' and `std::vector<???>' have in common; write your code in such a way as to use a simple `typedef', profile your code, and make your decision from those results.

    Congratulations, you now know how to choose between the two containers.




    It's my perception that there is very little concensus about how to choose between vector and deque.
    Welcome to the world of programmers; it's nice to have you.




    Deque is faster when you don't know how many you are going to push, vector is faster when you know this.
    False. The performance characteristics of `std::deque<???>' demand one of only a few implementation techniques.

    The given usual implementation of a table of arrays carries additional, still constant, operations on all of the operations that `std::vector<???>' and `std::deque<???>' have in common. It could be possible for any given source that the overhead balances them out.

    Soma

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Mozza314
    It's my perception that there is very little concensus about how to choose between vector and deque.
    I did not state it in that other thread, but like jimblumberg, I also use Josuttis' rules of thumb:
    Quote Originally Posted by Nicolai Josuttis
    • By default, you should use a vector. It has the simplest internal data structure and provides random access. Thus, data access is convenient and flexible, and the data processing is often fast enough.
    • If you insert and/or remove elements often at the beginning and the end of a sequence, you should use a deque. You should also use a deque if it is important that the amount of internal memory used by the container shrinks when elements are removed. Also, because a vector usually uses one block of memory for its elements, a deque might be able to contain more elements because it uses several blocks.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    The results for a vector depend on precisely how many items you push_back. Your test could either land you near the situation where one more push_back would require growing the vector, or it could land you near the situation where one fewer push_back would have avoided the last grow. Given that the last grow is the most expensive part, it kinda matters. But of course it's implementation specific when it grows. So to be fair it may need to be averaged over a random number of push_back's
    I.e. do 256 times...
    - choose n = random length
    - push_back n times onto vector, let vector go out of scope
    - push_back n times onto deque, let deque go out of scope
    Doing this several times should virtually negate any caching effects that make it faster for the second test.
    Then there's the issue whereby you in theory need to ensure that nothing is optimised out that shouldn't be. For that I would expect at least summing up all elements at the end, and displaying the result.
    This brings me onto my last point, also mearusing the iteration speed of a vector vs deque gives a better picture of real-world performance, since any program that populates a container is bound to do so because it needs to access those items at some point.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by kmdv View Post
    This comparison is worthless. I haven't read all the code, but just looked at the command line. You tested it without the most important optimizations. -O2 does not even give inlining, which is very important here. You should turn on all CPU-specific ones.
    Do at least:
    Code:
    -O3
    -march=pentium3
    -fomit-frame-pointer
    -fexpensive-optimizations
    Deque is faster when you don't know how many you are going to push, vector is faster when you know this.
    Results:
    Code:
    vectorVsDeque$ g++ push_back.cpp stopwatch.cpp -O3 -march=pentium3 -fomit-frame-pointer -fexpensive-optimizations
    vectorVsDeque$ a.out
    Calibrating stopwatch: resolution 1e-06s
    100,000,000 * vector<int>::push_back(): 5.66s
    100,000,000 * deque<int>::push_back(): 2.06s
    vectorVsDeque$ a.out
    Calibrating stopwatch: resolution 1e-06s
    100,000,000 * vector<int>::push_back(): 4.66s
    100,000,000 * deque<int>::push_back(): 1.96s
    vectorVsDeque$ a.out
    Calibrating stopwatch: resolution 1e-06s
    100,000,000 * vector<int>::push_back(): 4.72s
    100,000,000 * deque<int>::push_back(): 2s
    I did -O2 before because I've heard that's the standard optimisation that libraries and such are usually shipped with.

    Oh by the way, I've discovered that my timer resolution is really 0.01s, other than that it's fairly valid I think. It's weird actually; calls to clock() always give multiples of 10,000.

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by anon View Post
    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.
    Last edited by Mozza314; 02-22-2011 at 07:03 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Performance and footprint of virtual function
    By George2 in forum C++ Programming
    Replies: 8
    Last Post: 01-31-2008, 07:34 PM
  2. File map performance
    By George2 in forum C++ Programming
    Replies: 8
    Last Post: 01-04-2008, 04:18 AM
  3. Using DEQUE within Class Definition
    By wbeasl in forum C++ Programming
    Replies: 8
    Last Post: 10-07-2007, 09:50 AM
  4. Confusion with a Deque program
    By Bluefish in forum C++ Programming
    Replies: 0
    Last Post: 05-20-2006, 03:13 PM
  5. costum grow() not working
    By Opel_Corsa in forum C++ Programming
    Replies: 2
    Last Post: 02-17-2006, 10:11 PM