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

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: thorsten.ottosen (thorsten.ottosen_at_[hidden])
Date: 2017-10-15 13:50:41

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