Posts Comments

Home > Programming > C++ > C++ benchmark – std::vector VS std::list

C++ benchmark – std::vector VS std::list

November 26, 2012 by 43 Comments

A updated version of this article is available: C++ benchmark – std::vector VS std::list VS std::deque

In C++, the two most used data structures are the std::vector and the std::list. In this article, we will compare the performance in practice of these two data structures on several different workloads. In this article, when I talk about a list it is the std::list implementation and vector refers to the std::vector implementation.

It is generally said that a list should be used when random insert and remove will be performed (performed in O(1) versus O(n) for a vector). If we look only at the complexity, search in both data structures should be roughly equivalent, complexity being in O(n). When random insert/replace operations are performed on a vector, all the subsequent data needs to be moved and so each element will be copied. That is why the size of the data type is an important factor when comparing those two data structures.

However, in practice, there is a huge difference, the usage of the memory caches. All the data in a vector is contiguous where the std::list allocates separately memory for each element. How does that change the results in practice ?

Keep in mind that all the tests performed are made on vector and list even if other data structures could be better suited to the given workload.

In the graphs and in the text, n is used to refer to the number of elements of the collection.

All the tests performed have been performed on an Intel Core i7 Q 820  @ 1.73GHz. The code has been compiled in 64 bits with GCC 4.7.2 with -02 and -march=native. The code has been compiled with C++11 support (-std=c++11).

Fill

The first test that is performed is to fill the data structures by adding elements to the back of the container. Two variations of vector are used, vector_pre being a std::vector with the size passed in parameters to the constructor, resulting in only one allocation of memory.

All data structures are impacted the same way when the data size increases, because there will be more memory to allocate. The vector_pre is clearly the winner of this test, being one order of magnitude faster than a list and about twice faster than a vector without pre-allocation. The result are directly linked to the allocations that have to be performed, allocation being slow. Whatever the data size is, push_back to a vector will always be faster than to a list. This is logical becomes vector allocates more memory than necessary and so does not need to allocate memory for each element.

But this test is not very interesting, generally building the data structure is not critical. What is critical is the operations that are performed on the data structure. That will be tested in the next sections.

Related posts:

  1. C++ benchmark – std::vector VS std::list VS std::deque
  2. New WordPress Plugin – Google Visualization Charts
  3. Integer Linear Time Sorting Algorithms
  4. GCC 4.7 vs CLang 3.1 on eddic
  5. Find closest pair of point with Plane Sweep Algorithm in O(n ln n)
 

Filed under: C++ Tagged with , , ,
  • fabiano

    I like a lot your blog posts.. just a note, sometimes I have difficulties to grasp the meaning of the graphs, I suggest to add the measure unit (and variable menaing) to the graph axes (IMHO)
    Keep doing!

    • wichtounet

      Thank you :)

      I added the unit in the title of the graphs and the in x axis. Unfortunately I cannot add the unit next to the y axis due to the limitations of the wordpress plugin. I’m generating the graphs with a plugin. I’ll try to find a way to have better graphs in the future.

  • Roman

    Can you please use some more distinct colors? Like blue and red, for example.

    • wichtounet

      Sure :)

      Is it better ?

  • Luke

    Some are a bit hard to see, could we get a logarithmic y-scale?

    • wichtounet

      Sorry, the graphs are indeed far from perfect. The tool that I Use cannot do better. We’ll think of a solution for the next articles.

  • Julien

    Interesting read, thanks for sharing. I am curious how a std::deque would perform, since it’s supposed to be more cache friendly than a std::list.

    • wichtounet

      It could indeed be a very good idea. That will done this weekend and published on monday.

  • Ricode

    Thanks for sharing, would be aswesome if you could add std::deque to these tests.

    • wichtounet

      That will be done this week-end. I will publish an updated version on Monday.

  • Mateusz Pusz

    +1 for std::deque.
    I would also love to read what type of data you used. Was it POD (memmove probably used by STL) or a class that have a non trivial copy-constructor? Polymorphic dynamically allocated classes could also be an interesting point here.
    In that and similar tests I also always miss the destruction performance of such a container. We sometimes forget that it is not enough to create a container and fill it with data. Destroying it can also take significant time in case of big std::list.

    • wichtounet

      The code was compiled with GCC 4.7.2 with C++11 option (I edited the article to add that information). Thanks.

      The data type is a single struct with an array of int. I just change the size of the array for the different data types. That could probably be made with memmove and optimizations (SSE).

      I will add the destruction performance this week-end as well as std::deque. If I have time, I will try to add a non-POD as well. Thanks for the suggestion :)

      • Mateusz Pusz

        I looked into your source code and your structure is not POD. Try running std::is_pod type trait on it. VS uses std::is_pod and gcc uses std::is_trivial for STL optimizations and uses memmove only in that case.
        I also found that you count destruction performance in some of your tests which may provide significant delay and provide wrong values for intended experiment.

        • http://www.baptiste-wicht.com/ Baptiste Wicht

          You’re right :(

          I didn’t know that the conditions were so strong to be considered POD (as a matter of fact I didn’t even know that there was type traits for that :s ).

          For the destruction time, the new version of the article (http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/) has fixed this. But not the POD issue.

          I’ll see this evening if I can easily update the struct to be POD and if that changes the results.

          Thanks a lot

        • http://www.baptiste-wicht.com/ Baptiste Wicht

          I tested with transforming my structures into POD. I haven’t seen any considerable difference in the benchmarks. I haven’t run all of them. Which benchmark do you think there will be a big difference ?

          • Mateusz Pusz

            Hmm interesting. I would expect the benefit in every std::vector test that moves large chunks of memory (push_back, erase from the middle, etc). One memmove on M elements where 0 < M < N should be much faster than manually running M copy constructors and still somehow faster in case of running M move constructors.

          • http://www.baptiste-wicht.com/ Baptiste Wicht

            Perhaps it can still do the optimization for memmove even if it is not real std::is_trivial ? Or perhaps I made the test wrong, but I tested fill_back and the results were not different and std::is_trivial was true.

  • bert hubert

    Thanks for this post, the effect is dramatic. Sadly, the effect is also lost when storing objects with their own allocator, like for example many std::string implementations. In this case, the string main instance is nicely contiguous, but it points all ways to the actual data. But still, I got great performance increases by using sorted std::vectors over std::map! With a custom allocator, we could try to get the underlying instances contigousser too ;-)

  • Pedro

    Have you tried out with large sized data types? For example, a vector of whatever of size 4k, or something like that. I remember seeing that for large sized data types, these performance advantages of the vector just vanish (even pushing back a bunch of elements became then faster using std::list). I guess it’s because the cost of dynamic allocation become less of an issue than the cost of copying. But I may have done things wrong.

    • wichtounet

      I will update the article this week-end and add one larger size, 4K or 8K seems a good idea.

  • Kjell Hedström

    Nice comparison. Reminded me of something I did once ;) [http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/]

    I think push_front is interesting,. in that it clearly is unsuitable for std::vector,. but also because it is as going against the nature of the std::vector. If “first” is the direction of growth (as it is for the linked-list normally) then the “push_back” would be used instead.

    Incidentally, push_back exists in the API, push_front doesn’t, very likely for this reason.(more examples at this: http://www.codeproject.com/Articles/340797/Number-crunching-Why-you-should-never-ever-EVER-us#TOC_DA_V)

    • wichtounet

      Yes, your nice comparison gave me the idea of this one, thanks :)

      I completely agree that push_front is going against the nature of the std::vector and should never be used. I put it in the benchmarks only to test the worst case of std::vector.

  • wichtounet

    Thanks a lot for all your comments :)

    I will update the benchmark this week-end and publish a new version on monday. I will add std::deque, bigger size data (4K or 8K) and add destruction time in my benchmark.

    Don’t hesitate if you have any other suggestion until the end of the week ;)

  • sellibitze

    Thanks for testing. Some ideas: How about a a logarithmic time axis? How does std::deque behave?

    • wichtounet

      For the logarithmic time axis, the tool I use to generate the graphs does not have suchs options. For the updated version of the article, I will look if it is possible with another tool.

      For the std::deque, we’ll see on monday :)

  • Leigh Johnston

    Take a look at my segmented_array container; it sits in a happy space between vector and list having the advantages of both: http://i42.co.uk/stuff/segmented_array.htm (benchmarks included).

    • wichtounet

      Very interesting :)

      The results look very promising.

  • http://twitter.com/sapien2 Sapo Lin Zhou

    What is meant by random add and remove from the list? Does this operation first tries to find random element by sequential iteration through the list elements which is obviously O(n)?

    • wichtounet

      Yes, that is exactly what is done. The random just means the position, not using direct access.

  • Pingback: Vectors And Lists « Bulldozer00's Blog

  • c l

    This article was amazing. Really good info on a topic that is often answered either incorrectly or answered without any evidence to back up the claims. This article fixes that with facts and numbers great job! And great website!

    • wichtounet

      Thank you :)
      I’m happy that people find it useful.

  • c l

    I read that you are going to update this article with more data types and destruction. May I suggest creating a second page and linking to it, this will keep the information on this page from getting drowned in the abundance of information. The current page answers the age old question, vector or list, keep that information to the point.

    • wichtounet

      Excellent suggestion. That is exactly what I was going to do :) Merging all the stuff will only means losing information. I will create a new article and cross-link to two.

  • Benjamin Lindley

    Is std::list really in the top two most used data structures in C++? I find that surprising. In my own code, std::map is used far more often than std::list. Linked lists are very special purpose and far too over-emphasized in CS courses, IMO.

    • http://www.baptiste-wicht.com/ Baptiste Wicht

      It is only from my experience that I said it was one of the two data structures. From what I saw in open source code, public forums, … In my own code, I use a lot more map/set and their unordered counter parts than list.

      You’re right that there are too much taught in courses, especially algorithm courses. When you learn linked list, you think that is great because of O(1) random insert, but nobody tell you that in practice searching through a list is bad…

  • Arash Partow

    Just out of curiosity, why are you including the destruction of the containers and the generation of random values in your timings?

    • http://www.baptiste-wicht.com/ Baptiste Wicht

      For the destruction, it is a shameful error :( Thanks for pointing that out.
      It will be fixed for the next version.

      For the generation of random values, imho, it is not a problem since all tests cases are doing the same number of random generation and so it does not change the relative factor between different tests.

  • http://twitter.com/clementval Clément Valentin

    Interesting article ! Is that part of your thesis ? Or just for the fun ?

    • http://www.baptiste-wicht.com/ Baptiste Wicht

      Thanks. No, it is just for fun :)

  • http://www.baptiste-wicht.com/ Baptiste Wicht

    For those who haven’t seen, the new version of the article is available: http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/