Add benchmarks for sorting and heap functions.

[sbenza]

Summary

Benchmarks for std::sort, std::stable_sort, std::make_heap,
std::sort_heap, std::pop_heap and std::push_heap.

The benchmarks are run with integers and strings, and with different
sorted input.

[mclow.lists]

Is there any value in breaking these out into one benchmark per file? I can see this file ever-growing as we add new benchmarks.

[sbenza]

In D53978#1283922, @mclow.lists wrote:

Is there any value in breaking these out into one benchmark per file? I can see this file ever-growing as we add new benchmarks.

No idea. I was just following the pattern of one benchmark .cpp per header. I think <algorithm> would be the only one with the potential bloat.

[EricWF]

In D53978#1283922, @mclow.lists wrote:

Is there any value in breaking these out into one benchmark per file? I can see this file ever-growing as we add new benchmarks.

I don't thin so. If you want to run a single benchmark in a file, you can use --benchmark_filter=<regex> to select it.

Otherwise, this LGTM.

benchmarks/algorithms.bench.cpp

327 ↗

(On Diff #172132)

For stable sort we want to explore more input sizes between 1 and 200. Currently stable sort is adaptive on the input size, switching to insertion sort for inputs smaller than 128. This seems to cause us to perform 2x worse for inputs of 100 elements. Early experiments show we perform better when the switch is around 16 to 32 elements, but we should have some coverage to prove it.

[sbenza]

Changed the sizes to be denser in the lower end.

libcxx/trunk/benchmarks/algorithms.bench.cpp

-#include <unordered_set>
-#include <vector>
+
+#include <algorithm>
 #include <cstdint>
+#include <map>
+#include <random>
+#include <string>
+#include <utility>
+#include <vector>
 
-#include "benchmark/benchmark.h"
+#include "CartesianBenchmarks.hpp"
 #include "GenerateInput.hpp"
+#include "benchmark/benchmark.h"
+#include "test_macros.h"
+
+namespace {
+
+enum class ValueType { Uint32, String };
+struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> {
+  static constexpr const char* Names[] = {"uint32", "string"};
+};
+
+template <class V>
+using Value =
+    std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>;
+
+enum class Order {
+  Random,
+  Ascending,
+  Descending,
+  SingleElement,
+  PipeOrgan,
+  Heap
+};
+struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> {
+  static constexpr const char* Names[] = {"Random",     "Ascending",
+                                          "Descending", "SingleElement",
+                                          "PipeOrgan",  "Heap"};
+};
+
+void fillValues(std::vector<uint32_t>& V, size_t N, Order O) {
+  if (O == Order::SingleElement) {
+    V.resize(N, 0);
+  } else {
+    while (V.size() < N)
+      V.push_back(V.size());
+  }
+}
 
-constexpr std::size_t TestNumInputs = 1024;
+void fillValues(std::vector<std::string>& V, size_t N, Order O) {
 
-template <class GenInputs>
-void BM_Sort(benchmark::State& st, GenInputs gen) {
-    using ValueType = typename decltype(gen(0))::value_type;
-    const auto in = gen(st.range(0));
-    std::vector<ValueType> inputs[5];
-    auto reset_inputs = [&]() {
-        for (auto& C : inputs) {
-            C = in;
-            benchmark::DoNotOptimize(C.data());
-        }
-    };
-    reset_inputs();
-    while (st.KeepRunning()) {
-        for (auto& I : inputs) {
-            std::sort(I.data(), I.data() + I.size());
-            benchmark::DoNotOptimize(I.data());
-        }
-        st.PauseTiming();
-        reset_inputs();
-        benchmark::ClobberMemory();
-        st.ResumeTiming();
-    }
+  if (O == Order::SingleElement) {
+    V.resize(N, getRandomString(1024));
+  } else {
+    while (V.size() < N)
+      V.push_back(getRandomString(1024));
+}
+
+template <class T>
+void sortValues(T& V, Order O) {
+  assert(std::is_sorted(V.begin(), V.end()));
+  switch (O) {
+  case Order::Random: {
+    std::random_device R;
+    std::mt19937 M(R());
+    std::shuffle(V.begin(), V.end(), M);
+    break;
+  }
+  case Order::Ascending:
+    std::sort(V.begin(), V.end());
+    break;
+  case Order::Descending:
+    std::sort(V.begin(), V.end(), std::greater<>());
+    break;
+  case Order::SingleElement:
+    // Nothing to do
+    break;
+  case Order::PipeOrgan:
+    std::sort(V.begin(), V.end());
+    std::reverse(V.begin() + V.size() / 2, V.end());
+    break;
+  case Order::Heap:
+    std::make_heap(V.begin(), V.end());
+    break;
+  }
+}
+
+template <class ValueType>
+std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N,
+                                                               Order O) {
+  // Let's make sure that all random sequences of the same size are the same.
+  // That way we can compare the different algorithms with the same input.
+  static std::map<std::pair<size_t, Order>, std::vector<Value<ValueType> > >
+      Cached;
+
+  auto& Values = Cached[{N, O}];
+  if (Values.empty()) {
+    fillValues(Values, N, O);
+    sortValues(Values, O);
+  const size_t NumCopies = std::max(size_t{1}, 1000 / N);
+  return { NumCopies, Values };
+}
+
+template <class T, class U>
+TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies,
+                                    U& Orig) {
+  state.PauseTiming();
+  for (auto& Copy : Copies)
+    Copy = Orig;
+  state.ResumeTiming();
+}
+
+template <class ValueType, class F>
+void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
+                   bool CountElements, F f) {
+  auto Copies = makeOrderedValues<ValueType>(Quantity, O);
+  const auto Orig = Copies[0];
+
+  const size_t Batch = CountElements ? Copies.size() * Quantity : Copies.size();
+  while (state.KeepRunningBatch(Batch)) {
+    for (auto& Copy : Copies) {
+      f(Copy);
+      benchmark::DoNotOptimize(Copy);
+    }
+    resetCopies(state, Copies, Orig);
+  }
+}
+
+template <class ValueType, class Order>
+struct Sort {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
+      std::sort(Copy.begin(), Copy.end());
+    });
+
+  bool skip() const { return Order() == ::Order::Heap; }
+
+  std::string name() const {
+    return "BM_Sort" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
+
+template <class ValueType, class Order>
+struct StableSort {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
+      std::stable_sort(Copy.begin(), Copy.end());
+    });
+
+  bool skip() const { return Order() == ::Order::Heap; }
+
+  std::string name() const {
+    return "BM_StableSort" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
+
+template <class ValueType, class Order>
+struct MakeHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
+      std::make_heap(Copy.begin(), Copy.end());
+    });
   }
 
-BENCHMARK_CAPTURE(BM_Sort, random_uint32,
-    getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+  std::string name() const {
+    return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
+
+template <class ValueType>
+struct SortHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order::Heap, false,
+        [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); });
+  }
 
-BENCHMARK_CAPTURE(BM_Sort, sorted_ascending_uint32,
-    getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+  std::string name() const {
+    return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity);
+  };
+};
 
-BENCHMARK_CAPTURE(BM_Sort, sorted_descending_uint32,
-    getReverseSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+template <class ValueType, class Order>
+struct MakeThenSortHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
+      std::make_heap(Copy.begin(), Copy.end());
+      std::sort_heap(Copy.begin(), Copy.end());
+    });
+  }
 
-BENCHMARK_CAPTURE(BM_Sort, single_element_uint32,
-    getDuplicateIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+  std::string name() const {
+    return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
 
-BENCHMARK_CAPTURE(BM_Sort, pipe_organ_uint32,
-    getPipeOrganIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+template <class ValueType, class Order>
+struct PushHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
+      for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
+        std::push_heap(Copy.begin(), I + 1);
+      }
+    });
+  }
 
-BENCHMARK_CAPTURE(BM_Sort, random_strings,
-    getRandomStringInputs)->Arg(TestNumInputs);
+  bool skip() const { return Order() == ::Order::Heap; }
 
-BENCHMARK_CAPTURE(BM_Sort, sorted_ascending_strings,
-    getSortedStringInputs)->Arg(TestNumInputs);
+  std::string name() const {
+    return "BM_PushHeap" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
 
-BENCHMARK_CAPTURE(BM_Sort, sorted_descending_strings,
-    getReverseSortedStringInputs)->Arg(TestNumInputs);
+template <class ValueType>
+struct PopHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
+      for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
+        std::pop_heap(B, I);
+      }
+    });
+  }
 
-BENCHMARK_CAPTURE(BM_Sort, single_element_strings,
-    getDuplicateStringInputs)->Arg(TestNumInputs);
+  std::string name() const {
+    return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity);
+  };
+};
 
+} // namespace
 
-BENCHMARK_MAIN();
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+
+  const std::vector<size_t> Quantities = {1 << 0, 1 << 2,  1 << 4,  1 << 6,
+                                          1 << 8, 1 << 10, 1 << 14, 1 << 18};
+  makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities);
+  makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>(
+      Quantities);
+  makeCartesianProductBenchmark<MakeHeap, AllValueTypes, AllOrders>(Quantities);
+  makeCartesianProductBenchmark<SortHeap, AllValueTypes>(Quantities);
+  makeCartesianProductBenchmark<MakeThenSortHeap, AllValueTypes, AllOrders>(
+      Quantities);
+  makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities);
+  makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}