vector::push_back performance

[Victor Bazarov]

Re: vector::push_ba ck performance

Method Man wrote:[color=blue]
> [...]
> Your analogies didn't really help in my understanding of realloc.[/color]

They were intended to show the pitfalls of using 'realloc' with generic
types. Since now we're talking specifically POD, they are moot.
[color=blue]
> 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.[/color]

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

Re: vector::push_ba ck performance


"Victor Bazarov" <v.Abazarov@com Acast.net> wrote in message
news:guy6d.3759 $Ae.406@newsrea d1.dllstx09.us. to.verio.net...[color=blue]
> Method Man wrote:[color=green]
> > [...]
> > Your analogies didn't really help in my understanding of realloc.[/color]
>
> They were intended to show the pitfalls of using 'realloc' with generic
> types. Since now we're talking specifically POD, they are moot.[/color]

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]

Re: vector::push_ba ck performance

Method Man wrote:
[color=blue]
> 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?[/color]


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]

Re: vector::push_ba ck performance

Method Man wrote:
[color=blue]
> 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.[/color]


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]

Re: vector::push_ba ck performance

> How do you time your execution time? Is there _one_ way to time this, or[color=blue]
> might your method differ from the OP method?[/color]

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.

[Uwe Schnitker]

Re: vector::push_ba ck performance

"Andrew Koenig" <ark@acm.org> wrote in message news:<dop6d.644 518$Gx4.176588@ bgtnsc04-news.ops.worldn et.att.net>...[color=blue]
> "Antonios Christofides" <anthony@itia.n tua.gr> wrote in message
> news:dc5.4159da 31.d0edf@voltai re...
>[color=green]
> > 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.[/color]
>
> 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.[/color]

Just for the records: Are you sure it _does_ call push_back at all?

Since your program doesn't produce any observable effect, the compiler
has licence to transfer it into something like

int main()
{
}

which should probably run quite fast, shouldn't it?

Have fun,

Uwe

[Peter van Merkerk]

Re: vector::push_ba ck performance

Uwe Schnitker wrote:
[color=blue]
> "Andrew Koenig" <ark@acm.org> wrote in message news:<dop6d.644 518$Gx4.176588@ bgtnsc04-news.ops.worldn et.att.net>...
>[color=green]
>>"Antonios Christofides" <anthony@itia.n tua.gr> wrote in message
>>news:dc5.4159 da31.d0edf@volt aire...
>>
>>[color=darkred]
>>>As I read in the archives, the performance problem caused by memory
>>>reallocation s 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.[/color]
>>
>>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.[/color]
>
>
> Just for the records: Are you sure it _does_ call push_back at all?
>
> Since your program doesn't produce any observable effect, the compiler
> has licence to transfer it into something like
>
> int main()
> {
> }
>
> which should probably run quite fast, shouldn't it?[/color]

Good point, one should always be carefull with drawing conclusions from
test like this.

I compiled Andrew program on MSVC 6.0 with full optimization and checked
the assembly output. On this compiler the loop isn't optimized away.
push_back() is inlined, but the function that inserts elements into the
vector is still called one million times. Nevertheless this program
completed in 0.10 seconds on a Pentium III @ 700Mhz.

But I can imagine when the objects in the vector are expensive to copy
the story changes quite a bit.

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

[Andrew Koenig]

Re: vector::push_ba ck performance


"Uwe Schnitker" <schnitkerAffen schaukel@sigma-c.com> wrote in message
news:30381f67.0 409292310.3a66b fd5@posting.goo gle.com...[color=blue]
> Just for the records: Are you sure it _does_ call push_back at all?
>
> Since your program doesn't produce any observable effect, the compiler
> has licence to transfer it into something like
>
> int main()
> {
> }
>
> which should probably run quite fast, shouldn't it?[/color]

If I insert the statement

std::cout << v.size() << std::endl;

in the appropriate place, it prints 1000000 and still runs in 0.03 seconds.

[algorithm]

Re: vector::push_ba ck performance

Uwe - do you know who yoe are questioning?
I guess not...
Have fun yourself

[Antonios Christofides]

Re: vector::push_ba ck performance

Hi again,

after several experiments, I see that, indeed, when vector::push_ba ck
needs to reallocate memory, it does construct a copy of the object and
destruct the old object. When I recompiled my program without
optimization, I saw that the reallocation routines don't actually take
much time, but the constructor of the contained class does; with
optimization, it is apparently inlined and the profiler indicates that
the time is spent in the reallocation routines. If I call
vector::reserve prior to performing the 306 thousand push_backs, the
constructor is called 306 thousand times; if I don't, it is called 830
thousand times (likewise for the destructor).

Why don't just memmove the objects? I understand that in the general
case this is not possible; for example, if the constructor registers
the object's address in some global vector object. But this would not
be a problem for my class, which does not do such things. Furthermore,
my examination with the debugger indicates that when I copy an
instance of it, the copy is identical, byte by byte; even a string
member points to the same memory location as the original. So is it
just that the compiler/stl can't know, and we can't hint it, that a
memmove would suffice?



Here's the class, for your reference:

struct Record {
Record(const Date& t, bool n, double v, string f):
timestamp(t), null(n), value(v), flags(f) { }
Date timestamp;
bool null;
double value;
string flags;
};

("Date" is a user class internally represented as a struct tm.)

[Uwe Schnitker]

Re: vector::push_ba ck performance

"algorithm" <boostrookie@ya hoo.com> wrote in message news:<0d82e5bc8 dba511ce1d0faa6 826d03a4@localh ost.talkaboutpr ogramming.com>. ..[color=blue]
> Uwe - do you know who yoe are questioning?
> I guess not...
> Have fun yourself[/color]

I'm not sure when I first read something either about or by AK, but it
must have been in the previous century ...

Questioning (well-earned) authority is not a matter of refusal to
learn from it. Quite the contrary.

[Victor Bazarov]

Re: vector::push_ba ck performance

Antonios Christofides wrote:[color=blue]
> [...]
> Why don't just memmove the objects? I understand that in the general
> case this is not possible; for example, if the constructor registers
> the object's address in some global vector object. But this would not
> be a problem for my class, which does not do such things. Furthermore,
> my examination with the debugger indicates that when I copy an
> instance of it, the copy is identical, byte by byte; even a string
> member points to the same memory location as the original. So is it
> just that the compiler/stl can't know, and we can't hint it, that a
> memmove would suffice?
> [...][/color]

Try implementing the copy c-tor for your class in terms of 'memmove'.
If you succeed, remember that it's not portable. If you don't succeed,
read up on "move semantics" for return values and temporaries (IIRC),
the discussion was in comp.lang.c++.m oderated somewhere in the past
couple of years.

Victor

[Tom Widmer]

Re: vector::push_ba ck performance

On Wed, 29 Sep 2004 07:37:21 +0000 (UTC), Antonios Christofides
<anthony@itia.n tua.gr> wrote:
[color=blue][color=green][color=darkred]
>> > 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?[/color][/color]
>
>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.[/color]

std::vector will also typically use memmove or memcpy for built in
types like int. The easiest way to see this is to trace into the
push_back calls in a debugger - working out the code path can be
difficult otherwise.

For object types with copy constructors, the language currently
contains no better way of moving them that copying them and then
destroying the original. However, move constructors are a future
solution to this problem.

Tom

[Tom Widmer]

Re: vector::push_ba ck performance

On Sun, 03 Oct 2004 18:52:16 -0000, Antonios Christofides
<anthony@itia.n tua.gr> wrote:
[color=blue]
>Hi again,
>
>after several experiments, I see that, indeed, when vector::push_ba ck
>needs to reallocate memory, it does construct a copy of the object and
>destruct the old object. When I recompiled my program without
>optimization , I saw that the reallocation routines don't actually take
>much time, but the constructor of the contained class does; with
>optimization , it is apparently inlined and the profiler indicates that
>the time is spent in the reallocation routines. If I call
>vector::reserv e prior to performing the 306 thousand push_backs, the
>constructor is called 306 thousand times; if I don't, it is called 830
>thousand times (likewise for the destructor).[/color]

Right. Unfortunately the std::allocator interface doesn't include any
kind of try_realloc method, so it always has to allocate a new block
and copy, even when there is free space after the current storage.
[color=blue]
>Why don't just memmove the objects? I understand that in the general
>case this is not possible; for example, if the constructor registers
>the object's address in some global vector object. But this would not
>be a problem for my class, which does not do such things. Furthermore,
>my examination with the debugger indicates that when I copy an
>instance of it, the copy is identical, byte by byte; even a string
>member points to the same memory location as the original. So is it
>just that the compiler/stl can't know, and we can't hint it, that a
>memmove would suffice?[/color]

Yes, exactly. Strictly speaking, you can't use memmove portably on any
non-POD type, but in practice it works well with many types.
[color=blue]
>Here's the class, for your reference:
>
> struct Record {
> Record(const Date& t, bool n, double v, string f):
> timestamp(t), null(n), value(v), flags(f) { }
> Date timestamp;
> bool null;
> double value;
> string flags;
> };
>
> ("Date" is a user class internally represented as a struct tm.)[/color]

Well, I can think of reasonable implementations of std::string that
wouldn't be memmoveable (e.g. using a COW based lock-free pointer XOR
reference linked list implementation) , so the copy-destroy cycle is
the best you can do until this comes to be:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html#Move%20Semantics

Tom

[David Harmon]

Re: vector::push_ba ck performance

On Thu, 30 Sep 2004 14:03:10 GMT in comp.lang.c++, "Andrew Koenig"
<ark@acm.org> wrote,[color=blue]
>
>If I insert the statement
>
> std::cout << v.size() << std::endl;
>
>in the appropriate place, it prints 1000000 and still runs in 0.03 seconds.[/color]

But perhaps the compiler is determining statically what the size of the
vector would be at that point and encoding only that string in the
executable. I think you have to read the initial 1000000 from a file
that is unknown at compile time.