456 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef TEST_BENCHMARKS_CONTAINERS_SEQUENCE_SEQUENCE_CONTAINER_BENCHMARKS_H11#define TEST_BENCHMARKS_CONTAINERS_SEQUENCE_SEQUENCE_CONTAINER_BENCHMARKS_H12 13#include <algorithm>14#include <cassert>15#include <cstddef>16#include <iterator>17#include <ranges> // for std::from_range18#include <string>19#include <type_traits>20#include <vector>21 22#include "benchmark/benchmark.h"23#include "test_iterators.h"24#include "../../GenerateInput.h"25 26namespace support {27 28template <class Container>29void DoNotOptimizeData(Container& c) {30 if constexpr (requires { c.data(); }) {31 benchmark::DoNotOptimize(c.data());32 } else {33 benchmark::DoNotOptimize(&c);34 }35}36 37template <class Container>38void sequence_container_benchmarks(std::string container) {39 using ValueType = typename Container::value_type;40 41 using Generator = ValueType (*)();42 Generator cheap = [] { return Generate<ValueType>::cheap(); };43 Generator expensive = [] { return Generate<ValueType>::expensive(); };44 auto tostr = [&](Generator gen) -> std::string {45 return gen == cheap ? " (cheap elements)" : " (expensive elements)";46 };47 std::vector<Generator> generators;48 generators.push_back(cheap);49 if constexpr (!std::is_integral_v<ValueType>) {50 generators.push_back(expensive);51 }52 53 // Some of these benchmarks are structured to perform the operation being benchmarked54 // a small number of times at each iteration, in order to offset the cost of55 // PauseTiming() and ResumeTiming().56 static constexpr std::size_t BatchSize = 32;57 58 auto bench = [&](std::string operation, auto f) {59 benchmark::RegisterBenchmark(container + "::" + operation, f)->Arg(32)->Arg(1024)->Arg(8192);60 };61 62 /////////////////////////63 // Constructors64 /////////////////////////65 if constexpr (std::is_constructible_v<Container, std::size_t>) {66 // not all containers provide this constructor67 bench("ctor(size)", [](auto& st) {68 auto const size = st.range(0);69 70 for ([[maybe_unused]] auto _ : st) {71 Container c(size); // we assume the destructor doesn't dominate the benchmark72 DoNotOptimizeData(c);73 }74 });75 }76 77 for (auto gen : generators)78 bench("ctor(size, value_type)" + tostr(gen), [gen](auto& st) {79 auto const size = st.range(0);80 ValueType value = gen();81 benchmark::DoNotOptimize(value);82 83 for ([[maybe_unused]] auto _ : st) {84 Container c(size, value); // we assume the destructor doesn't dominate the benchmark85 DoNotOptimizeData(c);86 }87 });88 89 for (auto gen : generators)90 bench("ctor(Iterator, Iterator)" + tostr(gen), [gen](auto& st) {91 auto const size = st.range(0);92 std::vector<ValueType> in;93 std::generate_n(std::back_inserter(in), size, gen);94 const auto begin = in.begin();95 const auto end = in.end();96 benchmark::DoNotOptimize(in);97 98 for ([[maybe_unused]] auto _ : st) {99 Container c(begin, end); // we assume the destructor doesn't dominate the benchmark100 DoNotOptimizeData(c);101 }102 });103 104#if defined(__cpp_lib_containers_ranges) && __cpp_lib_containers_ranges >= 202202L105 for (auto gen : generators)106 bench("ctor(Range)" + tostr(gen), [gen](auto& st) {107 auto const size = st.range(0);108 std::vector<ValueType> in;109 std::generate_n(std::back_inserter(in), size, gen);110 benchmark::DoNotOptimize(in);111 112 for ([[maybe_unused]] auto _ : st) {113 Container c(std::from_range, in); // we assume the destructor doesn't dominate the benchmark114 DoNotOptimizeData(c);115 }116 });117#endif118 119 for (auto gen : generators)120 bench("ctor(const&)" + tostr(gen), [gen](auto& st) {121 auto const size = st.range(0);122 Container in;123 std::generate_n(std::back_inserter(in), size, gen);124 DoNotOptimizeData(in);125 126 for ([[maybe_unused]] auto _ : st) {127 Container c(in); // we assume the destructor doesn't dominate the benchmark128 DoNotOptimizeData(c);129 DoNotOptimizeData(in);130 }131 });132 133 /////////////////////////134 // Assignment135 /////////////////////////136 for (auto gen : generators)137 bench("operator=(const&)" + tostr(gen), [gen](auto& st) {138 auto const size = st.range(0);139 Container in1, in2;140 std::generate_n(std::back_inserter(in1), size, gen);141 std::generate_n(std::back_inserter(in2), size, gen);142 DoNotOptimizeData(in1);143 DoNotOptimizeData(in2);144 145 // Assign from one of two containers in succession to avoid146 // hitting a self-assignment corner-case147 Container c(in1);148 bool toggle = false;149 for ([[maybe_unused]] auto _ : st) {150 c = toggle ? in1 : in2;151 toggle = !toggle;152 DoNotOptimizeData(c);153 DoNotOptimizeData(in1);154 DoNotOptimizeData(in2);155 }156 });157 158 // Benchmark Container::assign(input-iter, input-iter) when the container already contains159 // the same number of elements that we're assigning. The intent is to check whether the160 // implementation basically creates a new container from scratch or manages to reuse the161 // pre-existing storage.162 for (auto gen : generators)163 bench("assign(input-iter, input-iter) (full container)" + tostr(gen), [gen](auto& st) {164 auto const size = st.range(0);165 std::vector<ValueType> in1, in2;166 std::generate_n(std::back_inserter(in1), size, gen);167 std::generate_n(std::back_inserter(in2), size, gen);168 DoNotOptimizeData(in1);169 DoNotOptimizeData(in2);170 171 Container c(in1.begin(), in1.end());172 bool toggle = false;173 for ([[maybe_unused]] auto _ : st) {174 std::vector<ValueType>& in = toggle ? in1 : in2;175 auto first = in.data();176 auto last = in.data() + in.size();177 c.assign(cpp17_input_iterator(first), cpp17_input_iterator(last));178 toggle = !toggle;179 DoNotOptimizeData(c);180 }181 });182 183 /////////////////////////184 // Insertion185 /////////////////////////186 for (auto gen : generators)187 bench("insert(begin)" + tostr(gen), [gen](auto& st) {188 auto const size = st.range(0);189 std::vector<ValueType> in;190 std::generate_n(std::back_inserter(in), size, gen);191 DoNotOptimizeData(in);192 193 Container c(in.begin(), in.end());194 DoNotOptimizeData(c);195 196 ValueType value = gen();197 benchmark::DoNotOptimize(value);198 199 for ([[maybe_unused]] auto _ : st) {200 c.insert(c.begin(), value);201 DoNotOptimizeData(c);202 203 c.erase(std::prev(c.end())); // avoid growing indefinitely204 }205 });206 207 if constexpr (std::random_access_iterator<typename Container::iterator>) {208 for (auto gen : generators)209 bench("insert(middle)" + tostr(gen), [gen](auto& st) {210 auto const size = st.range(0);211 std::vector<ValueType> in;212 std::generate_n(std::back_inserter(in), size, gen);213 DoNotOptimizeData(in);214 215 Container c(in.begin(), in.end());216 DoNotOptimizeData(c);217 218 ValueType value = gen();219 benchmark::DoNotOptimize(value);220 221 for ([[maybe_unused]] auto _ : st) {222 auto mid = c.begin() + (size / 2); // requires random-access iterators in order to make sense223 c.insert(mid, value);224 DoNotOptimizeData(c);225 226 c.erase(c.end() - 1); // avoid growing indefinitely227 }228 });229 }230 231 if constexpr (requires(Container c) { c.reserve(0); }) {232 // Insert at the start of a vector in a scenario where the vector already233 // has enough capacity to hold all the elements we are inserting.234 for (auto gen : generators)235 bench("insert(begin, input-iter, input-iter) (no realloc)" + tostr(gen), [gen](auto& st) {236 auto const size = st.range(0);237 std::vector<ValueType> in;238 std::generate_n(std::back_inserter(in), size, gen);239 DoNotOptimizeData(in);240 auto first = in.data();241 auto last = in.data() + in.size();242 243 const int small = 100; // arbitrary244 Container c;245 c.reserve(size + small); // ensure no reallocation246 std::generate_n(std::back_inserter(c), small, gen);247 248 for ([[maybe_unused]] auto _ : st) {249 c.insert(c.begin(), cpp17_input_iterator(first), cpp17_input_iterator(last));250 DoNotOptimizeData(c);251 252 st.PauseTiming();253 c.erase(c.begin() + small, c.end()); // avoid growing indefinitely254 st.ResumeTiming();255 }256 });257 258 // Insert at the start of a vector in a scenario where the vector already259 // has almost enough capacity to hold all the elements we are inserting,260 // but does need to reallocate.261 for (auto gen : generators)262 bench("insert(begin, input-iter, input-iter) (half filled)" + tostr(gen), [gen](auto& st) {263 auto const size = st.range(0);264 std::vector<ValueType> in;265 std::generate_n(std::back_inserter(in), size, gen);266 DoNotOptimizeData(in);267 auto first = in.data();268 auto last = in.data() + in.size();269 270 const int overflow = size / 10; // 10% of elements won't fit in the vector when we insert271 Container c;272 for ([[maybe_unused]] auto _ : st) {273 st.PauseTiming();274 c = Container();275 c.reserve(size);276 std::generate_n(std::back_inserter(c), overflow, gen);277 st.ResumeTiming();278 279 c.insert(c.begin(), cpp17_input_iterator(first), cpp17_input_iterator(last));280 DoNotOptimizeData(c);281 }282 });283 284 // Insert at the start of a vector in a scenario where the vector can fit a few285 // more elements, but needs to reallocate almost immediately to fit the remaining286 // elements.287 for (auto gen : generators)288 bench("insert(begin, input-iter, input-iter) (near full)" + tostr(gen), [gen](auto& st) {289 auto const size = st.range(0);290 std::vector<ValueType> in;291 std::generate_n(std::back_inserter(in), size, gen);292 DoNotOptimizeData(in);293 auto first = in.data();294 auto last = in.data() + in.size();295 296 auto const overflow = 9 * (size / 10); // 90% of elements won't fit in the vector when we insert297 Container c;298 for ([[maybe_unused]] auto _ : st) {299 st.PauseTiming();300 c = Container();301 c.reserve(size);302 std::generate_n(std::back_inserter(c), overflow, gen);303 st.ResumeTiming();304 305 c.insert(c.begin(), cpp17_input_iterator(first), cpp17_input_iterator(last));306 DoNotOptimizeData(c);307 }308 });309 }310 311 /////////////////////////312 // Variations of push_back313 /////////////////////////314 static constexpr bool has_push_back = requires(Container c, ValueType v) { c.push_back(v); };315 static constexpr bool has_capacity = requires(Container c) { c.capacity(); };316 static constexpr bool has_reserve = requires(Container c) { c.reserve(0); };317 if constexpr (has_push_back) {318 if constexpr (has_capacity) {319 // For containers where we can observe capacity(), push_back a single element320 // without reserving to ensure the container needs to grow321 for (auto gen : generators)322 bench("push_back() (growing)" + tostr(gen), [gen](auto& st) {323 auto const size = st.range(0);324 std::vector<ValueType> in;325 std::generate_n(std::back_inserter(in), size, gen);326 DoNotOptimizeData(in);327 328 auto at_capacity = [](Container c) {329 while (c.size() < c.capacity())330 c.push_back(c.back());331 return c;332 };333 334 std::vector<Container> c(BatchSize, at_capacity(Container(in.begin(), in.end())));335 std::vector<Container> const original = c;336 337 while (st.KeepRunningBatch(BatchSize)) {338 for (std::size_t i = 0; i != BatchSize; ++i) {339 c[i].push_back(in[i]);340 DoNotOptimizeData(c[i]);341 }342 343 st.PauseTiming();344 for (std::size_t i = 0; i != BatchSize; ++i) {345 c[i] = at_capacity(Container(in.begin(), in.end()));346 assert(c[i].size() == c[i].capacity());347 }348 st.ResumeTiming();349 }350 });351 }352 353 // For containers where we can reserve, push_back a single element after reserving to354 // ensure the container doesn't grow355 if constexpr (has_reserve) {356 for (auto gen : generators)357 bench("push_back() (with reserve)" + tostr(gen), [gen](auto& st) {358 auto const size = st.range(0);359 std::vector<ValueType> in;360 std::generate_n(std::back_inserter(in), size, gen);361 DoNotOptimizeData(in);362 363 Container c(in.begin(), in.end());364 // Ensure the container has enough capacity365 c.reserve(c.size() + BatchSize);366 DoNotOptimizeData(c);367 368 while (st.KeepRunningBatch(BatchSize)) {369 for (std::size_t i = 0; i != BatchSize; ++i) {370 c.push_back(in[i]);371 }372 DoNotOptimizeData(c);373 374 st.PauseTiming();375 c.erase(c.end() - BatchSize, c.end());376 st.ResumeTiming();377 }378 });379 }380 381 // push_back many elements: this is amortized constant for std::vector but not all containers382 for (auto gen : generators)383 bench("push_back() (many elements)" + tostr(gen), [gen](auto& st) {384 auto const size = st.range(0);385 std::vector<ValueType> in;386 std::generate_n(std::back_inserter(in), size, gen);387 DoNotOptimizeData(in);388 389 Container c;390 DoNotOptimizeData(c);391 while (st.KeepRunningBatch(size)) {392 for (int i = 0; i != size; ++i) {393 c.push_back(in[i]);394 }395 DoNotOptimizeData(c);396 397 st.PauseTiming();398 c.clear();399 st.ResumeTiming();400 }401 });402 }403 404 /////////////////////////405 // Erasure406 /////////////////////////407 for (auto gen : generators)408 bench("erase(begin)" + tostr(gen), [gen](auto& st) {409 auto const size = st.range(0);410 std::vector<ValueType> in;411 std::generate_n(std::back_inserter(in), size, gen);412 DoNotOptimizeData(in);413 414 Container c(in.begin(), in.end());415 DoNotOptimizeData(c);416 417 ValueType value = gen();418 benchmark::DoNotOptimize(value);419 420 for ([[maybe_unused]] auto _ : st) {421 c.erase(c.begin());422 DoNotOptimizeData(c);423 424 c.insert(c.end(), value); // re-insert an element at the end to avoid needing a new container425 }426 });427 428 if constexpr (std::random_access_iterator<typename Container::iterator>) {429 for (auto gen : generators)430 bench("erase(middle)" + tostr(gen), [gen](auto& st) {431 auto const size = st.range(0);432 std::vector<ValueType> in;433 std::generate_n(std::back_inserter(in), size, gen);434 DoNotOptimizeData(in);435 436 Container c(in.begin(), in.end());437 DoNotOptimizeData(c);438 439 ValueType value = gen();440 benchmark::DoNotOptimize(value);441 442 for ([[maybe_unused]] auto _ : st) {443 auto mid = c.begin() + (size / 2);444 c.erase(mid);445 DoNotOptimizeData(c);446 447 c.insert(c.end(), value); // re-insert an element at the end to avoid needing a new container448 }449 });450 }451}452 453} // namespace support454 455#endif // TEST_BENCHMARKS_CONTAINERS_SEQUENCE_SEQUENCE_CONTAINER_BENCHMARKS_H456