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-18 14:18:23

El 18/10/2017 a las 15:18, Thorsten Ottosen via Boost escribió:
> Den 18-10-2017 kl. 15:10 skrev Joaquin M López Muñoz via Boost:
>> El 18/10/2017 a las 13:48, Thorsten Ottosen via Boost escribió:
>>> Den 18-10-2017 kl. 11:36 skrev Joaquin M López Muñoz via Boost:
>>>> El 16/10/2017 a las 19:38, Thorsten Ottosen via Boost escribió:
>>>
>>>>> Maybe this is lost to me in the details, but given code that works 
>>>>> for vector:
>>>>>
>>>>> Â  vector<int> v;
>>>>> Â  ...
>>>>> Â  v.reserve( v.size() + N );
>>>>>
>>>>> which guarantees no exceptions and no reallocations, how would 
>>>>> that work with your policy?
>
>>> Yes, sorry for being unclear, I'm talking about the guarantee given 
>>> to push_back() and insert() of N elements after the call to reserve(). 
>>
>> OK, now I get it. Well, my position is that reserve should be 
>> replaced by
>> some mechanism for explicitly controlling free space at each end. 
>> Then the user
>> can rely on the guarantee that she can do as many as
>> [back|front]_free_capacity() push_[back|front] ops without rellocation.
>
> and what about insert()? Do we then say if you want to avoid 
> reallocations, you must allocate twice the needed memory?
>
> For vector we do not reallocate on insert().
>
> (I'm not saying that is the wrong answer, I would just like to know 
> that the answer is). 

My proposed policy consumes back free capacity if we have a right 
insertion (past the
middle of the devector) and front free capacity in the case of a left 
insertion (before
the middle of the devector). If you want to guarantee N no-reallocation 
insertions at
any position so, yes, both front and back free capacity has to be >=N.

For the benefit of the readers, allow me to paste here the policy 
description:

* Fix the growing factor to G.
* The right balancing factor B is defined as the ratio between back free 
capacity and total
free capacity. Let's say this is 50% at the start, that is, we have 
front_free_capacity()=
back_free_capacity().
* Right insertions and left insertions shift to the right and left, 
respectively (as before).
* When reallocation is needed, calculate the new balance factor as a 
function of
front and back space consumption just prior to reallocation. Pseudocode 
follows:

 Â  struct free_space
 Â  {
 Â Â Â  std::size_t back,front
 Â  };

 Â  free_space new_space(free_space original,free_space remaining)
 Â  {
 Â Â Â  float balance=(float)std::max(original.back-remaining.back,0)/
(std::max(original.back-remaining.back,0)+std::max(original.front-remaining.front,0));
 Â Â Â  std::size_t 
new_space=std::max(size()*G,size()+remaining.back+remaining.front),
 Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  new_free_space=new_space-size();
 Â Â Â  return {balance*new_free_space,(1-balance)*new_free_space};
 Â  }

Joaquín M López Muñoz