Modifications to the algorithm sort benchmark

[minjaehwang]

Summary

Modifies the algorithm sort bench:

• shows sorting time per element, instead of sorting time per array.

This would make comparison between different sizes of arrays easier.

• adds std::pair benchmark cases.
• uses a large number of arrays to benchmark, instead of repeatedly sorting the same array.
• sorting the same array again and again would not show actual sorting performance over randomized data sets.

[EricWF]

LGTM

libcxx/benchmarks/algorithms.bench.cpp

228–229

Could you make this boolean value an enum, so it's clear what it means?

[minjaehwang]

Reflects EricWF's comment. Change a bool variable to an enum.

[minjaehwang]

Fix clang-tidy warnings.

[minjaehwang]

clang-tidy complains that "benchmark/benchmark.h" is not found at CartesianBehcmarks.h. This diff does not modify that file and this is a benign error. It compiles without a problem.

Could anyone land this diff into the master?

[mvels]

In D81770#2102480, @minjaehwang wrote:

clang-tidy complains that "benchmark/benchmark.h" is not found at CartesianBehcmarks.h. This diff does not modify that file and this is a benign error. It compiles without a problem.

Could anyone land this diff into the master?

I'll take a stab at committing this diff

[mvels]

libcxx/benchmarks/algorithms.bench.cpp

181

s/bencvhmark/benchmark/

[minjaehwang]

Fix the typo

[minjaehwang]

Resolved your comments!

libcxx/benchmarks/algorithms.bench.cpp

 
 #include <algorithm>
 #include <cstdint>
 #include <map>
 #include <random>
 #include <string>
 #include <utility>
 #include <vector>
 
 #include "CartesianBenchmarks.h"
 #include "GenerateInput.h"
 #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"};
+enum class ValueType { Uint32, Uint64, Pair, Tuple, String };
+struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 5> {
+  static constexpr const char* Names[] = {
+      "uint32", "uint64", "pair<uint32, uint32>",
+      "tuple<uint32, uint64, uint32>", "string"};
 };
 
 template <class V>
-using Value =
-    std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>;
+using Value = std::conditional_t<
+    V() == ValueType::Uint32, uint32_t,
+    std::conditional_t<
+        V() == ValueType::Uint64, uint64_t,
+        std::conditional_t<
+            V() == ValueType::Pair, std::pair<uint32_t, uint32_t>,
+            std::conditional_t<V() == ValueType::Tuple,
+                               std::tuple<uint32_t, uint64_t, 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) {
+template <typename T>
+void fillValues(std::vector<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());
   }
 }
 
-void fillValues(std::vector<std::string>& V, size_t N, Order O) {
+template <typename T>
+void fillValues(std::vector<std::pair<T, T> >& V, size_t N, Order O) {
+  if (O == Order::SingleElement) {
+    V.resize(N, std::make_pair(0, 0));
+  } else {
+    while (V.size() < N)
+      // Half of array will have the same first element.
+      if (V.size() % 2) {
+        V.push_back(std::make_pair(V.size(), V.size()));
+      } else {
+        V.push_back(std::make_pair(0, V.size()));
+      }
+  }
+}
 
+template <typename T1, typename T2, typename T3>
+void fillValues(std::vector<std::tuple<T1, T2, T3> >& V, size_t N, Order O) {
+  if (O == Order::SingleElement) {
+    V.resize(N, std::make_tuple(0, 0, 0));
+  } else {
+    while (V.size() < N)
+      // One third of array will have the same first element.
+      // One third of array will have the same first element and the same second element.
+      switch (V.size() % 3) {
+      case 0:
+        V.push_back(std::make_tuple(V.size(), V.size(), V.size()));
+        break;
+      case 1:
+        V.push_back(std::make_tuple(0, V.size(), V.size()));
+        break;
+      case 2:
+        V.push_back(std::make_tuple(0, 0, V.size()));
+        break;
+      }
+  }
+}
+
+void fillValues(std::vector<std::string>& V, size_t N, Order O) {
   if (O == Order::SingleElement) {
-    V.resize(N, getRandomString(1024));
+    V.resize(N, getRandomString(64));
   } else {
     while (V.size() < N)
-      V.push_back(getRandomString(1024));
+      V.push_back(getRandomString(64));
   }
 }
 
 template <class T>
 void sortValues(T& V, Order O) {
   assert(std::is_sorted(V.begin(), V.end()));
   switch (O) {
   case Order::Random: {
case Order::PipeOrgan:
     std::reverse(V.begin() + V.size() / 2, V.end());
     break;
   case Order::Heap:
     std::make_heap(V.begin(), V.end());
     break;
   }
 }
 
+constexpr size_t TestSetElements =
+#if !TEST_HAS_FEATURE(memory_sanitizer)
+    1 << 18;
+#else
+    1 << 14;
+#endif
+
 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 };
+  std::vector<std::vector<Value<ValueType> > > Ret;
+  const size_t NumCopies = std::max(size_t{1}, TestSetElements / N);
+  Ret.resize(NumCopies);
+  for (auto& V : Ret) {
+    fillValues(V, N, O);
+    sortValues(V, O);
+  }
+  return Ret;
 }
 
 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();
 }
 
+enum class BatchSize {
+  CountElements,
+  CountBatch,
+};
+
 template <class ValueType, class F>
 void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
-                   bool CountElements, F f) {
+                   BatchSize count, F f) {
   auto Copies = makeOrderedValues<ValueType>(Quantity, O);
-  const auto Orig = Copies[0];
+  auto Orig = Copies;
 
-  const size_t Batch = CountElements ? Copies.size() * Quantity : Copies.size();
+  const size_t Batch = count == BatchSize::CountElements
+                           ? Copies.size() * Quantity
+                           : Copies.size();
   while (state.KeepRunningBatch(Batch)) {
     for (auto& Copy : Copies) {
       f(Copy);
       benchmark::DoNotOptimize(Copy);
     }
-    resetCopies(state, Copies, Orig);
+    state.PauseTiming();
+    Copies = Orig;
+    state.ResumeTiming();
   }
 }
 
 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());
-    });
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements,
+        [](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());
-    });
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements,
+        [](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());
-    });
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements,
+        [](auto& Copy) { std::make_heap(Copy.begin(), Copy.end()); });
   }
 
   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,
+        state, Quantity, Order::Heap, BatchSize::CountElements,
         [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); });
   }
 
   std::string name() const {
     return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity);
   };
 };
 
 template <class ValueType, class Order>
 struct MakeThenSortHeap {
   size_t Quantity;
 
   void run(benchmark::State& state) const {
-    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements,
+                             [](auto& Copy) {
                                std::make_heap(Copy.begin(), Copy.end());
                                std::sort_heap(Copy.begin(), Copy.end());
                              });
   }
 
   std::string name() const {
     return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" +
            std::to_string(Quantity);
   };
 };
 
 template <class ValueType, class Order>
 struct PushHeap {
   size_t Quantity;
 
   void run(benchmark::State& state) const {
-    runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
           for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
             std::push_heap(Copy.begin(), I + 1);
           }
         });
   }
 
   bool skip() const { return Order() == ::Order::Heap; }
 
   std::string name() const {
     return "BM_PushHeap" + ValueType::name() + Order::name() + "_" +
            std::to_string(Quantity);
   };
 };
 
 template <class ValueType>
 struct PopHeap {
   size_t Quantity;
 
   void run(benchmark::State& state) const {
-    runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
           for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
             std::pop_heap(B, I);
           }
         });
   }
 
   std::string name() const {
     return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity);
   };
 };
 
 } // namespace
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();
-}
+}
 No newline at end of file