[PATCH] D42357: Under limitation of allocated buffer, inplace_merge does NOT take usge of partial allocated buffer but uses native rotate directly. It makes the performace far behind from corresponding part of GCC. In this patch, it tries to use partial allocated...

[WeiChungChang via Phabricator via cfe-commits]

WeiChungChang created this revision.
Herald added a subscriber: cfe-commits.

...buffer firstly. Experiment shows 28.35% & 25.06% speedup for merging two 
equal size sorted integers for -O3 & no -O3 cases.


Repository:
  rCXX libc++

https://reviews.llvm.org/D42357

Files:
  include/algorithm


Index: include/algorithm
===================================================================
--- include/algorithm
+++ include/algorithm
@@ -2497,6 +2497,41 @@
 template <class _ForwardIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _ForwardIterator
+__buffered__rotate(_ForwardIterator __first, _ForwardIterator __middle, 
_ForwardIterator __last,
+         typename iterator_traits<_ForwardIterator>::value_type* __buff, 
ptrdiff_t __buff_size)
+{
+    if (__first == __middle)
+        return __last;
+    if (__middle == __last)
+        return __first;
+    typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type 
value_type;
+    typedef typename _VSTD::iterator_traits<_ForwardIterator>::difference_type 
difference_type;
+    typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type* 
pointer;
+    difference_type __len1, __len2;
+    __len1 = __middle - __first;
+    __len2 = __last - __middle;
+    if ((__len1 <= __buff_size) && __len1 < __len2) 
+    {
+        pointer __buff_end = __move(__first, __middle,  __buff);
+        __move(__middle, __last, __first);
+        return __move_backward(__buff, __buff_end, __last);
+    }
+    else if (__len2 <= __buff_size)
+    {
+        pointer __buffer_end = __move(__middle, __last,  __buff);
+        __move_backward(__first, __middle, __last);
+        return __move(__buff, __buffer_end, __first);
+    }
+    else
+    {
+        return _VSTD::__rotate(__first, __middle, __last,
+                               typename 
_VSTD::iterator_traits<_ForwardIterator>::iterator_category());
+    }
+}
+
+template <class _ForwardIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_ForwardIterator
 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator 
__last)
 {
     if (__first == __middle)
@@ -4543,7 +4578,8 @@
         difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
         // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
         // swap middle two partitions
-        __middle = _VSTD::rotate(__m1, __middle, __m2);
+        //__middle = _VSTD::rotate(__m1, __middle, __m2);
+        __middle = _VSTD::__buffered_rotate(__m1, __middle, __m2, __buff, 
__buff_size);
         // __len12 and __len21 now have swapped meanings
         // merge smaller range with recurisve call and larger with tail 
recursion elimination
         if (__len11 + __len21 < __len12 + __len22)



Index: include/algorithm
===================================================================
--- include/algorithm
+++ include/algorithm
@@ -2497,6 +2497,41 @@
 template <class _ForwardIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _ForwardIterator
+__buffered__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
+         typename iterator_traits<_ForwardIterator>::value_type* __buff, ptrdiff_t __buff_size)
+{
+    if (__first == __middle)
+        return __last;
+    if (__middle == __last)
+        return __first;
+    typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
+    typedef typename _VSTD::iterator_traits<_ForwardIterator>::difference_type difference_type;
+    typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type* pointer;
+    difference_type __len1, __len2;
+    __len1 = __middle - __first;
+    __len2 = __last - __middle;
+    if ((__len1 <= __buff_size) && __len1 < __len2) 
+    {
+        pointer __buff_end = __move(__first, __middle,  __buff);
+        __move(__middle, __last, __first);
+        return __move_backward(__buff, __buff_end, __last);
+    }
+    else if (__len2 <= __buff_size)
+    {
+        pointer __buffer_end = __move(__middle, __last,  __buff);
+        __move_backward(__first, __middle, __last);
+        return __move(__buff, __buffer_end, __first);
+    }
+    else
+    {
+        return _VSTD::__rotate(__first, __middle, __last,
+                               typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
+    }
+}
+
+template <class _ForwardIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_ForwardIterator
 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {
     if (__first == __middle)
@@ -4543,7 +4578,8 @@
         difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
         // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
         // swap middle two partitions
-        __middle = _VSTD::rotate(__m1, __middle, __m2);
+        //__middle = _VSTD::rotate(__m1, __middle, __m2);
+        __middle = _VSTD::__buffered_rotate(__m1, __middle, __m2, __buff, __buff_size);
         // __len12 and __len21 now have swapped meanings
         // merge smaller range with recurisve call and larger with tail recursion elimination
         if (__len11 + __len21 < __len12 + __len22)

_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits