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

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: degski (degski_at_[hidden])
Date: 2017-10-16 12:07:19

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