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, 64 insertions, 0 deletions

diff --git a/libcxx/benchmarks/algorithms.bench.cpp b/libcxx/benchmarks/algorithms.bench.cpp
index 86315390e0d..ab0e81b0cac 100644
--- a/libcxx/benchmarks/algorithms.bench.cpp
+++ b/libcxx/benchmarks/algorithms.bench.cpp
@@ -58,5 +58,69 @@ 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();