Re: [Stlport-devel] Tweaking vector allocation

[Ulrich E. <eck...@sa...>]

On Wednesday 23 July 2008, Nigel Stewart wrote:
> I've found that STLPort std::vector results in ~3x more malloc/
> free calls than the in-house vector we intend to retire.

Just one note: the C++ standardlibrary is a general purpose library. If you 
have special requirements, those are a valid reason to use a special 
container instead of one of the standard ones.

> The reason appears to relate to the allocation policy in STLPort,
> _vector.c line 86:
>
> size_type __len = __old_size + (max)(__old_size, __fill_len);
>
> Which roughly translates to: "become at least double the size
> or increase by _fill_len".  For push_back fill_len is 1.
>
> So for STLPort, as push_back is called the capacity grows
> as follows:  0,1,2,4,8,16,...

Yes, this partially follows from the "amortised constant time" for insertions 
at the end.

> For our purposes we'd generally prefer a sequence such as:
> 0,8,16,32,...  Avoiding too many (small) reallocations for
> (typically) small vectors.

My first approach to that would be to simply call reserve(). As amount, I 
would try to use the finally used number of elements or if that isn't 
available a number that is a compromise between wasted memory and unnecessary 
reallocations. I would further consider using std::deque, which can actually 
be quicker under some circumstances.

> Does it make any sense to think of extending STLPort vector
> allocation to be a bit more configurable....
>
> #define _STLP_VECTOR_GROW_MINIMUM   1
> #define _STLP_VECTOR_GROW_FACTOR    2
> #define _STLP_VECTOR_GROW_INCREMENT 0
>
> So _vector.c line 86 becomes something like:
>
> size_type __len = __old_size*(_STLP_VECTOR_GROW_FACTOR) +
> (_STLP_VECTOR_GROW_INCREMENT); __len =
> (max)(__len,(_STLP_VECTOR_GROW_MINIMUM));

Actually, I believe that you could use a different allocator to achieve that. 
Maybe it's just STLport and not standard, but I have seen a way for the 
allocator to tell the caller that it allocated more than just the requested 
number of elements. If you would then put a lower bound on that number, you 
could skip all the reallocations for the sizes 1..4. However, I'm not really 
confident with that part of STLport and I haven't actually used this feature 
myself, I just recently read the code. Hopefully someone else can tell you 
how to use that, otherwise I would really suggest deque<> or reserve().

good luck!

Uli

-- 
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932

**************************************************************************************
           Visit our website at <http://www.satorlaser.de/>
**************************************************************************************
Diese E-Mail einschließlich sämtlicher Anhänge ist nur für den Adressaten bestimmt und kann vertrauliche Informationen enthalten. Bitte benachrichtigen Sie den Absender umgehend, falls Sie nicht der beabsichtigte Empfänger sein sollten. Die E-Mail ist in diesem Fall zu löschen und darf weder gelesen, weitergeleitet, veröffentlicht oder anderweitig benutzt werden.
E-Mails können durch Dritte gelesen werden und Viren sowie nichtautorisierte Änderungen enthalten. Sator Laser GmbH ist für diese Folgen nicht verantwortlich.

**************************************************************************************