Boost logo

Boost :

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
 Â Â Â  // and front_free_capacity()==new_free_space.front
 Â  }
 Â  else{
 Â Â Â  // free space rebalance
 Â Â Â  // move and insert appropriately so that
 Â Â Â  // 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
guarantee memory contiguity.

Joaquín M López Muñoz

Boost list run by bdawes at, gregod at, cpdaniel at, john at