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

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-10-18 08:36:45

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