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
18namespace ContainerBenchmarks {
19
20template <class Container>
21void BM_ConstructSize(benchmark::State& st, Container) {
22 auto size = st.range(pos: 0);
23 for (auto _ : st) {
24 Container c(size);
25 DoNotOptimizeData(c);
26 }
27}
28
29template <class Container>
30void BM_CopyConstruct(benchmark::State& st, Container) {
31 auto size = st.range(pos: 0);
32 Container c(size);
33 for (auto _ : st) {
34 auto v = c;
35 DoNotOptimizeData(v);
36 }
37}
38
39template <class Container>
40void BM_Assignment(benchmark::State& st, Container) {
41 auto size = st.range(pos: 0);
42 Container c1;
43 Container c2(size);
44 for (auto _ : st) {
45 c1 = c2;
46 DoNotOptimizeData(c1);
47 DoNotOptimizeData(c2);
48 }
49}
50
51template <class Container>
52void BM_ConstructSizeValue(benchmark::State& st, Container, typename Container::value_type const& val) {
53 const auto size = st.range(pos: 0);
54 for (auto _ : st) {
55 Container c(size, val);
56 DoNotOptimizeData(c);
57 }
58}
59
60template <class Container, class GenInputs>
61void BM_ConstructIterIter(benchmark::State& st, Container, GenInputs gen) {
62 auto in = gen(st.range(pos: 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
72template <class Container, class GenInputs>
73void BM_ConstructFromRange(benchmark::State& st, Container, GenInputs gen) {
74 auto in = gen(st.range(pos: 0));
75 benchmark::DoNotOptimize(&in);
76 while (st.KeepRunning()) {
77 Container c(std::from_range, in);
78 DoNotOptimizeData(c);
79 }
80}
81
82template <class Container>
83void BM_Pushback_no_grow(benchmark::State& state, Container c) {
84 int count = state.range(pos: 0);
85 c.reserve(count);
86 while (state.KeepRunningBatch(n: 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
95template <class Container, class GenInputs>
96void BM_InsertValue(benchmark::State& st, Container c, GenInputs gen) {
97 auto in = gen(st.range(pos: 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
108template <class Container, class GenInputs>
109void BM_InsertValueRehash(benchmark::State& st, Container c, GenInputs gen) {
110 auto in = gen(st.range(pos: 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
122template <class Container, class GenInputs>
123void BM_InsertDuplicate(benchmark::State& st, Container c, GenInputs gen) {
124 auto in = gen(st.range(pos: 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
137template <class Container, class GenInputs>
138void BM_EmplaceDuplicate(benchmark::State& st, Container c, GenInputs gen) {
139 auto in = gen(st.range(pos: 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
152template <class Container, class GenInputs>
153static void BM_Find(benchmark::State& st, Container c, GenInputs gen) {
154 auto in = gen(st.range(pos: 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
166template <class Container, class GenInputs>
167static void BM_FindRehash(benchmark::State& st, Container c, GenInputs gen) {
168 c.rehash(8);
169 auto in = gen(st.range(pos: 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
181template <class Container, class GenInputs>
182static void BM_Rehash(benchmark::State& st, Container c, GenInputs gen) {
183 auto in = gen(st.range(pos: 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
195template <class Container, class GenInputs>
196static void BM_Compare_same_container(benchmark::State& st, Container, GenInputs gen) {
197 auto in = gen(st.range(pos: 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(value: &res);
206 benchmark::ClobberMemory();
207 }
208}
209
210template <class Container, class GenInputs>
211static void BM_Compare_different_containers(benchmark::State& st, Container, GenInputs gen) {
212 auto in1 = gen(st.range(pos: 0));
213 auto in2 = gen(st.range(pos: 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(value: &res);
222 benchmark::ClobberMemory();
223 }
224}
225
226} // end namespace ContainerBenchmarks
227
228#endif // BENCHMARK_CONTAINER_BENCHMARKS_H
229

source code of libcxx/benchmarks/ContainerBenchmarks.h