[RFC] Vector (string?) growth factor of 1.5 (insted of 2)

[Bo Persson]

----- Original Message ----- 
From: "Dhruv Matani" <dhruvbird@gmx.net>
To: "Paolo Carlini" <pcarlini@suse.de>
Cc: "libstdc++" <libstdc++@gcc.gnu.org>
Sent: Monday, February 02, 2004 5:41 PM
Subject: Re: [RFC] Vector (string?) growth factor of 1.5 (insted of 2)


> On Mon, 2004-02-02 at 20:52, Paolo Carlini wrote:
> > Hi everyone,
> >
> > I'm studying a recent discussion thread on comp.lang.c++.moderated
> > (google for 'vector growth factor of 1.5' if you are interested)
> > according to which this value, instead of the more common 2, should
> > be preferred.
> >
> > Naively, one could believe that which value is better (provided the
> > exponential requirements are fulfilled) should be decided empirically,
> > or even, that each application has its "best" value.
> >
> > Interestingly, however, Andrew Koenig pointed out that there are
> > *theoretical* reasons (related basically to memory fragmentation) to
> > prefer 1.5 to 2.
> >
> > Any opinions?
> >
> > As far as performance is concerned, actually my first rough test seem
> > to show a really *minor* negative impact, so, if memory usage is so
> > much better..
>
> Have you tried for vector<pod> and vector<with_non_trivial_copy_ctor>?
> such as std::string? How much is the difference for bot approaches with
> 2 and 1.5 as the growth factor? Does the performance improve as the size
> of the vector increases or does it deprove? What about memory
> fragmentation using the specialized libstdc++-v3 allocators? Are there
> any redundant copies made with using the specialized allocators?
>

I think we should not only measure speed, but also consider the amount of
memory wasted by over allocation.

If you want maximum speed for a particular container, you should of course
allocate every single byte available for it at once, and be done with it.


Bo Persson