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-10-05 17:02:02

Den 04-10-2017 kl. 23:28 skrev Ion Gaztañaga via Boost:
> On 04/10/2017 11:45, Thorsten Ottosen via Boost wrote:
> 
>> Can they share some of the implementation, or are we left with a 
>> double (or triple) implementation effort?
> 
> They can obviously share implementation. That's the case with 
> vector/small_vector/static_vector.

Ok, great.

>>> According to the usual STL rules, size_type shall come from the 
>>> allocator, which knows what type can represent the number of elements 
>>> that can be allocated. 
>>
>> I have no problems with STL rules, but it as you point out, even 
>> Boost.Container deviates from several of those.
> 
> Yes, but only when they are "clearly bad rules (TM)" ;-)

I don't have any strong position about the size_type but thought it nice 
to have a small size of the container on 64 system.

I do sometimes wonder if breaking the strong guarantee is a smart move.

It seems to me that we can end up with non-trivial objects where the 
invariant is broken. So in principle we can't even reliably destroy them 
if the destructor relies on the invariant.

I guess I really dislike that we are allowed to write move operations 
that are not noexcept (like swap).

>>> 4) unsafe_uninitialized_tag: I don’t like these non-safe 
>>> constructors, which are  the cases?. With reserve-only constructors + 
>>> unsafe emplace back a user can achieve nearly the same performance. 
>>> For POD types (like the socket example mentioned in the 
>>> documentation), I would suggest something like Boost.Container’s 
>>> “default_init_t”. Instead of “unsafe_uninitialized_resize_front” I 
>>> suggest resize_front(size_type, default_init_t)
>>
>> I didn't know about these default_init_t when we started in 2015. They 
>> have a good design IMO. But unfortunately they don't get rid of double 
>> initialization for non-trivial types. So maybe both
>>
>> resize_front( size_type, default_init_t )
>> resize_front( size_type, uninitialized_t )
>>
>> would be an idea.
> 
> I understand the idea to avoid zero initialization for buffers, but 
> what's the use case for types with non-trivial constructors? The 
> documentation shows a socket example, and that's covered ith 
> default_init_t.

Well, I don't know if my compiler is wrong, but vc 2017 says:

         class IntClass
         {
             int i;
         public:
             IntClass() : i(0) {}
             IntClass( int i ) : i( i )
             {}
         };

is trivially copyable (hence we can copy arrays of it as fast as arrays 
of ints). But it will be initialized with zero if I use default_init_t, 
right?

If so, I'm just saying that it may be nice/beneficial to be able to 
avoid double initialization also for IntClass (perhaps not relevant to 
sockets, but certainly to serialization).

I do agree that reserve + unchecked_emplace_back() should be working 
well for types that are /not/ trivially copyable (also better in terms 
of exception-safety). The unitialized_resize idea is probably before we 
had emplace and so at that time there was no efficient/easy way to 
construct an object inplace.

About the naming of unsafe_emplace_back: I prefer your suggestion with 
the unchecked_ prefix. Other ideas would be

nonreallocating_emplace_back
nonallocating_emplace_back
nonexpanding_emplace_back
nongrowing_emplace_back // seems wrong, since the size does change

>>> 5) reserve() / resize(): I think they have no sensible meaning in the 
>>> container (capacity() could be useful, depending on the reallocation 
>>> strategy). We should not treat back insertion as the “default” 
>>> insertion. IMHO the API of devector should be symmetrical.
>>
>> Symmetry is good, but what about generic code?
> 
> Generic code can't rely on reserve, only vector implements it in the 
> STL. But if reserve() and resize() are unbiased to back insertion maybe 
> they could make sense. reserve() allocates a new buffer if capacity() is 
> not enough and moves existing elements to the middle. Resize could do 
> the same and fill with elements on both ends.

If reserve is not an alias for reserve_back, the I think we must remove it.

I was thinking along generic code along the line

template< class BacKInsertionContiguousContainer >
void foo( BacKInsertionContiguousContainer& cont )
{
    cont.reserve( source.size() );
    for( ... )
       cont.push_back( ... );

}

why should that not work with both devector and vector?

> stable_insert can maintain stability with a middle insertion but there 
> is no equivalent operation for erasures. I just can't imagine a use case 
> that tan take advantage of stable_insert (it needs more or less a 
> positional insertion, but not absolute, instead of front/back insertion) 
> but it will surely exist.

Yeah, I don't have a use case at hand either. Somehow you would want to 
insert a segments somewhere among the other segments. Then why not allow 
the segments themselves to be rearranged? (potentially almost trivial to 
implement). So I guess we could expose a complete container interface to 
the segments, but it is perhaps premature until we have a good use case.

>> This is tricky. I think the best is to treat both ends independently.
>> If you start moving things around, you can break the O(1) amortized 
>> guarantee by interleaving push_front/push_back.
> 
> What do you mean by "treat both ends independtly"?

I mean that buffer extensions at either end should never affect each 
other. That is, a push_back can never remove free capacity from the 
front, a push_front can never remove free capacity from the back.

kind regards

Thorsten