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: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-09-26 15:59:21

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

>> Is it it not obvious that an O(1) push_front performs better than an O(n)
>> vec.insert( vec.begin(), x ) ?
>>
> 
> I find the use of the word "obvious" when applied to optimization to be a
> little suspect. 

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

> Then, it is a question of whether the relative performance recommends
> devector or deque.  As of this writing, I have to write benchmarks or do a
> lot of custom profiling to figure out which works better.
> 
> My strong preference would be that the author provide sufficient
> measurements of a few use cases of both of these data structures at various
> values of N, so that I can make a reasonable educated guess when first
> selecting the data structure to use.  It won't allow me to elide profiling
> altogether, but it will get me going in the right direction more often,
> with less effort for me as a user.

I agree that is not a bad thing to add to the documentation.

>  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. Basically, a 
poly-collection stores a vector for each dynamic type, and this is a bit 
like a segment (although segment size may differ).

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

I dislike the word "unsafe" used in the naming of such functions, but 
that is what Benedek has chosen. For example, I don't think a function 
should be labeled unsafe just because it has one extra precondition 
compared to a similar function. If we did that, quite a few "unsafe" 
labels would appear in a normal high-level C++ program.

Now, the functions that allow you to avoid double initialization can be 
misused. They have a strict contract if you will. Does that mean no 
library can ever contain such functionality? My personal view is that
if containers over-encapsulate in order to be "safe" (or "safer"), but 
sacrifice near-optimal performance, some users will chose not to use 
them. And what they fall back on is going to be so much worse than using 
a container that is built to help them (worse in terms of 
exception-safety, abstraction, low-levelness of code). So what has been 
added to devector is the minimal thing needed to accomplish the goal of 
giving the user the choice of getting rid of double initialization.

So if we chose not to add such functionality, it will make the container 
less useful to some (not all) people. And that is perhaps why I don't 
understand your argument. Yes, some of the function are more difficult 
to use, but only if actually use them. And those very few who do need to 
use them will find them much easier to use than the alternatives.

> 
>> Serialization:
>> --------------
>>
>> std types are over encapsulated which means that they can't avoid double
>> initialization, nor process elements in batches. Is it not obvious that
>> double initialization is more expensive than single initialization?
> 
> 
> In the abstract, of course you cannot argue with that.  I don't find it to
> be a useful question, though.  The questions I have are:
> 
> 1) In my specific case, do I care (that is, is it measurable)?  In many
> cases, a type will be expensive to copy or non-default-construct, but
> trivial to default construct.
> 2) If the answer to #1 is yes, is reserve() not sufficient?
> 
> I would expect the answer to one of those two questions to be "no" in
> almost all cases.  It's not that you'd *never* answer "yes" to both, it's
> just that this represents a low-frequency corner.

No matter how we program, I think it's safe to say that container<int> 
or container<char> is not going away any time soon. So the answer to 
your question is that "it depends". If you high-level objects are build 
upon low-level things, making those low-level things faster can 
certainly impact the high-level things.

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

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

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.

>> 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. 
unsafe_push_back does not change anything wrt. what the container manages.

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

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.

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

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.

kind regards

Thorsten