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