[libc++] Granularize algorithm benchmarks

[Mordante]

In general looks like an improvement, but I have some questions and remarks.

libcxx/benchmarks/CMakeLists.txt

191

nice no more globbing!

213

Can you explain why this is done?

libcxx/benchmarks/algorithms.bench.cpp

1

Can you use common.h instead of Common.h?

62

Please try to do these changes in a separate commit and not while moving code.
If this is the only change, I won't object.

libcxx/benchmarks/algorithms/make_heap.bench.cpp

30

Does an anonymous namespace add value here?

[philnik]

libcxx/benchmarks/CMakeLists.txt

213

Otherwise it would try to compile make_heap.bench.cpp and not algorithms/make_heap.bench.cpp, which it obviously doesn't find.

libcxx/benchmarks/algorithms.bench.cpp

62

Yes, this was the only code change (and the inline added below). It's just to silence a warning. The warnings was there before, but now it's duplicated for every file in benchmark/.

libcxx/benchmarks/algorithms/make_heap.bench.cpp

30

With an anonymous namespace the compiler is much more likely if the function is only used in a single place to inline stuff because it could remove the function then. The cost of inlining an empty functions is -15030, so probably almost no function is emitted when it's in an anonymous namespace and used only once. I don't know if it makes any performance difference in these cases though.

[philnik]

• Address comments

[ldionne]

LGTM with my comment applied.

libcxx/benchmarks/algorithms/common.h

244

I think I'd rather not introduce this macro since the other benchmarks don't use it. IMO the cost of this duplication is not enough to try avoiding it with a macro.

[philnik]

• Remove main macro

libcxx/benchmarks/CMakeLists.txt

set_target_properties(${native_target}
           CXX_EXTENSIONS NO)
   endif()
 endfunction()
 
 
 #==============================================================================
 # Register Benchmark tests
 #==============================================================================
-file(GLOB BENCHMARK_TESTS "*.bench.cpp")
+set(BENCHMARK_TESTS
+    algorithms/make_heap_then_sort_heap.bench.cpp
+    algorithms/make_heap.bench.cpp
+    algorithms/min_max_element.bench.cpp
+    algorithms/pop_heap.bench.cpp
+    algorithms/push_heap.bench.cpp
+    algorithms/sort_heap.bench.cpp
+    algorithms/stable_sort.bench.cpp
+    algorithms.partition_point.bench.cpp
+    allocation.bench.cpp
+    deque.bench.cpp
+    filesystem.bench.cpp
+    function.bench.cpp
+    map.bench.cpp
+    ordered_set.bench.cpp
+    string.bench.cpp
+    stringstream.bench.cpp
+    to_chars.bench.cpp
+    unordered_set_operations.bench.cpp
+    util_smartptr.bench.cpp
+    variant_visit_1.bench.cpp
+    variant_visit_2.bench.cpp
+    variant_visit_3.bench.cpp
+    vector_operations.bench.cpp
+    )
 
-if (NOT LIBCXX_ENABLE_INCOMPLETE_FEATURES)
-  list(FILTER BENCHMARK_TESTS EXCLUDE REGEX "(format_to_n|format_to|format|formatted_size|formatter_float|std_format_spec_string_unicode).bench.cpp")
+if (LIBCXX_ENABLE_INCOMPLETE_FEATURES)
+  set(BENCHMARK_TESTS
+      ${BENCHMARK_TESTS}
+      format_to_n.bench.cpp
+      format_to.bench.cpp
+      format.bench.cpp
+      formatted_size.bench.cpp
+      formatter_float.bench.cpp
+      std_format_spec_string_unicode.bench.cpp)
 endif()
 
 foreach(test_path ${BENCHMARK_TESTS})
   get_filename_component(test_file "${test_path}" NAME)
   string(REPLACE ".bench.cpp" "" test_name "${test_file}")
   if (NOT DEFINED ${test_name}_REPORTED)
     message(STATUS "Adding Benchmark: ${test_file}")
     # Only report the adding of the benchmark once.
     set(${test_name}_REPORTED ON CACHE INTERNAL "")
   endif()
-  add_benchmark_test(${test_name} ${test_file})
+  add_benchmark_test(${test_name} ${test_path})
 endforeach()
 
 if (LIBCXX_INCLUDE_TESTS)
   include(AddLLVM)
 
   if (NOT DEFINED LIBCXX_TEST_DEPS)
     message(FATAL_ERROR "Expected LIBCXX_TEST_DEPS to be defined")
   endif()

libcxx/benchmarks/algorithms/common.h

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LIBCXX_ALGORITHMS_COMMON_H
+#define LIBCXX_ALGORITHMS_COMMON_H
 
 #include <algorithm>
-#include <cstdint>
-#include <map>
-#include <random>
-#include <string>
-#include <utility>
+#include <numeric>
+#include <tuple>
 #include <vector>
 
-#include "CartesianBenchmarks.h"
-#include "GenerateInput.h"
-#include "benchmark/benchmark.h"
-#include "test_macros.h"
-
-namespace {
+#include "../CartesianBenchmarks.h"
+#include "../GenerateInput.h"
 
 enum class ValueType { Uint32, Uint64, Pair, Tuple, String, Float };
 struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 6> {
   static constexpr const char* Names[] = {"uint32", "uint64", "pair<uint32, uint32>", "tuple<uint32, uint64, uint32>",
                                           "string", "float"};
 };
 
 using Types = std::tuple< uint32_t, uint64_t, std::pair<uint32_t, uint32_t>, std::tuple<uint32_t, uint64_t, uint32_t>,

 // "A Killer Adversary for Quicksort", M. D. McIlroy, Software—Practice &
 // ExperienceVolume 29 Issue 4 April 10, 1999 pp 341–344.
 // https://dl.acm.org/doi/10.5555/311868.311871.
 template <class T>
 void fillAdversarialQuickSortInput(T& V, size_t N) {
   assert(N > 0);
   // If an element is equal to gas, it indicates that the value of the element
   // is still to be decided and may change over the course of time.
-  const int gas = N - 1;
+  const unsigned int gas = N - 1;
   V.resize(N);
-  for (int i = 0; i < N; ++i) {
+  for (unsigned int i = 0; i < N; ++i) {
     V[i] = gas;
   }
   // Candidate for the pivot position.
   int candidate = 0;
   int nsolid = 0;
   // Populate all positions in the generated input to gas.
   std::vector<int> ascVals(V.size());
   // Fill up with ascending values from 0 to V.size()-1.  These will act as
while (V.size() < N)
         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) {
+inline void fillValues(std::vector<std::string>& V, size_t N, Order O) {
   if (O == Order::SingleElement) {
     V.resize(N, getRandomString(64));
   } else {
     while (V.size() < N)
       V.push_back(getRandomString(64));
   }
 }
 
for (auto& Copy : Copies) {
       benchmark::DoNotOptimize(Copy);
     }
     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(), 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(), 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(), 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, 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(), 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(), 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(), 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);
-  };
-};
-
-template <class ValueType, class Order>
-struct MinMaxElement {
-  size_t Quantity;
-
-  void run(benchmark::State& state) const {
-    runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
-      benchmark::DoNotOptimize(std::minmax_element(Copy.begin(), Copy.end()));
-    });
-  }
-
-  std::string name() const {
-    return "BM_MinMaxElement" + ValueType::name() + Order::name() + "_" + std::to_string(Quantity);
-  }
-};
-
-} // namespace
-
-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,
     // Running each benchmark in parallel consumes too much memory with MSAN
     // and can lead to the test process being killed.
 #if !TEST_HAS_FEATURE(memory_sanitizer)
-                                          1 << 18
 #endif
-  };
-  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);
-  makeCartesianProductBenchmark<MinMaxElement, AllValueTypes, AllOrders>(Quantities);
-  benchmark::RunSpecifiedBenchmarks();
+
+#define LIBCPP_ALGORITHMS_BENCHMARK_MAIN(...)                                                                          \
+  int main(int argc, char** argv) {                                                                                    \
+    benchmark::Initialize(&argc, argv);                                                                                \
+    if (benchmark::ReportUnrecognizedArguments(argc, argv))                                                            \
+      return 1;                                                                                                        \
+                                                                                                                       \
+    makeCartesianProductBenchmark<__VA_ARGS__>(Quantities);                                                            \
+    benchmark::RunSpecifiedBenchmarks();                                                                               \
   }
+
+#endif // LIBCXX_ALGORITHMS_COMMON_H

libcxx/benchmarks/algorithms/make_heap.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 "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct MakeHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    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);
+  };
+};
+} // namespace
+
+
+LIBCPP_ALGORITHMS_BENCHMARK_MAIN(MakeHeap, AllValueTypes, AllOrders)

libcxx/benchmarks/algorithms/make_heap_then_sort_heap.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 "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct MakeThenSortHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    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);
+  };
+};
+} // namespace
+
+
+LIBCPP_ALGORITHMS_BENCHMARK_MAIN(MakeThenSortHeap, AllValueTypes, AllOrders)

libcxx/benchmarks/algorithms/min_max_element.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 "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct MinMaxElement {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
+      benchmark::DoNotOptimize(std::minmax_element(Copy.begin(), Copy.end()));
+    });
+  }
+
+  std::string name() const {
+    return "BM_MinMaxElement" + ValueType::name() + Order::name() + "_" + std::to_string(Quantity);
+  }
+};
+} // namespace
+
+
+LIBCPP_ALGORITHMS_BENCHMARK_MAIN(MinMaxElement, AllValueTypes, AllOrders)

libcxx/benchmarks/algorithms/pop_heap.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 "common.h"
+
+namespace {
+template <class ValueType>
+struct PopHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    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
+
+
+LIBCPP_ALGORITHMS_BENCHMARK_MAIN(PopHeap, AllValueTypes)

libcxx/benchmarks/algorithms/push_heap.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 "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct PushHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    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);
+  };
+};
+} // namespace
+
+
+LIBCPP_ALGORITHMS_BENCHMARK_MAIN(PushHeap, AllValueTypes, AllOrders)

libcxx/benchmarks/algorithms/sort.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 "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct Sort {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    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);
+  };
+};
+} // namespace
+
+LIBCPP_ALGORITHMS_BENCHMARK_MAIN(Sort, AllValueTypes, AllOrders)

libcxx/benchmarks/algorithms/sort_heap.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 "common.h"
+
+namespace {
+template <class ValueType>
+struct SortHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(
+        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);
+  };
+};
+} // namespace
+
+
+LIBCPP_ALGORITHMS_BENCHMARK_MAIN(SortHeap, AllValueTypes)

libcxx/benchmarks/algorithms/stable_sort.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 "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct StableSort {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    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);
+  };
+};
+} // namespace
+
+
+LIBCPP_ALGORITHMS_BENCHMARK_MAIN(StableSort, AllValueTypes, AllOrders)