This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
Here is a patch which makes vector rvalref-aware, so it never performs unnessasary copies of things internally when it is shifting around things. I haven't added any more of the user-visable changes (function which allow you to push_back an rvalref, etc), espically due to recent problems with the constructors. The major final thing I haven't added (and the reason I've been quiet for a while) is that I've been having great problems implementing move semantics on stable_sort and stable_partition without either moveable types or trivial types (like int) being sub-optimal, or the code bloating. I hope to crack this soon :) I also now consider that all the "basic framework" and most of the speed improvement of templated-based rvalue references are present. However it looks like it might be too late now for 4.1? This patch has been bootstrapped on powerpc-apple-darwin8.2.0 and x86 linux.
Binary files libstdc++-v3.so_7.clean/include/.DS_Store and libstdc++-v3/include/.DS_Store differ
diff -urNx '*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_construct.h libstdc++-v3/include/bits/stl_construct.h
--- libstdc++-v3.so_7.clean/include/bits/stl_construct.h 2005-07-05 08:46:01.000000000 +0100
+++ libstdc++-v3/include/bits/stl_construct.h 2005-08-08 21:03:13.000000000 +0100
@@ -98,6 +98,29 @@
/**
* @if maint
+ * Should move construct an object in existing memory by invoking the
+ * allocated object's move constructor, but move construction only occurs
+ * in the specialization below.
+ * @endif
+ */
+ template<typename _T1, typename _T2, typename _Allocator>
+ inline void
+ _Construct_move_a(_T1* __p, _T2& __value, _Allocator __alloc)
+ { __alloc.construct(__p, __value); }
+
+ /**
+ * @if maint
+ * Move constructs an object in existing memory by invoking an allocated
+ * object's move constructor.
+ * @endif
+ */
+ template<typename _T1, typename _T2, typename _Tp>
+ inline void
+ _Construct_move_a(_T1* __p, _T2& __value, allocator<_Tp>)
+ { ::new(static_cast<void*>(__p)) _T1(__gnu_cxx::__move(__value)); }
+
+ /**
+ * @if maint
* Destroy the object pointed to by a pointer type.
* @endif
*/
diff -urNx '*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_uninitialized.h libstdc++-v3/include/bits/stl_uninitialized.h
--- libstdc++-v3.so_7.clean/include/bits/stl_uninitialized.h 2005-07-05 08:46:02.000000000 +0100
+++ libstdc++-v3/include/bits/stl_uninitialized.h 2005-08-08 21:09:14.000000000 +0100
@@ -113,6 +113,59 @@
_Is_POD());
}
+ /**
+ * @brief Moves the range [first,last) into result.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ * @param result An output iterator.
+ * @return result + (first - last)
+ *
+ * Like copy(), but moves and does not require an initialized output range.
+ */
+ template<typename _InputIterator, typename _ForwardIterator>
+ inline typename __enable_if<_ForwardIterator,
+ __gnu_cxx::__is_moveable<
+ typename std::iterator_traits<_ForwardIterator>::value_type>::__value
+ && __are_same<typename std::iterator_traits<_InputIterator>::value_type,
+ typename std::iterator_traits<_ForwardIterator>::value_type>
+ ::__value>::__type
+ __uninitialized_move(_InputIterator __first, _InputIterator __last,
+ _ForwardIterator __result)
+ {
+ _ForwardIterator __cur = __result;
+ try
+ {
+ for (; __first != __last; ++__first, ++__cur)
+ std::_Construct(&*__cur, __gnu_cxx::__move(*__first));
+ return __cur;
+ }
+ catch(...)
+ {
+ std::_Destroy(__result, __cur);
+ __throw_exception_again;
+ }
+ }
+
+ /**
+ * @brief Moves the range [first,last) into result.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ * @param result An output iterator.
+ * @return result + (first - last)
+ *
+ * Like copy(), but moves and does not require an initialized output range.
+ */
+ template<typename _InputIterator, typename _ForwardIterator>
+ inline typename __enable_if<_ForwardIterator,
+ !(__gnu_cxx::__is_moveable<
+ typename std::iterator_traits<_ForwardIterator>::value_type>::__value
+ && __are_same<typename std::iterator_traits<_InputIterator>::value_type,
+ typename std::iterator_traits<_ForwardIterator>::value_type>
+ ::__value)>::__type
+ __uninitialized_move(_InputIterator __first, _InputIterator __last,
+ _ForwardIterator __result)
+ { return std::uninitialized_copy(__first, __last, __result); }
+
inline char*
uninitialized_copy(const char* __first, const char* __last, char* __result)
{
@@ -218,10 +271,10 @@
std::__uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
}
- // Extensions: versions of uninitialized_copy, uninitialized_fill,
- // and uninitialized_fill_n that take an allocator parameter.
- // We dispatch back to the standard versions when we're given the
- // default allocator. For nondefault allocators we do not use
+ // Extensions: versions of uninitialized_copy, uninitialized_fill,
+ // uninitialized_fill_n and uninitialized_move that take an allocator
+ // parameter. We dispatch back to the standard versions when we're given
+ // the default allocator. For nondefault allocators we do not use
// any of the POD optimizations.
template<typename _InputIterator, typename _ForwardIterator,
@@ -254,6 +307,38 @@
return std::uninitialized_copy(__first, __last, __result);
}
+ template<typename _InputIterator, typename _ForwardIterator, typename _Tp>
+ inline
+ typename __enable_if<_ForwardIterator,
+ __gnu_cxx::__is_moveable<
+ typename iterator_traits<_InputIterator>::value_type>::__value
+ && __are_same<typename iterator_traits<_InputIterator>::value_type,
+ typename iterator_traits<_ForwardIterator>::value_type>
+ ::__value>::__type
+ __uninitialized_move_a(_InputIterator __first, _InputIterator __last,
+ _ForwardIterator __result,
+ allocator<_Tp>)
+ { return std::__uninitialized_move(__first, __last, __result); }
+
+ template<typename _InputIterator, typename _ForwardIterator, typename _Tp>
+ inline typename __enable_if<_ForwardIterator,
+ !(__gnu_cxx::__is_moveable<
+ typename std::iterator_traits<_ForwardIterator>::value_type>::__value
+ && __are_same<typename std::iterator_traits<_InputIterator>::value_type,
+ typename std::iterator_traits<_ForwardIterator>::value_type>
+ ::__value)>::__type
+ __uninitialized_move_a(_InputIterator __first, _InputIterator __last,
+ _ForwardIterator __result, allocator<_Tp> __alloc)
+ { return std::__uninitialized_copy_a(__first, __last, __result, __alloc); }
+
+ template<typename _InputIterator, typename _ForwardIterator,
+ typename _Allocator>
+ _ForwardIterator
+ __uninitialized_move_a(_InputIterator __first, _InputIterator __last,
+ _ForwardIterator __result,
+ _Allocator __alloc)
+ { return std::__uninitialized_copy_a(__first, __last, __result, __alloc); }
+
template<typename _ForwardIterator, typename _Tp, typename _Allocator>
void
__uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last,
diff -urNx '*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_vector.h libstdc++-v3/include/bits/stl_vector.h
--- libstdc++-v3.so_7.clean/include/bits/stl_vector.h 2005-08-08 16:57:27.000000000 +0100
+++ libstdc++-v3/include/bits/stl_vector.h 2005-07-30 18:19:44.000000000 +0100
@@ -789,6 +789,30 @@
}
}
+ /**
+ * @if maint
+ * Memory expansion handler. Uses the member allocation function to
+ * obtain @a n bytes of memory, and then moves [first,last) into it.
+ * @endif
+ */
+ template<typename _ForwardIterator>
+ pointer
+ _M_allocate_and_move(size_type __n,
+ _ForwardIterator __first, _ForwardIterator __last)
+ {
+ pointer __result = this->_M_allocate(__n);
+ try
+ {
+ std::__uninitialized_move_a(__first, __last, __result,
+ _M_get_Tp_allocator());
+ return __result;
+ }
+ catch(...)
+ {
+ _M_deallocate(__result, __n);
+ __throw_exception_again;
+ }
+ }
// Internal constructor functions follow.
diff -urNx '*CVS*' libstdc++-v3.so_7.clean/include/bits/vector.tcc libstdc++-v3/include/bits/vector.tcc
--- libstdc++-v3.so_7.clean/include/bits/vector.tcc 2005-07-05 08:46:02.000000000 +0100
+++ libstdc++-v3/include/bits/vector.tcc 2005-08-08 21:08:18.000000000 +0100
@@ -73,7 +73,7 @@
if (this->capacity() < __n)
{
const size_type __old_size = size();
- pointer __tmp = _M_allocate_and_copy(__n,
+ pointer __tmp = _M_allocate_and_move(__n,
this->_M_impl._M_start,
this->_M_impl._M_finish);
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
@@ -250,14 +250,15 @@
{
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
{
- this->_M_impl.construct(this->_M_impl._M_finish,
- *(this->_M_impl._M_finish - 1));
+ std::_Construct_move_a(this->_M_impl._M_finish,
+ *(this->_M_impl._M_finish - 1),
+ _M_get_Tp_allocator());
++this->_M_impl._M_finish;
- _Tp __x_copy = __x;
- std::copy_backward(__position,
- iterator(this->_M_impl._M_finish-2),
- iterator(this->_M_impl._M_finish-1));
- *__position = __x_copy;
+ _Tp __x_copy(__x);
+ std::__move_backward(__position,
+ iterator(this->_M_impl._M_finish-2),
+ iterator(this->_M_impl._M_finish-1));
+ *__position = __gnu_cxx::__move(__x_copy);
}
else
{
@@ -277,14 +278,14 @@
try
{
__new_finish =
- std::__uninitialized_copy_a(iterator(this->_M_impl._M_start),
+ std::__uninitialized_move_a(iterator(this->_M_impl._M_start),
__position,
__new_start,
_M_get_Tp_allocator());
this->_M_impl.construct(__new_finish.base(), __x);
++__new_finish;
__new_finish =
- std::__uninitialized_copy_a(__position,
+ std::__uninitialized_move_a(__position,
iterator(this->_M_impl._M_finish),
__new_finish,
_M_get_Tp_allocator());
@@ -320,12 +321,12 @@
iterator __old_finish(this->_M_impl._M_finish);
if (__elems_after > __n)
{
- std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
+ std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
this->_M_impl._M_finish,
this->_M_impl._M_finish,
_M_get_Tp_allocator());
this->_M_impl._M_finish += __n;
- std::copy_backward(__position, __old_finish - __n,
+ std::__move_backward(__position, __old_finish - __n,
__old_finish);
std::fill(__position, __position + __n, __x_copy);
}
@@ -336,7 +337,7 @@
__x_copy,
_M_get_Tp_allocator());
this->_M_impl._M_finish += __n - __elems_after;
- std::__uninitialized_copy_a(__position, __old_finish,
+ std::__uninitialized_move_a(__position, __old_finish,
this->_M_impl._M_finish,
_M_get_Tp_allocator());
this->_M_impl._M_finish += __elems_after;
@@ -359,14 +360,14 @@
try
{
__new_finish =
- std::__uninitialized_copy_a(begin(), __position,
+ std::__uninitialized_move_a(begin(), __position,
__new_start,
_M_get_Tp_allocator());
std::__uninitialized_fill_n_a(__new_finish, __n, __x,
_M_get_Tp_allocator());
__new_finish += __n;
__new_finish =
- std::__uninitialized_copy_a(__position, end(), __new_finish,
+ std::__uninitialized_move_a(__position, end(), __new_finish,
_M_get_Tp_allocator());
}
catch(...)
@@ -418,13 +419,13 @@
iterator __old_finish(this->_M_impl._M_finish);
if (__elems_after > __n)
{
- std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
+ std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
this->_M_impl._M_finish,
this->_M_impl._M_finish,
_M_get_Tp_allocator());
this->_M_impl._M_finish += __n;
- std::copy_backward(__position, __old_finish - __n,
- __old_finish);
+ std::__move_backward(__position, __old_finish - __n,
+ __old_finish);
std::copy(__first, __last, __position);
}
else
@@ -435,7 +436,7 @@
this->_M_impl._M_finish,
_M_get_Tp_allocator());
this->_M_impl._M_finish += __n - __elems_after;
- std::__uninitialized_copy_a(__position, __old_finish,
+ std::__uninitialized_move_a(__position, __old_finish,
this->_M_impl._M_finish,
_M_get_Tp_allocator());
this->_M_impl._M_finish += __elems_after;
@@ -458,7 +459,7 @@
try
{
__new_finish =
- std::__uninitialized_copy_a(iterator(this->_M_impl._M_start),
+ std::__uninitialized_move_a(iterator(this->_M_impl._M_start),
__position,
__new_start,
_M_get_Tp_allocator());
@@ -466,7 +467,7 @@
std::__uninitialized_copy_a(__first, __last, __new_finish,
_M_get_Tp_allocator());
__new_finish =
- std::__uninitialized_copy_a(__position,
+ std::__uninitialized_move_a(__position,
iterator(this->_M_impl._M_finish),
__new_finish,
_M_get_Tp_allocator());
diff -urNx '*CVS*' libstdc++-v3.so_7.clean/testsuite/23_containers/vector/modifiers/moveable.cc libstdc++-v3/testsuite/23_containers/vector/modifiers/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/23_containers/vector/modifiers/moveable.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/23_containers/vector/modifiers/moveable.cc 2005-08-09 19:43:41.000000000 +0100
@@ -0,0 +1,143 @@
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction. Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License. This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <vector>
+#include <testsuite_hooks.h>
+#include <testsuite_rvalref.h>
+
+using namespace __gnu_test;
+
+// Test vector::push_back makes no unneeded copies.
+void
+test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ std::vector<copycounter> a;
+ copycounter c(1);
+ copycounter::copycount = 0;
+ for(int i = 0; i < 10; ++i)
+ a.push_back(c);
+ VERIFY(copycounter::copycount == 10);
+
+ for(int i = 0; i < 100; ++i)
+ a.insert(a.begin() + i, c);
+ VERIFY(copycounter::copycount == 110);
+
+ for(int i = 0; i < 1000; ++i)
+ a.insert(a.end(), c);
+ VERIFY(copycounter::copycount == 1110);
+}
+
+// Test vector::insert(iterator, iterator, iterator) makes no unneeded copies
+// when it has to also reallocate the vector's internal buffer.
+void
+test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ copycounter c(1);
+ std::vector<copycounter> a(10, c), b(100, c);
+ copycounter::copycount = 0;
+ a.insert(a.begin(), b.begin(), b.begin() + 20);
+ VERIFY(copycounter::copycount == 20);
+ a.insert(a.end(), b.begin(), b.begin() + 50);
+ VERIFY(copycounter::copycount == 70);
+ a.insert(a.begin() + 50, b.begin(), b.end());
+ VERIFY(copycounter::copycount == 170);
+}
+
+// Test vector::insert(iterator, iterator, iterator) makes no unneeded copies
+// when it doesn't have to reallocate the vector's internal buffer.
+void
+test03()
+{
+ bool test __attribute__((unused)) = true;
+ copycounter c(1);
+ std::vector<copycounter> a(10, c), b(100, c);
+ copycounter::copycount = 0;
+ a.reserve(1000);
+ VERIFY(copycounter::copycount == 0);
+ a.insert(a.begin(), b.begin(), b.begin() + 20);
+ VERIFY(copycounter::copycount == 20);
+ a.insert(a.end(), b.begin(), b.begin() + 50);
+ VERIFY(copycounter::copycount == 70);
+ a.insert(a.begin() + 50, b.begin(), b.end());
+ VERIFY(copycounter::copycount == 170);
+}
+
+// Test vector::insert(iterator, value, count) makes no unneeded copies
+// when it has to also rellocate the vector's internal buffer.
+void
+test04()
+{
+bool test __attribute__((unused)) = true;
+
+ copycounter c(1);
+ std::vector<copycounter> a(10, c);
+ copycounter::copycount = 0;
+ a.insert(a.begin(), 20, c);
+ VERIFY(copycounter::copycount == 20);
+ a.insert(a.end(), 50, c);
+ VERIFY(copycounter::copycount == 70);
+ a.insert(a.begin() + 50, 100, c);
+ VERIFY(copycounter::copycount == 170);
+}
+
+// Test vector::insert(iterator, value, count) makes no unneeded copies
+// when it doesn't have to rellocate the vector's internal buffer.
+void
+test05()
+{
+ bool test __attribute__((unused)) = true;
+
+ copycounter c(1);
+ std::vector<copycounter> a(10, c);
+ copycounter::copycount = 0;
+ a.reserve(1000);
+ a.insert(a.begin(), 20, c);
+ // NOTE : These values are each one higher than might be expected, as
+ // vector::insert(iterator, value, count) for currently copies the value
+ // it is given when it doesn't reallocate the buffer.
+ VERIFY(copycounter::copycount == 20 + 1);
+ a.insert(a.end(), 50, c);
+ VERIFY(copycounter::copycount == 70 + 2);
+ a.insert(a.begin() + 50, 100, c);
+ VERIFY(copycounter::copycount == 170 + 3);
+}
+
+
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ test05();
+ return 0;
+}
diff -urNx '*CVS*' libstdc++-v3.so_7.clean/testsuite/testsuite_rvalref.h libstdc++-v3/testsuite/testsuite_rvalref.h
--- libstdc++-v3.so_7.clean/testsuite/testsuite_rvalref.h 2005-07-27 20:10:57.000000000 +0100
+++ libstdc++-v3/testsuite/testsuite_rvalref.h 2005-08-08 21:39:13.000000000 +0100
@@ -36,6 +36,9 @@
namespace __gnu_test
{
+ // This class is designed to test libstdc++'s template-based rvalue
+ // reference support. It should fail at compile-time if there is an attempt
+ // to copy it (although see note just below).
class rvalstruct
{
bool
@@ -109,6 +112,84 @@
rhs.val = temp;
}
+ // This is a moveable class which copies how many times it is copied.
+ // This is mainly of use in the containers, where the an element inserted
+ // into a container has to be copied once to get there, but we want to check
+ // nothing else is copied.
+ struct copycounter
+ {
+ static int copycount;
+ int val;
+ bool valid;
+
+ copycounter() : val(0), valid(false)
+ { }
+
+ copycounter(int inval) : val(inval), valid(true)
+ { }
+
+ copycounter(const copycounter& in) : val(in.val), valid(true)
+ {
+ VERIFY(in.valid == true);
+ ++copycount;
+ }
+
+ copycounter(__gnu_cxx::__rvalref<copycounter> in)
+ {
+ VERIFY(in.__ref.valid == true);
+ val = in.__ref.val;
+ in.__ref.valid = false;
+ valid = true;
+ }
+
+ copycounter&
+ operator=(int newval)
+ {
+ val = newval;
+ valid = true;
+ }
+
+ bool
+ operator=(const copycounter& in)
+ {
+ VERIFY(in.valid == true);
+ ++copycount;
+ val = in.val;
+ valid = true;
+ }
+
+ copycounter&
+ operator=(__gnu_cxx::__rvalref<copycounter> in)
+ {
+ VERIFY(in.__ref.valid == true);
+ val = in.__ref.val;
+ in.__ref.valid = false;
+ valid = true;
+ return *this;
+ }
+ };
+
+ int copycounter::copycount = 0;
+
+ bool
+ operator==(const copycounter& lhs,
+ const copycounter& rhs)
+ { return lhs.val == rhs.val; }
+
+ bool
+ operator<(const copycounter& lhs,
+ const copycounter& rhs)
+ { return lhs.val < rhs.val; }
+
+ void
+ swap(copycounter& lhs, copycounter& rhs)
+ {
+ VERIFY(lhs.valid && rhs.valid);
+ int temp = lhs.val;
+ lhs.val = rhs.val;
+ rhs.val = temp;
+ }
+
}; // namespace __gnu_test
namespace __gnu_cxx
@@ -116,6 +197,10 @@
template<>
struct __is_moveable<__gnu_test::rvalstruct>
{ static const bool __value = true; };
+
+ template<>
+ struct __is_moveable<__gnu_test::copycounter>
+ { static const bool __value = true; };
}
#endif // _GLIBCXX_TESTSUITE_TR1_H
Attachment:
changelog-vector
Description: application/text
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |