Hi mclow.lists, howard.hinnant,
In certain cases vector can use memcpy to construct a range of elements at the
back of the vector. We currently don't do this resulting in terrible code gen
in non-optimized mode and a
very large slowdown compared to libstdc++.
This patch adds a `__construct_forward_range(Allocator, Iter, Iter, _Ptr&)` and
`__construct_forward_range(Allocator, Tp*, Tp*, Tp*&)` functions to
`allocator_traits` which act similarly to the existing
`__construct_forward(...)` functions.
This patch also changes vectors `__construct_at_end(Iter, Iter)` to be
`__construct_at_end(Iter, Iter, SizeType)` where SizeType is the size of the
range. `__construct_at_end(Iter, Iter, SizeType)` now calls
`allocator_traits<Tp>::__construct_forward_range(...)`.
This patch is based off the design of `__swap_out_circular_buffer(...)` which
uses `allocator_traits<Tp>::__construct_forward(...)`.
On my machine this code performs 4x better than the current implementation when
tested against `std::vector<int>`.
http://reviews.llvm.org/D8109
Files:
include/memory
include/vector
EMAIL PREFERENCES
http://reviews.llvm.org/settings/panel/emailpreferences/
Index: include/memory
===================================================================
--- include/memory
+++ include/memory
@@ -1525,6 +1525,34 @@
__begin2 += _Np;
}
+ template <class _Iter, class _Ptr>
+ _LIBCPP_INLINE_VISIBILITY
+ static
+ void
+ __construct_range_forward(allocator_type& __a, _Iter __begin1, _Iter __end1, _Ptr& __begin2)
+ {
+ for (; __begin1 != __end1; ++__begin1, (void) ++__begin2)
+ construct(__a, _VSTD::__to_raw_pointer(__begin2), *__begin1);
+ }
+
+ template <class _Tp>
+ _LIBCPP_INLINE_VISIBILITY
+ static
+ typename enable_if
+ <
+ (is_same<allocator_type, allocator<_Tp> >::value
+ || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
+ is_trivially_move_constructible<_Tp>::value,
+ void
+ >::type
+ __construct_range_forward(allocator_type& __a, _Tp* __begin1, _Tp* __end1, _Tp*& __begin2)
+ {
+ typedef typename remove_const<_Tp>::type _Vp;
+ ptrdiff_t _Np = __end1 - __begin1;
+ _VSTD::memcpy(const_cast<_Vp*>(__begin2), __begin1, _Np * sizeof(_Tp));
+ __begin2 += _Np;
+ }
+
template <class _Ptr>
_LIBCPP_INLINE_VISIBILITY
static
Index: include/vector
===================================================================
--- include/vector
+++ include/vector
@@ -783,7 +783,7 @@
__is_forward_iterator<_ForwardIterator>::value,
void
>::type
- __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
+ __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n);
void __append(size_type __n);
void __append(size_type __n, const_reference __x);
_LIBCPP_INLINE_VISIBILITY
@@ -1021,16 +1021,12 @@
__is_forward_iterator<_ForwardIterator>::value,
void
>::type
-vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
+vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
{
allocator_type& __a = this->__alloc();
- for (; __first != __last; ++__first)
- {
- __RAII_IncreaseAnnotator __annotator(*this);
- __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
- __annotator.__done();
- ++this->__end_;
- }
+ __RAII_IncreaseAnnotator __annotator(*this, __n);
+ __alloc_traits::__construct_range_forward(__a, __first, __last, this->__end_);
+ __annotator.__done();
}
// Default constructs __n objects starting at __end_
@@ -1177,7 +1173,7 @@
if (__n > 0)
{
allocate(__n);
- __construct_at_end(__first, __last);
+ __construct_at_end(__first, __last, __n);
}
}
@@ -1197,7 +1193,7 @@
if (__n > 0)
{
allocate(__n);
- __construct_at_end(__first, __last);
+ __construct_at_end(__first, __last, __n);
}
}
@@ -1212,7 +1208,7 @@
if (__n > 0)
{
allocate(__n);
- __construct_at_end(__x.__begin_, __x.__end_);
+ __construct_at_end(__x.__begin_, __x.__end_, __n);
}
}
@@ -1227,7 +1223,7 @@
if (__n > 0)
{
allocate(__n);
- __construct_at_end(__x.__begin_, __x.__end_);
+ __construct_at_end(__x.__begin_, __x.__end_, __n);
}
}
@@ -1286,7 +1282,7 @@
if (__il.size() > 0)
{
allocate(__il.size());
- __construct_at_end(__il.begin(), __il.end());
+ __construct_at_end(__il.begin(), __il.end(), __il.size());
}
}
@@ -1301,7 +1297,7 @@
if (__il.size() > 0)
{
allocate(__il.size());
- __construct_at_end(__il.begin(), __il.end());
+ __construct_at_end(__il.begin(), __il.end(), __il.size());
}
}
@@ -1394,12 +1390,13 @@
>::type
vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
{
- typename iterator_traits<_ForwardIterator>::difference_type __new_size = _VSTD::distance(__first, __last);
- if (static_cast<size_type>(__new_size) <= capacity())
+ typename iterator_traits<_ForwardIterator>::difference_type __new_size_diff = _VSTD::distance(__first, __last);
+ size_type __new_size = static_cast<size_type>(__new_size_diff);
+ if (__new_size <= capacity())
{
_ForwardIterator __mid = __last;
bool __growing = false;
- if (static_cast<size_type>(__new_size) > size())
+ if (__new_size > size())
{
__growing = true;
__mid = __first;
@@ -1407,15 +1404,15 @@
}
pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
if (__growing)
- __construct_at_end(__mid, __last);
+ __construct_at_end(__mid, __last, __new_size - size());
else
this->__destruct_at_end(__m);
}
else
{
deallocate();
- allocate(__recommend(static_cast<size_type>(__new_size)));
- __construct_at_end(__first, __last);
+ allocate(__recommend(__new_size));
+ __construct_at_end(__first, __last, __new_size);
}
}
@@ -1967,8 +1964,9 @@
if (__n > __dx)
{
__m = __first;
- _VSTD::advance(__m, this->__end_ - __p);
- __construct_at_end(__m, __last);
+ difference_type __diff = this->__end_ - __p;
+ _VSTD::advance(__m, __diff);
+ __construct_at_end(__m, __last, __n - __diff);
__n = __dx;
}
if (__n > 0)
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
