commit dda14512e0375bda850751205731735164b8c04e
author Louis Dionne <ldionne@apple.com> Mon Dec 17 16:04:39 2018 +0000
committer Louis Dionne <ldionne@apple.com> Mon Dec 17 16:04:39 2018 +0000
tree 16c6cd2a3af275bbca0a8f178a366d139143094c
parent 009b40c2d1689bad59029777b660e2591b762dc4

[libcxx] Speeding up partition_point/lower_bound/upper_bound

This is a re-application of r345525, which had been reverted by fear of
a regression.

Reviewed as https://reviews.llvm.org/D53994.
Thanks to Denis Yaroshevskiy for the patch.

llvm-svn: 349358
Cr-Mirrored-From: sso://chromium.googlesource.com/_direct/external/github.com/llvm/llvm-project
Cr-Mirrored-Commit: 04695a7539b47f602eca298cc99783a5dd32c63a

include/algorithm

diff --git a/include/algorithm b/include/algorithm
index 9f425cf..d102899 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -750,6 +750,32 @@
     bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
 };
 
+// Perform division by two quickly for positive integers (llvm.org/PR39129)
+
+template <typename _Integral>
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+typename enable_if
+<
+    is_integral<_Integral>::value,
+    _Integral
+>::type
+__half_positive(_Integral __value)
+{
+    return static_cast<_Integral>(static_cast<typename make_unsigned<_Integral>::type>(__value) / 2);
+}
+
+template <typename _Tp>
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+typename enable_if
+<
+    !is_integral<_Tp>::value,
+    _Tp
+>::type
+__half_positive(_Tp __value)
+{
+    return __value / 2;
+}
+
 #ifdef _LIBCPP_DEBUG
 
 template <class _Compare>
@@ -3202,7 +3228,7 @@
     difference_type __len = _VSTD::distance(__first, __last);
     while (__len != 0)
     {
-        difference_type __l2 = __len / 2;
+        difference_type __l2 = _VSTD::__half_positive(__len);
         _ForwardIterator __m = __first;
         _VSTD::advance(__m, __l2);
         if (__pred(*__m))
@@ -4070,7 +4096,7 @@
     difference_type __len = _VSTD::distance(__first, __last);
     while (__len != 0)
     {
-        difference_type __l2 = __len / 2;
+        difference_type __l2 = _VSTD::__half_positive(__len);
         _ForwardIterator __m = __first;
         _VSTD::advance(__m, __l2);
         if (__comp(*__m, __value_))
@@ -4112,7 +4138,7 @@
     difference_type __len = _VSTD::distance(__first, __last);
     while (__len != 0)
     {
-        difference_type __l2 = __len / 2;
+        difference_type __l2 = _VSTD::__half_positive(__len);
         _ForwardIterator __m = __first;
         _VSTD::advance(__m, __l2);
         if (__comp(__value_, *__m))
@@ -4154,7 +4180,7 @@
     difference_type __len = _VSTD::distance(__first, __last);
     while (__len != 0)
     {
-        difference_type __l2 = __len / 2;
+        difference_type __l2 = _VSTD::__half_positive(__len);
         _ForwardIterator __m = __first;
         _VSTD::advance(__m, __l2);
         if (__comp(*__m, __value_))