From 8c40d81d4f019b8b1ae02c154be657b949c2cf4d Mon Sep 17 00:00:00 2001
From: Eric Fiselier <eric@efcs.ca>
Date: Mon, 29 Oct 2018 19:25:02 +0000
Subject: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by
 using unsigned division by 2 when possible.

Patch by Denis Yaroshevskiy (denis.yaroshevskij@gmail.com)

The rational and measurements can be found in the bug description: https://bugs.llvm.org/show_bug.cgi?id=39129

Reviewed as https://reviews.llvm.org/D52697

llvm-svn: 345525
---
 libcxx/include/algorithm | 34 ++++++++++++++++++++++++++++++----
 1 file changed, 30 insertions(+), 4 deletions(-)

(limited to 'libcxx/include/algorithm')

diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index beee6b5b837..f119d252063 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -750,6 +750,32 @@ public:
     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 @@ partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __
     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))
@@ -4069,7 +4095,7 @@ __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va
     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_))
@@ -4111,7 +4137,7 @@ __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va
     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))
@@ -4153,7 +4179,7 @@ __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va
     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_))
-- 
cgit v1.2.3