
Boost : 
Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21  September 30
From: Ion GaztaÃ±aga (igaztanaga_at_[hidden])
Date: 20170927 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
20060214
__________________________________________________________________
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[i1]
Which also can be expressed:
S[i] = f S[i1] = 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]^i1 S[j] >= S[i+1]
Substituting in f and S[0]:
Î£[j=0]^i1 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]^i1 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]
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk