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
  32     : EnumValuesAsTuple<AllAccessPattern, AccessPattern, 2> {
  33   static constexpr const char* Names[] = {"Ordered", "Random"};
  34 };
  35
  36 void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) {
  37   if (AP == AccessPattern::Random) {
  38     std::random_device R;
  39     std::mt19937 M(R());
  40     std::shuffle(std::begin(Keys), std::end(Keys), M);
  41   }
  42 }
  43
  44 struct TestSets {
  45   std::vector<std::set<uint64_t> > Sets;
  46   std::vector<uint64_t> Keys;
  47 };
  48
  49 TestSets makeTestingSets(size_t TableSize, size_t NumTables, HitType Hit,
  50                          AccessPattern Access) {
  51   TestSets R;
  52   R.Sets.resize(1);
  53
  54   for (uint64_t I = 0; I < TableSize; ++I) {
  55     R.Sets[0].insert(2 * I);
  56     R.Keys.push_back(Hit == HitType::Hit ? 2 * I : 2 * I + 1);
  57   }
  58   R.Sets.resize(NumTables, R.Sets[0]);
  59   sortKeysBy(R.Keys, Access);
  60
  61   return R;
  62 }
  63
  64 struct Base {
  65   size_t TableSize;
  66   size_t NumTables;
  67   Base(size_t T, size_t N) : TableSize(T), NumTables(N) {}
  68
  69   bool skip() const {
  70     size_t Total = TableSize * NumTables;
  71     return Total < 100 || Total > 1000000;
  72   }
  73
  74   std::string baseName() const {
  75     return "_TableSize" + std::to_string(TableSize) + "_NumTables" +
  76            std::to_string(NumTables);
  77   }
  78 };
  79
  80 template <class Access>
  81 struct Create : Base {
  82   using Base::Base;
  83
  84   void run(benchmark::State& State) const {
  85     std::vector<uint64_t> Keys(TableSize);
  86     std::iota(Keys.begin(), Keys.end(), uint64_t{0});
  87     sortKeysBy(Keys, Access());
  88
  89     while (State.KeepRunningBatch(TableSize * NumTables)) {
  90       std::vector<std::set<uint64_t>> Sets(NumTables);
  91       for (auto K : Keys) {
  92         for (auto& Set : Sets) {
  93           benchmark::DoNotOptimize(Set.insert(K));
  94         }
  95       }
  96     }
  97   }
  98
  99   std::string name() const {
 100     return "BM_Create" + Access::name() + baseName();
 101   }
 102 };
 103
 104 template <class Hit, class Access>
 105 struct Find : Base {
 106   using Base::Base;
 107
 108   void run(benchmark::State& State) const {
 109     auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
 110
 111     while (State.KeepRunningBatch(TableSize * NumTables)) {
 112       for (auto K : Data.Keys) {
 113         for (auto& Set : Data.Sets) {
 114           benchmark::DoNotOptimize(Set.find(K));
 115         }
 116       }
 117     }
 118   }
 119
 120   std::string name() const {
 121     return "BM_Find" + Hit::name() + Access::name() + baseName();
 122   }
 123 };
 124
 125 template <class Hit, class Access>
 126 struct FindNeEnd : Base {
 127   using Base::Base;
 128
 129   void run(benchmark::State& State) const {
 130     auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
 131
 132     while (State.KeepRunningBatch(TableSize * NumTables)) {
 133       for (auto K : Data.Keys) {
 134         for (auto& Set : Data.Sets) {
 135           benchmark::DoNotOptimize(Set.find(K) != Set.end());
 136         }
 137       }
 138     }
 139   }
 140
 141   std::string name() const {
 142     return "BM_FindNeEnd" + Hit::name() + Access::name() + baseName();
 143   }
 144 };
 145
 146 template <class Access>
 147 struct InsertHit : Base {
 148   using Base::Base;
 149
 150   void run(benchmark::State& State) const {
 151     auto Data = makeTestingSets(TableSize, NumTables, HitType::Hit, Access());
 152
 153     while (State.KeepRunningBatch(TableSize * NumTables)) {
 154       for (auto K : Data.Keys) {
 155         for (auto& Set : Data.Sets) {
 156           benchmark::DoNotOptimize(Set.insert(K));
 157         }
 158       }
 159     }
 160   }
 161
 162   std::string name() const {
 163     return "BM_InsertHit" + Access::name() + baseName();
 164   }
 165 };
 166
 167 template <class Access>
 168 struct InsertMissAndErase : Base {
 169   using Base::Base;
 170
 171   void run(benchmark::State& State) const {
 172     auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, Access());
 173
 174     while (State.KeepRunningBatch(TableSize * NumTables)) {
 175       for (auto K : Data.Keys) {
 176         for (auto& Set : Data.Sets) {
 177           benchmark::DoNotOptimize(Set.erase(Set.insert(K).first));
 178         }
 179       }
 180     }
 181   }
 182
 183   std::string name() const {
 184     return "BM_InsertMissAndErase" + Access::name() + baseName();
 185   }
 186 };
 187
 188 struct IterateRangeFor : Base {
 189   using Base::Base;
 190
 191   void run(benchmark::State& State) const {
 192     auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss,
 193                                 AccessPattern::Ordered);
 194
 195     while (State.KeepRunningBatch(TableSize * NumTables)) {
 196       for (auto& Set : Data.Sets) {
 197         for (auto& V : Set) {
 198           benchmark::DoNotOptimize(V);
 199         }
 200       }
 201     }
 202   }
 203
 204   std::string name() const { return "BM_IterateRangeFor" + baseName(); }
 205 };
 206
 207 struct IterateBeginEnd : Base {
 208   using Base::Base;
 209
 210   void run(benchmark::State& State) const {
 211     auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss,
 212                                 AccessPattern::Ordered);
 213
 214     while (State.KeepRunningBatch(TableSize * NumTables)) {
 215       for (auto& Set : Data.Sets) {
 216         for (auto it = Set.begin(); it != Set.end(); ++it) {
 217           benchmark::DoNotOptimize(*it);
 218         }
 219       }
 220     }
 221   }
 222
 223   std::string name() const { return "BM_IterateBeginEnd" + baseName(); }
 224 };
 225
 226 }  // namespace
 227
 228 int main(int argc, char** argv) {
 229   benchmark::Initialize(&argc, argv);
 230   if (benchmark::ReportUnrecognizedArguments(argc, argv))
 231     return 1;
 232
 233   const std::vector<size_t> TableSize{1, 10, 100, 1000, 10000, 100000, 1000000};
 234   const std::vector<size_t> NumTables{1, 10, 100, 1000, 10000, 100000, 1000000};
 235
 236   makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables);
 237   makeCartesianProductBenchmark<Find, AllHitTypes, AllAccessPattern>(
 238       TableSize, NumTables);
 239   makeCartesianProductBenchmark<FindNeEnd, AllHitTypes, AllAccessPattern>(
 240       TableSize, NumTables);
 241   makeCartesianProductBenchmark<InsertHit, AllAccessPattern>(
 242       TableSize, NumTables);
 243   makeCartesianProductBenchmark<InsertMissAndErase, AllAccessPattern>(
 244       TableSize, NumTables);
 245   makeCartesianProductBenchmark<IterateRangeFor>(TableSize, NumTables);
 246   makeCartesianProductBenchmark<IterateBeginEnd>(TableSize, NumTables);
 247   benchmark::RunSpecifiedBenchmarks();
 248 }