Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > efficiency of vector::push_back?

Reply
Thread Tools

efficiency of vector::push_back?

 
 
Mark P
Guest
Posts: n/a
 
      05-13-2005
Say I have objects of class C which are fairly large. Then consider:

vector<C> vc;
vc.push_back(C());

Naively this would seem to construct a temporary object C(), copy it
into the space owned by the vector, and then delete the temporary object.

I realize this is implementation dependent, but will most modern
compilers optimize away the creation of the temporary object, or is
there a compelling reason why this is not possible?

Thanks,
Mark
 
Reply With Quote
 
 
 
 
Alvin
Guest
Posts: n/a
 
      05-13-2005
Mark P wrote:

> Say I have objects of class C which are fairly large. Then consider:
>
> vector<C> vc;
> vc.push_back(C());
>
> Naively this would seem to construct a temporary object C(), copy it
> into the space owned by the vector, and then delete the temporary object.
>
> I realize this is implementation dependent, but will most modern
> compilers optimize away the creation of the temporary object, or is
> there a compelling reason why this is not possible?
>
> Thanks,
> Mark


I believe what happens is the:

1. vc is created with 0 capacity.
2. When push_back is called a temporary C object is constructed.
3. vc is then grown to capacity of 1.
4. As the vector is grown, another C object is constructed. This one is
inside of vc
5. Then the temporary C object (created by the call to push_back in 2) is
then copied (via the operator= or copy constructor into the C object that
is inside the vector (created in 4).
 
Reply With Quote
 
 
 
 
Jonathan Mcdougall
Guest
Posts: n/a
 
      05-13-2005
>Say I have objects of class C which are fairly
>large. Then consider:


>vector<C> vc;
>vc.push_back(C());


>Naively this would seem to construct a temporary
>object C(), copy it into the space owned by the
>vector, and then delete the temporary object.


>I realize this is implementation dependent, but
>will most modern compilers optimize away the
>creation of the temporary object, or is there a
>compelling reason why this is not possible?


If constructing and copying objects of class C is
expensive, do not store them by value.
std::vector is usually implemented using a
dynamic array, so when it has to allocate memory,
it will copy its elements. Use pointers instead.

std::vector<C*> vc;
vc.push_back(new C);

--
Jonathan
[FAQ] - http://www.parashift.com/c++-faq-lite/

 
Reply With Quote
 
E. Robert Tisdale
Guest
Posts: n/a
 
      05-13-2005
Mark P wrote:

> Say I have objects of class C which are fairly large.
> Then consider:
>
> vector<C> vc;
> vc.push_back(C());
>
> Naively, this would seem to construct a temporary object C(),
> copy it into the space owned by the vector
> and then delete the temporary object.


Yes, but...

> I realize [that] this is implementation dependent
> but will most modern compilers optimize away
> the creation of the temporary object
> or is there a compelling reason why this is not possible?


> cat main.cc

#include <iostream>
#include <vector>

class C {
private:
// representation
int I;
public:
// operators
friend
std:stream& operator<<(std:stream& os, const C& c) {
return os << c.I;
}
// constructors
C(int i = 0): I(i) {
std::cerr << "C::C(int)" << std::endl;
}
C(const C& c): I(c.I) {
std::cerr << "C::C(const C&)" << std::endl;
}
~C(void) {
std::cerr << "C::~C(void)" << std::endl;
}
};

int main(int argc, char* argv[]) {
std::vector<C> vc;
vc.push_back(C());
return 0;
}

> g++ -Wall -ansi -pedantic -O3 -o main main.cc
> ./main

C::C(int)
C::C(const C&)
C::~C(void)
C::~C(void)

Since the constructors, destructors and the push_back function
are all defined to be inline functions
the compiler can optimize away everything
except the diagnostic messages to standard error.
 
Reply With Quote
 
Mark P
Guest
Posts: n/a
 
      05-13-2005
E. Robert Tisdale wrote:
> Mark P wrote:
>
>> Say I have objects of class C which are fairly large.
>> Then consider:
>>
>> vector<C> vc;
>> vc.push_back(C());
>>
>> Naively, this would seem to construct a temporary object C(),
>> copy it into the space owned by the vector
>> and then delete the temporary object.

>
>
> Yes, but...
>
>> I realize [that] this is implementation dependent
>> but will most modern compilers optimize away
>> the creation of the temporary object
>> or is there a compelling reason why this is not possible?

>
>
> > cat main.cc

> #include <iostream>
> #include <vector>
>
> class C {
> private:
> // representation
> int I;
> public:
> // operators
> friend
> std:stream& operator<<(std:stream& os, const C& c) {
> return os << c.I;
> }
> // constructors
> C(int i = 0): I(i) {
> std::cerr << "C::C(int)" << std::endl;
> }
> C(const C& c): I(c.I) {
> std::cerr << "C::C(const C&)" << std::endl;
> }
> ~C(void) {
> std::cerr << "C::~C(void)" << std::endl;
> }
> };
>
> int main(int argc, char* argv[]) {
> std::vector<C> vc;
> vc.push_back(C());
> return 0;
> }
>
> > g++ -Wall -ansi -pedantic -O3 -o main main.cc
> > ./main

> C::C(int)
> C::C(const C&)
> C::~C(void)
> C::~C(void)
>
> Since the constructors, destructors and the push_back function
> are all defined to be inline functions
> the compiler can optimize away everything
> except the diagnostic messages to standard error.


I don't understand your conclusions here. It appears that the
temporaary is constructed and then copied rather than being constructed
"in place" within the vector. How do you know that everything but the
std error messages is optimized away?
 
Reply With Quote
 
Jean-Sebastien Samson
Guest
Posts: n/a
 
      05-13-2005
> I realize this is implementation dependent, but will most modern compilers
> optimize away the creation of the temporary object, or is there a
> compelling reason why this is not possible?


Some compilers might have done that in the past. But it is now forbidden by
the standard (since there are situations where you rely on the exact number
of copy). The only copy they are allowed to optimize away is the return
value of a function. Ex: CObj obj = fun();
--
JS


 
Reply With Quote
 
Francis Glassborow
Guest
Posts: n/a
 
      05-13-2005
In article <(E-Mail Removed). com>,
Jonathan Mcdougall <(E-Mail Removed)> writes
>If constructing and copying objects of class C is
>expensive, do not store them by value.
>std::vector is usually implemented using a
>dynamic array, so when it has to allocate memory,
>it will copy its elements. Use pointers instead.
>
>std::vector<C*> vc;
>vc.push_back(new C);


However if you store raw pointers you will have a memory leak if an
exception gets thrown across the point at which you define vc. Use a
suitable smart pointer instead.


--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
 
Reply With Quote
 
Francis Glassborow
Guest
Posts: n/a
 
      05-13-2005
In article <42846b44$0$590$(E-Mail Removed)>, Jean-Sebastien Samson
<(E-Mail Removed)> writes
>> I realize this is implementation dependent, but will most modern compilers
>> optimize away the creation of the temporary object, or is there a
>> compelling reason why this is not possible?

>
>Some compilers might have done that in the past. But it is now forbidden by
>the standard (since there are situations where you rely on the exact number
>of copy). The only copy they are allowed to optimize away is the return
>value of a function. Ex: CObj obj = fun();


No. While there is rather more restriction on when a copy may be
optimised away it is nowhere near as strict as that.


--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
 
Reply With Quote
 
Robert W Hand
Guest
Posts: n/a
 
      05-13-2005
On Fri, 13 May 2005 07:47:51 GMT, Mark P <(E-Mail Removed)> wrote:

>E. Robert Tisdale wrote:
>> Mark P wrote:
>>
>>> Say I have objects of class C which are fairly large.
>>> Then consider:
>>>
>>> vector<C> vc;
>>> vc.push_back(C());

<snip>
>> Since the constructors, destructors and the push_back function
>> are all defined to be inline functions
>> the compiler can optimize away everything
>> except the diagnostic messages to standard error.

>
>I don't understand your conclusions here. It appears that the
>temporaary is constructed and then copied rather than being constructed
>"in place" within the vector. How do you know that everything but the
>std error messages is optimized away?


I always thought that the point of optimization was invisibility to
the user, other than perhaps execution time or program size. It would
be quite surprising to find that the result of a calculation varied
with turning on and off compiler optimization switches.

By requiring the program to print error messages logging the execution
path, the compiler cannot optimize away "everything".
--

Best wishes,

Bob
 
Reply With Quote
 
Francis Glassborow
Guest
Posts: n/a
 
      05-13-2005
In article <(E-Mail Removed)>, Robert W Hand
<(E-Mail Removed)> writes
>
>I always thought that the point of optimization was invisibility to
>the user, other than perhaps execution time or program size. It would
>be quite surprising to find that the result of a calculation varied
>with turning on and off compiler optimization switches.
>
>By requiring the program to print error messages logging the execution
>path, the compiler cannot optimize away "everything".



But C++ gives specific authorisation wrt copy ctors. Under that licence
side effects of a copy ctor are not required to happen (and may also
happen at semi-arbitrary points if the compiler determines that it
wishes to create a temporary copy)

--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
perl efficiency -- fastest grepping? Bryan Krone Perl 1 11-08-2004 11:15 PM
Efficiency of dynamically adding web user controls MC D ASP .Net 4 11-18-2003 07:27 PM
Custom Paging Efficiency Joseph D. DeJohn ASP .Net 1 08-06-2003 06:24 PM
CISCO 1721 efficiency problem DarejDok \(Dariusz Dħbrowski\) Cisco 0 07-16-2003 07:15 AM
dataset efficiency question Trevor Hartman ASP .Net 0 07-03-2003 08:20 PM



Advertisments