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-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include <algorithm>
10 #include <deque>
11
12 #include "benchmark/benchmark.h"
13
14 namespace {
run_sizes(auto benchmark)15 void run_sizes(auto benchmark) {
16 benchmark->Arg(0)
17 ->Arg(1)
18 ->Arg(2)
19 ->Arg(64)
20 ->Arg(512)
21 ->Arg(1024)
22 ->Arg(4000)
23 ->Arg(4096)
24 ->Arg(5500)
25 ->Arg(64000)
26 ->Arg(65536)
27 ->Arg(70000);
28 }
29
30 template <class FromContainer, class ToContainer, class Func>
benchmark_containers(benchmark::State & state,FromContainer & d,ToContainer & v,Func && func)31 void benchmark_containers(benchmark::State& state, FromContainer& d, ToContainer& v, Func&& func) {
32 for (auto _ : state) {
33 benchmark::DoNotOptimize(v);
34 benchmark::DoNotOptimize(d);
35 func(d.begin(), d.end(), v.begin());
36 }
37 }
38
39 template <class Func>
benchmark_deque_vector(benchmark::State & state,Func && func)40 void benchmark_deque_vector(benchmark::State& state, Func&& func) {
41 auto size = state.range(0);
42 std::deque<int> d;
43 d.resize(size);
44 std::ranges::fill(d, 10);
45 std::vector<int> v;
46 v.resize(size);
47 benchmark_containers(state, d, v, func);
48 }
49
50 template <class Func>
benchmark_deque_deque(benchmark::State & state,Func && func)51 void benchmark_deque_deque(benchmark::State& state, Func&& func) {
52 auto size = state.range(0);
53 std::deque<int> d;
54 d.resize(size);
55 std::ranges::fill(d, 10);
56 std::deque<int> v;
57 v.resize(size);
58 benchmark_containers(state, d, v, func);
59 }
60
61 template <class Func>
benchmark_vector_deque(benchmark::State & state,Func && func)62 void benchmark_vector_deque(benchmark::State& state, Func&& func) {
63 auto size = state.range(0);
64 std::vector<int> d;
65 d.resize(size);
66 std::ranges::fill(d, 10);
67 std::deque<int> v;
68 v.resize(size);
69 benchmark_containers(state, d, v, func);
70 }
71
72 template <class FromContainer, class ToContainer, class Func>
benchmark_containers_backward(benchmark::State & state,FromContainer & d,ToContainer & v,Func && func)73 void benchmark_containers_backward(benchmark::State& state, FromContainer& d, ToContainer& v, Func&& func) {
74 for (auto _ : state) {
75 benchmark::DoNotOptimize(v);
76 benchmark::DoNotOptimize(d);
77 func(d.begin(), d.end(), v.end());
78 }
79 }
80
81 template <class Func>
benchmark_deque_vector_backward(benchmark::State & state,Func && func)82 void benchmark_deque_vector_backward(benchmark::State& state, Func&& func) {
83 auto size = state.range(0);
84 std::deque<int> d;
85 d.resize(size);
86 std::ranges::fill(d, 10);
87 std::vector<int> v;
88 v.resize(size);
89 benchmark_containers_backward(state, d, v, func);
90 }
91
92 template <class Func>
benchmark_deque_deque_backward(benchmark::State & state,Func && func)93 void benchmark_deque_deque_backward(benchmark::State& state, Func&& func) {
94 auto size = state.range(0);
95 std::deque<int> d;
96 d.resize(size);
97 std::ranges::fill(d, 10);
98 std::deque<int> v;
99 v.resize(size);
100 benchmark_containers_backward(state, d, v, func);
101 }
102
103 template <class Func>
benchmark_vector_deque_backward(benchmark::State & state,Func && func)104 void benchmark_vector_deque_backward(benchmark::State& state, Func&& func) {
105 auto size = state.range(0);
106 std::vector<int> d;
107 d.resize(size);
108 std::ranges::fill(d, 10);
109 std::deque<int> v;
110 v.resize(size);
111 benchmark_containers_backward(state, d, v, func);
112 }
113
114 struct CopyFunctor {
115 template <class... Args>
operator ()__anon39d7b8840111::CopyFunctor116 auto operator()(Args... args) const {
117 std::copy(std::forward<Args>(args)...);
118 }
119 } copy;
120
121 struct MoveFunctor {
122 template <class... Args>
operator ()__anon39d7b8840111::MoveFunctor123 auto operator()(Args... args) const {
124 std::move(std::forward<Args>(args)...);
125 }
126 } move;
127
128 struct CopyBackwardFunctor {
129 template <class... Args>
operator ()__anon39d7b8840111::CopyBackwardFunctor130 auto operator()(Args... args) const {
131 std::copy_backward(std::forward<Args>(args)...);
132 }
133 } copy_backward;
134
135 struct MoveBackwardFunctor {
136 template <class... Args>
operator ()__anon39d7b8840111::MoveBackwardFunctor137 auto operator()(Args... args) const {
138 std::move_backward(std::forward<Args>(args)...);
139 }
140 } move_backward;
141
142 // copy
BM_deque_vector_copy(benchmark::State & state)143 void BM_deque_vector_copy(benchmark::State& state) { benchmark_deque_vector(state, copy); }
144 BENCHMARK(BM_deque_vector_copy)->Apply(run_sizes);
145
BM_deque_vector_ranges_copy(benchmark::State & state)146 void BM_deque_vector_ranges_copy(benchmark::State& state) { benchmark_deque_vector(state, std::ranges::copy); }
147 BENCHMARK(BM_deque_vector_ranges_copy)->Apply(run_sizes);
148
BM_deque_deque_copy(benchmark::State & state)149 void BM_deque_deque_copy(benchmark::State& state) { benchmark_deque_deque(state, copy); }
150 BENCHMARK(BM_deque_deque_copy)->Apply(run_sizes);
151
BM_deque_deque_ranges_copy(benchmark::State & state)152 void BM_deque_deque_ranges_copy(benchmark::State& state) { benchmark_deque_deque(state, std::ranges::copy); }
153 BENCHMARK(BM_deque_deque_ranges_copy)->Apply(run_sizes);
154
BM_vector_deque_copy(benchmark::State & state)155 void BM_vector_deque_copy(benchmark::State& state) { benchmark_vector_deque(state, copy); }
156 BENCHMARK(BM_vector_deque_copy)->Apply(run_sizes);
157
BM_vector_deque_ranges_copy(benchmark::State & state)158 void BM_vector_deque_ranges_copy(benchmark::State& state) { benchmark_vector_deque(state, std::ranges::copy); }
159 BENCHMARK(BM_vector_deque_ranges_copy)->Apply(run_sizes);
160
161 // move
BM_deque_vector_move(benchmark::State & state)162 void BM_deque_vector_move(benchmark::State& state) { benchmark_deque_vector(state, move); }
163 BENCHMARK(BM_deque_vector_move)->Apply(run_sizes);
164
BM_deque_vector_ranges_move(benchmark::State & state)165 void BM_deque_vector_ranges_move(benchmark::State& state) { benchmark_deque_vector(state, std::ranges::move); }
166 BENCHMARK(BM_deque_vector_ranges_move)->Apply(run_sizes);
167
BM_deque_deque_move(benchmark::State & state)168 void BM_deque_deque_move(benchmark::State& state) { benchmark_deque_deque(state, move); }
169 BENCHMARK(BM_deque_deque_move)->Apply(run_sizes);
170
BM_deque_deque_ranges_move(benchmark::State & state)171 void BM_deque_deque_ranges_move(benchmark::State& state) { benchmark_deque_deque(state, std::ranges::move); }
172 BENCHMARK(BM_deque_deque_ranges_move)->Apply(run_sizes);
173
BM_vector_deque_move(benchmark::State & state)174 void BM_vector_deque_move(benchmark::State& state) { benchmark_vector_deque(state, move); }
175 BENCHMARK(BM_vector_deque_move)->Apply(run_sizes);
176
BM_vector_deque_ranges_move(benchmark::State & state)177 void BM_vector_deque_ranges_move(benchmark::State& state) { benchmark_vector_deque(state, std::ranges::move); }
178 BENCHMARK(BM_vector_deque_ranges_move)->Apply(run_sizes);
179
180 // copy_backward
BM_deque_vector_copy_backward(benchmark::State & state)181 void BM_deque_vector_copy_backward(benchmark::State& state) { benchmark_deque_vector_backward(state, copy_backward); }
182 BENCHMARK(BM_deque_vector_copy_backward)->Apply(run_sizes);
183
BM_deque_vector_ranges_copy_backward(benchmark::State & state)184 void BM_deque_vector_ranges_copy_backward(benchmark::State& state) {
185 benchmark_deque_vector_backward(state, std::ranges::copy_backward);
186 }
187 BENCHMARK(BM_deque_vector_ranges_copy_backward)->Apply(run_sizes);
188
BM_deque_deque_copy_backward(benchmark::State & state)189 void BM_deque_deque_copy_backward(benchmark::State& state) { benchmark_deque_deque_backward(state, copy_backward); }
190 BENCHMARK(BM_deque_deque_copy_backward)->Apply(run_sizes);
191
BM_deque_deque_ranges_copy_backward(benchmark::State & state)192 void BM_deque_deque_ranges_copy_backward(benchmark::State& state) {
193 benchmark_deque_deque_backward(state, std::ranges::copy_backward);
194 }
195 BENCHMARK(BM_deque_deque_ranges_copy_backward)->Apply(run_sizes);
196
BM_vector_deque_copy_backward(benchmark::State & state)197 void BM_vector_deque_copy_backward(benchmark::State& state) { benchmark_vector_deque_backward(state, copy_backward); }
198 BENCHMARK(BM_vector_deque_copy_backward)->Apply(run_sizes);
199
BM_vector_deque_ranges_copy_backward(benchmark::State & state)200 void BM_vector_deque_ranges_copy_backward(benchmark::State& state) {
201 benchmark_vector_deque_backward(state, std::ranges::copy_backward);
202 }
203 BENCHMARK(BM_vector_deque_ranges_copy_backward)->Apply(run_sizes);
204
205 // move_backward
BM_deque_vector_move_backward(benchmark::State & state)206 void BM_deque_vector_move_backward(benchmark::State& state) { benchmark_deque_vector_backward(state, move_backward); }
207 BENCHMARK(BM_deque_vector_move_backward)->Apply(run_sizes);
208
BM_deque_vector_ranges_move_backward(benchmark::State & state)209 void BM_deque_vector_ranges_move_backward(benchmark::State& state) {
210 benchmark_deque_vector_backward(state, std::ranges::move_backward);
211 }
212 BENCHMARK(BM_deque_vector_ranges_move_backward)->Apply(run_sizes);
213
BM_deque_deque_move_backward(benchmark::State & state)214 void BM_deque_deque_move_backward(benchmark::State& state) { benchmark_deque_deque_backward(state, move_backward); }
215 BENCHMARK(BM_deque_deque_move_backward)->Apply(run_sizes);
216
BM_deque_deque_ranges_move_backward(benchmark::State & state)217 void BM_deque_deque_ranges_move_backward(benchmark::State& state) {
218 benchmark_deque_deque_backward(state, std::ranges::move_backward);
219 }
220 BENCHMARK(BM_deque_deque_ranges_move_backward)->Apply(run_sizes);
221
BM_vector_deque_move_backward(benchmark::State & state)222 void BM_vector_deque_move_backward(benchmark::State& state) { benchmark_vector_deque_backward(state, move_backward); }
223 BENCHMARK(BM_vector_deque_move_backward)->Apply(run_sizes);
224
BM_vector_deque_ranges_move_backward(benchmark::State & state)225 void BM_vector_deque_ranges_move_backward(benchmark::State& state) {
226 benchmark_vector_deque_backward(state, std::ranges::move_backward);
227 }
228 BENCHMARK(BM_vector_deque_ranges_move_backward)->Apply(run_sizes);
229
230 } // namespace
231
232 BENCHMARK_MAIN();
233