RFC: exponential growth of string and vector

[Jonathan Wakely]

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