RFC: exponential growth of string and vector

[Gabriel Dos Reis]

On Thu, Mar 14, 2013 at 5:52 AM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> From https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#memory-handling
>
> "With time, other compilers reduced the growth factor to 1.5, but gcc
> has staunchly used a growth factor of 2. In fact it can be
> mathematically proven that a growth factor of 2 is rigorously the
> worst possible because it never allows the vector to reuse any of its
> previously-allocated memory. That makes the vector cache- unfriendly
> and memory manager unfriendly."
>
> The rest of the section is worth reading and makes me wonder if we
> should revisit the growth factor we use. Switching to the non-COW
> vstring implementation would be a good time to do it for std::string.
>
> The code says:
>
>       // The below implements an exponential growth policy, necessary to
>       // meet amortized linear time requirements of the library: see
>       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
>       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
>         {
>           __capacity = 2 * __old_capacity;
>
>
> I don't know where in the standard it says doubling is required, as
> Nathan says at the link above and
> http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html but we should at
> least think about whether it's still the right choice.

Funny you should bring up this subject.
Sean Parent visited TAMU last week, and this topic was the subject
of an extensive discussion.  The conclusion of the discussion was
that, from their measurements, any factor less than 2 is empirically
worse  -- unless we are talking about space constrained devices,
but then we are still short on extensive empirical evidence.

-- Gaby