preserving capacity of a vector

[Ivan Vecerina]

"Lasse Skyum" <lskyum(AT)mail.dk> wrote in message
| For my renderer at each frame I'm filling a vector with CVisual* elements,
| sorting it, rendering the objects and then clearing the vector again.
|
| I suspect there will be an overhead if the vector is resizing it's
capacity
| all the time... is there a way to prevent this?

An std::vector instance will NOT release the memory it has allocated
when its size is reduced, or when it is emptied ( by calling its
clear() member ). So resizing a vector of pointers can only trigger
a memory reallocation if its new size is larger than what it has
ever been - the capacity is preserved by default.

For the elements that are added/removed by calling resize(), there
can still be, however, a small overhead for initializing/destroying
elements (but for pointers, the destructions will be optimized out
on a good library implementation).

Regards,
Ivan

 

[Peter van Merkerk]

For my renderer at each frame I'm filling a vector with CVisual*
elements,

sorting it, rendering the objects and then clearing the vector again.

I suspect there will be an overhead if the vector is resizing it's capacity
all the time... is there a way to prevent this?

Suspecting something is a poor foundation for optimization efforts. Make
sure your code is correct first, optimize (using profiling tools to
identify the bottlenecks) later. That being said, resizing or clearing
typically does not affect the vectors capacity. So there is no need for
you to prevent this as it does not happen. Also if you know how big the
vector is going to be in advance, it is a good idea to call
std::vector::reserve() with the anticipated size. Note that
std::vector::reserve() only increases the capacity of the vector, the
capacity of a vector is never decreased by a std::vector::reserve()
regardless of the number passed to this function.

 

[tom_usenet]

"Lasse Skyum" <lskyum(AT)mail.dk> wrote in message
| For my renderer at each frame I'm filling a vector with CVisual* elements,
| sorting it, rendering the objects and then clearing the vector again.
|
| I suspect there will be an overhead if the vector is resizing it's
capacity
| all the time... is there a way to prevent this?

An std::vector instance will NOT release the memory it has allocated
when its size is reduced, or when it is emptied ( by calling its
clear() member ).

.... unless you are using MSVC 7.1. Dinkumware made clear() release all
storage in response to customer demand. Apparently they're going to
put it back the way the standard seems to imply (sticky capacity) in
the next version.

Tom

 

[Peter van Merkerk]

Oki, sticky capacity seems to be what I need... but this leads me to another
question: Can't I reset the capacity somehow if I want to?

I use std::vector for object-buckets on a map (for a game) and it seems
silly to hold a huge capacity somewhere just because there once was a lot of
objects there.

IIRC the book "Effective STL" from Scott Meyers recommends swapping
vectors to reduce capacity.

 

[Lasse Skyum]

For my renderer at each frame I'm filling a vector with CVisual* elements,
sorting it, rendering the objects and then clearing the vector again.

I suspect there will be an overhead if the vector is resizing it's capacity
all the time... is there a way to prevent this?

 

[Philipp]

(...) optimize (using profiling tools to
identify the bottlenecks) later.

Can you or anybody else recommend some tools to do such optimisation? Are
there any free/open source applications to find bottlenecks in a program you
are aware of?

Thanks Phil

 

[Peter van Merkerk]

(...) optimize (using profiling tools to

Can you or anybody else recommend some tools to do such optimisation?

The tools don't do the optimization, they only tell you where in the
code is most time spend. Using this information you can determine which
for part of the code optimization will make a difference.

Are there any free/open source applications to find bottlenecks in a program
you are aware of?

It depends on your development environment which profilers you can use.
G++ comes with GProf, MSVC comes which its own profiler (though I
believe only in the Enterprise edition). AQTime can handle quite a few
development environments on the PC platform
http://www.automatedqa.com/products/aqtime.asp but is not free (but
quite affordable for professional use). If you are running on a Intel
platform and willing to spend some dollars V-Tune
(http://www.intel.com/software/products/vtune/) might be an
consideration

 

[Lasse Skyum]

... unless you are using MSVC 7.1. Dinkumware made clear() release all
storage in response to customer demand. Apparently they're going to
put it back the way the standard seems to imply (sticky capacity) in
the next version.

Oki, sticky capacity seems to be what I need... but this leads me to another
question: Can't I reset the capacity somehow if I want to?

I use std::vector for object-buckets on a map (for a game) and it seems
silly to hold a huge capacity somewhere just because there once was a lot of
objects there.

 

[Lasse Skyum]

IIRC the book "Effective STL" from Scott Meyers recommends swapping
vectors to reduce capacity.

Okay, seems a little "hack" style... is it guarenteed to work by the
standard? And does it work in practice?

 

[Ivan Vecerina]

"Lasse Skyum" <lskyum(AT)mail.dk> wrote in message
| > IIRC the book "Effective STL" from Scott Meyers recommends swapping
| > vectors to reduce capacity.

The specific idiom is:
vector<ItemType>().swap( vectorToBeCleared );

| Okay, seems a little "hack" style... is it guarenteed to work by the
| standard?
No formal/absolute guarantee.

| And does it work in practice?
Yes. Implementations where this wouldn't work are hard to imagine
given some constraints imposed in the standard (i.e. iterators are
not to be invalidated by a swap operation, IIRC).


Regards,
Ivan