[libcxx] Optimize vectors uninitialized construction of trivial types from an iterator range.

[EricWF]

Summary

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

[mclow.lists]

include/vector

1029

This is not exception safe.
If one of the constructions throws, then the ASAN annotations will be wrong.

[EricWF]

include/vector

1029

This actually is exception safe but I had to think about it for a long time before I understood.

1. __RAII_IncreaseAnnotate __annotator(*this, __n);: Unpoison the next __n elements.
2. __annotator.__done(). commits to unpoisoning the elements.
3. ~__annotator: If __done() has been called the destructor does nothing. Otherwise it re-poisons everything from __end_ on.

[mclow.lists]

include/vector

1029

I don't think that's right - but I think that the problem is in __RAII_IncreaseAnnotate, not here.

__annotate_shrink needs the old size to reset the poisoned area, but it's passing size() + __n, where __n is the sized that was originally grown. This works fine as long as we're only increasing by 1 element, and failure means "no change" to the size. However, now that we're increasing by >1, we have to deal with the idea that failure can still change the size.

One possible way of fixing this is to change __RAII_IncreaseAnnotator so that instead of saving off the __n that is passed in, it saves off size() + __n.

[EricWF]

Adding Kostya to this patch to discuss the __RAII_IncreaseAnnotate changes.

[mclow.lists]

include/vector

1393–1394

This requires traversing the sequence (in the case of non-RA iterators). Do we really want to do that? Is it worth having a separate version for RA iterators?

[EricWF]

include/vector

1029

That fix is up for review as D8172.

1393–1394

Maybe but I don't have benchmarks to prove it yet. I didn't add the call to distance in this case so I don't think that should block this patch. However I am aware of this issue and am looking into it separately.

[mclow.lists]

LGTM.

include/vector

1394

I would combine these two lines into one:
size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));

and not bother with __new_size_diff

[EricWF]

Address @mclow.lists comments.

include/memory

             __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

include/vector

             __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

     __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_

     if (__n > 0)
     {
         allocate(__n);
-        __construct_at_end(__first, __last);
+        __construct_at_end(__first, __last, __n);
     }
 }
 

     if (__n > 0)
     {
         allocate(__n);
-        __construct_at_end(__first, __last);
+        __construct_at_end(__first, __last, __n);
     }
 }
 

     if (__n > 0)
     {
         allocate(__n);
-        __construct_at_end(__x.__begin_, __x.__end_);
+        __construct_at_end(__x.__begin_, __x.__end_, __n);
     }
 }
 

     if (__n > 0)
     {
         allocate(__n);
-        __construct_at_end(__x.__begin_, __x.__end_);
+        __construct_at_end(__x.__begin_, __x.__end_, __n);
     }
 }
 

     if (__il.size() > 0)
     {
         allocate(__il.size());
-        __construct_at_end(__il.begin(), __il.end());
+        __construct_at_end(__il.begin(), __il.end(), __il.size());
     }
 }
 

     if (__il.size() > 0)
     {
         allocate(__il.size());
-        __construct_at_end(__il.begin(), __il.end());
+        __construct_at_end(__il.begin(), __il.end(), __il.size());
     }
 }
 

 >::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())
+    size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));
+    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;

         }
         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);
     }
 }
 

             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)