Performance tweaking rotate.

rotate is a critical algorithm because it is often used by other algorithms,
both std and non-std.  The main thrust of this optimization is a specialized
algorithm when the 'distance' to be shifted is 1 (either left or right).  To my
surprise, this 'optimization' was not effective for types like std::string.
std::string favors rotate algorithms which only use swap.  But for types like
scalars, and especially when the sequence is random access, these new
specializations are a big win.  If it is a vector<size_t> for example, the
rotate is done via a memmove and can be several times faster than the gcd
algorithm.

I'm using is_trivially_move_assignable to distinguish between types like int and
types like string.  This is obviously an ad-hoc approximation, but I haven't
found a case where it doesn't give good results.

I've used a 'static if' (with is_trivially_move_assignable) in three places. 
Testing with both -Os and -O3 showed that clang eliminated all code not be
executed by the 'static if' (including the 'static if' itself).

llvm-svn: 161247

1 files changed, 84 insertions, 27 deletions

diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index 67e1101704d9..1ce14b46d425 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -2103,12 +2103,31 @@ reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _Out
 
 template <class _ForwardIterator>
 _ForwardIterator
-__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, false_type)
+__rotate_left(_ForwardIterator __first, _ForwardIterator __last)
+{
+    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
+    value_type __tmp = _VSTD::move(*__first);
+    _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
+    *__lm1 = _VSTD::move(__tmp);
+    return __lm1;
+}
+
+template <class _BidirectionalIterator>
+_BidirectionalIterator
+__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
+{
+    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
+    _BidirectionalIterator __lm1 = _VSTD::prev(__last);
+    value_type __tmp = _VSTD::move(*__lm1);
+    _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
+    *__first = _VSTD::move(__tmp);
+    return __fp1;
+}
+
+template <class _ForwardIterator>
+_ForwardIterator
+__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {
-    if (__first == __middle)
-        return __last;
-    if (__middle == __last)
-        return __first;
     _ForwardIterator __i = __middle;
     while (true)
     {
@@ -2156,15 +2175,11 @@ __gcd(_Integral __x, _Integral __y)
 
 template<typename _RandomAccessIterator>
 _RandomAccessIterator
-__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, true_type)
+__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
 
-    if (__first == __middle)
-        return __last;
-    if (__middle == __last)
-        return __first;
     const difference_type __m1 = __middle - __first;
     const difference_type __m2 = __last - __middle;
     if (__m1 == __m2)
@@ -2172,15 +2187,15 @@ __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomA
         _VSTD::swap_ranges(__first, __middle, __middle);
         return __middle;
     }
-    const difference_type __g = __gcd(__m1, __m2);
+    const difference_type __g = _VSTD::__gcd(__m1, __m2);
     for (_RandomAccessIterator __p = __first + __g; __p != __first;)
     {
-        value_type __t(*--__p);
+        value_type __t(_VSTD::move(*--__p));
         _RandomAccessIterator __p1 = __p;
         _RandomAccessIterator __p2 = __p1 + __m1;
         do
         {
-            *__p1 = *__p2;
+            *__p1 = _VSTD::move(*__p2);
             __p1 = __p2;
             const difference_type __d = __last - __p2;
             if (__m1 < __d)
@@ -2188,7 +2203,7 @@ __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomA
             else
                 __p2 = __first + (__m1 - __d);
         } while (__p2 != __p);
-        *__p1 = __t;
+        *__p1 = _VSTD::move(__t);
     }
     return __first + __m2;
 }
@@ -2196,22 +2211,64 @@ __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomA
 template <class _ForwardIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _ForwardIterator
+__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
+         _VSTD::forward_iterator_tag)
+{
+    typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
+    if (_VSTD::is_trivially_move_assignable<value_type>::value)
+    {
+        if (_VSTD::next(__first) == __middle)
+            return _VSTD::__rotate_left(__first, __last);
+    }
+    return _VSTD::__rotate_forward(__first, __middle, __last);
+}
+
+template <class _BidirectionalIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_BidirectionalIterator
+__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
+         _VSTD::bidirectional_iterator_tag)
+{
+    typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
+    if (_VSTD::is_trivially_move_assignable<value_type>::value)
+    {
+        if (_VSTD::next(__first) == __middle)
+            return _VSTD::__rotate_left(__first, __last);
+        if (_VSTD::next(__middle) == __last)
+            return _VSTD::__rotate_right(__first, __last);
+    }
+    return _VSTD::__rotate_forward(__first, __middle, __last);
+}
+
+template <class _RandomAccessIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_RandomAccessIterator
+__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
+         _VSTD::random_access_iterator_tag)
+{
+    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
+    if (_VSTD::is_trivially_move_assignable<value_type>::value)
+    {
+        if (_VSTD::next(__first) == __middle)
+            return _VSTD::__rotate_left(__first, __last);
+        if (_VSTD::next(__middle) == __last)
+            return _VSTD::__rotate_right(__first, __last);
+        return _VSTD::__rotate_gcd(__first, __middle, __last);
+    }
+    return _VSTD::__rotate_forward(__first, __middle, __last);
+}
+
+template <class _ForwardIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_ForwardIterator
 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {
+    if (__first == __middle)
+        return __last;
+    if (__middle == __last)
+        return __first;
     return _VSTD::__rotate(__first, __middle, __last,
-                          integral_constant
-                          <
-                               bool,
-                               is_convertible
-                               <
-                                   typename iterator_traits<_ForwardIterator>::iterator_category,
-                                   random_access_iterator_tag
-                               >::value &&
-                               is_trivially_copy_assignable
-                               <
-                                   typename iterator_traits<_ForwardIterator>::value_type
-                               >::value
-                           >());
+                           typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 // rotate_copy