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