Basic merge benchmarks

[dyaroshev]

Summary

These are very basic benchmarks for std::merge.
I also enabled the same benchmarks for std::set_union, just because it was for free.
I can remove them if you feel like the benchmarks for set_union that do not try different duplicate count are not interesting.

[dyaroshev]

Ping

libcxx/benchmarks/algorithms.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
 
 #include <algorithm>
 #include <cstdint>
 #include <map>
 #include <random>
 #include <string>
 #include <utility>
 #include <vector>

libcxx/benchmarks/algorithms.merge.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <array>
+#include <string>
+
+#include "benchmark/benchmark.h"
+
+#include "CartesianBenchmarks.h"
+#include "GenerateInput.h"
+#include "test_macros.h"
+
+namespace {
+
+constexpr size_t kSplitPointCount = 5;
+
+template <class I>
+std::array<I, kSplitPointCount> pickSplitPoints(I f, I l) {
+  std::ptrdiff_t N = std::distance(f, l);
+
+  return {f + N / 4, f + N / 3, f + N / 2, f + 2 * N / 3, f + 3 * N / 4};
+}
+
+template <class IntT>
+struct TestIntBase {
+  static std::vector<IntT> generateInput(size_t size) {
+    std::vector<IntT> Res(size);
+    std::generate(Res.begin(), Res.end(),
+                  [] { return getRandomInteger<IntT>(); });
+    return Res;
+  }
+};
+
+struct TestInt32 : TestIntBase<std::int32_t> {
+  static constexpr const char* Name = "TestInt32";
+};
+
+struct TestInt64 : TestIntBase<std::int64_t> {
+  static constexpr const char* Name = "TestInt64";
+};
+
+struct TestUint32 : TestIntBase<std::uint32_t> {
+  static constexpr const char* Name = "TestUint32";
+};
+
+struct TestMediumString {
+  static constexpr const char* Name = "TestMediumString";
+  static constexpr size_t StringSize = 32;
+
+  static std::vector<std::string> generateInput(size_t size) {
+    std::vector<std::string> Res(size);
+    std::generate(Res.begin(), Res.end(),
+                  [] { return getRandomString(StringSize); });
+    return Res;
+  }
+};
+
+using AllTestTypes =
+    std::tuple<TestInt32, TestInt64, TestUint32, TestMediumString>;
+
+struct MergeAlg {
+  template <class I1, class I2, class O>
+  O operator()(I1 first1, I1 last1, I2 first2, I2 last2, O out) {
+    return std::merge(first1, last1, first2, last2, out);
+  }
+
+  static constexpr const char* Name = "MergeAlg";
+};
+
+struct SetUnionAlg {
+  template <class I1, class I2, class O>
+  O operator()(I1 first1, I1 last1, I2 first2, I2 last2, O out) {
+    return std::set_union(first1, last1, first2, last2, out);
+  }
+
+  static constexpr const char* Name = "SetUnionAlg";
+};
+
+using AllAlgs = std::tuple<MergeAlg, SetUnionAlg>;
+
+} // namespace
+
+template <class Alg, class TestType>
+struct MergeBench {
+  size_t Quantity;
+
+  std::string name() const {
+    return std::string("MergeBench_") + Alg::Name + "_" + TestType::Name + '/' +
+           std::to_string(Quantity);
+  }
+
+  template <typename VecT>
+  struct BenchmarkPrepared {
+    std::array<VecT, kSplitPointCount> LhsArray;
+    std::array<VecT, kSplitPointCount> RhsArray;
+    VecT output;
+  };
+
+  TEST_NOINLINE auto prepareBenchmark() const {
+    auto Data = TestType::generateInput(Quantity);
+    using VecT = decltype(Data);
+
+    const auto SplitPoints = pickSplitPoints(Data.begin(), Data.end());
+
+    BenchmarkPrepared<VecT> Res;
+
+    VecT* LhsIt = Res.LhsArray.begin();
+    VecT* RhsIt = Res.RhsArray.begin();
+    for (auto Split : SplitPoints) {
+      *LhsIt = VecT{Data.begin(), Split};
+      *RhsIt = VecT{Split, Data.end()};
+      std::sort(LhsIt->begin(), LhsIt->end());
+      std::sort(RhsIt->begin(), RhsIt->end());
+      ++LhsIt;
+      ++RhsIt;
+    }
+
+    Res.output = VecT(Data.size());
+
+    return Res;
+  }
+
+  void run(benchmark::State& state) const {
+    auto [LhsArray, RhsArray, Output] = prepareBenchmark();
+
+    for (auto _ : state) {
+      for (size_t i = 0; i < LhsArray.size(); ++i) {
+        Alg{}(LhsArray[i].begin(), LhsArray[i].end(), RhsArray[i].begin(),
+              RhsArray[i].end(), Output.begin());
+        benchmark::DoNotOptimize(Output);
+      }
+    }
+  }
+};
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+
+  const std::vector<size_t> Quantities = {1 << 9, 1 << 11, 1 << 21};
+  makeCartesianProductBenchmark<MergeBench, AllAlgs, AllTestTypes>(Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}

libcxx/benchmarks/algorithms.partition_point.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
 #include <array>
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <tuple>
 #include <vector>
 
 #include "benchmark/benchmark.h"