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

1 files changed, 59 insertions, 0 deletions

diff --git a/libcxx/test/libcxx/algorithms/half_positive.pass.cpp b/libcxx/test/libcxx/algorithms/half_positive.pass.cpp
new file mode 100644
index 00000000000..178055cbbd0
--- /dev/null
+++ b/libcxx/test/libcxx/algorithms/half_positive.pass.cpp
@@ -0,0 +1,59 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template <typename _Tp> _Tp __half_positive(const _Tp&);
+
+// __half_positive divide integer number by 2 as unsigned number
+// if it's safe to do so. It can be an important optimization for lower bound,
+// for example.
+
+#include <algorithm>
+#include <cassert>
+#include <limits>
+#include <type_traits>
+
+#include "test_macros.h"
+#include "user_defined_integral.hpp"
+
+namespace {
+
+template <class IntType, class UnderlyingType = IntType>
+TEST_CONSTEXPR bool test(IntType max_v = IntType(std::numeric_limits<UnderlyingType>::max())) {
+    return std::__half_positive(max_v) == max_v / 2;
+}
+
+}  // namespace
+
+int main()
+{
+    {
+        assert(test<char>());
+        assert(test<int>());
+        assert(test<long>());
+        assert((test<UserDefinedIntegral<int>, int>()));
+        assert(test<size_t>());
+#if !defined(_LIBCPP_HAS_NO_INT128)
+        assert(test<__int128_t>());
+#endif  // !defined(_LIBCPP_HAS_NO_INT128)
+    }
+
+#if TEST_STD_VER >= 11
+    {
+        static_assert(test<char>(), "");
+        static_assert(test<int>(), "");
+        static_assert(test<long>(), "");
+        static_assert(test<size_t>(), "");
+#if !defined(_LIBCPP_HAS_NO_INT128)
+        static_assert(test<__int128_t>(), "");
+#endif  // !defined(_LIBCPP_HAS_NO_INT128)
+    }
+#endif // TEST_STD_VER >= 11
+}