Boost logo

Boost :

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Zach Laine (whatwasthataddress_at_[hidden])
Date: 2017-09-26 17:22:48

On Tue, Sep 26, 2017 at 10:59 AM, Thorsten Ottosen via Boost <
boost_at_[hidden]> wrote:

> Den 26-09-2017 kl. 03:39 skrev Zach Laine via Boost:
>> On Mon, Sep 25, 2017 at 12:17 PM, Thorsten Ottosen via Boost <
>> boost_at_[hidden]> wrote:

> But the larger point to me is that I can use vector when I care
>> about amortized O(1) growth in either direction. I only care about
>> devector or deque when I need amortized O(1) growth in *both* directions.
> Can you explain how that works for vector when growing the front?


std::vector<int> v;


for (auto it = v.rbegin(), end = rend(); it != end; ++it) {
    // whatever

Just as you don't care whether your stack grow up or down, you don't care
whether you're pushing to the "front" or "back" if you only push/pop to one
side -- because you can always view the resulting sequence in reverse.

 As an aside, my experiments with segmented iteration
>> have been of mixed utility. The standard algorithms useful on segments is
>> limited, since they cannot see across segment boundaries. For instance,
>> adjacent_difference() does not work without some gymnastics.
> We recently got Boost.PolyCollection. It has specialized algorithms:
> I'm wondering if its possible to make these more general.

I think that would be interesting work, perhaps something we could even

> Are you opposed to such containers or is it "all the extra" stuff (which
>>> you don't have to use btw) that makes you uneasy?
>> Up until now, in this post all my objections have been related to runtime
>> efficiency. But now you've brought back up a major complaint that I have,
>> which is the unsafety of the interface. To say that I don't have to use
>> it
>> is a bit disingenuous to me. Adding an unsafe API weakens the invariants
>> of the type, making it more difficult to reason about and use. The idea
>> that I can add elements that will be manually destructed but that are not
>> yet constructed is a serious defect in my opinion. Any throwing operation
>> I do between the creation of such elements and their construction is now
>> unsafe.
> For the record, I'm not trying to be disingeneous. Let me explain.
> The invariant of the container remains the same no matter you do.

They do not. The most basic container invariant is RAII. That is,
elements that have been constructed in the container will be destructed
properly when the container is destructed, and -- importantly -- nothing
else. I should not have to worry about destruction of not-yet-constructed
elements for which there is storage allocated (as with
unsafe_uninitialized* APIs). It does not matter that I do not use these
APIs. If they exist, then later under maintenance I or a coworker may add
use of them. I therefore have to write code that operates under the
invariants of the type, not my particular use of it.

But again, don't get me wrong -- I'm not opposed to doing these kinds of
low-level hacks to get performance. For instance, move operations are
unsafe in a similar fashion (though not as unsafe, IMO), and I use them all
the time.

The issue to me is that these are high-level container types, and yet they
have invariants that are less safe than std::array. I feel they are not
sufficiently justified in such a container.

By the way, there are other ways to get similar performance gains without
sacrificing safety:

template <typename T>
struct devector_guts
    // low level unsafe stuff goes here, "here be dragons", etc.

    T * elements_;
    size_t size_;
    size_t capacity_;

template <typename T>
struct devector
    // only safe operations here

    devector_guts steal_guts () &&; // returns guts; empties *this

    devector_guts guts_;


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.
>>> You are comparing apples and oranges. push_back on vector may be worse
>>> than on deque (just try to store array<T,1024>).
>> Re-reading that. I think I didn't state my point very clearly. What I
>> was
>> trying to say is that the zero-point implied in having separate front and
>> back capacities means that I need to guess the relative frequency of front
>> and back pushes if I want the benefits of reserving space.
> Well, there is nothing that requires you to use
> reserve_front/reserve_back. Just like there is no one that requires you to
> use reserve in vector.

Sure. I'm trying to point out that when I *do* want to use it, the current
separate-and-fixed scheme is hard to use, because you must guess something
close to the relative ratio of front and back pushes.

> When you
>> combine that with the fact that growing a devector requires copying every
>> element, it may be a pessimization to use one over a deque. To me, that's
>> not an apples/oranges comparison, because my use of the entire library
>> boils down to the case where I know I need growth in *both* directions,
>> and
>> now I must determine whether devector or deque is a better fit.
> We are not in disagreement here. But std::deque may be faster than
> std::vector for push_back. So I don't see how that can be a criticism of
> devector. It's not better than vector in this respect.

It's not a criticism of devector at all. It's an open question for which I
have no answer, meaning I have to 1) do a lot of homework (profiling, etc.)
before knowing if I should even consider devector, and 2) weigh any
possible gains in performance against loss of ability to reason about my

It is, however, a criticism of the library, which should do this profiling
homework and proper encapsulation for me.

> And I agree some form of performance tests to give a rough idea of how the
> containers compare would be good.
> The first use case for devector is actually in the implementation of
>>> batch_deque. One could use some deque implementation, but that would not
>>> be
>>> optimal for performance.
>> For small objects or large? For what values of N? For what pattern of
>> calls? Only for double-ended growth, or for single-ended growth as well?
>> I don't necessarily doubt your claim, I just don't have the relative
>> superiority of devector quantified in any way that I can use.
> If you write a deque like container, you need some data-structure to hold
> the segments. For some reason, implementations of deque tends to call this
> a map. Anyway, this "map" needs to support amortized O(1) growth at both
> ends in order for the deque class to guarantee amortized O(1) growth at
> both ends. What all the implementations I know of do is then to create this
> map as an internal data-structure. This clutters the code considerably
> compared to what Benedek has done.
> The reason that you don't want to use deque as a building block for
> batch_deque is that it destroys "map" locality.

Thanks for the explanation. That makes sense.

> I need a justification for unsafe_push_front() besides "avoiding a check,
>>>> thus sparing a few instructions". My intuition is that it does not
>>>> matter, since
>>>> branch prediction is quite good these days, and a single allocation will
>>>> swallow all the gains if there are any.
> [snip]
> First, please demonstrate that I should care about those few instructions.
>> Second, I agree that the difference is slight, but I disagree that it's ok
>> to make that slight change. One of the chief invariants of a standard
>> container is that it manages its storage. This breaks that.
> It's not an invariant of vector that push_back allocates memory.

Sure it is. says:
template reference emplace_back(Args&&... args);
template iterator emplace(const_iterator position, Args&&... args);
void push_back(const T& x);
void push_back(T&& x);
Remarks: Causes reallocation if the new size is greater than the old
capacity. Reallocation invalidates all the references...

> Dangerous
>> interfaces are not necessarily evil, but they certainly need to be
>> justified. I would need significant use cases with significant
>> performance
>> benefits (not night-and-day, but significant) to tolerate this unsafety.
> It might be hard to make you personally care. But even if you don't
> personally care, rest assured that some people will care.

I *do* care about maximizing efficiency. I just want any unsafe code I
have to write to be encapsulated so that I can unit-test it, and not care
about the unsafe details. To the extent that the unsafe details leak out
of the interface, I need *justification for* -- not complete absence of --
the unsafe bits.

> And I do think the documentation should be improved. But the simplicity
> (or not) of a function affects a lot of things:
> - exception specification: unsafe_push_back can be made conditionally
> noexcept, push_back cannot (it is not right now, but it should be).

If it can be, we should do it in Boost. If nothing else, that will serve
as an existence proof of successful industrial use of that approach, making
it a lot easier to sell to the committee.

> - inlineability: the simpler the function, the higher the chance it get's
> inlined
> - register allocation: the simpler the function, the better for the
> optimizer
> - branch prediction: on some platforms this works well, on other not so
> much
> which may depending on situation/platform be a big deal.

I agree with all that.

> But seriously, we should not call functions with one extra precondition
> "dangerous" or "unsafe". It's still much better than the alternative, and
> as I explained above, we should strive to make the inherently low-level and
> unsafe code obsolete. And the only way to do that is to present an
> alternative that is just as per formant (or better) yet offers a superior
> high-level approach. We don't want people to
> use local arrays and manage the size of it manually.

I think that the unsafety comes from changing the invariants in such a way
that I can no longer reason about lifetimes, etc. And going straight to
handwritten code over arrays is IMO a red herring. A second unsafe tier
can be provided with the desired operations, that everyone knows is unsafe,
is truly opt0in, etc.

> buffer.unsafe_uninitialized_resize_back(recvSize);
> It changes the size of the container so you can't read uninitialized
>>> values.
>> That's true, though some sort of span would accomplish the same thing with
>> no loss of safety.
> But then you just postponed the double initialization to when the span
> needs to be copied into a proper container!

Well, in the limited case where I copy it, sure. But that's also true if I
copy buffer after calling


above. The point is you want to use the [0, recvSize) subsequence of
buffer, and you don't need to have a unsafe_uninitialized_resize_back()
member to do that.

> The whole point is that we don't want to forego the great benefit of a
> container just because we are interfacing with a low-level API.

I think we can actually have both.


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