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-06 09:53:01

Den 05-10-2017 kl. 22:42 skrev Ion Gaztañaga via Boost:
> On 05/10/2017 19:02, Thorsten Ottosen via Boost wrote:
>>> 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?
> 
> Right.

But I agree we don't need two overloads, the existing one just has to
work in terms of trivially copyable. We can also put a static assertion 
in there to lock it down to such types for now.
>> If reserve is not an alias for reserve_back, the I think we must 
>> remove it.
> 
> reserve() means that a container won't reallocate if size() < 
> capacity(). Where memory is reserved is irrelevant for the user.
> 
>> 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?
> 
> It would work, but it would not be as efficient as vector.

It may be. But I guess my concern was to make it compile. Sure, if
a call to reserve is conditioned on d.capacity() - d.size(), it can 
behave differently. Reserve maybe easier to do something about.

We may need to tweak the definition of reserve_back/reserve_front a little.

Let's say we have

   x x 1 1 x

so front_free_capacity is 2, back free capacity is 1 ans size is 2.

with

     d.reserve( d.size() + 3 );

devector uses the expression

   n = new_capacity - size()

so we get n = 5 - 2 = 3 and we get

   x x 1 1 x x x

. A vector 1 1 x does the same. So is your concern that users use 
capacity to determine what/if to reserve?

>>>> 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.
> 
> Ok. I still have no clear idea which allocation strategy would be the 
> "natural" one. I've found this blog with a similar discussion and 
> alternatives:
> 
> http://larshagencpp.github.io/blog/2016/05/22/devector
> 
> also linked from the blog post:
> 
> https://github.com/orlp/devector

Certainly a good analysis.

> Moving elements just one step when one side is full and the other side 
> has capacity has bad quadratic behavior while current capacity is being 
> exhausted and we continue inserting in the same side. Moving elements to 
> the middle of the buffer seems a simple operation that reduces this to 
> something closer to O(NlogN). In any case, I will always bad insertion 
> sequence that hurts our strategy, so optimizing the common case seems 
> the way to go.

I'm ok with inserts in the middle to move stuff around since it already 
has O(n) worst case behavior. For push_back/push_front I don't know.

It would have to be really simple to be worth the effort IMO. Say, only 
when other_size_free_capacity >= size().

The simple thing would be to grow independently, and then the user calls 
shrink to fit when done if he cares about it.

BTW: Before the review some people complained that the container could 
not work as deque when you repeatedly pop from one end and push another.

Something to ponder ...

kind regards

Thorsten