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_ConstructSizeValue(benchmark::State& st, Container, typename Container::value_type const& val) {
31   const auto size = st.range(0);
32   for (auto _ : st) {
33     Container c(size, val);
34     DoNotOptimizeData(c);
35   }
36 }
37 
38 template <class Container, class GenInputs>
39 void BM_ConstructIterIter(benchmark::State& st, Container, GenInputs gen) {
40     auto in = gen(st.range(0));
41     const auto begin = in.begin();
42     const auto end = in.end();
43     benchmark::DoNotOptimize(&in);
44     while (st.KeepRunning()) {
45         Container c(begin, end);
46         DoNotOptimizeData(c);
47     }
48 }
49 
50 template <class Container, class GenInputs>
51 void BM_InsertValue(benchmark::State& st, Container c, GenInputs gen) {
52     auto in = gen(st.range(0));
53     const auto end = in.end();
54     while (st.KeepRunning()) {
55         c.clear();
56         for (auto it = in.begin(); it != end; ++it) {
57             benchmark::DoNotOptimize(&(*c.insert(*it).first));
58         }
59         benchmark::ClobberMemory();
60     }
61 }
62 
63 template <class Container, class GenInputs>
64 void BM_InsertValueRehash(benchmark::State& st, Container c, GenInputs gen) {
65     auto in = gen(st.range(0));
66     const auto end = in.end();
67     while (st.KeepRunning()) {
68         c.clear();
69         c.rehash(16);
70         for (auto it = in.begin(); it != end; ++it) {
71             benchmark::DoNotOptimize(&(*c.insert(*it).first));
72         }
73         benchmark::ClobberMemory();
74     }
75 }
76 
77 
78 template <class Container, class GenInputs>
79 void BM_InsertDuplicate(benchmark::State& st, Container c, GenInputs gen) {
80     auto in = gen(st.range(0));
81     const auto end = in.end();
82     c.insert(in.begin(), in.end());
83     benchmark::DoNotOptimize(&c);
84     benchmark::DoNotOptimize(&in);
85     while (st.KeepRunning()) {
86         for (auto it = in.begin(); it != end; ++it) {
87             benchmark::DoNotOptimize(&(*c.insert(*it).first));
88         }
89         benchmark::ClobberMemory();
90     }
91 }
92 
93 
94 template <class Container, class GenInputs>
95 void BM_EmplaceDuplicate(benchmark::State& st, Container c, GenInputs gen) {
96     auto in = gen(st.range(0));
97     const auto end = in.end();
98     c.insert(in.begin(), in.end());
99     benchmark::DoNotOptimize(&c);
100     benchmark::DoNotOptimize(&in);
101     while (st.KeepRunning()) {
102         for (auto it = in.begin(); it != end; ++it) {
103             benchmark::DoNotOptimize(&(*c.emplace(*it).first));
104         }
105         benchmark::ClobberMemory();
106     }
107 }
108 
109 template <class Container, class GenInputs>
110 static void BM_Find(benchmark::State& st, Container c, GenInputs gen) {
111     auto in = gen(st.range(0));
112     c.insert(in.begin(), in.end());
113     benchmark::DoNotOptimize(&(*c.begin()));
114     const auto end = in.data() + in.size();
115     while (st.KeepRunning()) {
116         for (auto it = in.data(); it != end; ++it) {
117             benchmark::DoNotOptimize(&(*c.find(*it)));
118         }
119         benchmark::ClobberMemory();
120     }
121 }
122 
123 template <class Container, class GenInputs>
124 static void BM_FindRehash(benchmark::State& st, Container c, GenInputs gen) {
125     c.rehash(8);
126     auto in = gen(st.range(0));
127     c.insert(in.begin(), in.end());
128     benchmark::DoNotOptimize(&(*c.begin()));
129     const auto end = in.data() + in.size();
130     while (st.KeepRunning()) {
131         for (auto it = in.data(); it != end; ++it) {
132             benchmark::DoNotOptimize(&(*c.find(*it)));
133         }
134         benchmark::ClobberMemory();
135     }
136 }
137 
138 } // end namespace ContainerBenchmarks
139 
140 #endif // BENCHMARK_CONTAINER_BENCHMARKS_H
141