Boost logo

Boost :

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.



    [1]Howard E. Hinnant

             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)


    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


     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).


   1. mailto:howard.hinnant_at_[hidden]

Boost list run by bdawes at, gregod at, cpdaniel at, john at