Revert "Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible."

This reverts r345525. I'm reverting because that patch apparently caused
a regression on certain platforms (see https://reviews.llvm.org/D53994).
Since we don't fully understand the reasons for the regression, I'm
reverting until we can provide a fix we understand.

llvm-svn: 345893

1 files changed, 0 insertions, 64 deletions

diff --git a/libcxx/benchmarks/algorithms.bench.cpp b/libcxx/benchmarks/algorithms.bench.cpp
index ab0e81b0cac..86315390e0d 100644
--- a/libcxx/benchmarks/algorithms.bench.cpp
+++ b/libcxx/benchmarks/algorithms.bench.cpp
@@ -58,69 +58,5 @@ BENCHMARK_CAPTURE(BM_Sort, sorted_descending_strings,
 BENCHMARK_CAPTURE(BM_Sort, single_element_strings,
     getDuplicateStringInputs)->Arg(TestNumInputs);
 
-template <typename GenInputs, typename Alg>
-void do_binary_search_benchmark(benchmark::State& st, GenInputs gen, Alg alg)
-{
-    using ValueType = typename decltype(gen(0))::value_type;
-    auto in = gen(st.range(0));
-    std::sort(in.begin(), in.end());
-
-    const auto every_10_percentile = [&]() -> std::vector<ValueType*>  {
-        size_t step = in.size() / 10;
-
-        if (step == 0) {
-            st.SkipWithError("Input doesn't contain enough elements");
-            return {};
-        }
-
-        std::vector<ValueType*> res;
-        for (size_t i = 0; i < in.size(); i += step)
-            res.push_back(&in[i]);
-
-        return res;
-    }();
-
-    for (auto _ : st)
-    {
-        for (auto* test : every_10_percentile)
-          benchmark::DoNotOptimize(alg(in.begin(), in.end(), *test));
-    }
-}
-
-template <typename GenInputs>
-void BM_LowerBound(benchmark::State& st, GenInputs gen)
-{
-    do_binary_search_benchmark(st, gen, [](auto f, auto l, const auto& v) {
-        return std::lower_bound(f, l, v);
-    });
-}
-
-BENCHMARK_CAPTURE(BM_LowerBound, random_int32, getRandomIntegerInputs<int32_t>)
-    ->Arg(TestNumInputs)                    // Small int32_t vector
-    ->Arg(TestNumInputs * TestNumInputs);   // Big int32_t   vector
-
-BENCHMARK_CAPTURE(BM_LowerBound, random_int64, getRandomIntegerInputs<int64_t>)
-    ->Arg(TestNumInputs);  // Small int64_t vector. Should also represent pointers.
-
-BENCHMARK_CAPTURE(BM_LowerBound, random_strings, getRandomStringInputs)
-    ->Arg(TestNumInputs);  // Small string vector. What happens if the comparison is not very cheap.
-
-template <typename GenInputs>
-void BM_EqualRange(benchmark::State& st, GenInputs gen)
-{
-    do_binary_search_benchmark(st, gen, [](auto f, auto l, const auto& v) {
-        return std::equal_range(f, l, v);
-    });
-}
-
-BENCHMARK_CAPTURE(BM_EqualRange, random_int32, getRandomIntegerInputs<int32_t>)
-    ->Arg(TestNumInputs)                    // Small int32_t vector
-    ->Arg(TestNumInputs * TestNumInputs);   // Big int32_t   vector
-
-BENCHMARK_CAPTURE(BM_EqualRange, random_int64, getRandomIntegerInputs<int64_t>)
-    ->Arg(TestNumInputs);  // Small int64_t vector. Should also represent pointers.
-
-BENCHMARK_CAPTURE(BM_EqualRange, random_strings, getRandomStringInputs)
-    ->Arg(TestNumInputs);  // Small string vector. What happens if the comparison is not very cheap.
 
 BENCHMARK_MAIN();