|
Boost : |
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk