Add benchmark for std::set.

[sbenza]

Summary

Benchmarks for construct, find, insert and iterate, with sequential
and random ordered inputs.

It also improves the cartesian product benchmark header to allow for
runtime values to be specified in the product.

[dyaroshev]

Hi!

FYI, this patch fails to compile on my machine:

Required change:

void run(benchmark::State& State) const {
  std::vector<size_t> Keys(TableSize);

void run(benchmark::State& State) const {
  std::vector<uint64_t> Keys(TableSize);

I'll add to the pr I'm working on now.

/space/llvm/llvm/projects/libcxx/benchmarks/CartesianBenchmarks.hpp:46:69: note: in instantiation of member function '(anonymous

namespace)::Create<internal::EnumValue<(anonymous namespace)::AllAccessPattern, (anonymous namespace)::AccessPattern, 1> >::run' requested
here
                             [=](benchmark::State& S) { Bench.run(S); });
                                                              ^

/space/llvm/llvm/projects/libcxx/benchmarks/CartesianBenchmarks.hpp:53:3: note: in instantiation of function template specialization

    'internal::makeBenchmarkFromValuesImpl<(anonymous namespace)::Create<internal::EnumValue<(anonymous namespace)::AllAccessPattern,
    (anonymous namespace)::AccessPattern, 1> >, std::__1::vector<std::__1::tuple<unsigned long, unsigned long>,
    std::__1::allocator<std::__1::tuple<unsigned long, unsigned long> > >, 0, 1>' requested here
makeBenchmarkFromValuesImpl<B>(A, std::index_sequence_for<Args...>());
^

/space/llvm/llvm/projects/libcxx/benchmarks/CartesianBenchmarks.hpp:58:3: note: in instantiation of function template specialization

    'internal::makeBenchmarkFromValues<(anonymous namespace)::Create<internal::EnumValue<(anonymous namespace)::AllAccessPattern,
    (anonymous namespace)::AccessPattern, 1> >, unsigned long, unsigned long>' requested here
makeBenchmarkFromValues<B<U...> >(A);
^

/space/llvm/llvm/projects/libcxx/benchmarks/CartesianBenchmarks.hpp:65:14: note: in instantiation of function template specialization

    'internal::makeBenchmarkImpl<Create, std::__1::vector<std::__1::tuple<unsigned long, unsigned long>,
    std::__1::allocator<std::__1::tuple<unsigned long, unsigned long> > >, internal::EnumValue<(anonymous namespace)::AllAccessPattern,
    (anonymous namespace)::AccessPattern, 1> >' requested here
(internal::makeBenchmarkImpl<B>(A, std::tuple<U..., T>(), rest...), ...);
           ^

/space/llvm/llvm/projects/libcxx/benchmarks/CartesianBenchmarks.hpp:115:13: note: in instantiation of function template specialization

    'internal::makeBenchmarkImpl<Create, std::__1::vector<std::__1::tuple<unsigned long, unsigned long>,
    std::__1::allocator<std::__1::tuple<unsigned long, unsigned long> > >, internal::EnumValue<(anonymous namespace)::AllAccessPattern,
    (anonymous namespace)::AccessPattern, 0>, internal::EnumValue<(anonymous namespace)::AllAccessPattern, (anonymous namespace)::AccessPattern,
    1> >' requested here
internal::makeBenchmarkImpl<B>(V, std::tuple<>(), Tuples()...);
          ^

/space/llvm/llvm/projects/libcxx/benchmarks/ordered_set.bench.cpp:237:3: note: in instantiation of function template specialization

    'makeCartesianProductBenchmark<Create, (anonymous namespace)::AllAccessPattern, std::__1::vector<unsigned long, std::__1::allocator<unsigned
    long> >, std::__1::vector<unsigned long, std::__1::allocator<unsigned long> > >' requested here
makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables);
^

/space/llvm/llvm/projects/libcxx/benchmarks/ordered_set.bench.cpp:37:6: note: candidate function not viable: no known conversion from

'std::vector<size_t>' (aka 'vector<unsigned long>') to 'std::vector<uint64_t> &' (aka 'vector<unsigned long long> &') for 1st argument

void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) {

^

/space/llvm/llvm/projects/libcxx/benchmarks/ordered_set.bench.cpp:88:5: error: no matching function for call to 'sortKeysBy'

sortKeysBy(Keys, Access());
^~~~~~~~~~

/space/llvm/llvm/projects/libcxx/benchmarks/CartesianBenchmarks.hpp:46:69: note: in instantiation of member function '(anonymous

namespace)::Create<internal::EnumValue<(anonymous namespace)::AllAccessPattern, (anonymous namespace)::AccessPattern, 0> >::run' requested
here
                             [=](benchmark::State& S) { Bench.run(S); });
                                                              ^

/space/llvm/llvm/projects/libcxx/benchmarks/CartesianBenchmarks.hpp:53:3: note: in instantiation of function template specialization

    'internal::makeBenchmarkFromValuesImpl<(anonymous namespace)::Create<internal::EnumValue<(anonymous namespace)::AllAccessPattern,
    (anonymous namespace)::AccessPattern, 0> >, std::__1::vector<std::__1::tuple<unsigned long, unsigned long>,
    std::__1::allocator<std::__1::tuple<unsigned long, unsigned long> > >, 0, 1>' requested here
makeBenchmarkFromValuesImpl<B>(A, std::index_sequence_for<Args...>());
^

/space/llvm/llvm/projects/libcxx/benchmarks/CartesianBenchmarks.hpp:58:3: note: in instantiation of function template specialization

    'internal::makeBenchmarkFromValues<(anonymous namespace)::Create<internal::EnumValue<(anonymous namespace)::AllAccessPattern,
    (anonymous namespace)::AccessPattern, 0> >, unsigned long, unsigned long>' requested here
makeBenchmarkFromValues<B<U...> >(A);
^

/space/llvm/llvm/projects/libcxx/benchmarks/CartesianBenchmarks.hpp:65:14: note: in instantiation of function template specialization

    'internal::makeBenchmarkImpl<Create, std::__1::vector<std::__1::tuple<unsigned long, unsigned long>,
    std::__1::allocator<std::__1::tuple<unsigned long, unsigned long> > >, internal::EnumValue<(anonymous namespace)::AllAccessPattern,
    (anonymous namespace)::AccessPattern, 0> >' requested here
(internal::makeBenchmarkImpl<B>(A, std::tuple<U..., T>(), rest...), ...);
           ^

/space/llvm/llvm/projects/libcxx/benchmarks/CartesianBenchmarks.hpp:115:13: note: in instantiation of function template specialization

    'internal::makeBenchmarkImpl<Create, std::__1::vector<std::__1::tuple<unsigned long, unsigned long>,
    std::__1::allocator<std::__1::tuple<unsigned long, unsigned long> > >, internal::EnumValue<(anonymous namespace)::AllAccessPattern,
    (anonymous namespace)::AccessPattern, 0>, internal::EnumValue<(anonymous namespace)::AllAccessPattern, (anonymous namespace)::AccessPattern,
    1> >' requested here
internal::makeBenchmarkImpl<B>(V, std::tuple<>(), Tuples()...);
          ^

/space/llvm/llvm/projects/libcxx/benchmarks/ordered_set.bench.cpp:237:3: note: in instantiation of function template specialization

    'makeCartesianProductBenchmark<Create, (anonymous namespace)::AllAccessPattern, std::__1::vector<unsigned long, std::__1::allocator<unsigned
    long> >, std::__1::vector<unsigned long, std::__1::allocator<unsigned long> > >' requested here
makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables);
^

/space/llvm/llvm/projects/libcxx/benchmarks/ordered_set.bench.cpp:37:6: note: candidate function not viable: no known conversion from

'std::vector<size_t>' (aka 'vector<unsigned long>') to 'std::vector<uint64_t> &' (aka 'vector<unsigned long long> &') for 1st argument

void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) {

^

2 warnings and 2 errors generated.
make[3]: * [projects/libcxx/benchmarks/CMakeFiles/ordered_set_libcxx.dir/ordered_set.bench.cpp.o] Error 1
make[2]: * [projects/libcxx/benchmarks/CMakeFiles/ordered_set_libcxx.dir/all] Error 2
make[1]: * [projects/libcxx/benchmarks/CMakeFiles/cxx-benchmarks.dir/rule] Error 2
make: * [cxx-benchmarks] Error 2

[sbenza]

Sorry for the break.
I submitted the fix.

benchmarks/CartesianBenchmarks.hpp

 //===----------------------------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is dual licensed under the MIT and the University of Illinois Open
 // Source Licenses. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 
 #include <string>
 #include <tuple>
 #include <type_traits>
+#include <vector>
 
 #include "benchmark/benchmark.h"
 #include "test_macros.h"
 
 namespace internal {
 
 template <class D, class E, size_t I>
 struct EnumValue : std::integral_constant<E, static_cast<E>(I)> {
   static std::string name() { return std::string("_") + D::Names[I]; }
 };
 
 template <class D, class E, size_t ...Idxs>
 constexpr auto makeEnumValueTuple(std::index_sequence<Idxs...>) {
   return std::make_tuple(EnumValue<D, E, Idxs>{}...);
 }
 
-template <class T>
-static auto skip(int) -> decltype(T::skip()) {
-  return T::skip();
+template <class B>
+static auto skip(const B& Bench, int) -> decltype(Bench.skip()) {
+  return Bench.skip();
 }
-template <class T>
-static bool skip(char) {
+template <class B>
+static auto skip(const B& Bench, char) {
   return false;
 }
 
-template <template <class...> class B, class... U>
-void makeBenchmarkImpl(std::tuple<U...> t) {
-  using T = B<U...>;
-  if (!internal::skip<T>(0))
-    benchmark::RegisterBenchmark(T::name().c_str(), T::run);
+template <class B, class Args, size_t... Is>
+void makeBenchmarkFromValuesImpl(const Args& A, std::index_sequence<Is...>) {
+  for (auto& V : A) {
+    B Bench{std::get<Is>(V)...};
+    if (!internal::skip(Bench, 0)) {
+      benchmark::RegisterBenchmark(Bench.name().c_str(),
+                                   [=](benchmark::State& S) { Bench.run(S); });
+    }
+  }
+}
+
+template <class B, class... Args>
+void makeBenchmarkFromValues(const std::vector<std::tuple<Args...> >& A) {
+  makeBenchmarkFromValuesImpl<B>(A, std::index_sequence_for<Args...>());
+}
+
+template <template <class...> class B, class Args, class... U>
+void makeBenchmarkImpl(const Args& A, std::tuple<U...> t) {
+  makeBenchmarkFromValues<B<U...> >(A);
 }
 
-template <template <class...> class B, class... U, class... T, class... Tuples>
-void makeBenchmarkImpl(std::tuple<U...>, std::tuple<T...>, Tuples... rest) {
-  (internal::makeBenchmarkImpl<B>(std::tuple<U..., T>(), rest...), ...);
+template <template <class...> class B, class Args, class... U,
+          class... T, class... Tuples>
+void makeBenchmarkImpl(const Args& A, std::tuple<U...>, std::tuple<T...>,
+                       Tuples... rest) {
+  (internal::makeBenchmarkImpl<B>(A, std::tuple<U..., T>(), rest...), ...);
+}
+
+template <class R, class T>
+void allValueCombinations(R& Result, const T& Final) {
+  return Result.push_back(Final);
+}
+
+template <class R, class T, class V, class... Vs>
+void allValueCombinations(R& Result, const T& Prev, const V& Value,
+                          const Vs&... Values) {
+  for (const auto& E : Value) {
+    allValueCombinations(Result, std::tuple_cat(Prev, std::make_tuple(E)),
+                         Values...);
+  }
 }
 
 }  // namespace internal
 
 // CRTP class that enables using enum types as a dimension for
 // makeCartesianProductBenchmark below.
 // The type passed to `B` will be a std::integral_constant<E, e>, with the
 // additional static function `name()` that returns the stringified name of the
 // label.
 //
 // Eg:
 // enum class MyEnum { A, B };
 // struct AllMyEnum : EnumValuesAsTuple<AllMyEnum, MyEnum, 2> {
 //   static constexpr absl::string_view Names[] = {"A", "B"};
 // };
 template <class Derived, class EnumType, size_t NumLabels>
 using EnumValuesAsTuple =
     decltype(internal::makeEnumValueTuple<Derived, EnumType>(
         std::make_index_sequence<NumLabels>{}));
 
 // Instantiates B<T0, T1, ..., TN> where <Ti...> are the combinations in the
-// cartesian product of `Tuples...`
+// cartesian product of `Tuples...`, and pass (arg0, ..., argN) as constructor
+// arguments where `(argi...)` are the combination in the cartesian product of
+// the runtime values of `A...`.
 // B<T...> requires:
-//  - static std::string name(): The name of the benchmark.
-//  - static void run(benchmark::State&): The body of the benchmark.
+//  - std::string name(args...): The name of the benchmark.
+//  - void run(benchmark::State&, args...): The body of the benchmark.
 // It can also optionally provide:
-//  - static bool skip(): When `true`, skips the combination. Default is false.
+//  - bool skip(args...): When `true`, skips the combination. Default is false.
 //
 // Returns int to facilitate registration. The return value is unspecified.
-template <template <class...> class B, class... Tuples>
-int makeCartesianProductBenchmark() {
-  internal::makeBenchmarkImpl<B>(std::tuple<>(), Tuples()...);
+template <template <class...> class B, class... Tuples, class... Args>
+int makeCartesianProductBenchmark(const Args&... A) {
+  std::vector<std::tuple<typename Args::value_type...> > V;
+  internal::allValueCombinations(V, std::tuple<>(), A...);
+  internal::makeBenchmarkImpl<B>(V, std::tuple<>(), Tuples()...);
+  return 0;
+}
+
+template <class B, class... Args>
+int makeCartesianProductBenchmark(const Args&... A) {
+  std::vector<std::tuple<typename Args::value_type...> > V;
+  internal::allValueCombinations(V, std::tuple<>(), A...);
+  internal::makeBenchmarkFromValues<B>(V);
   return 0;
 }
 
 // When `opaque` is true, this function hides the runtime state of `value` from
 // the optimizer.
 // It returns `value`.
 template <class T>
 TEST_ALWAYS_INLINE inline T maybeOpaque(T value, bool opaque) {
   if (opaque) benchmark::DoNotOptimize(value);
   return value;
 }
 

benchmarks/ordered_set.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+#include <cstdint>
+#include <memory>
+#include <random>
+#include <set>
+#include <string>
+#include <vector>
+
+#include "CartesianBenchmarks.hpp"
+#include "benchmark/benchmark.h"
+#include "test_macros.h"
+
+namespace {
+
+enum class HitType { Hit, Miss };
+
+struct AllHitTypes : EnumValuesAsTuple<AllHitTypes, HitType, 2> {
+  static constexpr const char* Names[] = {"Hit", "Miss"};
+};
+
+enum class AccessPattern { Ordered, Random };
+
+struct AllAccessPattern
+    : EnumValuesAsTuple<AllAccessPattern, AccessPattern, 2> {
+  static constexpr const char* Names[] = {"Ordered", "Random"};
+};
+
+void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) {
+  if (AP == AccessPattern::Random) {
+    std::random_device R;
+    std::mt19937 M(R());
+    std::shuffle(std::begin(Keys), std::end(Keys), M);
+  }
+}
+
+struct TestSets {
+  std::vector<std::set<uint64_t> > Sets;
+  std::vector<uint64_t> Keys;
+};
+
+TestSets makeTestingSets(size_t TableSize, size_t NumTables, HitType Hit,
+                         AccessPattern Access) {
+  TestSets R;
+  R.Sets.resize(1);
+
+  for (uint64_t I = 0; I < TableSize; ++I) {
+    R.Sets[0].insert(2 * I);
+    R.Keys.push_back(Hit == HitType::Hit ? 2 * I : 2 * I + 1);
+  }
+  R.Sets.resize(NumTables, R.Sets[0]);
+  sortKeysBy(R.Keys, Access);
+
+  return R;
+}
+
+struct Base {
+  size_t TableSize;
+  size_t NumTables;
+  Base(size_t T, size_t N) : TableSize(T), NumTables(N) {}
+
+  bool skip() const {
+    size_t Total = TableSize * NumTables;
+    return Total < 100 || Total > 1000000;
+  }
+
+  std::string baseName() const {
+    return "_TableSize" + std::to_string(TableSize) + "_NumTables" +
+           std::to_string(NumTables);
+  }
+};
+
+template <class Access>
+struct Create : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    std::vector<size_t> Keys(TableSize);
+    std::iota(Keys.begin(), Keys.end(), size_t{0});
+    sortKeysBy(Keys, Access());
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      std::vector<std::set<size_t>> Sets(NumTables);
+      for (auto K : Keys) {
+        for (auto& Set : Sets) {
+          benchmark::DoNotOptimize(Set.insert(K));
+        }
+      }
+    }
+  }
+
+  std::string name() const {
+    return "BM_Create" + Access::name() + baseName();
+  }
+};
+
+template <class Hit, class Access>
+struct Find : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto K : Data.Keys) {
+        for (auto& Set : Data.Sets) {
+          benchmark::DoNotOptimize(Set.find(K));
+        }
+      }
+    }
+  }
+
+  std::string name() const {
+    return "BM_Find" + Hit::name() + Access::name() + baseName();
+  }
+};
+
+template <class Hit, class Access>
+struct FindNeEnd : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto K : Data.Keys) {
+        for (auto& Set : Data.Sets) {
+          benchmark::DoNotOptimize(Set.find(K) != Set.end());
+        }
+      }
+    }
+  }
+
+  std::string name() const {
+    return "BM_FindNeEnd" + Hit::name() + Access::name() + baseName();
+  }
+};
+
+template <class Access>
+struct InsertHit : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, HitType::Hit, Access());
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto K : Data.Keys) {
+        for (auto& Set : Data.Sets) {
+          benchmark::DoNotOptimize(Set.insert(K));
+        }
+      }
+    }
+  }
+
+  std::string name() const {
+    return "BM_InsertHit" + Access::name() + baseName();
+  }
+};
+
+template <class Access>
+struct InsertMissAndErase : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, Access());
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto K : Data.Keys) {
+        for (auto& Set : Data.Sets) {
+          benchmark::DoNotOptimize(Set.erase(Set.insert(K).first));
+        }
+      }
+    }
+  }
+
+  std::string name() const {
+    return "BM_InsertMissAndErase" + Access::name() + baseName();
+  }
+};
+
+struct IterateRangeFor : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss,
+                                AccessPattern::Ordered);
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto& Set : Data.Sets) {
+        for (auto& V : Set) {
+          benchmark::DoNotOptimize(V);
+        }
+      }
+    }
+  }
+
+  std::string name() const { return "BM_IterateRangeFor" + baseName(); }
+};
+
+struct IterateBeginEnd : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss,
+                                AccessPattern::Ordered);
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto& Set : Data.Sets) {
+        for (auto it = Set.begin(); it != Set.end(); ++it) {
+          benchmark::DoNotOptimize(*it);
+        }
+      }
+    }
+  }
+
+  std::string name() const { return "BM_IterateBeginEnd" + baseName(); }
+};
+
+}  // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+
+  const std::vector<size_t> TableSize{1, 10, 100, 1000, 10000, 100000, 1000000};
+  const std::vector<size_t> NumTables{1, 10, 100, 1000, 10000, 100000, 1000000};
+
+  makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables);
+  makeCartesianProductBenchmark<Find, AllHitTypes, AllAccessPattern>(
+      TableSize, NumTables);
+  makeCartesianProductBenchmark<FindNeEnd, AllHitTypes, AllAccessPattern>(
+      TableSize, NumTables);
+  makeCartesianProductBenchmark<InsertHit, AllAccessPattern>(
+      TableSize, NumTables);
+  makeCartesianProductBenchmark<InsertMissAndErase, AllAccessPattern>(
+      TableSize, NumTables);
+  makeCartesianProductBenchmark<IterateRangeFor>(TableSize, NumTables);
+  makeCartesianProductBenchmark<IterateBeginEnd>(TableSize, NumTables);
+  benchmark::RunSpecifiedBenchmarks();
+}