Re: [boost] [devector] optimum growing/insertion policy

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-10-17 12:08:59

El 16/10/2017 a las 1:45, Ion Gaztañaga via Boost escribió:
> On 15/10/2017 17:59, Joaquin M López Muñoz via Boost wrote:
>> The assumption is of an ever growing sequence. That said, I 
>> recorgnize there are
>> scenarios not falling under this, most notably FIFO queues. I've 
>> given the policy
>> a little more thought and think we can twist it to also accommodate 
>> non-growing
>> scenarios, please keep on reading.
>>
>> Thougths?
>
> I think that the default (we could have other policies) should be 
> simple and similar to
> vector/string/stable_vector/etc.... In this sense, capacity() and 
> reserve(), if provided,
> should make sense. If we reallocate depending on the free capacity of 
> one side, then
> capacity() and reserve() make no sense to the user
>
> I think the user expects capacity() as the maximum number of 
> insertions, in any position,
> that will be accepted before reallocating. Making free_capacity = 
> capacity() - size(), less
> than, say, back_free_capacity() will be really hard to understand by 
> users.

I think providig capacity() will lead to confusion no matter the 
growing/insertion policy. For instance,
users of vector/string/... expect capacity()-size() to be the number of 
push_back()'s accepted without
iterator invalidation. Your policy below does break this expectation 
--as any policy other than the
pathological case where front is given no free space ever.

> I propose a simple strategy:
>
> [...]

For any policy, there's a tradeoff between number of movements and 
wasted space --i.e.
space not used before reallocation. Yours prioritizes the latter, mine 
the former.

> Statistics based policies seem more complex, and I don't know how well 
> they will adapt to
> pattern changes thorough the lifetime of the container, plus they 
> impose a size cost to the
> container. I wouldn't make the the default choice, as the average user 
> should easily understand
> the default policy.

Any policy can in principle be implemented behind the following interface:

 Â  struct free_space{std::size_t back,front;};
 Â  free_space query_for_insertion(std::size_t pos,std::size_t n);

used like this (pseudocode):

 Â  auto new_free_space=query_for_insertion(pos,n);
 Â  if(new_free_space.back+new_free_space.front>free_capacity()){
 Â Â Â  // allocate or request in-place extension
 Â Â Â  // move and insert appropriately so that 
back_free_capacity()==new_free_space.back
 Â Â Â  // and front_free_capacity()==new_free_space.front
 Â  }
 Â  else{
 Â Â Â  // free space rebalance
assert(new_free_space.back+new_free_space.front==free_capacity());
 Â Â Â  // move and insert appropriately so that 
back_free_capacity()==new_free_space.back
 Â Â Â  // and front_free_capacity()==new_free_space.front
 Â  }

Why don't we equip devector with such a customization point and test the
different alternatives for real?

> For a FIFO, I think a deque that reuses free segment capacity on one 
> side and transfers
> it to the other side before allocating new memory would be the best 
> choice. Currently
> boost::container::deque does not do this, but pull requests are 
> welcome ;-) 

Or a circular buffer, but devector is the only structure that would 
additionally
guarantee memory contiguity.

Joaquín M López Muñoz