std::deque typically faster then std::list for push_back(), front(), pop_front()?
in [C++]
|
Prev: std::deque typically faster then std::list for push_back(), front(), pop_front()?
Next: compile problem
From: Maciej Sobczak on 10 Jan 2008 05:09 On 10 Sty, 16:08, "Victor V. Terber" <VTer...(a)gmail.com> wrote: > Does such a replacement of list by deque seem reasonable? Would you > typically expect real-world performance changes? I wouldn't be surprised [*] to see a performance improvement in this case. One of the most expensive operations is a memory allocation from generic (default) allocator. Very likely std::list does this more often than deque for the same number of pushed elements. There is also a memory access pattern that is better (more cache-friendly) in the case of deque. [*] No strict statements are possible at this level, these are only common-sense meditations. Check your implementations for final answers. -- Maciej Sobczak * www.msobczak.com * www.inspirel.com -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Lance Diduck on 10 Jan 2008 05:12
On Jan 10, 10:08 am, "Victor V. Terber" <VTer...(a)gmail.com> wrote: > In existing sources I found a std::list using only methods > push_back(), front() and pop_front(). I'm considering to replace the > list by std::deque. > > The usual rule of thumb to use the simplest container that does the > job seems to apply here. I'm aware that the standard doesn't say much > about performance behavior, but due to various restrictions (client's > site, varying compilers, STLs, OS) actual measuring is very hard in > this case. > > Does such a replacement of list by deque seem reasonable? Would you > typically expect real-world performance changes? In this case it seems like the "simplest" container would be a std::queue. To answer your question more directly, it has a lot to do with just how big the "T" is that you are storing. Over a certain size T, std::deque typically morphs (internally) into a std::list + std::vector combination (the vector is so that std::deque can support random access iterators.) For small T, std::deque more of less "pages" the allocations, packing several T on the same page. At least for Dinkum (on Microsoft) the size of T has to be fairly small -- above 16 or so it does not pack at all. If you want performance (and dont care about the random access iterators) then combining a std::list with a pool allocator that allocates large pages that store mutliple T's is your best bet, no matter the vendor. This combination will almost always blow away std::deque. A few vendors already sneak in a pool allocator for this use. A std::list always ask for the same size blocks, making allocators easy to write. It is easy to get 10x-20x perforamnce increases, esp for small T. Lance -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |