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: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2017-09-27 21:06:06

On 26/09/2017 22:03, Joaquin M López Muñoz via Boost wrote:

> 4. Same goes for the growing policy. Not even boost::container::vector 
> features a growing
> policy, which seems an indication that this is not a heavily demanded 
> customization point.

True. But is on my todo list I was recently trying to add customization 
options to Boost.Container containers (I need to offer something 
different to my fans that the standard containers can't offer ;-).

Usually the choice is usually between a factor of 2 and 1.5. The 
theoretical limit value for the growth factor to be able to reuse 
previously allocated memory is roughly 1.61. Howard Hinnant shared with 
my a nice paper about this more than ten years ago showing how to grow 
using a factor of 1.6 and the math behind this. I just reviewed that 
brief paper recently, and since it's not longer online, Howard kindly 
has given me permission to share it with the Boost community.

Best,

Ion


    [1]Howard E. Hinnant
    2006-02-14
     __________________________________________________________________

             Growth Factor deriviation for reallocating a buffer

template <typename T, class Allocator>

typename some_container<T, Allocator>::size_type

some_container<T, Allocator>::grow_by(size_type n)

{

    const size_type m = max_size();

    const size_type c = capacity();

    if (n > m - c)

        base::throw_length_error();

    const size_type m3 = m / 3;

    if (c < m3)

        return c + std::max(3*(c+1)/5, n);

    if (c < m3*2)

        return c + std::max((c+1)/2, n);

    return m;

}

   The rationale for the 1.6 growth factor stems from an argument that
   Andrew Koenig has made: If you do nothing but continually grow a buffer
   by 2, freeing the old buffer, the new buffer will never fit into the
   spaces already deallocated. It will always be too large. So Andy
   computed what the largest growth factor could be such that after a
   while, the deallocated buffers (assuming they were coalesced by the
   heap manager) satisfy the request for the new buffer. The factor (f)
   can be derived by considering the current buffer size: S[i], and how it
   relates to the previous buffer size:

     S[i] = f S[i-1]

   Which also can be expressed:

     S[i] = f S[i-1] = f^ i S[0]

   Now for some i we want the sum of all previous buffers to be greater
   than or equal to the next buffer size:

     ∑[j=0]^i-1 S[j] >= S[i+1]

   Substituting in f and S[0]:

     Σ[j=0]^i-1 f^ j S[0] >= f^ i+1 S[0]

   The initial buffer size S[0] is known to be positive and can be
   factored out of the equation.

     Σ[j=0]^i-1 f^ j >= f^ i+1

   The summation on the left hand side can be algebraically simplified:

     (f^ i - 1) / (f - 1) >= f^ i+1

   The growth factor f is known to be greater than 1, so we can multiply
   through by the denominator of the left hand side:

     f^ i - 1 >= f^ i+1 (f - 1)

   Expand and rearrange:

     0 >= f^ i+2 - f^ i+1 - f^ i + 1

   For sufficiently large i, the constant factor 1 can be neglected, and
   then a factor of f^ i can be factored out:

     0 >= f^ i (f^ 2 - f - 1)

   Since f^ i is known to be positive we can simplify to:

     0 >= f^ 2 - f - 1

   This equation can be solved for f, picking the root that is greater
   than 1, we obtain:

     1 < f <= (1 + √5) / 2

   or

     1 < f <= 1.618033989...

   Dinkumware has repeatedly advertised that they are using a growth
   factor of 1.5, based on this same argument (for vector and string).

References

   1. mailto:howard.hinnant_at_[hidden]