Implement a few optimizations for vector push_back and insert. Fixes r10828365.

llvm-svn: 150542

3 files changed, 103 insertions, 26 deletions

diff --git a/libcxx/include/__split_buffer b/libcxx/include/__split_buffer
index f28a6e590cf..e0aa13b8988 100644
--- a/libcxx/include/__split_buffer
+++ b/libcxx/include/__split_buffer
@@ -95,7 +95,7 @@ public:
     void reserve(size_type __n);
     void shrink_to_fit() _NOEXCEPT;
     void push_front(const_reference __x);
-    void push_back(const_reference __x);
+    _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
     void push_front(value_type&& __x);
     void push_back(value_type&& __x);
@@ -133,8 +133,10 @@ public:
 
     _LIBCPP_INLINE_VISIBILITY
     void __destruct_at_end(pointer __new_last) _NOEXCEPT
-        {__destruct_at_end(__new_last, is_trivially_destructible<value_type>());}
+        {__destruct_at_end(__new_last, false_type());}
+    _LIBCPP_INLINE_VISIBILITY
         void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT;
+    _LIBCPP_INLINE_VISIBILITY
         void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT;
 
     void swap(__split_buffer& __x)
@@ -287,7 +289,7 @@ _LIBCPP_INLINE_VISIBILITY inline
 void
 __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type)
 {
-    while (__begin_ < __new_begin)
+    while (__begin_ != __new_begin)
         __alloc_traits::destroy(__alloc(), __begin_++);
 }
 
@@ -304,7 +306,7 @@ _LIBCPP_INLINE_VISIBILITY inline
 void
 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT
 {
-    while (__new_last < __end_)
+    while (__new_last != __end_)
         __alloc_traits::destroy(__alloc(), --__end_);
 }
 
diff --git a/libcxx/include/memory b/libcxx/include/memory
index 0e14275c114..e841b2cf051 100644
--- a/libcxx/include/memory
+++ b/libcxx/include/memory
@@ -597,6 +597,7 @@ void* align(size_t alignment, size_t size, void*& ptr, size_t& space);
 #include <__functional_base>
 #include <iosfwd>
 #include <tuple>
+#include <cstring>
 #if defined(_LIBCPP_NO_EXCEPTIONS)
     #include <cassert>
 #endif
@@ -1395,6 +1396,14 @@ struct __has_construct
 {
 };
 
+#else  // _LIBCPP_HAS_NO_VARIADICS
+
+template <class _Alloc, class _Pointer, class _Args>
+struct __has_construct
+    : false_type
+{
+};
+
 #endif  // _LIBCPP_HAS_NO_VARIADICS
 
 template <class _Alloc, class _Pointer>
@@ -1524,6 +1533,60 @@ struct _LIBCPP_VISIBLE allocator_traits
                 __has_select_on_container_copy_construction<const allocator_type>(),
                 __a);}
 
+    template <class _Ptr>
+        _LIBCPP_INLINE_VISIBILITY
+        static
+        void
+        __construct_forward(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __begin2)
+        {
+            for (; __begin1 != __end1; ++__begin1, ++__begin2)
+                construct(__a, _VSTD::__to_raw_pointer(__begin2), _VSTD::move_if_noexcept(*__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_forward(allocator_type& __a, _Tp* __begin1, _Tp* __end1, _Tp*& __begin2)
+        {
+            ptrdiff_t _Np = __end1 - __begin1;
+            _VSTD::memcpy(__begin2, __begin1, _Np * sizeof(_Tp));
+            __begin2 += _Np;
+        }
+
+    template <class _Ptr>
+        _LIBCPP_INLINE_VISIBILITY
+        static
+        void
+        __construct_backward(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __end2)
+        {
+            while (__end1 != __begin1)
+                construct(__a, _VSTD::__to_raw_pointer(--__end2), _VSTD::move_if_noexcept(*--__end1));
+        }
+
+    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_backward(allocator_type& __a, _Tp* __begin1, _Tp* __end1, _Tp*& __end2)
+        {
+            ptrdiff_t _Np = __end1 - __begin1;
+            __end2 -= _Np;
+            _VSTD::memcpy(__end2, __begin1, _Np * sizeof(_Tp));
+        }
+
 private:
 
     _LIBCPP_INLINE_VISIBILITY
diff --git a/libcxx/include/vector b/libcxx/include/vector
index 9d5c23c698e..282713e70fb 100644
--- a/libcxx/include/vector
+++ b/libcxx/include/vector
@@ -366,7 +366,7 @@ protected:
 
     _LIBCPP_INLINE_VISIBILITY
     void __destruct_at_end(const_pointer __new_last) _NOEXCEPT
-        {__destruct_at_end(__new_last, is_trivially_destructible<value_type>());}
+        {__destruct_at_end(__new_last, false_type());}
     _LIBCPP_INLINE_VISIBILITY
     void __destruct_at_end(const_pointer __new_last, false_type) _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
@@ -439,7 +439,7 @@ _LIBCPP_INLINE_VISIBILITY inline
 void
 __vector_base<_Tp, _Allocator>::__destruct_at_end(const_pointer __new_last, false_type) _NOEXCEPT
 {
-    while (__new_last < __end_)
+    while (__new_last != __end_)
         __alloc_traits::destroy(__alloc(), const_cast<pointer>(--__end_));
 }
 
@@ -676,7 +676,7 @@ public:
 
     _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-    void push_back(value_type&& __x);
+    _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
 #ifndef _LIBCPP_HAS_NO_VARIADICS
     template <class... _Args>
         void emplace_back(_Args&&... __args);
@@ -789,14 +789,20 @@ private:
 #endif
         __base::__destruct_at_end(__new_last);
     }
+    template <class _Up>
+        void
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+        __push_back_slow_path(_Up&& __x);
+#else
+        __push_back_slow_path(_Up& __x);
+#endif
 };
 
 template <class _Tp, class _Allocator>
 void
 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
 {
-    for (pointer __p = this->__end_; this->__begin_ < __p;)
-        __v.push_front(_VSTD::move_if_noexcept(*--__p));
+    __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
     _VSTD::swap(this->__begin_, __v.__begin_);
     _VSTD::swap(this->__end_, __v.__end_);
     _VSTD::swap(this->__end_cap(), __v.__end_cap());
@@ -809,10 +815,8 @@ typename vector<_Tp, _Allocator>::pointer
 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
 {
     pointer __r = __v.__begin_;
-    for (pointer __i = __p; this->__begin_ < __i;)
-        __v.push_front(_VSTD::move_if_noexcept(*--__i));
-    for (pointer __i = __p; __i < this->__end_; ++__i)
-        __v.push_back(_VSTD::move_if_noexcept(*__i));
+    __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_);
+    __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_);
     _VSTD::swap(this->__begin_, __v.__begin_);
     _VSTD::swap(this->__end_, __v.__end_);
     _VSTD::swap(this->__end_cap(), __v.__end_cap());
@@ -1438,27 +1442,40 @@ vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
 }
 
 template <class _Tp, class _Allocator>
+template <class _Up>
+void
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
+#else
+vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
+#endif
+{
+    allocator_type& __a = this->__alloc();
+    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
+    // __v.push_back(_VSTD::forward<_Up>(__x));
+    __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_++), _VSTD::forward<_Up>(__x));
+    __swap_out_circular_buffer(__v);
+}
+
+template <class _Tp, class _Allocator>
+_LIBCPP_INLINE_VISIBILITY inline
 void
 vector<_Tp, _Allocator>::push_back(const_reference __x)
 {
-    if (this->__end_ < this->__end_cap())
+    if (this->__end_ != this->__end_cap())
     {
         __alloc_traits::construct(this->__alloc(),
                                   _VSTD::__to_raw_pointer(this->__end_), __x);
         ++this->__end_;
     }
     else
-    {
-        allocator_type& __a = this->__alloc();
-        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
-        __v.push_back(__x);
-        __swap_out_circular_buffer(__v);
-    }
+        __push_back_slow_path(__x);
 }
 
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
 template <class _Tp, class _Allocator>
+_LIBCPP_INLINE_VISIBILITY inline
 void
 vector<_Tp, _Allocator>::push_back(value_type&& __x)
 {
@@ -1470,12 +1487,7 @@ vector<_Tp, _Allocator>::push_back(value_type&& __x)
         ++this->__end_;
     }
     else
-    {
-        allocator_type& __a = this->__alloc();
-        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
-        __v.push_back(_VSTD::move(__x));
-        __swap_out_circular_buffer(__v);
-    }
+        __push_back_slow_path(_VSTD::move(__x));
 }
 
 #ifndef _LIBCPP_HAS_NO_VARIADICS