Boost logo

Boost :

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Benedek Thaler (thalerbenedek_at_[hidden])
Date: 2017-09-25 21:13:39

On Mon, Sep 25, 2017 at 2:52 AM, Zach Laine via Boost <boost_at_[hidden]
> wrote:

> I vote to reject Boost.DoubleEnded.
Thanks for your review, I really appreciate your time.

> My first concern is that this library is centered around runtime
> performance,
> yet there appears to be no measurement done to determine what -- or even
> whether -- optimization occurs when using this library instead of the
> standard
> containers.

I'm sure you've seen the `benchmark` documentation page, and the linked ML

I wasn't able to create a convincing micro-benchmark for this container: It
is really hard for the general case. (esp. comparing to vector, which
offers only a subset of devectors features)

On the other hand, a macro-benchmark would require a use-case, which makes
it subjective again. I don't think there's a point in comparing performance
of a small vector vs standard vector, given that the developer got the
`small` size right.

> There are no standard containers for which capacity() == 16 implies that
> when there are three elements, an allocation will occur when I add a
> fourth. That's substantially odd. It means that as a user I must know
> about extrinsic state information (how many pushes were to the front or
> back) in order to predict memory usage and the number of allocations even
> roughly.

No need for extrinsic state info, there are the front_free_capacity() and
back_free_capacity() members.

> de::devector<int> reserved_devector(32, 16, de::reserve_only_tag{});
> [snip]
> That's not a compelling use case to me. Why can't I just do this:
> std::vector<int> reserved_vector;
> vector.reserve(48);

The reserve_only_tag is a convenient shorthand I tend to miss.

> For that matter, is the performance of devector better than std::deque when
> I
> don't know the relative frequency of front- and back-pushes? It seems in
> many
> cases that it would be quite a bit worse.

I do agree. If you have no clue, use a deque - except, in cases when you
are not supposed to use anything more complicated (see: the internal map of
segments of batch_deque is a devector), or contiguous storage is required.

> A custom growth policy must have an integral growth factor, but a commonly
> used growth factor is 3/2.

The growth policy takes the old capacity, and returns the new. new =
uint(3/2*old) is a possible implementation. I don't think float capacity
makes sense.

> I don't understand why should_shrink() is part of GrowthPolicy. If I'm
> growing the container, why am I worried about shrinking it?

Because next time you can avoid growing it.

> Again, from the example docs:
> // int sockfd = socket(...); connect(...);
> de::devector<char> buffer(256, de::unsafe_uninitialized_tag{});
> long recvSize = recv(sockfd,, buffer.size(), 0);
> if (recvSize >= 0)
> {
> buffer.unsafe_uninitialized_resize_back(recvSize);
> // process contents of buffer
> }
> else { /* handle error */ }
> The unsafe resize does nothing in this case, since char has a trivial
> dtor. For
> nontrivially destructed types, we get RAII violations. I don't know how to
> use a type that does that.

One must explicitly call unsafe_uninitialized_resize_back again, after the
exact size is known, avoiding the UB.

> > - What is your evaluation of the implementation?
> >
> I did not look.
> > - What is your evaluation of the documentation?
> >
> There are a lot of aspects of the docs I found to be unclear.
> The Benchmarks section contains no benchmarks.
> There is this:
> "
> Reference stability is an important feature of the batch_deque. Inserting
> elements to the front or to the back of the sequence never invalidates any
> references. Moreover, a special insert operation is provided,
> stable_insert,
> which takes an iterator, as a hint, and inserts a sequence of elements (not
> necessary directly) before the element pointed by the hint, in a way that
> it doesn't invalidate references.
> "
> I find that very difficult to understand. It seems to be saying that
> stable_insert() does not always insert where you wanted in the sequence,
> because the insertion point is just a hint. I think what is intended is
> that the insertion will not necessarily be contiguous (or at least I hope
> that's what is intended).

Perhaps the reference helps?


Boost list run by bdawes at, gregod at, cpdaniel at, john at