This is the mail archive of the
mailing list for the libstdc++ project.
RFC: exponential growth of string and vector
- From: Jonathan Wakely <jwakely dot gcc at gmail dot com>
- To: "libstdc++" <libstdc++ at gcc dot gnu dot org>
- Cc: ncm at cantrip dot org
- Date: Thu, 14 Mar 2013 10:52:19 +0000
- Subject: 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
http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html but we should at
least think about whether it's still the right choice.