preserving capacity of a vector

[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?

--
Lasse

[Ivan Vecerina]

Re: preserving capacity of a vector

"Lasse Skyum" <lskyum(AT)mail .dk> wrote in message
news:3f9d1427$0 $69952$edfadb0f @dread12.news.t ele.dk...
| 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
--

http://ivan.vecerina.com

Brainbench MVP for C++ <> http://www.brainbench.com

[Peter van Merkerk]

Re: preserving capacity of a vector

> For my renderer at each frame I'm filling a vector with CVisual*
elements,[color=blue]
> 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[/color]
capacity[color=blue]
> all the time... is there a way to prevent this?[/color]

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::re serve() with the anticipated size. Note that
std::vector::re serve() only increases the capacity of the vector, the
capacity of a vector is never decreased by a std::vector::re serve()
regardless of the number passed to this function.

--
Peter van Merkerk
peter.van.merke rk(at)dse.nl

[tom_usenet]

Re: preserving capacity of a vector

On Mon, 27 Oct 2003 14:01:24 +0100, "Ivan Vecerina"
<NONE_use_form@ website_to_cont act_me> wrote:
[color=blue]
>"Lasse Skyum" <lskyum(AT)mail .dk> wrote in message
>news:3f9d1427$ 0$69952$edfadb0 f@dread12.news. tele.dk...
>| 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 ).[/color]

.... 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

[Lasse Skyum]

Re: preserving capacity of a vector

[color=blue]
> ... 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.[/color]

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

[Peter van Merkerk]

Re: preserving capacity of a vector

[color=blue][color=green]
> > ... unless you are using MSVC 7.1. Dinkumware made clear() release[/color][/color]
all[color=blue][color=green]
> > 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.[/color]
>
> Oki, sticky capacity seems to be what I need... but this leads me to[/color]
another[color=blue]
> 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[/color]
seems[color=blue]
> silly to hold a huge capacity somewhere just because there once was a[/color]
lot of[color=blue]
> objects there.[/color]

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

--
Peter van Merkerk
peter.van.merke rk(at)dse.nl

[Philipp]

Re: preserving capacity of a vector

[color=blue]
> (...) optimize (using profiling tools to
> identify the bottlenecks) later.[/color]

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

[Lasse Skyum]

Re: preserving capacity of a vector

[color=blue]
> IIRC the book "Effective STL" from Scott Meyers recommends swapping
> vectors to reduce capacity.[/color]

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

--
Lasse

[Peter van Merkerk]

Re: preserving capacity of a vector

> > (...) optimize (using profiling tools to[color=blue][color=green]
> > identify the bottlenecks) later.[/color]
>
> Can you or anybody else recommend some tools to do such optimisation?[/color]

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.
[color=blue]
> Are there any free/open source applications to find bottlenecks in a[/color]
program[color=blue]
> you are aware of?[/color]

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

--
Peter van Merkerk
peter.van.merke rk(at)dse.nl

[Ivan Vecerina]

Re: preserving capacity of a vector

"Lasse Skyum" <lskyum(AT)mail .dk> wrote in message
news:3f9d2831$0 $69977$edfadb0f @dread12.news.t ele.dk...
| > IIRC the book "Effective STL" from Scott Meyers recommends swapping
| > vectors to reduce capacity.

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

| 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
--

http://ivan.vecerina.com