|
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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk