[devector] optimum growing/insertion policy

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
38 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[devector] optimum growing/insertion policy

Boost - Dev mailing list
Hi,

Much an worthy discussion has taken place with respect to growing and
insertion
policies of boost::double_ended::devector. I think I can justify what
the optimum policy
is when the overall goal is to minimize number of element movements.
What follows
is *not* a formal optimality proof, though it's my hunch one could be
provided
relatively easily.

Assumptions

* The cost of allocating new memory is negligible when compared to the cost
of moving elements around (either intra-buffer or when migrating to a
new buffer);
so, the growing/insertion policy should focus on minimizing number of
elements
moved. This implies fully occupying free space before reallocation is
*not* the primary
goal of the growing/insertion policy.
* For the purposes of our discussion, we consider an ever-growing
devector without
intervening erasures --erasures can be accomodated later as we will see.
* Element insertion is modelled as a process where each new insertion
happens at a
random position within the current devector. The minimal
characterization (i.e. its
1st moment in stochastic process theory terminology) is just the
percentage R of
insertions that happen within the right half of the devector --we call these
*right insertions*; left insertions happen then with a frequency L=1-R.
push_back is a
right insertion, push_front a left insertion.

Facts

* When  a right insertion arrives, if there's free back capacity the
optimum insertion
policy is to shift elements to the right, as this involves fewer
movements than
the other way around. The symmetrical applies for left insertions.
* If a right insertion at position N arrives and there's no free back
capacity (but there
is free front capacity), we have only two options:
   A. Reallocate to get back free capacity.
   B. Shift elements to the left.
The key observation here is that A is cheaper in the long run: as the
scenario is one
of an ever-growing sequence, reallocation will happen eventually and we can
just amortize it in our analysis, so reallocating early saves us the
extra movements
incurred when left shifting on a right insertion, namely N - (size()-N)
= 2*N - size()
movements. In fact, we save more than that as insertion is done
simultaneously with
reallocation, hence no shifting occurs additionally to the (amortized)
reallocation
cost. All this analysis applies symmetrically to left insertions, of course.
* The optimum growing policy is that which maximizes the probability
that *both*
front and back free capacities get exhausted at the same time. With our
1st moment
characterization of the insertion random process, this implies that when
reallocating
a percentage R of the new space should be devoted to the right side, and
a percentage
L to the left side.

Description of resulting policy

* Fix the growing factor to G (this can be 1.5 or 2 or anything greater
than one,
the actual figure is orthogonal to the discussion).
* Maintain a counter right_ of right insertions that gets incremented when a
right insertion occurs and *decremented* when an erasure is issued past the
middle of the devector.
* Right insertions trigger right shifting except when there's no back
free capacity,
in which case a reallocation is performed.
* Left insertions trigger left shifting except when there's no front
free capacity,
in which case a reallocation is performed.
* Reallocation reserves space for G*size() elements: of the resulting
G*size()-size()
free space, a fraction right_/size() is devoted to back free capacity,
the rest to
front free capacity. In practice, we may want to keep some minimum space
at each end as determined by some empirical threshold.

And that's it. Comments welcome.

Joaquín M López Muñoz


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
hi Joaquin,

Thanks for this. Some comments below.

Assumptions

* The cost of allocating new memory is negligible when compared to the cost
of moving elements around (either intra-buffer or when migrating to a
new buffer);
so, the growing/insertion policy should focus on minimizing number of
elements
moved. This implies fully occupying free space before reallocation is
*not* the primary
goal of the growing/insertion policy.
——-

But in the real world allocations (+ the implied deallocation ) is not that
cheap, especially not with non trivial destructors. For small containers,
typical for flat containers, I’m not sure this is a good assumption.


Facts

* When  a right insertion arrives, if there's free back capacity the
optimum insertion
policy is to shift elements to the right, as this involves fewer
movements than
the other way around. The symmetrical applies for left insertions.
* If a right insertion at position N arrives and there's no free back
capacity (but there
is free front capacity), we have only two options:
   A. Reallocate to get back free capacity.
   B. Shift elements to the left.
The key observation here is that A is cheaper in the long run: as the
scenario is one
of an ever-growing sequence, reallocation will happen eventually and we can
just amortize it in our analysis, so reallocating early saves us the
extra movements
incurred when left shifting on a right insertion, namely N - (size()-N)
= 2*N - size()

——

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.



Description of resulting policy

* Fix the growing factor to G (this can be 1.5 or 2 or anything greater
than one,
the actual figure is orthogonal to the discussion).
* Maintain a counter right_ of right insertions that gets incremented when a
right insertion occurs and *decremented* when an erasure is issued past the
middle of the devector.
* Right insertions trigger right shifting except when there's no back
free capacity,
in which case a reallocation is performed.
* Left insertions trigger left shifting except when there's no front
free capacity,
in which case a reallocation is performed.
* Reallocation reserves space for G*size() elements: of the resulting
G*size()-size()
free space, a fraction right_/size() is devoted to back free capacity,
the rest to
front free capacity. In practice, we may want to keep some minimum space
at each end as determined by some empirical threshold.


And that's it. Comments welcome.



—-____


Interesting analysis. Thanks. I agree if the sequence is ever growing, it’s
better to allocate when one end is full.

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?

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 .

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.
 
It will also make operations slower, but that can be tested.

Kind regards

Thorsten



--
Sent from: http://boost.2283326.n4.nabble.com/Boost-Dev-f2600599.html

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
El 15/10/2017 a las 15:50, thorsten.ottosen via Boost escribió:

> hi Joaquin,
>
> Thanks for this. Some comments below.
>
> Assumptions
>
> * The cost of allocating new memory is negligible when compared to the cost
> of moving elements around (either intra-buffer or when migrating to a
> new buffer);
> so, the growing/insertion policy should focus on minimizing number of
> elements
> moved. This implies fully occupying free space before reallocation is
> *not* the primary
> goal of the growing/insertion policy.
> —
> But in the real world allocations (+ the implied deallocation ) is not that
> cheap, especially not with non trivial destructors. For small containers,
> typical for flat containers, I’m not sure this is a good assumption.

The assumption is of an ever growing sequence. That said, I recorgnize
there are
scenarios not falling under this, most notably FIFO queues. I've given
the policy
a little more thought and think we can twist it to also accommodate
non-growing
scenarios, please keep on reading.

> Facts
>
> [...]
> * If a right insertion at position N arrives and there's no free back
> capacity (but there
> is free front capacity), we have only two options:
>     A. Reallocate to get back free capacity.
>     B. Shift elements to the left.
> The key observation here is that A is cheaper in the long run: as the
> scenario is one
> of an ever-growing sequence, reallocation will happen eventually and we can
> just amortize it in our analysis, so reallocating early saves us the
> extra movements
> incurred when left shifting on a right insertion, namely N - (size()-N)
> = 2*N - size()
>
> —
> 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? 
The worst case
is when N is right at the end of the sequence (N=size()) and there's no
free space at
the back, the penalty is then N - (size()-N) = size(), that is, we have
to shift the
entire sequence to the left (in which case it's clear that reallocating
would have been
a better decision).

> Description of resulting policy
>
> [...]
>
> —
>
> Interesting analysis. Thanks. I agree if the sequence is ever growing, it’s
> better to allocate when one end is full.
>
> 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?
>
> 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 .
>
> 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.

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.

* 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)/
       (original.back+original.front-remaining.back-remaining.front); //
denominator can't be 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};
   }

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.

Thougths?

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
El 15/10/2017 a las 17:59, Joaquin M López Muñoz escribió:
> [...]
>
>     float balance=(float)std::max(original.back-remaining.back,0)/
> (original.back+original.front-remaining.back-remaining.front); //
> denominator can't be 0

This should be

     float balance=(float)std::max(original.back-remaining.back,0)/
(std::max(original.back-remaining.back,0)+std::max(original.front-remaining.front,0);

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 15/10/2017 17:59, Joaquin M López Muñoz via Boost wrote:
> The assumption is of an ever growing sequence. That said, I recorgnize
> there are
> scenarios not falling under this, most notably FIFO queues. I've given
> the policy
> a little more thought and think we can twist it to also accommodate
> non-growing
> scenarios, please keep on reading.
>
> Thougths?

I think that the default (we could have other policies) should be simple
and similar to vector/string/stable_vector/etc.... In this sense,
capacity() and reserve(), if provided, should make sense. If we
reallocate depending on the free capacity of one side, then capacity()
and reserve() make no sense to the user

I think the user expects capacity() as the maximum number of insertions,
in any position, that will be accepted before reallocating. Making
free_capacity = capacity() - size(), less than, say,
back_free_capacity() will be really hard to understand by users.

I propose a simple strategy:

Definitions:
---------

capacity() = the size of the buffer
free_capacity() = capacity() - size()
xxx_free_capacity() = the number of unconstructed items in the xxx (xxx
= left or right) side of the buffer.
N = the number of items to be inserted
GF = growth factor

Strategy:
---------

1) devector is initialized with equal free capacity for both ends.
2) If a xxx (xxx = left or right) insertion is needed and
xxx_free_capacity >= the number of items to be inserted, a xxx insertion
is done (minimizes moves).
3) Otherwise if a xxx (xxx = left or right) insertion is needed and
xxx_free_capacity < N, the sequence containing new plus old elements
should be placed in the middle of the buffer. (Note: This step should be
limited if amortized constant time is desired for push_xxx insertions)
4) Otherwise if the allocator supports in-place expansion, the buffer is
expanded for max(size()+N, capacity()*GF) and if successful, steps 2 or
3 are performed depending on the new xxx_free_capacity value.
5) Otherwise a new buffer is allocated and the new sequence containing
new plus old elements should be placed in the middle of the buffer.

For uniformly distributed random insertions on both ends, very few extra
movements will be done. This means it's amortized constant time, just
like vector.

Worst case: for a repeated one-side insertion, when N/2 insertions are
performed, the first relocation step will take place. In general,
log(N/2) relocation steps (each one with a increasing number of moves)
will be performed before reallocating a new buffer. I don't think it's
amortized constant time, but amortized logarithmic time (but see below).

Extra moves can be reduced by imposing a capacity() that is a factor
(say reallocation factor, RF) of the buffer size, forcing to
reallocation when the load factor is high. This means that if size() is
capacity() = RF*internal_buffer_size, even if there is room for the
left/right insertions a reallocation will be performed. This means that
capacity() = RF*internal buffer is known and means something to the
user. Memory usage will grow, but data movement will be minimized. RF
could be a policy-based parameter.

I think the RF factor obtains an amortized constant time for one side
insertion if that property is considered useful. It's equivalent to
reduce the number of relocations to a to a fixed number of steps, so the
average movement to insert N elements in a devector of capacity C = N/RF
is proportional to N.

For a quick example (number might be wrong, but you get the idea) of a
repeated push_back:

If relocation steps are limited to 3, which happens with RF = 15/16, we
need N = 15/16 C moves to insert new elements, plus C/2 + 3/4*C + 7/8*C
moves to move already inserted elements. This means something like N +
17/8*C = N + 17/8*N/RF = 49/15*N = 3,26*N moves.

A fast choice would be to allow just two relocations, a RF of 7/8 =
(0,87) which would mean aprox. 2,6*N moves to push_back N elements. A RF
of 3/4 (0.75, single relocation step) would mean 1,33*N moves to
push_back N elements.

Statistics based policies seem more complex, and I don't know how well
they will adapt to pattern changes thorough the lifetime of the
container, plus they impose a size cost to the container. I wouldn't
make the the default choice, as the average user should easily
understand the default policy.

For a FIFO, I think a deque that reuses free segment capacity on one
side and transfers it to the other side before allocating new memory
would be the best choice. Currently boost::container::deque does not do
this, but pull requests are welcome ;-)

Best,

Ion

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
I can only say that I fully agree with the approach taken in this thread.

All of the above builds on the assumption of free_front equals free_back on
relocation. I think, since we are starting to talk about a *very*
performant vector-type implementation, that it would be appropriate to
provide a free_allocation_ratio_policy<F, B> of sorts, i.e. generalise the
1:1 and make it std::ratio<F, B>, with a default of std::ratio<1, 1> (so
not everybody needs to read the small print).

On small devectors this has rounding issues. std::ratio<1000, 999> could
denote that, this would mean roughly a policy of 1:1, but to 'round towards
the front'.

One could imagine a de::devector_tuner, deriving from de::devector, to
trace and be queried over how front and back pushed/emplacements are split,
so one can apply the optimal free_allocation_ratio_policy<F, B> after
a/some test runs in a live situation (adaptive is possible as well, that
that might be a high price to pay).

Another thought (off thread!) is that de::devector should provide void
unordered_erase ( iterator & it_ ) noexcept;, often when one uses a
vector-like structure, one does not care about order. So I imagine a member
function, conceptually like the below, providing O1 erase:

void unordered_erase ( iterator & it_ ) noexcept {

   *it_ = back ( );
   resize ( size ( )  - 1 );
}

degski
--
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 16-10-2017 kl. 01:45 skrev Ion Gaztañaga via Boost:

> On 15/10/2017 17:59, Joaquin M López Muñoz via Boost wrote:
>> The assumption is of an ever growing sequence. That said, I recorgnize
>> there are
>> scenarios not falling under this, most notably FIFO queues. I've given
>> the policy
>> a little more thought and think we can twist it to also accommodate
>> non-growing
>> scenarios, please keep on reading.
>>
>> Thougths?
>
> I think that the default (we could have other policies) should be simple
> and similar to vector/string/stable_vector/etc....

Yes, let's keep it simple.


> I propose a simple strategy:
>
> Definitions:
> ---------
>
> capacity() = the size of the buffer
> free_capacity() = capacity() - size()
> xxx_free_capacity() = the number of unconstructed items in the xxx (xxx
> = left or right) side of the buffer.
> N = the number of items to be inserted
> GF = growth factor
>
> Strategy:
> ---------
>
> 1) devector is initialized with equal free capacity for both ends.

I assume that implies reserve() does the very same?

> 2) If a xxx (xxx = left or right) insertion is needed and
> xxx_free_capacity >= the number of items to be inserted, a xxx insertion
> is done (minimizes moves).
> 3) Otherwise if a xxx (xxx = left or right) insertion is needed and
> xxx_free_capacity < N, the sequence containing new plus old elements
> should be placed in the middle of the buffer. (Note: This step should be
> limited if amortized constant time is desired for push_xxx insertions)

There might be some corner cases here. Suppose we have
front_free_capacity() == 3, back_free_capacity() == 0 and is about to
insert to the right half. Does it then make sense to place elements in
the middle?

If we shift by one element position we pay (on average)

  size * 3/4 moves

If we move to the middle, we have to move everything and pay

  size * moves

We now have two (average) insertions to gain the lost moves before we
allocate. One will be in the left side, so has no impact. The other
insertion will now take

  size * 1/4 moves

if we placed in the middle and

  size * 3/4 moves

if we shifted. So shifting leads to

  size * 6/4 moves

and moving to the middle leads to

  size * 5/4 moves.

So I agree, we should probably always move to the middle if the free
space >= 3 (at the other end). This applies to situations where
reallocating is not desired.

> Worst case: for a repeated one-side insertion, when N/2 insertions are
> performed, the first relocation step will take place. In general,
> log(N/2) relocation steps (each one with a increasing number of moves)
> will be performed before reallocating a new buffer. I don't think it's
> amortized constant time, but amortized logarithmic time (but see below).
>
> Extra moves can be reduced by imposing a capacity() that is a factor
> (say reallocation factor, RF) of the buffer size, forcing to
> reallocation when the load factor is high. This means that if size() is
> capacity() = RF*internal_buffer_size, even if there is room for the
> left/right insertions a reallocation will be performed. This means that
> capacity() = RF*internal buffer is known and means something to the
> user. Memory usage will grow, but data movement will be minimized. RF
> could be a policy-based parameter.
>
> I think the RF factor obtains an amortized constant time for one side
> insertion if that property is considered useful.

I think that is a must.

> A fast choice would be to allow just two relocations, a RF of 7/8 =
> (0,87) which would mean aprox. 2,6*N moves to push_back N elements. A RF
> of 3/4 (0.75, single relocation step) would mean 1,33*N moves to
> push_back N elements.

I like low numbers here.

> For a FIFO, I think a deque that reuses free segment capacity on one
> side and transfers it to the other side before allocating new memory
> would be the best choice. Currently boost::container::deque does not do
> this, but pull requests are welcome ;-)

Or maybe just boost::circular_buffer (is this not the optimal way to
handle that case?). No one is saying that devector has to solve every
problem.

I do want to focus on simple properties from a user's perspective. Some
cases to consider:

# case 1: push_back from empty state
------------------------------------

   vector<int> v;
   v.reserve( N );

This guarantees N pushes without exceptions and without reallocation.


# case 2: push_back from unknown state
--------------------------------------

   vector<int> v;
   ...
   v.reserve( v.size() + N );

This guarantees N pushes without exceptions and without reallocation.

# case 3: insert from empty state
---------------------------------

   vector<int> v;
   v.reserve( N );

This guarantees N inserts without exceptions and without reallocation.

# case 4: insert from unknown state
-----------------------------------

   vector<int> v;
   ...
   v.reserve( v.size() + N );

This guarantees N inserts without exceptions and without reallocation.

How do these properties work for a devector? If I understand your
strategy, we get the following:

# case 1: push_back from empty state
------------------------------------

   devector<int> v;
   v.reserve( N );

This does not guarantee N pushes without exceptions or without
reallocation. To get that guarantee we have to write

   devector<int> v;
   v.reserve_back( N );


# case 2: push_back from unknown state
--------------------------------------

Same as for case 1: no guarantees unless reserve_back is called.

# case 3: insert from empty state
---------------------------------

   devector<int> v;
   v.reserve( N );

This does not guarantees N inserts without exceptions or without
reallocation. Using reserve_back or reserve_front doesn't help either.
The only thing that works is if insert defers all reallocation till it
is absolutely needed.


# case 4: insert from unknown state
-----------------------------------

Same as for case 3: no guarantees unless insert exhaust memory.


There are various ways to fix that: either the user replaces

    v.reserve( N )
    v.reserve( v.size() + N )

with

    v.reserve( N * 2 )
    v.reserve( v.size() + N * 2 )

or reserve() automatically acquires double the extra memory requested.
The latter will also make generic code work as expected. Using the
double amount of requested memory automatically guarantees the optimal
insertion performance: no move to the middle is ever required and on
average devector performs half the moves of vector.

If the user wants less memory waste for push_front/push_back, he can use
reserve_front/reserve_back.

If the user wants full capacity usage for insert, he can only get that
if we exhaust memory for insert by moving to the middle and make reserve
allocate exactly what he asks for. Even so, devector should perform no
worse than vector, and likely somewhat better.

Unfortunately, the is no scheme that is 100% compatible with vector if
reserve() for devector produces front_free_capacity() ==
back_free_capacity(). For that to work, reserve() must act as
reserve_back().

Would that be undesirable for insert of reserve() is modeled after the
vector? What would happen is that the first time an element falls in the
front half, the elements are moved to the middle. This is probably
acceptable compared to removing reserve() altogether because its
semantics are ambiguous.

How do we get the optimal performance for flat containers? We can still
call reserve( 2 * N ) and then only pay one move to the middle
operation. This is not 100% optimal, granted. For that to happen flat
containers would need to forward additional arguments for reserve().
(and possibly clear() as well)

How bad is it to waste 50% memory for optimal flat containers. If the
container is local in a function, it is probably of no concern at all.
Otherwise one may use trim_to_fit() if that applies. At any rate, it
would be the user that decides.

kind regards

Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 15-10-2017 kl. 14:09 skrev Joaquin M López Muñoz via Boost:
> Hi,

> * Maintain a counter right_ of right insertions that gets incremented
> when a
> right insertion occurs and *decremented* when an erasure is issued past the
> middle of the devector.

So to implement this with a custom Resizing policy, the policy would
need be stored via compressed_pair as a member and additionally provide
a hook:

   right_event( int elements )

where elements can be both positive and negative and which is called
from push_back and insert as needed. By default this could be an empty
function.

> * Right insertions trigger right shifting except when there's no back
> free capacity,
> in which case a reallocation is performed.
> * Left insertions trigger left shifting except when there's no front
> free capacity,
> in which case a reallocation is performed.
> * Reallocation reserves space for G*size() elements: of the resulting
> G*size()-size()
> free space, a fraction right_/size() is devoted to back free capacity,

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? Is it going to depend on no left insertions ever to
have been made for v?

kind regards

-Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 16-10-2017 kl. 19:18 skrev Thorsten Ottosen via Boost:

> I do want to focus on simple properties from a user's perspective. Some
> cases to consider:
>
> # case 1: push_back from empty state
> ------------------------------------
>
>    vector<int> v;
>    v.reserve( N );
>
> This guarantees N pushes without exceptions and without reallocation.
>
>
> # case 2: push_back from unknown state
> --------------------------------------
>
>    vector<int> v;
>    ...
>    v.reserve( v.size() + N );
>
> This guarantees N pushes without exceptions and without reallocation.

A note: this is why I absolutely loathe reserve() compared to a function
called

   v.anticipate( N )

which would work equally well in both cases.

-Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 16/10/2017 19:18, Thorsten Ottosen via Boost wrote:
>>
>> 1) devector is initialized with equal free capacity for both ends.
>
> I assume that implies reserve() does the very same?

Yes.

>> 2) If a xxx (xxx = left or right) insertion is needed and
>> xxx_free_capacity >= the number of items to be inserted, a xxx
>> insertion is done (minimizes moves).
>> 3) Otherwise if a xxx (xxx = left or right) insertion is needed and
>> xxx_free_capacity < N, the sequence containing new plus old elements
>> should be placed in the middle of the buffer. (Note: This step should
>> be limited if amortized constant time is desired for push_xxx insertions)
>
> There might be some corner cases here. Suppose we have
> front_free_capacity() == 3, back_free_capacity() == 0 and is about to
> insert to the right half. Does it then make sense to place elements in
> the middle?

We are optimizing the general case, we don't know where the user is
going to insert the next element. Putting data in the middle seems the
choice that minimizes worst-case scenarios. What if the next insertion
is in the left half (say, via flat_map)? In any case if we want some
kind of cache, we could just move new elements to the side where free
elements were available in the old buffer with some kind of logic, like
moving data more to left if right free capacity was exhausted.

>> I think the RF factor obtains an amortized constant time for one side
>> insertion if that property is considered useful.
>
> I think that is a must.

Ok. That's what's used in the alternative implementation in:

http://larshagencpp.github.io/blog/2016/05/22/devector

using a reallocation factor of 0.8. push_back benchmarks seem quite
inline with vector and deque. But it uses some statistics based approach
to relocate the buffer so that the push_back case is optimized instead
of a random insertion scenario.

>> For a FIFO, I think a deque that reuses free segment capacity on one
>> side and transfers it to the other side before allocating new memory
>> would be the best choice. Currently boost::container::deque does not
>> do this, but pull requests are welcome ;-)
>
> Or maybe just boost::circular_buffer (is this not the optimal way to
> handle that case?). No one is saying that devector has to solve every
> problem.

You are right, circular_buffer should be container to use.

> I do want to focus on simple properties from a user's perspective. Some
> cases to consider:
>
> # case 1: push_back from empty state
> # case 2: push_back from unknown state
> # case 3: insert from empty state
> # case 4: insert from unknown state
>
> How do these properties work for a devector? If I understand your
> strategy, we get the following:

I think all of them work.

> # case 1: push_back from empty state
> ------------------------------------
>
>    devector<int> v;
>    v.reserve( N );
>
> This does not guarantee N pushes without exceptions or without
> reallocation. To get that guarantee we have to write

If I'm not mistaken, you get the same guarantee. The difference is that
elements are "relocated" (moved), but there is no "reallocation" (new
buffer allocation). They are first moved when N/2 elements are
push_backed and left/right_free_capacity() is zero, then after
push_backing additional N/2 elements, etc (the number of relocations
(moves) steps depend on the "relocation factor"). Since push_back
requires nothrow move constructible to avoid exceptions, moving elements
is not a problem, because all of them will be noexcept.

If I understand it correctly, it's more or less the same strategy used in:

http://larshagencpp.github.io/blog/2016/05/22/devector

Best,

Ion

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
Den 16-10-2017 kl. 22:57 skrev Ion Gaztañaga via Boost:
> On 16/10/2017 19:18, Thorsten Ottosen via Boost wrote:

>>> 2) If a xxx (xxx = left or right) insertion is needed and
>>> xxx_free_capacity >= the number of items to be inserted, a xxx
>>> insertion is done (minimizes moves).
>>> 3) Otherwise if a xxx (xxx = left or right) insertion is needed and
>>> xxx_free_capacity < N, the sequence containing new plus old elements
>>> should be placed in the middle of the buffer. (Note: This step should
>>> be limited if amortized constant time is desired for push_xxx
>>> insertions)
>>
>> There might be some corner cases here. Suppose we have
>> front_free_capacity() == 3, back_free_capacity() == 0 and is about to
>> insert to the right half. Does it then make sense to place elements in
>> the middle?
>
> We are optimizing the general case, we don't know where the user is
> going to insert the next element. Putting data in the middle seems the
> choice that minimizes worst-case scenarios. What if the next insertion
> is in the left half (say, via flat_map)? In any case if we want some
> kind of cache, we could just move new elements to the side where free
> elements were available in the old buffer with some kind of logic, like
> moving data more to left if right free capacity was exhausted.

Right. My point was simply that it pays (in the average case) to move to
the middle even when there is only a free space of 3 on the other side.

>>> I think the RF factor obtains an amortized constant time for one side
>>> insertion if that property is considered useful.
>>
>> I think that is a must.
>
> Ok. That's what's used in the alternative implementation in:
>
> http://larshagencpp.github.io/blog/2016/05/22/devector
>
> using a reallocation factor of 0.8. push_back benchmarks seem quite
> inline with vector and deque. But it uses some statistics based approach
> to relocate the buffer so that the push_back case is optimized instead
> of a random insertion scenario.

Yeah, I'm not too happy about push_back/push_front doing movements
except in few cases. I think such ideas belong in advanced use of the
resize policy.


>> I do want to focus on simple properties from a user's perspective.
>> Some cases to consider:
>>
>> # case 1: push_back from empty state
>> # case 2: push_back from unknown state
>> # case 3: insert from empty state
>> # case 4: insert from unknown state
>>
>> How do these properties work for a devector? If I understand your
>> strategy, we get the following:
>
> I think all of them work.
>
>> # case 1: push_back from empty state
>> ------------------------------------
>>
>>    devector<int> v;
>>    v.reserve( N );
>>
>> This does not guarantee N pushes without exceptions or without
>> reallocation. To get that guarantee we have to write
>
> If I'm not mistaken, you get the same guarantee. The difference is that
> elements are "relocated" (moved), but there is no "reallocation" (new
> buffer allocation). They are first moved when N/2 elements are
> push_backed and left/right_free_capacity() is zero, then after
> push_backing additional N/2 elements, etc (the number of relocations
> (moves) steps depend on the "relocation factor").

Well, we don't get an O(1) push_back in that case, right? And if we do,
we have to reallocate.

How about about this: we use Joaquin's idea that if the requested new
buffer is smaller/equal to capacity, push_back shifts the whole sequence
to the leftmost position (and wise versa for push_front).

Then we just make sure that the allocated buffer size is always even, so
if the user asks for 5, we allocate 6. Then when the the right hand side
is full, we ask for size()*GF (GF should be two) and this is exactly the
the capacity.

This could work when we start with an empty container, but still leaves

   devector<int> v;
   ...
   v.reserve( v.size() + N );

as a potential problem, doesn't it (unless we allocate twice as much as
requested)?

I think there is no prefect solution, only it is clear that optimal
vector usage and optimal flat container usage requires slightly
different behavior of reserve() & clear(). Do we then

A. make reserve() & clear() behave like in vector while providing
versions that balance around the middle, e.g.

    reserve( int front, int back );
    clear( int front_capacity );

B. make reserve() & clear() behave unlike vector, with balance around
the middle. vector code can be made optimal by using

    reserve_back( int capacity );
    clear_back();

C. Don't define reserve() and clear() for devector.

kind regards

Thorsten



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
El 16/10/2017 a las 1:45, Ion Gaztañaga via Boost escribió:

> On 15/10/2017 17:59, Joaquin M López Muñoz via Boost wrote:
>> The assumption is of an ever growing sequence. That said, I
>> recorgnize there are
>> scenarios not falling under this, most notably FIFO queues. I've
>> given the policy
>> a little more thought and think we can twist it to also accommodate
>> non-growing
>> scenarios, please keep on reading.
>>
>> Thougths?
>
> I think that the default (we could have other policies) should be
> simple and similar to
> vector/string/stable_vector/etc.... In this sense, capacity() and
> reserve(), if provided,
> should make sense. If we reallocate depending on the free capacity of
> one side, then
> capacity() and reserve() make no sense to the user
>
> I think the user expects capacity() as the maximum number of
> insertions, in any position,
> that will be accepted before reallocating. Making free_capacity =
> capacity() - size(), less
> than, say, back_free_capacity() will be really hard to understand by
> users.

I think providig capacity() will lead to confusion no matter the
growing/insertion policy. For instance,
users of vector/string/... expect capacity()-size() to be the number of
push_back()'s accepted without
iterator invalidation. Your policy below does break this expectation
--as any policy other than the
pathological case where front is given no free space ever.

> I propose a simple strategy:
>
> [...]

For any policy, there's a tradeoff between number of movements and
wasted space --i.e.
space not used before reallocation. Yours prioritizes the latter, mine
the former.

> Statistics based policies seem more complex, and I don't know how well
> they will adapt to
> pattern changes thorough the lifetime of the container, plus they
> impose a size cost to the
> container. I wouldn't make the the default choice, as the average user
> should easily understand
> the default policy.

Any policy can in principle be implemented behind the following interface:

   struct free_space{std::size_t back,front;};
   free_space query_for_insertion(std::size_t pos,std::size_t n);

used like this (pseudocode):

   auto new_free_space=query_for_insertion(pos,n);
   if(new_free_space.back+new_free_space.front>free_capacity()){
     // allocate or request in-place extension
     // move and insert appropriately so that
back_free_capacity()==new_free_space.back
     // and front_free_capacity()==new_free_space.front
   }
   else{
     // free space rebalance
assert(new_free_space.back+new_free_space.front==free_capacity());
     // move and insert appropriately so that
back_free_capacity()==new_free_space.back
     // and front_free_capacity()==new_free_space.front
   }

Why don't we equip devector with such a customization point and test the
different alternatives for real?

> For a FIFO, I think a deque that reuses free segment capacity on one
> side and transfers
> it to the other side before allocating new memory would be the best
> choice. Currently
> boost::container::deque does not do this, but pull requests are
> welcome ;-)

Or a circular buffer, but devector is the only structure that would
additionally
guarantee memory contiguity.

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 17 October 2017 at 15:08, Joaquin M López Muñoz via Boost <
[hidden email]> wrote:

> Any policy can in principle be implemented behind the following interface:
>
>   struct free_space{std::size_t back,front;};
>   free_space query_for_insertion(std::size_t pos,std::size_t n);
>
> used like this (pseudocode):
>
>   auto new_free_space=query_for_insertion(pos,n);
>   if(new_free_space.back+new_free_space.front>free_capacity()){
>     // allocate or request in-place extension
>     // move and insert appropriately so that back_free_capacity()==new_free
> _space.back
>     // and front_free_capacity()==new_free_space.front
>   }
>   else{
>     // free space rebalance
> assert(new_free_space.back+new_free_space.front==free_capacity());
>     // move and insert appropriately so that back_free_capacity()==new_free
> _space.back
>     // and front_free_capacity()==new_free_space.front
>   }
>
> Why don't we equip devector with such a customization point and test the
> different alternatives for real?


I've been saying that for a while now...

I wrote (from yesterday):

All of the above builds on the assumption of free_front equals free_back on
relocation. I think, since we are starting to talk about a *very*
performant vector-type implementation, that it would be appropriate to
provide a free_allocation_ratio_policy<F, B> of sorts, i.e. generalise the
1:1 and make it std::ratio<F, B>, with a default of std::ratio<1, 1> (so
not everybody needs to read the small print).

On small devectors this has rounding issues. std::ratio<1000, 999> could
denote that, this would mean roughly a policy of 1:1, but to 'round towards
the front'.

degski
--
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 17-10-2017 kl. 14:23 skrev Joaquin M López Muñoz via Boost:
> El 16/10/2017 a las 10:45, Thorsten Ottosen via Boost escribió:

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

Correct. If you want that for insert, you would need to allocate twice
the needed space.

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

My reservation is not really with capacity(), but with the cost of
allocation for small flat containers. Last I checked, you could copy
hundreds of objects for the price of one allocation (and the
deallocation that is implied).

kind regards

Thorsten



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 17-10-2017 kl. 14:08 skrev Joaquin M López Muñoz via Boost:

> Any policy can in principle be implemented behind the following interface:
>
>    struct free_space{std::size_t back,front;};
>    free_space query_for_insertion(std::size_t pos,std::size_t n);

n is the current size of the container or the capacity?

> used like this (pseudocode):
>
>    auto new_free_space=query_for_insertion(pos,n);
>    if(new_free_space.back+new_free_space.front>free_capacity()){
>      // allocate or request in-place extension
>      // move and insert appropriately so that
> back_free_capacity()==new_free_space.back
>      // and front_free_capacity()==new_free_space.front
>    }
>    else{
>      // free space rebalance
> assert(new_free_space.back+new_free_space.front==free_capacity());
>      // move and insert appropriately so that
> back_free_capacity()==new_free_space.back
>      // and front_free_capacity()==new_free_space.front
>    }
>
> Why don't we equip devector with such a customization point and test the
> different alternatives for real?

I can try that, but won't be until next week. In the mean time, people
can post their favorite policy and answer what it does in the following
situations (so it is easier to follow):

A. what is the front_free_capacity/back_free_capacity after reserve() on
an empty devector?

B. what is the front_free_capacity/back_free_capacity after clear()

C. what is the front_free_capacity/back_free_capacity after push_back on
an empty devector?

D. what is the front_free_capacity/back_free_capacity after push_front
on an empty devector?

E. what is the front_free_capacity/back_free_capacity after insert on an
empty devector?

F. what is the front_free_capacity/back_free_capacity after reserve on a
non-empty empty devector?


>> For a FIFO, I think a deque that reuses free segment capacity on one
>> side and transfers
>> it to the other side before allocating new memory would be the best
>> choice. Currently
>> boost::container::deque does not do this, but pull requests are
>> welcome ;-)
>
> Or a circular buffer, but devector is the only structure that would
> additionally
> guarantee memory contiguity.

Right. So it may be worth considering. Note as we have discussed
previously, that if we shift all the way to the front, a subsequent
push_front shifts all the way to the back, and a subsequent push_back
shifts all the way to the front. This can in principle go on until the
size is again larger than the threshold used for shifting.

kind regards

Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
El 18/10/2017 a las 10:36, Thorsten Ottosen via Boost escribió:
> Den 17-10-2017 kl. 14:08 skrev Joaquin M López Muñoz via Boost:
>
>> Any policy can in principle be implemented behind the following
>> interface:
>>
>>    struct free_space{std::size_t back,front;};
>>    free_space query_for_insertion(std::size_t pos,std::size_t n);
>
> n is the current size of the container or the capacity?

n is meant to indicate the number of elements being inserted at once.

> [...]
>
>>> For a FIFO, I think a deque that reuses free segment capacity on one
>>> side and transfers
>>> it to the other side before allocating new memory would be the best
>>> choice. Currently
>>> boost::container::deque does not do this, but pull requests are
>>> welcome ;-)
>>
>> Or a circular buffer, but devector is the only structure that would
>> additionally
>> guarantee memory contiguity.
>
> Right. So it may be worth considering. Note as we have discussed
> previously, that if we shift all the way to the front, a subsequent
> push_front shifts all the way to the back, and a subsequent push_back
> shifts all the way to the front. This can in principle go on until the
> size is again larger than the threshold used for shifting.

Right, ths is why I suggest rebalance includes some safeguards (minimum
free space
on each side) to avoid thrashing.

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
El 17/10/2017 a las 15:25, Thorsten Ottosen via Boost escribió:

> Den 17-10-2017 kl. 14:23 skrev Joaquin M López Muñoz via Boost:
>
>> 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.
>
> My reservation is not really with capacity(), but with the cost of
> allocation for small flat containers. Last I checked, you could copy
> hundreds of objects for the price of one allocation (and the
> deallocation that is implied).

If your concern is allocation cost and you do not worry that much about
wasted
space, you can increase the growing factor G to lower that (amortized)
cost down
at the expense of increasing the average free space not used on on one
of both
sides when the other side gets exhausted.

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [devector] optimum growing/insertion policy

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
El 16/10/2017 a las 19:38, Thorsten Ottosen via Boost escribió:

> Den 15-10-2017 kl. 14:09 skrev Joaquin M López Muñoz via Boost:
>> Hi,
>
>> * Maintain a counter right_ of right insertions that gets incremented
>> when a
>> right insertion occurs and *decremented* when an erasure is issued
>> past the
>> middle of the devector.
>
> So to implement this with a custom Resizing policy, the policy would
> need be stored via compressed_pair as a member and additionally
> provide a hook:
>
>   right_event( int elements )
>
> where elements can be both positive and negative and which is called
> from push_back and insert as needed. By default this could be an empty
> function.

In another post I'm proposing an alternative policy interface which can in
principle accommodate any policy --AFAICS.

>
>> * Right insertions trigger right shifting except when there's no back
>> free capacity,
>> in which case a reallocation is performed.
>> * Left insertions trigger left shifting except when there's no front
>> free capacity,
>> in which case a reallocation is performed.
>> * Reallocation reserves space for G*size() elements: of the resulting
>> G*size()-size()
>> free space, a fraction right_/size() is devoted to back free capacity,
>
> 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?

Sorry, now it's me who's lost :-) std::vector::reserve can both throw
and reallocate, right?

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
12