Why do people say std::deque is bad?

[eulo...@live.com]

I think it is very good for std::stack/std::queue.

[Nicol Bolas]

We cannot effectively answer criticisms that have not been made. So unless you can point to some actual criticisms, there's not much that can be said.

[sean.mid...@gmail.com]

std::deque so far as the standard is concerned is just fine and I can't think of many reasons someone would complain about it in the abstract sense.

However, some actual standard library implementations of deque tend to be quite bad in terms of cache usage and memory allocations and may only offer a small linear improvement over using std::list.

Those std::deque implementations use a chain of chunks to implement deque but use relatively small chunk sizes. This means that it only takes a few unbalanced push operations to cause a new allocation, and also means that iterating the container requires jumping through a lot of disjoint memory blocks. These are roughly the same performance problems that std::list suffers from. Going from a guaranteed unique block per element for a list to a small handful of items per block in a std::deque is useful enough for some folks, but falls far short of the required efficiency of many users. The per-element space savings is likewise pretty small for a deque vs a list in those implementations.

You can avoid the memory allocation problems if you stick to mostly balanced push/pop operations on most of those implementations. That is, if you're mostly alternating between push/pop then you won't get a ton of allocations (just about all the implementations will recycle at least one chunk) and if you're not planning to iterate the container often then the disjoint allocations won't matter a ton. If you have long chains of pushes followed by long chains of pops, however, then you are more likely going to run into excessive allocation/deallocation problems.

Replacing your implementation's std::deque with a hand-rolled (still fully standard-compliant) version that uses much larger chunks (e.g. 4k/pages or the like) can provide some rather large performance benefits, depending on just what you're doing. I also don't know if anyone's done any _recent_ analysis of std::deque implementation in this light; a lot of us were forced to avoid it in years past and just continue to do so, either out of habit or because we're using some complete STL replacement that's more reliably optimized for our target uses and hardware.

If you're not measuring any real perf problems with std::deque for your uses though then there's no compelling reason for you to replace it. 

[David Krauss]

On 2016–10–29, at 8:09 AM, sean.mid...@gmail.com wrote:

Those std::deque implementations use a chain of chunks

Deque needs an array of pointers to chunks to achieve O(1) access time. Anything else is nonconforming.

But yes, small chunk size can cause locality problems. It would be nice if it were adjustable, perhaps by introducing a trait somehow or by something like constexpr allocator_traits::min_size().

If you have long chains of pushes followed by long chains of pops, however, then you are more likely going to run into excessive allocation/deallocation problems.

There’s another (conforming) structure for deque which may avoid this, using a variable chunk size. I’ve never implemented it because I never had a convincing use case, but if you’re interested we could try it.

[sean.mid...@gmail.com]

On Friday, October 28, 2016 at 9:19:25 PM UTC-7, David Krauss wrote:

Deque needs an array of pointers to chunks to achieve O(1) access time. Anything else is nonconforming.

Right, right. Not sure why I said chain. Brain fart.

 

There’s another (conforming) structure for deque which may avoid this, using a variable chunk size. I’ve never implemented it because I never had a convincing use case, but if you’re interested we could try it.

That is a thought. I'm generally not a fan of memory allocation patterns that aren't super predictable, from a fragmentation perspective, but from a general-purpose point of view that may indeed be a good call.

 

[Bo Persson]

There is another trade-off here of course, in that indexing will be
harder (slower?) when the chunk size varies.


Bo Persson

[ltpmouse]

在 2016年10月29日星期六 UTC+8上午1:42:30，eulo...@live.com写道：

I think it is very good for std::stack/std::queue.

I simply don't understand why people decided we were going to need a random-accessible double-ended queue.

Basically a double-ended queue is envisioned to be a FIFO container and it should behave the best for this purpose.

Yes a circular buffer would be nice and with a hopefully sufficient reservation it suffers from few memory relocations for trivial element types.

It is just that it doesn't conform to the standard because of invalidation of references to elements once a relocation occurs.

-- And more importantly, deque does not have a noexcept move constructor. -- Yet another thing I can't understand.

[Nicol Bolas]

On Tuesday, November 1, 2016 at 2:48:44 AM UTC-4, ltpmouse wrote:

在 2016年10月29日星期六 UTC+8上午1:42:30，eulo...@live.com写道：

I think it is very good for std::stack/std::queue.

I simply don't understand why people decided we were going to need a random-accessible double-ended queue.

Basically a double-ended queue is envisioned to be a FIFO container and it should behave the best for this purpose.

Does the random-accessibility of `deque` impose that much overhead on implementations? It forces them into using fixed-sized blocks, and having an array of pointers to blocks. Is that overhead too much, or are there more problems?

If you take the random-accessibility out of `deque`, you can still have iterators and arbitrary insertion operations.

I think the idea with giving `deque` random accessibility is that if you didn't, it wouldn't be anything more than a slightly more optimized `list`. Where each node, rather than being 1 element is an array of up-to-10 elements.

Yes a circular buffer would be nice and with a hopefully sufficient reservation it suffers from few memory relocations for trivial element types.

It is just that it doesn't conform to the standard because of invalidation of references to elements once a relocation occurs.

But that has nothing to do with random accessibility. That's more about usability. If you cause the iterators to be invalidated on pretty much every insertion/removal operation, then you basically cannot use iterators anymore. At least, not for any insertion/removal operations.

Something as simple as `std::back_inserter` cannot work in such an environment. Not without a specialization for such a type.

-- And more importantly, deque does not have a noexcept move constructor. -- Yet another thing I can't understand.

It's for the same reason that `list` doesn't. `deque` is, effectively, a node-based container.

[Howard Hinnant]

On Nov 1, 2016, at 2:48 AM, ltpmouse <ltpm...@gmail.com> wrote:
>
> -- And more importantly, deque does not have a noexcept move constructor. -- Yet another thing I can't understand.

Only vector and string are required to have noexcept move constructors. The other containers are allowed to. Here is the current status for three implementations:

http://howardhinnant.github.io/container_summary.html

Howard

[ltpmouse]

在 2016年11月1日星期二 UTC+8下午10:27:52，Nicol Bolas写道：

On Tuesday, November 1, 2016 at 2:48:44 AM UTC-4, ltpmouse wrote:

在 2016年10月29日星期六 UTC+8上午1:42:30，eulo...@live.com写道：

I think it is very good for std::stack/std::queue.

I simply don't understand why people decided we were going to need a random-accessible double-ended queue.

Basically a double-ended queue is envisioned to be a FIFO container and it should behave the best for this purpose.

Does the random-accessibility of `deque` impose that much overhead on implementations? It forces them into using fixed-sized blocks, and having an array of pointers to blocks. Is that overhead too much, or are there more problems?

It is gold plating.

 

If you take the random-accessibility out of `deque`, you can still have iterators and arbitrary insertion operations.

I think the idea with giving `deque` random accessibility is that if you didn't, it wouldn't be anything more than a slightly more optimized `list`. Where each node, rather than being 1 element is an array of up-to-10 elements.

On the contrary, I prefer to invalidate references and iterators to elements upon insert()/push_back()/push_front(), enabling a deque to be implemented as a circular buffer.

 

Yes a circular buffer would be nice and with a hopefully sufficient reservation it suffers from few memory relocations for trivial element types.

It is just that it doesn't conform to the standard because of invalidation of references to elements once a relocation occurs.

But that has nothing to do with random accessibility. That's more about usability. If you cause the iterators to be invalidated on pretty much every insertion/removal operation, then you basically cannot use iterators anymore. At least, not for any insertion/removal operations.

You do use iterators of std::vector and std::string, no?

 

Something as simple as `std::back_inserter` cannot work in such an environment. Not without a specialization for such a type.

False. `std::back_insert_iterator` just calls `container->push_back(blah)` on assignment. It doesn't need to know what side effect the insertion is going to cause.

-- And more importantly, deque does not have a noexcept move constructor. -- Yet another thing I can't understand.

It's for the same reason that `list` doesn't. `deque` is, effectively, a node-based container.

 Why would the move ctor of a deque throw an exception? 

[Marc Mutz]

On Friday 28 October 2016 19:42:30 eulo...@live.com wrote:
> I think it is very good for std::stack/std::queue.

It is. That's what is was made for. However, iteration over it is quote
expensive, compared to std::vector, yet it was allowed in the API. At least
that's _my_ main critique. There's been experiments with hierarchical
iterators (similar to the bucket iterator of unordered_map) which brings back
native iteration speed.

HTH,
Marc

--
Marc Mutz <marc...@kdab.com> | Senior Software Engineer
KDAB (Deutschland) GmbH & Co.KG, a KDAB Group Company
Tel: +49-30-521325470
KDAB - The Qt, C++ and OpenGL Experts