libcxx/benchmarks/ContainerBenchmarks.h

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef BENCHMARK_CONTAINER_BENCHMARKS_H
  11 #define BENCHMARK_CONTAINER_BENCHMARKS_H
  12
  13 #include <cassert>
  14
  15 #include "Utilities.h"
  16 #include "benchmark/benchmark.h"
  17
  18 namespace ContainerBenchmarks {
  19
  20 template <class Container>
  21 void BM_ConstructSize(benchmark::State& st, Container) {
  22   auto size = st.range(0);
  23   for (auto _ : st) {
  24     Container c(size);
  25     DoNotOptimizeData(c);
  26   }
  27 }
  28
  29 template <class Container>
  30 void BM_CopyConstruct(benchmark::State& st, Container) {
  31   auto size = st.range(0);
  32   Container c(size);
  33   for (auto _ : st) {
  34     auto v = c;
  35     DoNotOptimizeData(v);
  36   }
  37 }
  38
  39 template <class Container>
  40 void BM_Assignment(benchmark::State& st, Container) {
  41   auto size = st.range(0);
  42   Container c1;
  43   Container c2(size);
  44   for (auto _ : st) {
  45     c1 = c2;
  46     DoNotOptimizeData(c1);
  47     DoNotOptimizeData(c2);
  48   }
  49 }
  50
  51 template <class Container>
  52 void BM_ConstructSizeValue(benchmark::State& st, Container, typename Container::value_type const& val) {
  53   const auto size = st.range(0);
  54   for (auto _ : st) {
  55     Container c(size, val);
  56     DoNotOptimizeData(c);
  57   }
  58 }
  59
  60 template <class Container, class GenInputs>
  61 void BM_ConstructIterIter(benchmark::State& st, Container, GenInputs gen) {
  62   auto in          = gen(st.range(0));
  63   const auto begin = in.begin();
  64   const auto end   = in.end();
  65   benchmark::DoNotOptimize(&in);
  66   while (st.KeepRunning()) {
  67     Container c(begin, end);
  68     DoNotOptimizeData(c);
  69   }
  70 }
  71
  72 template <class Container, class GenInputs>
  73 void BM_ConstructFromRange(benchmark::State& st, Container, GenInputs gen) {
  74   auto in = gen(st.range(0));
  75   benchmark::DoNotOptimize(&in);
  76   while (st.KeepRunning()) {
  77     Container c(std::from_range, in);
  78     DoNotOptimizeData(c);
  79   }
  80 }
  81
  82 template <class Container>
  83 void BM_Pushback(benchmark::State& state, Container c) {
  84   int count = state.range(0);
  85   c.reserve(count);
  86   while (state.KeepRunningBatch(count)) {
  87     c.clear();
  88     for (int i = 0; i != count; ++i) {
  89       c.push_back(i);
  90     }
  91     benchmark::DoNotOptimize(c.data());
  92   }
  93 }
  94
  95 template <class Container, class GenInputs>
  96 void BM_InsertValue(benchmark::State& st, Container c, GenInputs gen) {
  97   auto in        = gen(st.range(0));
  98   const auto end = in.end();
  99   while (st.KeepRunning()) {
 100     c.clear();
 101     for (auto it = in.begin(); it != end; ++it) {
 102       benchmark::DoNotOptimize(&(*c.insert(*it).first));
 103     }
 104     benchmark::ClobberMemory();
 105   }
 106 }
 107
 108 template <class Container, class GenInputs>
 109 void BM_InsertValueRehash(benchmark::State& st, Container c, GenInputs gen) {
 110   auto in        = gen(st.range(0));
 111   const auto end = in.end();
 112   while (st.KeepRunning()) {
 113     c.clear();
 114     c.rehash(16);
 115     for (auto it = in.begin(); it != end; ++it) {
 116       benchmark::DoNotOptimize(&(*c.insert(*it).first));
 117     }
 118     benchmark::ClobberMemory();
 119   }
 120 }
 121
 122 template <class Container, class GenInputs>
 123 void BM_InsertDuplicate(benchmark::State& st, Container c, GenInputs gen) {
 124   auto in        = gen(st.range(0));
 125   const auto end = in.end();
 126   c.insert(in.begin(), in.end());
 127   benchmark::DoNotOptimize(&c);
 128   benchmark::DoNotOptimize(&in);
 129   while (st.KeepRunning()) {
 130     for (auto it = in.begin(); it != end; ++it) {
 131       benchmark::DoNotOptimize(&(*c.insert(*it).first));
 132     }
 133     benchmark::ClobberMemory();
 134   }
 135 }
 136
 137 template <class Container, class GenInputs>
 138 void BM_EmplaceDuplicate(benchmark::State& st, Container c, GenInputs gen) {
 139   auto in        = gen(st.range(0));
 140   const auto end = in.end();
 141   c.insert(in.begin(), in.end());
 142   benchmark::DoNotOptimize(&c);
 143   benchmark::DoNotOptimize(&in);
 144   while (st.KeepRunning()) {
 145     for (auto it = in.begin(); it != end; ++it) {
 146       benchmark::DoNotOptimize(&(*c.emplace(*it).first));
 147     }
 148     benchmark::ClobberMemory();
 149   }
 150 }
 151
 152 template <class Container, class GenInputs>
 153 static void BM_Find(benchmark::State& st, Container c, GenInputs gen) {
 154   auto in = gen(st.range(0));
 155   c.insert(in.begin(), in.end());
 156   benchmark::DoNotOptimize(&(*c.begin()));
 157   const auto end = in.data() + in.size();
 158   while (st.KeepRunning()) {
 159     for (auto it = in.data(); it != end; ++it) {
 160       benchmark::DoNotOptimize(&(*c.find(*it)));
 161     }
 162     benchmark::ClobberMemory();
 163   }
 164 }
 165
 166 template <class Container, class GenInputs>
 167 static void BM_FindRehash(benchmark::State& st, Container c, GenInputs gen) {
 168   c.rehash(8);
 169   auto in = gen(st.range(0));
 170   c.insert(in.begin(), in.end());
 171   benchmark::DoNotOptimize(&(*c.begin()));
 172   const auto end = in.data() + in.size();
 173   while (st.KeepRunning()) {
 174     for (auto it = in.data(); it != end; ++it) {
 175       benchmark::DoNotOptimize(&(*c.find(*it)));
 176     }
 177     benchmark::ClobberMemory();
 178   }
 179 }
 180
 181 template <class Container, class GenInputs>
 182 static void BM_Rehash(benchmark::State& st, Container c, GenInputs gen) {
 183   auto in = gen(st.range(0));
 184   c.max_load_factor(3.0);
 185   c.insert(in.begin(), in.end());
 186   benchmark::DoNotOptimize(c);
 187   const auto bucket_count = c.bucket_count();
 188   while (st.KeepRunning()) {
 189     c.rehash(bucket_count + 1);
 190     c.rehash(bucket_count);
 191     benchmark::ClobberMemory();
 192   }
 193 }
 194
 195 template <class Container, class GenInputs>
 196 static void BM_Compare_same_container(benchmark::State& st, Container, GenInputs gen) {
 197   auto in = gen(st.range(0));
 198   Container c1(in.begin(), in.end());
 199   Container c2 = c1;
 200
 201   benchmark::DoNotOptimize(&(*c1.begin()));
 202   benchmark::DoNotOptimize(&(*c2.begin()));
 203   while (st.KeepRunning()) {
 204     bool res = c1 == c2;
 205     benchmark::DoNotOptimize(&res);
 206     benchmark::ClobberMemory();
 207   }
 208 }
 209
 210 template <class Container, class GenInputs>
 211 static void BM_Compare_different_containers(benchmark::State& st, Container, GenInputs gen) {
 212   auto in1 = gen(st.range(0));
 213   auto in2 = gen(st.range(0));
 214   Container c1(in1.begin(), in1.end());
 215   Container c2(in2.begin(), in2.end());
 216
 217   benchmark::DoNotOptimize(&(*c1.begin()));
 218   benchmark::DoNotOptimize(&(*c2.begin()));
 219   while (st.KeepRunning()) {
 220     bool res = c1 == c2;
 221     benchmark::DoNotOptimize(&res);
 222     benchmark::ClobberMemory();
 223   }
 224 }
 225
 226 } // end namespace ContainerBenchmarks
 227
 228 #endif // BENCHMARK_CONTAINER_BENCHMARKS_H