This is the mail archive of the mailing list for the libstdc++ project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

RFC: exponential growth of string and vector


"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
      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 but we should at
least think about whether it's still the right choice.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]