vector::push_ba ck performance

[Antonios Christofides]

Hi,

As I read in the archives, the performance problem caused by memory
reallocations during vector::push_ba ck is a common one. My first C++
program is suffering from it: 300 thousand push_backs result,
according to the profiler, in 20 reallocations; these 20 reallocations
account for 3.6 seconds (Celeron 1.3G), which is 40% of total
execution time.

What I don't understand: why is the reallocation code so complex? I
studied the library source and I have a hard time understanding it,
but it seems to be copying the vector item by item in each
reallocation. Why wouldn't a "realloc" suffice?

And, given that I don't know the vector size beforehand, is there
anything else I can do other than trying deqeue or a guessed
vector::reserve ?

In case it matters, I'm using gcc 3.3 with its standard c++ library on
a Debian sarge, but portability is also an issue.

Thanks!

[Antonios Christofides]

> > All the texts I have read state that, when a dynamic array needs

to be extended, it is better/faster to 'realloc' instead of
creating a new array and copying the elements manually.

So why is 'realloc' more efficient?

Except for what was already said, I believe that even in the cases
when realloc needs to allocate a new memory block rather than extend
the existing one, it uses memmove or some similar operation which will
be faster than manually copying the elements if its implementation
uses specialized mass-byte-copying CPU instructions.

[Magnus]

"Andrew Koenig" <ar*@acm.org> skrev i melding
news:do******** *************@b gtnsc04-news.ops.worldn et.att.net...

I'm skeptical.

Here's a little program:

#include <vector>

int main()
{
std::vector<int > v;
for (std::vector<in t>::size_type i = 0; i != 1000000; ++i)
v.push_back(i);
return 0;
}

When I run this program on my machine (admittedly faster than 1.3G, but no
more than twice as fast), it runs in three *hundredths* of a second. And it calls push_back a million times, not 300,000 times.

This behavior suggests to me that your vector must contain objects of a
class that is much more expensive to copy than int.

So I think we need to see more information about your program in order to
understand the source of the performance problem.

How do you time your execution time? Is there _one_ way to time this, or
might your method differ from the OP method?

- Magnus

[Antonios Christofides]

Siemel Naran wrote:

For user types, especially those managing dynamic memory like
std::string or std::deque, we have to call the overloaded copy
constructor or operator= to the copy.

Thank you for your responses. The contained type is indeed a class
that contains, among other things, a string and another user-class
object. I'll go back to Stroustrup to re-read about shallow and deep
copies and copy constructors and so on, and I'll come back either to
summarize or to ask more questions (the latter seems more likely :-)

[Rolf Magnus]

Victor Bazarov wrote:

Antonios Christofides wrote:

As I read in the archives, the performance problem caused by memory
reallocations during vector::push_ba ck is a common one. My first C++
program is suffering from it: 300 thousand push_backs result,
according to the profiler, in 20 reallocations; these 20 reallocations
account for 3.6 seconds (Celeron 1.3G), which is 40% of total
execution time.

Three hundred thousand push_backs into a vector without reserve? Seems
unjustified.

From all we know, the number of elements could be between 1 and 30 Million.
After all, the OP said he doesn't know the number of elements beforehand.
So how much would you reserve?

[Rolf Magnus]

Method Man wrote:

That's what a "realloc" does, too. You usually can't easily make an
already allocated memory block bigger (what would you do with data after
it?), so a new block must be allocated and the data be copied over to it,
then the old one destroyed.

All the texts I have read state that, when a dynamic array needs to be
extended, it is better/faster to 'realloc' instead of creating a new array
and copying the elements manually.

So why is 'realloc' more efficient?

It might just behave like push_back() and allocate more memory than
requested so that the next realloc doesn't need to copy the data to a new
block.

[Victor Bazarov]

Method Man wrote:

[...]
Your analogies didn't really help in my understanding of realloc.
They were intended to show the pitfalls of using 'realloc' with generic
types. Since now we're talking specifically POD, they are moot.
I was
looking for something like -- 'realloc' is never/sometimes/always more
efficient than malloc'ing a new array and manually copying from the old
array (of PODs). Then justify the choice.

'realloc' works in an implementation-defined way. There is always some
possibility that a memory block allocated for an array can be simply
extended without the need to copy. There is always some possibility
that mere calling malloc and then some kind of copying (even memcpy)
can be less efficient when it's done from within your code than if it
is done in the library written (and optimised) specifically for your
hardware. So, in general 'realloc' will _always_ be at least as fast
as you can emulate it with your own 'malloc' and 'memcpy'.

More on C standard library - in comp.lang.c.

Victor

[Jeff Flinn]

"Victor Bazarov" <v.********@com Acast.net> wrote in message
news:gu******** *******@newsrea d1.dllstx09.us. to.verio.net...

Method Man wrote:

[...]
Your analogies didn't really help in my understanding of realloc.

They were intended to show the pitfalls of using 'realloc' with generic
types. Since now we're talking specifically POD, they are moot.

Aah, but elsewhere in this thread to OP informs us that in fact he is
dealing with a user defined class. so your analogies were very apt.

Jeff F

[Ioannis Vranos]

Method Man wrote:

All the texts I have read state that, when a dynamic array needs to be
extended, it is better/faster to 'realloc' instead of creating a new array
and copying the elements manually.

So why is 'realloc' more efficient?

Regarding vector, nowhere is required that all elements are copied in a
new location after some vector::push_ba ck(), vector::resize( ) or some
other modifier. In all these case, an operation similar to realloc() is
assumed.
However, as with realloc(), objects may be moved.

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[Ioannis Vranos]

Method Man wrote:

Your analogies didn't really help in my understanding of realloc. I was
looking for something like -- 'realloc' is never/sometimes/always more
efficient than malloc'ing a new array and manually copying from the old
array (of PODs). Then justify the choice.

As Victor said in a follow-up message,

"So, in general 'realloc' will _always_ be at least as fast as you can
emulate it with your own 'malloc' and 'memcpy'."
However your messages are not comprehensible. I haven't understood
exactly what you want to learn since the beginning of this thread.

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[Andrew Koenig]

> How do you time your execution time? Is there _one_ way to time this, or

might your method differ from the OP method?

A factor of 100 difference? Hardly likely.

Try the program yourself and see.

On my machine it runs so fast that I don't even have time to get my finger
off the enter button before it finishes.