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

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-10-16 08:45:18

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ó:
>> hi Joaquin,
>>
>> Thanks for this. Some comments below.

>> Facts
>>

>> —
>> How do you get that number ? I would say  we save
>> Incur 1/2 * size movements on average for shifting to the end with free
>> space.
> 
> The number follows from: assume right insertion is at position N, that 
> means that
> under normal conditions (there's back free capacity) we need to make
> size()-N movements to the right. If instead of that we shift to the left 
> the resulting
> number of movements is N, so the penalty for taking the "wrong" decision is
> the difference N - (size()-N) = 2*N - size(). Did I explain myself now? 

yes, I somehow got confused.

>> Description of resulting policy
>>

>> 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?

>> 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.

>> 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.

> 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.

kind regards

Thorsten