Std::deque is really quite bad

[woodb...@gmail.com]

Around the 47 minutes and 40 seconds mark in this video

https://www.youtube.com/watch?v=vElZc6zSIXM&spfreload=1

Chandler Carruth says: "the std::deque data type is
really quite bad. I wouldn't recommend anyone use
it for anything." Do you agree that std::deque should
be added to std::junkpile?

I've known about some of the problems with std::deque
for years, but I have one place where I use it here:

http://webEbenezer.net/misc/cmwAmbassador.cc

. I'm not sure what would be a better alternative there.
Tia.


Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

[JiiPee]

Performance reasons: "std::deque performs better than a std::vector for
inserting at random positions (especially at the front, which is
constant time)"

http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

[Mr Flibble]

On 04/10/2016 19:01, woodb...@gmail.com wrote:
>

> Around the 47 minutes and 40 seconds mark in this video
>
> https://www.youtube.com/watch?v=vElZc6zSIXM&spfreload=1
>
> Chandler Carruth says: "the std::deque data type is
> really quite bad. I wouldn't recommend anyone use
> it for anything." Do you agree that std::deque should
> be added to std::junkpile?
>
> I've known about some of the problems with std::deque
> for years, but I have one place where I use it here:

std::deque is no worse and no better than any other container and should
be used where appropriate so Carruth is simply incorrect.

When one fully understands the complexity and reference/iterator
invalidation behaviour for each of a container's operations one can make
an intelligent choice for which container to use for a specific task.

/Flibble

[Mr Flibble]

On 04/10/2016 19:13, JiiPee wrote:
> Performance reasons: "std::deque performs better than a std::vector for
> inserting at random positions (especially at the front, which is
> constant time)"

False; the performance of std::deque insert in the middle is just as
poor as for std::vector.

/Flibble

[Öö Tiib]

On Tuesday, 4 October 2016 21:01:40 UTC+3, woodb...@gmail.com wrote:
> Around the 47 minutes and 40 seconds mark in this video
>
> https://www.youtube.com/watch?v=vElZc6zSIXM&spfreload=1
>
> Chandler Carruth says: "the std::deque data type is
> really quite bad. I wouldn't recommend anyone use
> it for anything." Do you agree that std::deque should
> be added to std::junkpile?

Container's performance does not care about opinions of whatever young
googlers, youtubers or llvmers the internet keeps spitting at us.
'std::deque' is doing quite well in profile of several algorithms.

>
> I've known about some of the problems with std::deque
> for years, but I have one place where I use it here:
>
> http://webEbenezer.net/misc/cmwAmbassador.cc
>
> . I'm not sure what would be a better alternative there.
> Tia.

The standard library containers are all likely performing worse for
FIFO of smart pointers that you seem to have there. 'std::queue'
(adaptor) makes its usage likely slightly less verbose and also
documents better that it is FIFO.

From outside of standard library it may easily be that for example 'boost::circular_buffer_space_optimized' is performing better there.
That needs profiling, if it matters.

[Chris Vine]

On Tue, 4 Oct 2016 11:01:26 -0700 (PDT)
woodb...@gmail.com wrote:

> Around the 47 minutes and 40 seconds mark in this video
>
> https://www.youtube.com/watch?v=vElZc6zSIXM&spfreload=1
>
> Chandler Carruth says: "the std::deque data type is
> really quite bad. I wouldn't recommend anyone use
> it for anything." Do you agree that std::deque should
> be added to std::junkpile?
>
> I've known about some of the problems with std::deque
> for years, but I have one place where I use it here:
>
> http://webEbenezer.net/misc/cmwAmbassador.cc
>
> . I'm not sure what would be a better alternative there.
> Tia.

Your leaning towards authority figures like Chandler, and your
willingness to give their views special validity, may explain why you
are religious nutjob. You need to think for yourself.

If you have a use case where you frequently insert or remove elements at
the start and end of the container, std::deque is the first container
to try unless profiling tells you that something else works better.
std::vector may possibly do so for containers of built-in types where
most operations are at the end and only some at the beginning, and the
whole container frequently fits within a single cache line.

[JiiPee]

according the measurements on this site:

http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html


it faster.

[Mr Flibble]

It, like std::vector, is still linear complexity.

/Flibble

[Jerry Stuckle]

Please - don't confuse him with the facts.

I've also found std::deque insert in the middle is faster than
std::vector. The latter is a real dog. The former only a half dog :)


--
==================
Remove the "x" from my email address
Jerry Stuckle
jstu...@attglobal.net
==================

[woodb...@gmail.com]

On Tuesday, October 4, 2016 at 2:28:12 PM UTC-5, Öö Tiib wrote:
> On Tuesday, 4 October 2016 21:01:40 UTC+3, woodb...@gmail.com wrote:
> > Around the 47 minutes and 40 seconds mark in this video
> >
> > https://www.youtube.com/watch?v=vElZc6zSIXM&spfreload=1
> >
> > Chandler Carruth says: "the std::deque data type is
> > really quite bad. I wouldn't recommend anyone use
> > it for anything." Do you agree that std::deque should
> > be added to std::junkpile?
>
> Container's performance does not care about opinions of whatever young
> googlers, youtubers or llvmers the internet keeps spitting at us.
> 'std::deque' is doing quite well in profile of several algorithms.

Really?

>
> >
> > I've known about some of the problems with std::deque
> > for years, but I have one place where I use it here:
> >
> > http://webEbenezer.net/misc/cmwAmbassador.cc
> >
> > . I'm not sure what would be a better alternative there.
> > Tia.
>
> The standard library containers are all likely performing worse for
> FIFO of smart pointers that you seem to have there. 'std::queue'
> (adaptor) makes its usage likely slightly less verbose and also
> documents better that it is FIFO.

I agree with you about std::queue documenting better that
it's a FIFO, but disagree about the usage being less verbose:

::std::deque<::std::unique_ptr<cmw_request> > pendingTransactions;

versus

::std::queue<::std::unique_ptr<cmw_request>
,::std::deque<::std::unique_ptr<cmw_request>>
> pendingTransactions;

So I'm not sure that the gain in readability by using std::queue
would be worth it. If we could write that instead as:

::std::queue<::std::deque<::std::unique_ptr<cmw_request>>
> pendingTransactions;

, I'd be more inclined to use it. I guess that's a wart in
the container adaptors.

>
> From outside of standard library it may easily be that for example 'boost::circular_buffer_space_optimized' is performing better there.
> That needs profiling, if it matters.

I can use Boost containers in the back tier of the C++ Middleware
Writer, but not here as they aren't portable enough. Maybe it's
more of a distribution problem than a portability problem.

Brian
Ebenezer Enterprises - "Remember that you were slaves in Egypt and
that the L-rd your G-d set you free." Deuteronomy 24:18

http://webEbenezer.net

[woodb...@gmail.com]

On Tuesday, October 4, 2016 at 5:51:29 PM UTC-5, Chris Vine wrote:
> On Tue, 4 Oct 2016 11:01:26 -0700 (PDT)
> woodb...@gmail.com wrote:
>
> > Around the 47 minutes and 40 seconds mark in this video
> >
> > https://www.youtube.com/watch?v=vElZc6zSIXM&spfreload=1
> >
> > Chandler Carruth says: "the std::deque data type is
> > really quite bad. I wouldn't recommend anyone use
> > it for anything." Do you agree that std::deque should
> > be added to std::junkpile?
> >
> > I've known about some of the problems with std::deque
> > for years, but I have one place where I use it here:
> >
> > http://webEbenezer.net/misc/cmwAmbassador.cc
> >
> > . I'm not sure what would be a better alternative there.
> > Tia.
>
> Your leaning towards authority figures like Chandler, and your
> willingness to give their views special validity, may explain why you
> are religious nutjob. You need to think for yourself.

You are an anti-religious bigot.


Brian
Ebenezer Enterprises - If you can't join 'em, beat 'em.
http://webEbenezer.net

[Chris M. Thomasson]

That's all you got! ;^o

[Öö Tiib]

On Wednesday, 5 October 2016 04:51:11 UTC+3, woodb...@gmail.com wrote:
> On Tuesday, October 4, 2016 at 2:28:12 PM UTC-5, Öö Tiib wrote:
> >
> > The standard library containers are all likely performing worse for
> > FIFO of smart pointers that you seem to have there. 'std::queue'
> > (adaptor) makes its usage likely slightly less verbose and also
> > documents better that it is FIFO.
>
> I agree with you about std::queue documenting better that
> it's a FIFO, but disagree about the usage being less verbose:
>
> ::std::deque<::std::unique_ptr<cmw_request> > pendingTransactions;
>
> versus
>
> ::std::queue<::std::unique_ptr<cmw_request>
> ,::std::deque<::std::unique_ptr<cmw_request>>
> > pendingTransactions;
>
> So I'm not sure that the gain in readability by using std::queue
> would be worth it. If we could write that instead as:
>
> ::std::queue<::std::deque<::std::unique_ptr<cmw_request>>
> > pendingTransactions;
>
> , I'd be more inclined to use it. I guess that's a wart in
> the container adaptors.

Why you typed a default template argument out on case of 'queue'
but not on case of 'dequeue'? Same "comparison":

std::deque< std::unique_ptr<cmw_request>

, std::allocator<std::unique_ptr<cmw_request>>
> pendingTransactions1;

std::queue<std::unique_ptr<cmw_request>> pendingTransactions2;

I was talking about interface of 'queue' that is succinctly interface
of FIFO and is not interface of generic container.

[Chris Vine]

On Tue, 4 Oct 2016 19:37:52 -0700 (PDT)
woodb...@gmail.com wrote:
> On Tuesday, October 4, 2016 at 5:51:29 PM UTC-5, Chris Vine wrote:

[snip]

> > Your leaning towards authority figures like Chandler, and your
> > willingness to give their views special validity, may explain why
> > you are religious nutjob. You need to think for yourself.
>
> You are an anti-religious bigot.

I am not. I am generally pro-religion. I am however against people
who post off topic nonsense to news groups. (And for that matter,
against religious bigots, people who post weird messages about coders
who follow a particular approach to setting out their code as a "royal
priesthood", and people who claim that they have been appointed by God
to lead C++.)

Since you on this occasion did make an on topic post, I gave you my
answer to your question, as below:

> > If you have a use case where you frequently insert or remove
> > elements at the start and end of the container, std::deque is
> > the first container to try unless profiling tells you that
> > something else works better. std::vector may possibly do so for
> > containers of built-in types where most operations are at the end
> > and only some at the beginning, and the whole container frequently
> > fits within a single cache line.

Since you say you have "known about some of the problems with
std::deque for years", what are the problems that you know about? Have
you done any measurements?

[Jorgen Grahn]

On Tue, 2016-10-04, Chris Vine wrote:
> On Tue, 4 Oct 2016 11:01:26 -0700 (PDT)
> woodb...@gmail.com wrote:
>
>> Around the 47 minutes and 40 seconds mark in this video
>>
>> https://www.youtube.com/watch?v=vElZc6zSIXM&spfreload=1
>>
>> Chandler Carruth says: "the std::deque data type is
>> really quite bad. I wouldn't recommend anyone use
>> it for anything." Do you agree that std::deque should
>> be added to std::junkpile?
>>
>> I've known about some of the problems with std::deque
>> for years, but I have one place where I use it here:
>>
>> http://webEbenezer.net/misc/cmwAmbassador.cc
>>
>> . I'm not sure what would be a better alternative there.
>> Tia.
>
> Your leaning towards authority figures like Chandler, and your
> willingness to give their views special validity, may explain why you
> are religious nutjob. You need to think for yourself.

I get the feeling it's the other way around: he /is/ thinking for
himself, disliking most of the standard containers, and looking for
authority figures who confirm his views.

I'm more interested in woodbrian's own arguments.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[woodb...@gmail.com]

Sorry, I thought it was (still) required.


Brian
Ebenezer Enterprises
http://webEbenezer.net

[woodb...@gmail.com]

On Wednesday, October 5, 2016 at 4:40:56 AM UTC-5, Chris Vine wrote:
> On Tue, 4 Oct 2016 19:37:52 -0700 (PDT)
> woodb...@gmail.com wrote:
> > On Tuesday, October 4, 2016 at 5:51:29 PM UTC-5, Chris Vine wrote:
> [snip]
> > > Your leaning towards authority figures like Chandler, and your
> > > willingness to give their views special validity, may explain why
> > > you are religious nutjob. You need to think for yourself.
> >
> > You are an anti-religious bigot.
>
> I am not. I am generally pro-religion. I am however against people
> who post off topic nonsense to news groups. (And for that matter,
> against religious bigots, people who post weird messages about coders
> who follow a particular approach to setting out their code as a "royal
> priesthood", and people who claim that they have been appointed by God
> to lead C++.)

I claim there are blessings, such as insights, for those who
follow G-d. I'm not forcing anyone to follow me. I provide
servant (service) leadership to others by following G-d. G-d
is the ultimate service provider and is willing to teach His
people how to be like Him.

>
> Since you on this occasion did make an on topic post, I gave you my
> answer to your question, as below:
>
> > > If you have a use case where you frequently insert or remove
> > > elements at the start and end of the container, std::deque is
> > > the first container to try unless profiling tells you that
> > > something else works better. std::vector may possibly do so for
> > > containers of built-in types where most operations are at the end
> > > and only some at the beginning, and the whole container frequently
> > > fits within a single cache line.
>
> Since you say you have "known about some of the problems with
> std::deque for years", what are the problems that you know about?

One is that you can't control the chunk size in std::deque.
Leigh can probably list other weaknesses of std::deque more
easily than I can.

> Have
> you done any measurements?

Not recently.


Brian
Ebenezer Enterprises - "He who watches over Israel will neither
slumber nor sleep." Psalsm 121:4

http://webEbenezer.net

[Juha Nieminen]

woodb...@gmail.com wrote:
> Chandler Carruth says: "the std::deque data type is
> really quite bad. I wouldn't recommend anyone use
> it for anything." Do you agree that std::deque should
> be added to std::junkpile?

std::deque has features that other containers either don't
have, or are more inefficient about them.

std::deque does not need the same kind of resizing as std::vector
does, which may be relevant if you need to append lots of elements
individually (without knowin in advance how many of them there will be).
std::deque doesn't cause as much memory fragmentation as std::vector
(for the same reason.) Pointers to std::deque elements do not get
invalidated when new elements are appended (or prepended) to the
container, unlike std::vector.

std::deque offers random access, unlike std::list. std::deque also
makes significantly less memory allocations than std::list, making
it more efficient (and reducing memory fragmentation). std::deque
is a much more efficient queue structure (it's in its name!) than
either std::list or std::vector. (A queue structure is one where you
add elements to one end and pop them from the other.)

std::deque might be more efficient as a stack structure than std::vector,
but this one I'm not sure of, without actual experimentation. I suppose
it depends on how the stack will be used.

I regularly use std::deque when the need arises (especially when I need
a queue structure, which is exactly what the container has been designed
for.)

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[woodb...@gmail.com]

On Monday, October 10, 2016 at 4:29:51 PM UTC-5, Juha Nieminen wrote:
> woodb...@gmail.com wrote:
> > Chandler Carruth says: "the std::deque data type is
> > really quite bad. I wouldn't recommend anyone use
> > it for anything." Do you agree that std::deque should
> > be added to std::junkpile?
>
> std::deque has features that other containers either don't
> have, or are more inefficient about them.
>
> std::deque does not need the same kind of resizing as std::vector
> does, which may be relevant if you need to append lots of elements
> individually (without knowin in advance how many of them there will be).
> std::deque doesn't cause as much memory fragmentation as std::vector
> (for the same reason.) Pointers to std::deque elements do not get
> invalidated when new elements are appended (or prepended) to the
> container, unlike std::vector.
>
> std::deque offers random access, unlike std::list. std::deque also
> makes significantly less memory allocations than std::list, making
> it more efficient (and reducing memory fragmentation). std::deque
> is a much more efficient queue structure (it's in its name!) than
> either std::list or std::vector. (A queue structure is one where you
> add elements to one end and pop them from the other.)

Around the 3 minutes and 30 seconds mark of the talk that
I linked to above, Chandler says that they use their small
vector class as the basis for implementing queues. That's
kind of surprising to me. And at the time that I mentioned
in the original post, he says the constraints on std::deque
are such that "it has very few opportunities to be an
efficient data structure."

For now I took OO Tiib's advice to use std::queue. That
resulted in an 80 byte reduction in the size of the executable.

[Jerry Stuckle]

It's also much more efficient to delete items from the beginning or
middle of std::deque than std::vector.

[Alf P. Steinbach]

On 11.10.2016 00:11, woodb...@gmail.com wrote:
>
> For now I took OO Tiib's advice to use std::queue. That
> resulted in an 80 byte reduction in the size of the executable.

Wow! :-o


Cheers!,

- Alf

[Juha Nieminen]

Jerry Stuckle <jstu...@attglobal.net> wrote:
> It's also much more efficient to delete items from the beginning or
> middle of std::deque than std::vector.

From the beginning sure, of course. But from the middle? It requires as
many operations as with std::vector. If there are differences, I don't
think they are so big.

[Alf P. Steinbach]

On 11.10.2016 08:08, Juha Nieminen wrote:
> Jerry Stuckle <jstu...@attglobal.net> wrote:
>> It's also much more efficient to delete items from the beginning or
>> middle of std::deque than std::vector.
>
> From the beginning sure, of course. But from the middle? It requires as
> many operations as with std::vector. If there are differences, I don't
> think they are so big.

In the formal, yes, but reportedly a typical std::deque implementation
uses a sequence of blocks of items. Only the items within a block then
need to be shifted. Not all items till the end of the item sequence.

E.g. see <url:
http://stackoverflow.com/questions/5728359/stl-internals-deque-implementation>

I am not sure how constant time [] access is provided with this
implementation. That's an interesting question that maybe can be
answered by inspecting some source code. Now that I think of it. ;-)

The standard's requirements instead makes it seem more like a cursor gap
array, with the gap fixed to be between end and beginning.

With a cursor gap there's no problem providing constant time [] access,
and your “requires as many operations as with std::vector” would be true
also for the in-practice.


Cheers & hth.,

- Alf

[mark]

On 2016-10-11 09:10, Alf P. Steinbach wrote:
>>
>> From the beginning sure, of course. But from the middle? It requires as
>> many operations as with std::vector. If there are differences, I don't
>> think they are so big.
>
> In the formal, yes, but reportedly a typical std::deque implementation
> uses a sequence of blocks of items. Only the items within a block then
> need to be shifted. Not all items till the end of the item sequence.
>
> E.g. see <url:
> http://stackoverflow.com/questions/5728359/stl-internals-deque-implementation>

"Only the items within a block then need to be shifted." Which deque
implementation is capable of that? I haven't seen any. All the ones I
have looked at use arrays of fixed-size buckets and shift everything
either to the front or the back on insertion. None have buckets with a
variable number of items (except front and back bucket).

[Mr Flibble]

On 11/10/2016 07:08, Juha Nieminen wrote:
> Jerry Stuckle <jstu...@attglobal.net> wrote:
>> It's also much more efficient to delete items from the beginning or
>> middle of std::deque than std::vector.
>
> From the beginning sure, of course. But from the middle? It requires as
> many operations as with std::vector. If there are differences, I don't
> think they are so big.

I have timings for this made when benchmarking my segmented_array
container; they are:

std::vector random erase: 7.4317 seconds
std::deque random erase: 13.9245 seconds
std::list random erase: 24.8124 seconds
mkr::avl_array random erase: 0.1288 seconds
neolib::segmented_array (1) random erase: 0.2581 seconds
neolib::segmented_array (2) random erase: 0.1250 seconds
neolib::segmented_array (3) random erase: 0.0961 seconds
neolib::segmented_array (4) random erase: 0.0813 seconds
std::vector random insert: 56.7711 seconds
std::deque random insert: 19.2342 seconds
std::list random insert: 55.3831 seconds
mkr::avl_array random insert: 0.1560 seconds
neolib::segmented_array (1) random insert: 0.3113 seconds
neolib::segmented_array (2) random insert: 0.1489 seconds
neolib::segmented_array (3) random insert: 0.1355 seconds
neolib::segmented_array (4) random insert: 0.1741 seconds

Interestingly std::vector and std::deque swap places for erase() vs
insert().

http://i42.co.uk/stuff/segmented_array.htm

/Flibble