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

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: degski (degski_at_[hidden])
Date: 2017-10-17 12:36:46

On 17 October 2017 at 15:08, Joaquin M López Muñoz via Boost <
boost_at_[hidden]> 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