Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: degski (degski_at_[hidden])
Date: 2017-10-11 02:36:25

On 11 October 2017 at 00:23, Ion Gaztañaga via Boost <boost_at_[hidden]>
wrote:

> I think the following is coherent, maybe not optimal in moves if only
> push_back is used:
>
>   -----xxxxxxxxxxxxx---------
>
>   ^^^^^---------------------- front free capacity
>   ^^^^^^^^^^^^^^^^^^--------- front capacity
>   -----^^^^^^^^^^^^^--------- size
>   ------------------^^^^^^^^^ back free capacity
>   -----^^^^^^^^^^^^^^^^^^^^^^ back capacity
>   ^^^^^^^^^^^^^^^^^^^^^^^^^^^ capacity
>
> front/back_free_capacity indicates the number of push_front/backs until
> data movement (and maybe allocation) is needed.
>
> front/back_capacity is front/back_free_capacity + size. If size ==
> front/back_capacity, then data movement (and maybe allocation) will happen
>
> capacity == size means that any insertion will lead to reallocation.
>

 I've tested a toy implementation doing exactly this.

template<typename T, typename P = allocation_policy<1, 1>, typename A =
std::allocator<T>, typename G = vs_growth_policy<2>>
class veque : private A {

    // Stuff...

    inline size_type size ( ) const noexcept { return ( size_type ) ( m_end
- m_begin ); }
    inline size_type capacity ( ) const noexcept { return
m_free_capacity_begin + size ( ) + m_free_capacity_end; }

    size_type m_free_capacity_begin = 0, m_free_capacity_end = 0;
    pointer m_begin = nullptr, m_end = nullptr;
};

With a size_type std::uint32_t, the foot print is 24 bytes on 64 bit (like
de::devector).

The idea with the allocation policy is to re-balance the total free space
on relocation between front and back free space (1 to 1 in the default
case, but could obviously be anything). This leads to lower memory usage on
random growth (push_front/push_back) over a std::vector of veque(s)
(de::devector).

This approach is speedwise on par with de:devector for
push_front/push_back, and doesn't give surprises in the the free capacity
department.

degski
-- 
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798