efficiency of vector::push_back?

Discussion in 'C++' started by Mark P, May 13, 2005.

  1. Mark P

    Mark P Guest

    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
     
    Mark P, May 13, 2005
    #1
    1. Advertising

  2. Mark P

    Alvin Guest

    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).
     
    Alvin, May 13, 2005
    #2
    1. Advertising

  3. >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/
     
    Jonathan Mcdougall, May 13, 2005
    #3
  4. 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::eek:stream& operator<<(std::eek: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.
     
    E. Robert Tisdale, May 13, 2005
    #4
  5. Mark P

    Mark P Guest

    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::eek:stream& operator<<(std::eek: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?
     
    Mark P, May 13, 2005
    #5
  6. > 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
     
    Jean-Sebastien Samson, May 13, 2005
    #6
  7. In article <>,
    Jonathan Mcdougall <> 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
     
    Francis Glassborow, May 13, 2005
    #7
  8. In article <42846b44$0$590$>, Jean-Sebastien Samson
    <> 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
     
    Francis Glassborow, May 13, 2005
    #8
  9. On Fri, 13 May 2005 07:47:51 GMT, Mark P <> 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
     
    Robert W Hand, May 13, 2005
    #9
  10. In article <>, Robert W Hand
    <> 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
     
    Francis Glassborow, May 13, 2005
    #10
  11. 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?



    Well, push_back() creates a new object inside vector by using the copy constructor. The
    argument of push_back is const T &x, and thus in most compilers your argument is created
    and destroyed.

    However the above does not make any sense, so it would be better if you provided a real
    world example so as to provide some optimisation hints.


    In other words you can have the same effect to the above by writing:

    vector<C> vc(1);


    and avoid your temporary construction.



    --
    Ioannis Vranos

    http://www23.brinkster.com/noicys
     
    Ioannis Vranos, May 13, 2005
    #11
  12. Mark P

    Pete Becker Guest

    Mark P wrote:
    >
    > 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.
    >


    There's no reason to delete the temporary object. It will be destroyed,
    however.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
     
    Pete Becker, May 13, 2005
    #12
  13. In article <IsTge.1850$3%>,
    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


    In addition to some of the fine answers you've already received:

    In general the compiler does not know where (at what address) the vector
    is going to put the C() being push_back'd. During the push_back
    execution, the vector will decide where the object needs to be
    constructed (maybe space needs to be allocated, maybe not). At this
    point the temporary C() will have long since been constructed in order
    to initiate push_back execution in the first place.

    So no, the copy can not be optimized away today (or at least is not
    optimized away in practice today).

    All that being said, there is a proposal before the committee to address
    this problem: move semantics / rvalue reference:

    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm
    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html
    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1770.html
    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1771.html

    The basic idea is that the class C can have a move constructor which can
    execute far more efficiently than a copy constructor by transferring
    resources from the source to the target (instead of duplicating
    resources). And you can safely move from temporaries with copy syntax
    because nobody else has a reference to the temporary in order to detect
    a difference.

    So expanding on Robert's example:

    #include <iostream>
    #include <vector>

    class C {
    public:
    // constructors
    C() {
    std::cerr << "C::C()" << std::endl;
    }
    // copy semantics
    C(const C&) {
    std::cerr << "C::C(const C&)" << std::endl;
    }
    C& operator=(const C&) {
    std::cerr << "C::eek:perator=(const C&)" << std::endl;
    return *this;
    }
    // move semantics
    C(C&&) {
    std::cerr << "C::C(C&&)" << std::endl;
    }
    C& operator=(C&&) {
    std::cerr << "C::eek:perator=(C&&)" << std::endl;
    return *this;
    }
    // destructor
    ~C(void) {
    std::cerr << "C::~C(void)" << std::endl;
    }
    };

    int main() {
    std::vector<C> vc;
    vc.push_back(C());
    return 0;
    }

    This will now print out:

    C::C()
    C::C(C&&)
    C::~C(void)
    C::~C(void)

    I.e. The temporary is still created, but it is move constructed from
    instead of copy constructed from to create the C internal to the vector.

    In this simple example there is no efficiency gain. However if C held
    resources (such as dynamic memory, file references, mutex locks, socket
    connections, etc.) then those resources can be transfered out of the
    temporary and into the vector by coding C(C&&) appropriately. ~C() will
    then be called on the temporary which must then be able to properly deal
    with a resource-less object.

    vector will also use move semantics instead of copy semantics when
    moving around elements internally (e.g. during buffer reallocation).

    The status of this proposal within the committee is currently promising,
    and Metrowerks has a full implementation of it in a not yet released
    compiler/lib.

    -Howard
     
    Howard Hinnant, May 13, 2005
    #13
  14. Mark P

    Randy Guest

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


    Where can I find out more about this "smart pointer?"
     
    Randy, May 13, 2005
    #14
  15. In article <r65he.28$rI1.7@trnddc02>, Randy <abuse@127.0.0.1> wrote:

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

    >
    > Where can I find out more about this "smart pointer?"


    boost::shared_ptr is a good starting point.

    http://www.boost.org/libs/smart_ptr/smart_ptr.htm

    Your C++ compiler may come with it, but called std::tr1::shared_ptr.

    Other copyable smart pointers may work better for you, depending on your
    needs. There is no "One True smart pointer".

    -Howard
     
    Howard Hinnant, May 13, 2005
    #15
  16. On Fri, 13 May 2005 11:56:30 +0100, Francis Glassborow
    <> wrote:

    >In article <>, Robert W Hand
    ><> 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)


    Yes, 12.8 allows class copy constructors to be the exception. But as
    I understand it, the side-effects would occur only if the copy
    contructor was actually called. It appears that in this example, the
    side effects did occur indicating that the objects were created and
    destroyed. Otherwise, how could nothing (no object, remember) have
    effects?

    12.8 has this language.

    "...the implementation treats the source and target of the omitted
    copy operation as simply two different ways of referring to the same
    object, and the destruction of that object occurs at the later of the
    times when the two objects would have been destroyed without the
    optimization"

    I've always read this phrase to mean that the side-effects of the
    eliminated copy and destruction would not occur. What would be the
    point of the elision if eerie things happened? (I wrote eerie because
    these unborn objects are having effects much some ghost. Which leads
    us completely off-topic. Can ghosts be unborn, or must they always be
    dead?)

    You are right about the temporary copy issue. But you would not want
    to have substantially different behavior between implementations
    because one compiler wants a temporary and another does not.
    --

    Best wishes,

    Bob
     
    Robert W Hand, May 14, 2005
    #16
  17. In article <>, Robert W Hand
    <> writes
    >You are right about the temporary copy issue. But you would not want
    >to have substantially different behavior between implementations
    >because one compiler wants a temporary and another does not.


    But the burden is on the programmer not the implementation.
    >


    --
    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
     
    Francis Glassborow, May 14, 2005
    #17
  18. Mark P

    Alan Johnson Guest

    Francis Glassborow wrote:
    > In article <>,
    > Jonathan Mcdougall <> 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.
    >
    >


    Just a warning for someone who might read this and overlook the word
    'suitable', std::auto_ptr does NOT meet the requirements for storage in
    the STL containers. Others recommended in this thread may (I haven't
    checked).
     
    Alan Johnson, May 15, 2005
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ganesh Gella
    Replies:
    5
    Views:
    1,290
    John Harrison
    Jul 14, 2003
  2. Hitesh Bhatiya
    Replies:
    4
    Views:
    4,596
    John Harrison
    Aug 13, 2003
  3. Avi Bercovich
    Replies:
    5
    Views:
    23,743
    Evan Carew
    Jan 14, 2004
  4. Alex Vinokur
    Replies:
    9
    Views:
    546
    Alex Vinokur
    Apr 11, 2004
  5. Replies:
    8
    Views:
    2,001
    Csaba
    Feb 18, 2006
Loading...

Share This Page