Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

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:
>>
>
[snip]

>  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?

Sure:

std::vector<int> v;

v.push_back(1);
v.push_back(2);
v.push_back(3);

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:
>
>   https://tinyurl.com/yaffvebf
>
> I'm wondering if its possible to make these more general.

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

> 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

private:
    devector_guts guts_;
};

[snip]

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
code.

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. 26.3.11.5/1 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

buffer.unsafe_uninitialized_resize_back(recvSize);

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.

Zach