718 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef TEST_BENCHMARKS_CONTAINERS_ASSOCIATIVE_CONTAINER_BENCHMARKS_H10#define TEST_BENCHMARKS_CONTAINERS_ASSOCIATIVE_CONTAINER_BENCHMARKS_H11 12#include <algorithm>13#include <iterator>14#include <memory_resource>15#include <random>16#include <string>17#include <ranges>18#include <type_traits>19#include <utility>20#include <vector>21 22#include "benchmark/benchmark.h"23#include "../../GenerateInput.h"24#include "test_macros.h"25 26namespace support {27 28template <class Container>29struct adapt_operations {30 // using ValueType = ...;31 // using KeyType = ...;32 // static ValueType value_from_key(KeyType const& k);33 // static KeyType key_from_value(ValueType const& value);34 35 // using InsertionResult = ...;36 // static Container::iterator get_iterator(InsertionResult const&);37 38 // template <class Allocator>39 // using rebind_alloc = ...;40};41 42template <class Container>43void associative_container_benchmarks(std::string container) {44 using Key = typename Container::key_type;45 using Value = typename Container::value_type;46 47 auto generate_unique_keys = [=](std::size_t n) {48 std::set<Key> keys;49 while (keys.size() < n) {50 Key k = Generate<Key>::random();51 keys.insert(k);52 }53 return std::vector<Key>(keys.begin(), keys.end());54 };55 56 auto make_value_types = [](std::vector<Key> const& keys) {57 std::vector<Value> kv;58 for (Key const& k : keys)59 kv.push_back(adapt_operations<Container>::value_from_key(k));60 return kv;61 };62 63 auto get_key = [](Value const& v) { return adapt_operations<Container>::key_from_value(v); };64 65 auto bench = [&](std::string operation, auto f) {66 benchmark::RegisterBenchmark(container + "::" + operation, f)->Arg(0)->Arg(32)->Arg(1024)->Arg(8192);67 };68 69 static constexpr bool is_multi_key_container =70 !std::is_same_v<typename adapt_operations<Container>::InsertionResult,71 std::pair<typename Container::iterator, bool>>;72 73 static constexpr bool is_ordered_container = requires(Container c, Key k) { c.lower_bound(k); };74 75 static constexpr bool is_map_like = requires { typename Container::mapped_type; };76 77 // These benchmarks are structured to perform the operation being benchmarked78 // a small number of times at each iteration, in order to offset the cost of79 // PauseTiming() and ResumeTiming().80 static constexpr std::size_t BatchSize = 32;81 82 struct alignas(Container) ScratchSpace {83 char storage[sizeof(Container)];84 };85 86 /////////////////////////87 // Constructors88 /////////////////////////89 bench("ctor(const&)", [=](auto& st) {90 const std::size_t size = st.range(0);91 std::vector<Value> in = make_value_types(generate_unique_keys(size));92 Container src(in.begin(), in.end());93 ScratchSpace c[BatchSize];94 95 while (st.KeepRunningBatch(BatchSize)) {96 for (std::size_t i = 0; i != BatchSize; ++i) {97 new (c + i) Container(src);98 benchmark::DoNotOptimize(c + i);99 benchmark::ClobberMemory();100 }101 102 st.PauseTiming();103 for (std::size_t i = 0; i != BatchSize; ++i) {104 reinterpret_cast<Container*>(c + i)->~Container();105 }106 st.ResumeTiming();107 }108 });109 110 bench("ctor(const&, alloc)", [=](auto& st) {111 const std::size_t size = st.range(0);112 std::vector<Value> in = make_value_types(generate_unique_keys(size));113 Container src(in.begin(), in.end());114 ScratchSpace c[BatchSize];115 116 while (st.KeepRunningBatch(BatchSize)) {117 for (std::size_t i = 0; i != BatchSize; ++i) {118 new (c + i) Container(src, std::allocator<typename Container::value_type>());119 benchmark::DoNotOptimize(c + i);120 benchmark::ClobberMemory();121 }122 123 st.PauseTiming();124 for (std::size_t i = 0; i != BatchSize; ++i) {125 reinterpret_cast<Container*>(c + i)->~Container();126 }127 st.ResumeTiming();128 }129 });130 131 bench("ctor(&&, different allocs)", [=](auto& st) {132 using PMRContainer = adapt_operations<Container>::template rebind_alloc<133 std::pmr::polymorphic_allocator<typename Container::value_type>>;134 135 const std::size_t size = st.range(0);136 std::vector<Value> in = make_value_types(generate_unique_keys(size));137 std::pmr::monotonic_buffer_resource rs(size * 64 * BatchSize); // 64 bytes should be enough per node138 std::vector<PMRContainer> srcs;139 srcs.reserve(BatchSize);140 for (size_t i = 0; i != BatchSize; ++i)141 srcs.emplace_back(&rs).insert(in.begin(), in.end());142 alignas(PMRContainer) char c[BatchSize * sizeof(PMRContainer)];143 144 std::pmr::monotonic_buffer_resource rs2(size * 64 * BatchSize); // 64 bytes should be enough per node145 while (st.KeepRunningBatch(BatchSize)) {146 for (std::size_t i = 0; i != BatchSize; ++i) {147 new (c + i * sizeof(PMRContainer)) PMRContainer(std::move(srcs[i]), &rs2);148 benchmark::DoNotOptimize(c + i);149 benchmark::ClobberMemory();150 }151 152 st.PauseTiming();153 for (std::size_t i = 0; i != BatchSize; ++i) {154 reinterpret_cast<PMRContainer*>(c + i * sizeof(PMRContainer))->~PMRContainer();155 }156 rs2.release();157 srcs.clear();158 for (size_t i = 0; i != BatchSize; ++i)159 srcs.emplace_back(&rs).insert(in.begin(), in.end());160 161 st.ResumeTiming();162 }163 });164 165 bench("ctor(iterator, iterator) (unsorted sequence)", [=](auto& st) {166 const std::size_t size = st.range(0);167 std::mt19937 randomness;168 std::vector<Key> keys = generate_unique_keys(size);169 std::shuffle(keys.begin(), keys.end(), randomness);170 std::vector<Value> in = make_value_types(keys);171 ScratchSpace c[BatchSize];172 173 while (st.KeepRunningBatch(BatchSize)) {174 for (std::size_t i = 0; i != BatchSize; ++i) {175 new (c + i) Container(in.begin(), in.end());176 benchmark::DoNotOptimize(c + i);177 benchmark::ClobberMemory();178 }179 180 st.PauseTiming();181 for (std::size_t i = 0; i != BatchSize; ++i) {182 reinterpret_cast<Container*>(c + i)->~Container();183 }184 st.ResumeTiming();185 }186 });187 188 bench("ctor(iterator, iterator) (sorted sequence)", [=](auto& st) {189 const std::size_t size = st.range(0);190 std::vector<Key> keys = generate_unique_keys(size);191 std::sort(keys.begin(), keys.end());192 std::vector<Value> in = make_value_types(keys);193 ScratchSpace c[BatchSize];194 195 while (st.KeepRunningBatch(BatchSize)) {196 for (std::size_t i = 0; i != BatchSize; ++i) {197 new (c + i) Container(in.begin(), in.end());198 benchmark::DoNotOptimize(c + i);199 benchmark::ClobberMemory();200 }201 202 st.PauseTiming();203 for (std::size_t i = 0; i != BatchSize; ++i) {204 reinterpret_cast<Container*>(c + i)->~Container();205 }206 st.ResumeTiming();207 }208 });209 210 /////////////////////////211 // Assignment212 /////////////////////////213 bench("operator=(const&) (into cleared Container)", [=](auto& st) {214 const std::size_t size = st.range(0);215 std::vector<Value> in = make_value_types(generate_unique_keys(size));216 Container src(in.begin(), in.end());217 Container c[BatchSize];218 219 while (st.KeepRunningBatch(BatchSize)) {220 for (std::size_t i = 0; i != BatchSize; ++i) {221 c[i] = src;222 benchmark::DoNotOptimize(c[i]);223 benchmark::ClobberMemory();224 }225 226 st.PauseTiming();227 for (std::size_t i = 0; i != BatchSize; ++i) {228 c[i].clear();229 }230 st.ResumeTiming();231 }232 });233 234 bench("operator=(const&) (into partially populated Container)", [=](auto& st) {235 const std::size_t size = st.range(0);236 std::vector<Value> in = make_value_types(generate_unique_keys(size));237 Container src(in.begin(), in.end());238 Container c[BatchSize];239 240 while (st.KeepRunningBatch(BatchSize)) {241 for (std::size_t i = 0; i != BatchSize; ++i) {242 c[i] = src;243 benchmark::DoNotOptimize(c[i]);244 benchmark::ClobberMemory();245 }246 247 st.PauseTiming();248 for (std::size_t i = 0; i != BatchSize; ++i) {249 c[i].clear();250 }251 st.ResumeTiming();252 }253 });254 255 bench("operator=(const&) (into populated Container)", [=](auto& st) {256 const std::size_t size = st.range(0);257 std::vector<Value> in = make_value_types(generate_unique_keys(size));258 Container src(in.begin(), in.end());259 Container c[BatchSize];260 261 while (st.KeepRunningBatch(BatchSize)) {262 for (std::size_t i = 0; i != BatchSize; ++i) {263 c[i] = src;264 benchmark::DoNotOptimize(c[i]);265 benchmark::ClobberMemory();266 }267 }268 });269 270 /////////////////////////271 // Insertion272 /////////////////////////273 bench("insert(value) (already present)", [=](auto& st) {274 const std::size_t size = st.range(0) ? st.range(0) : 1;275 std::vector<Value> in = make_value_types(generate_unique_keys(size));276 Value to_insert = in[in.size() / 2]; // pick any existing value277 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));278 typename Container::iterator inserted[BatchSize];279 280 while (st.KeepRunningBatch(BatchSize)) {281 for (std::size_t i = 0; i != BatchSize; ++i) {282 inserted[i] = adapt_operations<Container>::get_iterator(c[i].insert(to_insert));283 benchmark::DoNotOptimize(inserted[i]);284 benchmark::DoNotOptimize(c[i]);285 benchmark::ClobberMemory();286 }287 288 if constexpr (is_multi_key_container) {289 st.PauseTiming();290 for (std::size_t i = 0; i != BatchSize; ++i) {291 c[i].erase(inserted[i]);292 }293 st.ResumeTiming();294 }295 }296 });297 298 bench("insert(value) (new value)", [=](auto& st) {299 const std::size_t size = st.range(0);300 std::vector<Value> in = make_value_types(generate_unique_keys(size + 1));301 Value to_insert = in.back();302 in.pop_back();303 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));304 305 while (st.KeepRunningBatch(BatchSize)) {306 for (std::size_t i = 0; i != BatchSize; ++i) {307 auto result = c[i].insert(to_insert);308 benchmark::DoNotOptimize(result);309 benchmark::DoNotOptimize(c[i]);310 benchmark::ClobberMemory();311 }312 313 st.PauseTiming();314 for (std::size_t i = 0; i != BatchSize; ++i) {315 c[i].erase(get_key(to_insert));316 }317 st.ResumeTiming();318 }319 });320 321 if constexpr (is_map_like && !is_multi_key_container) {322 bench("insert_or_assign(key, value) (already present)", [=](auto& st) {323 const std::size_t size = st.range(0) ? st.range(0) : 1;324 std::vector<Value> in = make_value_types(generate_unique_keys(size));325 Value to_insert = in[in.size() / 2]; // pick any existing value326 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));327 typename Container::iterator inserted[BatchSize];328 329 while (st.KeepRunningBatch(BatchSize)) {330 for (std::size_t i = 0; i != BatchSize; ++i) {331 inserted[i] =332 adapt_operations<Container>::get_iterator(c[i].insert_or_assign(to_insert.first, to_insert.second));333 benchmark::DoNotOptimize(inserted[i]);334 benchmark::DoNotOptimize(c[i]);335 benchmark::ClobberMemory();336 }337 }338 });339 340 bench("insert_or_assign(key, value) (new value)", [=](auto& st) {341 const std::size_t size = st.range(0);342 std::vector<Value> in = make_value_types(generate_unique_keys(size + 1));343 Value to_insert = in.back();344 in.pop_back();345 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));346 347 while (st.KeepRunningBatch(BatchSize)) {348 for (std::size_t i = 0; i != BatchSize; ++i) {349 auto result = c[i].insert_or_assign(to_insert.first, to_insert.second);350 benchmark::DoNotOptimize(result);351 benchmark::DoNotOptimize(c[i]);352 benchmark::ClobberMemory();353 }354 355 st.PauseTiming();356 for (std::size_t i = 0; i != BatchSize; ++i) {357 c[i].erase(get_key(to_insert));358 }359 st.ResumeTiming();360 }361 });362 }363 364 // The insert(hint, ...) methods are only relevant for ordered containers, and we lack365 // a good way to compute a hint for unordered ones.366 if constexpr (is_ordered_container) {367 auto insert_good_hint_bench = [=](bool bench_end_iter, auto& st) {368 const std::size_t size = st.range(0);369 std::vector<Value> in = make_value_types(generate_unique_keys(size + 1));370 auto skipped_val = bench_end_iter ? in.size() - 1 : in.size() / 2;371 Value to_insert = in[skipped_val];372 { // Remove the element373 std::vector<Value> tmp;374 tmp.reserve(in.size() - 1);375 for (size_t i = 0; i != in.size(); ++i)376 if (i != skipped_val)377 tmp.emplace_back(in[i]);378 in = std::move(tmp);379 }380 381 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));382 typename Container::iterator hints[BatchSize];383 for (std::size_t i = 0; i != BatchSize; ++i) {384 hints[i] = c[i].lower_bound(get_key(to_insert));385 }386 387 while (st.KeepRunningBatch(BatchSize)) {388 for (std::size_t i = 0; i != BatchSize; ++i) {389 auto result = c[i].insert(hints[i], to_insert);390 benchmark::DoNotOptimize(result);391 benchmark::DoNotOptimize(c[i]);392 benchmark::ClobberMemory();393 }394 395 st.PauseTiming();396 for (std::size_t i = 0; i != BatchSize; ++i) {397 c[i].erase(get_key(to_insert));398 hints[i] = c[i].lower_bound(get_key(to_insert)); // refresh hints in case of invalidation399 }400 st.ResumeTiming();401 }402 };403 bench("insert(hint, value) (good hint, end)", [=](auto& state) { insert_good_hint_bench(true, state); });404 bench("insert(hint, value) (good hint, middle)", [=](auto& state) { insert_good_hint_bench(false, state); });405 406 auto insert_bad_hint_bench = [=](bool bench_end_iter, auto& st) {407 const std::size_t size = st.range(0);408 std::vector<Value> in = make_value_types(generate_unique_keys(size + 1));409 auto skipped_val = bench_end_iter ? in.size() - 1 : in.size() / 2;410 Value to_insert = in[skipped_val];411 { // Remove the element412 std::vector<Value> tmp;413 tmp.reserve(in.size() - 1);414 for (size_t i = 0; i != in.size(); ++i)415 if (i != skipped_val)416 tmp.emplace_back(in[i]);417 in = std::move(tmp);418 }419 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));420 421 while (st.KeepRunningBatch(BatchSize)) {422 for (std::size_t i = 0; i != BatchSize; ++i) {423 auto result = c[i].insert(c[i].begin(), to_insert);424 benchmark::DoNotOptimize(result);425 benchmark::DoNotOptimize(c[i]);426 benchmark::ClobberMemory();427 }428 429 st.PauseTiming();430 for (std::size_t i = 0; i != BatchSize; ++i) {431 c[i].erase(get_key(to_insert));432 }433 st.ResumeTiming();434 }435 };436 437 bench("insert(hint, value) (bad hint, end)", [=](auto& state) { insert_bad_hint_bench(true, state); });438 bench("insert(hint, value) (bad hint, middle)", [=](auto& state) { insert_bad_hint_bench(false, state); });439 }440 441 bench("insert(iterator, iterator) (all new keys)", [=](auto& st) {442 const std::size_t size = st.range(0);443 std::vector<Value> in = make_value_types(generate_unique_keys(size + (size / 10)));444 445 // Populate a container with a small number of elements, that's what containers will start with.446 std::vector<Value> small;447 for (std::size_t i = 0; i != (size / 10); ++i) {448 small.push_back(in.back());449 in.pop_back();450 }451 Container c(small.begin(), small.end());452 453 for ([[maybe_unused]] auto _ : st) {454 c.insert(in.begin(), in.end());455 benchmark::DoNotOptimize(c);456 benchmark::ClobberMemory();457 458 st.PauseTiming();459 c = Container(small.begin(), small.end());460 st.ResumeTiming();461 }462 });463 464 bench("insert(iterator, iterator) (half new keys)", [=](auto& st) {465 const std::size_t size = st.range(0);466 std::vector<Value> in = make_value_types(generate_unique_keys(size));467 468 // Populate a container that already contains half the elements we'll try inserting,469 // that's what our container will start with.470 std::vector<Value> small;471 for (std::size_t i = 0; i != size / 2; ++i) {472 small.push_back(in.at(i * 2));473 }474 Container c(small.begin(), small.end());475 476 for ([[maybe_unused]] auto _ : st) {477 c.insert(in.begin(), in.end());478 benchmark::DoNotOptimize(c);479 benchmark::ClobberMemory();480 481 st.PauseTiming();482 c = Container(small.begin(), small.end());483 st.ResumeTiming();484 }485 });486 487 if constexpr (is_map_like) {488 bench("insert(iterator, iterator) (product_iterator from same type)", [=](auto& st) {489 const std::size_t size = st.range(0);490 std::vector<Value> in = make_value_types(generate_unique_keys(size + (size / 10)));491 Container source(in.begin(), in.end());492 493 Container c;494 495 for ([[maybe_unused]] auto _ : st) {496 c.insert(source.begin(), source.end());497 benchmark::DoNotOptimize(c);498 benchmark::ClobberMemory();499 500 st.PauseTiming();501 c = Container();502 st.ResumeTiming();503 }504 });505 506#if TEST_STD_VER >= 23507 bench("insert(iterator, iterator) (product_iterator from zip_view)", [=](auto& st) {508 const std::size_t size = st.range(0);509 std::vector<Key> keys = generate_unique_keys(size + (size / 10));510 std::sort(keys.begin(), keys.end());511 std::vector<typename Container::mapped_type> mapped(keys.size());512 513 auto source = std::views::zip(keys, mapped);514 515 Container c;516 517 for ([[maybe_unused]] auto _ : st) {518 c.insert(source.begin(), source.end());519 benchmark::DoNotOptimize(c);520 benchmark::ClobberMemory();521 522 st.PauseTiming();523 c = Container();524 st.ResumeTiming();525 }526 });527#endif528 }529 /////////////////////////530 // Erasure531 /////////////////////////532 bench("erase(key) (existent)", [=](auto& st) {533 const std::size_t size = st.range(0) ? st.range(0) : 1; // avoid empty container534 std::vector<Value> in = make_value_types(generate_unique_keys(size));535 Value element = in[in.size() / 2]; // pick any element536 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));537 538 while (st.KeepRunningBatch(BatchSize)) {539 for (std::size_t i = 0; i != BatchSize; ++i) {540 auto result = c[i].erase(get_key(element));541 benchmark::DoNotOptimize(result);542 benchmark::DoNotOptimize(c[i]);543 benchmark::ClobberMemory();544 }545 546 st.PauseTiming();547 for (std::size_t i = 0; i != BatchSize; ++i) {548 c[i].insert(element);549 }550 st.ResumeTiming();551 }552 });553 554 bench("erase(key) (non-existent)", [=](auto& st) {555 const std::size_t size = st.range(0);556 std::vector<Value> in = make_value_types(generate_unique_keys(size + BatchSize));557 std::vector<Key> keys;558 for (std::size_t i = 0; i != BatchSize; ++i) {559 keys.push_back(get_key(in.back()));560 in.pop_back();561 }562 Container c(in.begin(), in.end());563 564 while (st.KeepRunningBatch(BatchSize)) {565 for (std::size_t i = 0; i != BatchSize; ++i) {566 auto result = c.erase(keys[i]);567 benchmark::DoNotOptimize(result);568 benchmark::DoNotOptimize(c);569 benchmark::ClobberMemory();570 }571 572 // no cleanup required because we erased a non-existent element573 }574 });575 576 bench("erase(iterator)", [=](auto& st) {577 const std::size_t size = st.range(0) ? st.range(0) : 1; // avoid empty container578 std::vector<Value> in = make_value_types(generate_unique_keys(size));579 Value element = in[in.size() / 2]; // pick any element580 581 std::vector<Container> c;582 std::vector<typename Container::iterator> iterators;583 for (std::size_t i = 0; i != BatchSize; ++i) {584 c.push_back(Container(in.begin(), in.end()));585 iterators.push_back(c[i].find(get_key(element)));586 }587 588 while (st.KeepRunningBatch(BatchSize)) {589 for (std::size_t i = 0; i != BatchSize; ++i) {590 auto result = c[i].erase(iterators[i]);591 benchmark::DoNotOptimize(result);592 benchmark::DoNotOptimize(c[i]);593 benchmark::ClobberMemory();594 }595 596 st.PauseTiming();597 for (std::size_t i = 0; i != BatchSize; ++i) {598 iterators[i] = adapt_operations<Container>::get_iterator(c[i].insert(element));599 }600 st.ResumeTiming();601 }602 });603 604 bench("erase(iterator, iterator) (erase half the container)", [=](auto& st) {605 const std::size_t size = st.range(0);606 std::vector<Value> in = make_value_types(generate_unique_keys(size));607 Container c(in.begin(), in.end());608 609 auto first = std::next(c.begin(), c.size() / 4);610 auto last = std::next(c.begin(), 3 * (c.size() / 4));611 for ([[maybe_unused]] auto _ : st) {612 auto result = c.erase(first, last);613 benchmark::DoNotOptimize(result);614 benchmark::DoNotOptimize(c);615 benchmark::ClobberMemory();616 617 st.PauseTiming();618 c = Container(in.begin(), in.end());619 first = std::next(c.begin(), c.size() / 4);620 last = std::next(c.begin(), 3 * (c.size() / 4));621 st.ResumeTiming();622 }623 });624 625 bench("clear()", [=](auto& st) {626 const std::size_t size = st.range(0);627 std::vector<Value> in = make_value_types(generate_unique_keys(size));628 Container c(in.begin(), in.end());629 630 for ([[maybe_unused]] auto _ : st) {631 c.clear();632 benchmark::DoNotOptimize(c);633 benchmark::ClobberMemory();634 635 st.PauseTiming();636 c = Container(in.begin(), in.end());637 st.ResumeTiming();638 }639 });640 641 /////////////////////////642 // Query643 /////////////////////////644 auto with_existent_key = [=](auto func) {645 return [=](auto& st) {646 const std::size_t size = st.range(0);647 std::vector<Value> in = make_value_types(generate_unique_keys(size));648 // Pick any `BatchSize` number of elements649 std::vector<Key> keys;650 for (std::size_t i = 0; i < in.size(); i += (in.size() / BatchSize)) {651 keys.push_back(get_key(in.at(i)));652 }653 Container c(in.begin(), in.end());654 655 while (st.KeepRunningBatch(BatchSize)) {656 for (std::size_t i = 0; i != keys.size(); ++i) { // possible empty keys when Arg(0)657 auto result = func(c, keys[i]);658 benchmark::DoNotOptimize(c);659 benchmark::DoNotOptimize(result);660 benchmark::ClobberMemory();661 }662 }663 };664 };665 666 auto with_nonexistent_key = [=](auto func) {667 return [=](auto& st) {668 const std::size_t size = st.range(0);669 std::vector<Value> in = make_value_types(generate_unique_keys(size + BatchSize));670 std::vector<Key> keys;671 for (std::size_t i = 0; i != BatchSize; ++i) {672 keys.push_back(get_key(in.back()));673 in.pop_back();674 }675 Container c(in.begin(), in.end());676 677 while (st.KeepRunningBatch(BatchSize)) {678 for (std::size_t i = 0; i != BatchSize; ++i) {679 auto result = func(c, keys[i]);680 benchmark::DoNotOptimize(c);681 benchmark::DoNotOptimize(result);682 benchmark::ClobberMemory();683 }684 }685 };686 };687 688 auto find = [](Container const& c, Key const& key) { return c.find(key); };689 bench("find(key) (existent)", with_existent_key(find));690 bench("find(key) (non-existent)", with_nonexistent_key(find));691 692 auto count = [](Container const& c, Key const& key) { return c.count(key); };693 bench("count(key) (existent)", with_existent_key(count));694 bench("count(key) (non-existent)", with_nonexistent_key(count));695 696 auto contains = [](Container const& c, Key const& key) { return c.contains(key); };697 bench("contains(key) (existent)", with_existent_key(contains));698 bench("contains(key) (non-existent)", with_nonexistent_key(contains));699 700 if constexpr (is_ordered_container) {701 auto lower_bound = [](Container const& c, Key const& key) { return c.lower_bound(key); };702 bench("lower_bound(key) (existent)", with_existent_key(lower_bound));703 bench("lower_bound(key) (non-existent)", with_nonexistent_key(lower_bound));704 705 auto upper_bound = [](Container const& c, Key const& key) { return c.upper_bound(key); };706 bench("upper_bound(key) (existent)", with_existent_key(upper_bound));707 bench("upper_bound(key) (non-existent)", with_nonexistent_key(upper_bound));708 709 auto equal_range = [](Container const& c, Key const& key) { return c.equal_range(key); };710 bench("equal_range(key) (existent)", with_existent_key(equal_range));711 bench("equal_range(key) (non-existent)", with_nonexistent_key(equal_range));712 }713}714 715} // namespace support716 717#endif // TEST_BENCHMARKS_CONTAINERS_ASSOCIATIVE_CONTAINER_BENCHMARKS_H718