libcxx/benchmarks/ordered_set.bench.cpp

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include <algorithm>
  10 #include <cstdint>
  11 #include <memory>
  12 #include <random>
  13 #include <set>
  14 #include <string>
  15 #include <vector>
  16
  17 #include "CartesianBenchmarks.h"
  18 #include "benchmark/benchmark.h"
  19 #include "test_macros.h"
  20
  21 namespace {
  22
  23 enum class HitType { Hit, Miss };
  24
  25 struct AllHitTypes : EnumValuesAsTuple<AllHitTypes, HitType, 2> {
  26   static constexpr const char* Names[] = {"Hit", "Miss"};
  27 };
  28
  29 enum class AccessPattern { Ordered, Random };
  30
  31 struct AllAccessPattern : EnumValuesAsTuple<AllAccessPattern, AccessPattern, 2> {
  32   static constexpr const char* Names[] = {"Ordered", "Random"};
  33 };
  34
  35 void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) {
  36   if (AP == AccessPattern::Random) {
  37     std::random_device R;
  38     std::mt19937 M(R());
  39     std::shuffle(std::begin(Keys), std::end(Keys), M);
  40   }
  41 }
  42
  43 struct TestSets {
  44   std::vector<std::set<uint64_t> > Sets;
  45   std::vector<uint64_t> Keys;
  46 };
  47
  48 TestSets makeTestingSets(size_t TableSize, size_t NumTables, HitType Hit, AccessPattern Access) {
  49   TestSets R;
  50   R.Sets.resize(1);
  51
  52   for (uint64_t I = 0; I < TableSize; ++I) {
  53     R.Sets[0].insert(2 * I);
  54     R.Keys.push_back(Hit == HitType::Hit ? 2 * I : 2 * I + 1);
  55   }
  56   R.Sets.resize(NumTables, R.Sets[0]);
  57   sortKeysBy(R.Keys, Access);
  58
  59   return R;
  60 }
  61
  62 struct Base {
  63   size_t TableSize;
  64   size_t NumTables;
  65   Base(size_t T, size_t N) : TableSize(T), NumTables(N) {}
  66
  67   bool skip() const {
  68     size_t Total = TableSize * NumTables;
  69     return Total < 100 || Total > 1000000;
  70   }
  71
  72   std::string baseName() const {
  73     return "_TableSize" + std::to_string(TableSize) + "_NumTables" + std::to_string(NumTables);
  74   }
  75 };
  76
  77 template <class Access>
  78 struct Create : Base {
  79   using Base::Base;
  80
  81   void run(benchmark::State& State) const {
  82     std::vector<uint64_t> Keys(TableSize);
  83     std::iota(Keys.begin(), Keys.end(), uint64_t{0});
  84     sortKeysBy(Keys, Access());
  85
  86     while (State.KeepRunningBatch(TableSize * NumTables)) {
  87       std::vector<std::set<uint64_t>> Sets(NumTables);
  88       for (auto K : Keys) {
  89         for (auto& Set : Sets) {
  90           benchmark::DoNotOptimize(Set.insert(K));
  91         }
  92       }
  93     }
  94   }
  95
  96   std::string name() const { return "BM_Create" + Access::name() + baseName(); }
  97 };
  98
  99 template <class Hit, class Access>
 100 struct Find : Base {
 101   using Base::Base;
 102
 103   void run(benchmark::State& State) const {
 104     auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
 105
 106     while (State.KeepRunningBatch(TableSize * NumTables)) {
 107       for (auto K : Data.Keys) {
 108         for (auto& Set : Data.Sets) {
 109           benchmark::DoNotOptimize(Set.find(K));
 110         }
 111       }
 112     }
 113   }
 114
 115   std::string name() const { return "BM_Find" + Hit::name() + Access::name() + baseName(); }
 116 };
 117
 118 template <class Hit, class Access>
 119 struct FindNeEnd : Base {
 120   using Base::Base;
 121
 122   void run(benchmark::State& State) const {
 123     auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
 124
 125     while (State.KeepRunningBatch(TableSize * NumTables)) {
 126       for (auto K : Data.Keys) {
 127         for (auto& Set : Data.Sets) {
 128           benchmark::DoNotOptimize(Set.find(K) != Set.end());
 129         }
 130       }
 131     }
 132   }
 133
 134   std::string name() const { return "BM_FindNeEnd" + Hit::name() + Access::name() + baseName(); }
 135 };
 136
 137 template <class Access>
 138 struct InsertHit : Base {
 139   using Base::Base;
 140
 141   void run(benchmark::State& State) const {
 142     auto Data = makeTestingSets(TableSize, NumTables, HitType::Hit, Access());
 143
 144     while (State.KeepRunningBatch(TableSize * NumTables)) {
 145       for (auto K : Data.Keys) {
 146         for (auto& Set : Data.Sets) {
 147           benchmark::DoNotOptimize(Set.insert(K));
 148         }
 149       }
 150     }
 151   }
 152
 153   std::string name() const { return "BM_InsertHit" + Access::name() + baseName(); }
 154 };
 155
 156 template <class Access>
 157 struct InsertMissAndErase : Base {
 158   using Base::Base;
 159
 160   void run(benchmark::State& State) const {
 161     auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, Access());
 162
 163     while (State.KeepRunningBatch(TableSize * NumTables)) {
 164       for (auto K : Data.Keys) {
 165         for (auto& Set : Data.Sets) {
 166           benchmark::DoNotOptimize(Set.erase(Set.insert(K).first));
 167         }
 168       }
 169     }
 170   }
 171
 172   std::string name() const { return "BM_InsertMissAndErase" + Access::name() + baseName(); }
 173 };
 174
 175 struct IterateRangeFor : Base {
 176   using Base::Base;
 177
 178   void run(benchmark::State& State) const {
 179     auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, AccessPattern::Ordered);
 180
 181     while (State.KeepRunningBatch(TableSize * NumTables)) {
 182       for (auto& Set : Data.Sets) {
 183         for (auto& V : Set) {
 184           benchmark::DoNotOptimize(V);
 185         }
 186       }
 187     }
 188   }
 189
 190   std::string name() const { return "BM_IterateRangeFor" + baseName(); }
 191 };
 192
 193 struct IterateBeginEnd : Base {
 194   using Base::Base;
 195
 196   void run(benchmark::State& State) const {
 197     auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, AccessPattern::Ordered);
 198
 199     while (State.KeepRunningBatch(TableSize * NumTables)) {
 200       for (auto& Set : Data.Sets) {
 201         for (auto it = Set.begin(); it != Set.end(); ++it) {
 202           benchmark::DoNotOptimize(*it);
 203         }
 204       }
 205     }
 206   }
 207
 208   std::string name() const { return "BM_IterateBeginEnd" + baseName(); }
 209 };
 210
 211 } // namespace
 212
 213 int main(int argc, char** argv) {
 214   benchmark::Initialize(&argc, argv);
 215   if (benchmark::ReportUnrecognizedArguments(argc, argv))
 216     return 1;
 217
 218   const std::vector<size_t> TableSize{1, 10, 100, 1000, 10000, 100000, 1000000};
 219   const std::vector<size_t> NumTables{1, 10, 100, 1000, 10000, 100000, 1000000};
 220
 221   makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables);
 222   makeCartesianProductBenchmark<Find, AllHitTypes, AllAccessPattern>(TableSize, NumTables);
 223   makeCartesianProductBenchmark<FindNeEnd, AllHitTypes, AllAccessPattern>(TableSize, NumTables);
 224   makeCartesianProductBenchmark<InsertHit, AllAccessPattern>(TableSize, NumTables);
 225   makeCartesianProductBenchmark<InsertMissAndErase, AllAccessPattern>(TableSize, NumTables);
 226   makeCartesianProductBenchmark<IterateRangeFor>(TableSize, NumTables);
 227   makeCartesianProductBenchmark<IterateBeginEnd>(TableSize, NumTables);
 228   benchmark::RunSpecifiedBenchmarks();
 229 }