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:23:47

El 16/10/2017 a las 10:45, Thorsten Ottosen via Boost escribió:
> Den 15-10-2017 kl. 17:59 skrev Joaquin M López Muñoz via Boost:
>> El 15/10/2017 a las 15:50, thorsten.ottosen via Boost escribió: 
>>> The idea of keeping track of left right insertions also interesting. 
>>> It does
>>> assume additionally that the insert pattern in the future is the 
>>> same as in
>>> the past, right?
>
> Did you see this question?

Sorry, I missed that one. Yes, we use the insertion pattern after the last
reallocation to estimate the new one. If the insertion pattern changes over
time the policy will adapt with a delay of one reallocation.

>>> I think in the case where the user has called reserve, it’s a little
>>> problematic that insert may allocate anyway. That is, for many uses 
>>> there is
>>> no infinitely growing sequence .
>
> And this one? I'm still not sure we want to allocate on insert before 
> the buffer is full.

If we must guarantee that the buffer is full before reallocation, the 
resulting
policy won't be optimal wrt number of movements. This is the tradeoff. I 
guess
your reservation stems from the desire that capacity()-size() indicates the
number of insertions before reallocation, to that I just answered Ion in 
another post.
My (current) opinion is that capacity() should not be provided.

>
>>> The right_ member can become larger than size if elects are added to 
>>> the
>>> right and removed from the left, not sure what to do about that.
>>
>> Yes, you're right. right_ becoming greater thatn size() can't happen 
>> under the ever-
>> growing assumtion, but it certainly can in the real world.
>
> minor remark: If one goes with this approach, I think the member 
> should be left_ so as to not penalize normal push_back.

This is superseded by the alternative formulation I described above.

>> Let's slightly adjust the policy as follows. I think this copes with 
>> the ever-growing
>> and fixed-size scenarios equally well. Let us remember that the goal 
>> when reserving
>> new free space at both front and back is to make it so that both ends 
>> get exhausted
>> at the same time --if they ever are.
>
>> This has the effect that if no insertions happened at one end (more 
>> precisely,
>> more erasures than insertions took place at that end) then the new 
>> reserved space
>> for that end will be zero. Safe guards may be applied.
>> * When reallocation results in the same total space being reserved 
>> (this happens
>> when the size at reallocation time is equal or less than the size() 
>> at the last reallocation),
>> there is no need to request memory and we can simply shift the 
>> sequence so that
>> back and front free capacity are adjusted according to new_space 
>> calculations. This
>> nicely handles the FIFO scenario, for instance: when the growing side 
>> meets its end,
>> reallocaton resolves to shifting the entire sequence within the 
>> current buffer so that
>> space is kept at that end: this keeps cycling forever with no memory 
>> allocation and
>> minimal element shifting.
>
> So if no elements are added to the left but only to the right, the 
> live elements are
> shifted all the way to the left? That would certainly be optimal, and 
> letting the user decide
> the initial memory consumption let him control how often the shifting 
> is needed. 

Much as I think capacity() should not be provided, reserve would 
probably better replaced
by reserve_front_free/reserve_back_free or something similar.

Joaquín M López Muñoz