When using resize() and push_back(), an baseline instace of T is created and then the new members are assigned via the copy constructor. If T is complex this begins to add a non-negligible overhead, especially for push_back. Is there a reason /not/ to replace the [first] create & copy with in-place construction? Sample code: #include <iostream> struct Foo { Foo() { cout << "ctor " << this << endl ; } Foo(const Foo& rhs) { cout << "copyctor " << this << " from " << &rhs << endl ; } ~Foo() { cout << "dtor " << this << endl ; } } ; typedef vector<Foo> FOO ; int main(int argc, char* argv[]) { FOO bar; cout << "pushing" << endl ; bar.push_back(Foo()) ; cout << "end of program" << endl ; } Compilation: [osmith@fedex src]$ g++ -v -save-temps -O2 -g2 -Wall -o test -lstdc++ test.cpp Using built-in specs. Target: i386-redhat-linux Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-libgcj-multifile --enable-languages=c,c++,objc,obj-c++,java,fortran,ada --enable-java-awt=gtk --disable-dssi --enable-plugin --with-java-home=/usr/lib/jvm/java-1.4.2-gcj-1.4.2.0/jre --with-cpu=generic --host=i386-redhat-linux Thread model: posix gcc version 4.1.1 20070105 (Red Hat 4.1.1-51) /usr/libexec/gcc/i386-redhat-linux/4.1.1/cc1plus -E -quiet -v -D_GNU_SOURCE test.cpp -mtune=generic -Wall -fworking-directory -O2 -fpch-preprocess -o test.ii ignoring nonexistent directory "/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../i386-redhat-linux/include" #include "..." search starts here: #include <...> search starts here: /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1 /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/i386-redhat-linux /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/backward /usr/local/include /usr/lib/gcc/i386-redhat-linux/4.1.1/include /usr/include End of search list. /usr/libexec/gcc/i386-redhat-linux/4.1.1/cc1plus -fpreprocessed test.ii -quiet -dumpbase test.cpp -mtune=generic -auxbase test -g2 -O2 -Wall -version -o test.s GNU C++ version 4.1.1 20070105 (Red Hat 4.1.1-51) (i386-redhat-linux) compiled by GNU C version 4.1.1 20070105 (Red Hat 4.1.1-51). GGC heuristics: --param ggc-min-expand=98 --param ggc-min-heapsize=129076 Compiler executable checksum: 4720743fdfefd64206c8550433f6e508 as -V -Qy -o test.o test.s GNU assembler version 2.17.50.0.6-2.fc6 (i386-redhat-linux) using BFD version 2.17.50.0.6-2.fc6 20061020 /usr/libexec/gcc/i386-redhat-linux/4.1.1/collect2 --eh-frame-hdr -m elf_i386 --hash-style=gnu -dynamic-linker /lib/ld-linux.so.2 -o test /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../crt1.o /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../crti.o /usr/lib/gcc/i386-redhat-linux/4.1.1/crtbegin.o -L/usr/lib/gcc/i386-redhat-linux/4.1.1 -L/usr/lib/gcc/i386-redhat-linux/4.1.1 -L/usr/lib/gcc/i386-redhat-linux/4.1.1/../../.. -lstdc++ test.o -lstdc++ -lm -lgcc_s -lgcc -lc -lgcc_s -lgcc /usr/lib/gcc/i386-redhat-linux/4.1.1/crtend.o /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../crtn.o Output: pushing ctor 0xbfa3d327 copyctor 0x8c87008 from 0xbfa3d327 dtor 0xbfa3d327 end of program dtor 0x8c87008 If resize were being called, it the copyctor would be used to copy /0xbfa3d327/ into each new uninitialized instance: resizing ctor 0xbfa3d327 copyctor 0x8c87008 from 0xbfa3d327 copyctor 0x8c8700c from 0xbfa3d327 copyctor 0x8c87010 from 0xbfa3d327 dtor 0xbfa3d327 end of program dtor 0x8c87008 dtor 0x8c8700c dtor 0x8c87010 The optimization I am suggesting would produce the following [approximate] output: pushing ctor 0x8c87008 end of program dtor 0x8c87008 If resize() was being called instead of push_back, it might look like this: resizing ctor 0x8c87008 /first entry in the pool/ copyctor 0x8c8700c from 0x8c87008 /copy ctor of second entry from first/ copyctor 0x8c87010 from 0x8c87008 /copy ctor of third entry from first/ ... end of program dtor 0x8c87008 dtor 0x8c8700c dtor 0x8c87010
> The optimization I am suggesting would produce the following [approximate] is wrong. You have to bind a constant reference to a temp variable and then doing a copy as you do a[0] = b; So the optimization for resize is wrong and incorrect.
I suspect Oliver is raising a good point, in very general terms. Before going into the details, I want to make sure he knows this proposal, which is likely to make into C++0x, in some form: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2217.pdf
Andrew, currently it seems to work like this (pseudo code warning): T* newSpace = alloc(newSize); int i = 0 ; for ( ; i < size ; ++i ) { newSpace[i].constructor(oldSpace[i]) ; } const T defaultInstance ; for ( ; i < newSize ; i++ ) { newSpace[i].constructor(defaultInstance) ; } What I'm talking about is replacing "const T defaultInstance;" with // Execute the default constructor on the first new element newSpace[i].constructor() ; // Take a reference to this object for copying to subsequent instances const T& defaultInstance = newSpace[i] ; // Advance i to the next element ++i ;
Well for one push_back takes "const T&". This is what I was talking about, you can't really get any better in that case. Now the resize case is a different story.
Doh - yes - you're completely right about push_back. push_back itself isn't incurring the temporary variable, Foo() is. Lost track of that investigating the resize thing.
Just a short note to follow up to my first message: as expected, in the next standard both push_back and resize will be very different. The signature of the new push_back, already available under the experimental C++0x mode, becomes: template<typename... Args> void push_back(Args&&... args) As regards resize, will be split into: resize(size_type) resize(size_type, const T&) I'm considering implementing the new resize too under C++0x, in that case this PR will be closed.
Note that the split resize requires DefaultConstructible for the first overload, and therefore, missing Concepts, the vector class cannot be explicitely instantiated anymore for non-DefaultConstructible types.
*** Bug 42242 has been marked as a duplicate of this bug. ***
Note: the same problem with the DefaultConstructible requirement affects for example the new constructor vector(size_type). Thinking more about these issues I'm wondering whether in N3000 std::vector & co are still supposed to be explicitly instantiable for non-DefaultConstructible types - which would require a quite boring dispatching and base-class dances for the whole class for the sake of a few members, now that Concepts are gone - or not, or maybe just as QoI. Does anybody have an idea? Maybe not, maybe is not supposed to, otherwise, N2983 would not add the has_default_constructor trait as-if it was not necessary before...
On it.
Subject: Bug 32618 Author: paolo Date: Fri Jun 18 18:07:45 2010 New Revision: 161009 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=161009 Log: 2010-06-18 Paolo Carlini <paolo.carlini@oracle.com> PR libstdc++/32618 * include/bits/stl_list.h (vector<>::_M_default_initialize, _M_default_append): Declare. (list<>::list(size_type), resize(size_type)): Add in C++0x mode, use the latter. * include/bits/list.tcc (list<>::resize, _M_default_append): Define. * include/bits/stl_vector.h (vector<>::_M_default_initialize, _M_default_append): Declare. (vector<>::vector(size_type), resize(size_type)): Add in C++0x mode, use the latter. * include/bits/vector.tcc (vector<>::_M_default_append): Define. * include/bits/stl_deque.h (deque<>::_M_default_initialize, _M_default_append): Declare. (deque<>::deque(size_type), resize(size_type)): Add in C++0x mode, use the latter. * include/bits/deque.tcc (deque<>::_M_default_append): Define. * include/debug/vector: Update. * include/debug/deque: Likewise. * include/debug/list: Likewise. * include/profile/vector: Likewise. * include/profile/deque: Likewise. * include/profile/list: Likewise. * include/bits/forward_list.h (_M_default_initialize, _M_default_insert_after): Declare. (forward_list<>::forward_list(size_type), resize(size_type)): Fix, use the latter. * include/bits/forward_list.tcc (forward_list<>::_M_default_append, _M_default_insert_after): Define. * testsuite/util/testsuite_api.h (NonCopyConstructible): Add. * testsuite/23_containers/forward_list/modifiers/6.cc: Move to... * testsuite/23_containers/forward_list/capacity/resize_size.cc: ... here. * testsuite/23_containers/forward_list/cons/10.cc: Move to... * testsuite/23_containers/forward_list/cons/cons_size.cc: ... here. * testsuite/23_containers/vector/resize/1.cc: Move to... * testsuite/23_containers/vector/capacity/resize/1.cc: ... here. * testsuite/23_containers/vector/resize/moveable.cc: Move to... * testsuite/23_containers/vector/resize/capacity/moveable.cc: ... here. * testsuite/23_containers/vector/cons/cons_size.cc: New. * testsuite/23_containers/vector/capacity/resize/resize_size.cc: Likewise. * testsuite/23_containers/deque/cons/cons_size.cc: Likewise. * testsuite/23_containers/deque/capacity/resize_size.cc: Likewise. * testsuite/23_containers/list/cons/cons_size.cc: Likewise. * testsuite/23_containers/list/capacity/resize_size.cc: Likewise. * testsuite/23_containers/vector/capacity/resize/moveable.cc: Adjust. * testsuite/23_containers/deque/capacity/moveable.cc: Likewise. * testsuite/23_containers/forward_list/requirements/dr438/ assign_neg.cc: Adjust dg-error line numbers. * testsuite/23_containers/forward_list/requirements/dr438/ insert_neg.cc: Likewise. * testsuite/23_containers/forward_list/requirements/dr438/ constructor_1_neg.cc: Likewise. * testsuite/23_containers/forward_list/requirements/dr438/ constructor_2_neg.cc: Likewise. * testsuite/23_containers/vector/requirements/dr438/ assign_neg.cc: Likewise. * testsuite/23_containers/vector/requirements/dr438/insert_neg.cc: Likewise. * testsuite/23_containers/vector/requirements/dr438/ constructor_1_neg.cc: Likewise. * testsuite/23_containers/vector/requirements/dr438/ constructor_2_neg.cc: Likewise. * testsuite/23_containers/deque/requirements/dr438/ assign_neg.cc: Likewise. * testsuite/23_containers/deque/requirements/dr438/insert_neg.cc: Likewise. * testsuite/23_containers/deque/requirements/dr438/ constructor_1_neg.cc: Likewise. * testsuite/23_containers/deque/requirements/dr438/ constructor_2_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/ constructor_1_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/ constructor_2_neg.cc: Likewise. Added: trunk/libstdc++-v3/testsuite/23_containers/deque/capacity/resize_size.cc trunk/libstdc++-v3/testsuite/23_containers/deque/cons/cons_size.cc trunk/libstdc++-v3/testsuite/23_containers/forward_list/capacity/resize_size.cc - copied, changed from r160898, trunk/libstdc++-v3/testsuite/23_containers/forward_list/modifiers/6.cc trunk/libstdc++-v3/testsuite/23_containers/forward_list/cons/cons_size.cc - copied, changed from r160898, trunk/libstdc++-v3/testsuite/23_containers/forward_list/cons/10.cc trunk/libstdc++-v3/testsuite/23_containers/list/capacity/resize_size.cc trunk/libstdc++-v3/testsuite/23_containers/list/cons/cons_size.cc trunk/libstdc++-v3/testsuite/23_containers/vector/capacity/resize/ - copied from r160967, trunk/libstdc++-v3/testsuite/23_containers/vector/resize/ trunk/libstdc++-v3/testsuite/23_containers/vector/capacity/resize/resize_size.cc trunk/libstdc++-v3/testsuite/23_containers/vector/cons/cons_size.cc Removed: trunk/libstdc++-v3/testsuite/23_containers/forward_list/cons/10.cc trunk/libstdc++-v3/testsuite/23_containers/forward_list/modifiers/6.cc trunk/libstdc++-v3/testsuite/23_containers/vector/resize/ Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/deque.tcc trunk/libstdc++-v3/include/bits/forward_list.h trunk/libstdc++-v3/include/bits/forward_list.tcc trunk/libstdc++-v3/include/bits/list.tcc trunk/libstdc++-v3/include/bits/stl_deque.h trunk/libstdc++-v3/include/bits/stl_list.h trunk/libstdc++-v3/include/bits/stl_vector.h trunk/libstdc++-v3/include/bits/vector.tcc trunk/libstdc++-v3/include/debug/deque trunk/libstdc++-v3/include/debug/list trunk/libstdc++-v3/include/debug/vector trunk/libstdc++-v3/include/profile/deque trunk/libstdc++-v3/include/profile/list trunk/libstdc++-v3/include/profile/vector trunk/libstdc++-v3/testsuite/23_containers/deque/capacity/moveable.cc trunk/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/assign_neg.cc trunk/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/constructor_1_neg.cc trunk/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/constructor_2_neg.cc trunk/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/insert_neg.cc trunk/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/assign_neg.cc trunk/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/constructor_1_neg.cc trunk/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/constructor_2_neg.cc trunk/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/insert_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc trunk/libstdc++-v3/testsuite/23_containers/vector/capacity/resize/moveable.cc trunk/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/assign_neg.cc trunk/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/constructor_1_neg.cc trunk/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/constructor_2_neg.cc trunk/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/insert_neg.cc trunk/libstdc++-v3/testsuite/util/testsuite_api.h
Done.