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

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2017-10-16 20:57:47

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