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
14namespace {
15void 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
30template <class FromContainer, class ToContainer, class Func>
31void 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
39template <class Func>
40void 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
50template <class Func>
51void 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
61template <class Func>
62void 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
72template <class FromContainer, class ToContainer, class Func>
73void 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
81template <class Func>
82void 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
92template <class Func>
93void 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
103template <class Func>
104void 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
114struct CopyFunctor {
115 template <class... Args>
116 auto operator()(Args... args) const {
117 std::copy(std::forward<Args>(args)...);
118 }
119} copy;
120
121struct MoveFunctor {
122 template <class... Args>
123 auto operator()(Args... args) const {
124 std::move(std::forward<Args>(args)...);
125 }
126} move;
127
128struct CopyBackwardFunctor {
129 template <class... Args>
130 auto operator()(Args... args) const {
131 std::copy_backward(std::forward<Args>(args)...);
132 }
133} copy_backward;
134
135struct MoveBackwardFunctor {
136 template <class... Args>
137 auto operator()(Args... args) const {
138 std::move_backward(std::forward<Args>(args)...);
139 }
140} move_backward;
141
142// copy
143void BM_deque_vector_copy(benchmark::State& state) { benchmark_deque_vector(state, copy); }
144BENCHMARK(BM_deque_vector_copy)->Apply(run_sizes);
145
146void BM_deque_vector_ranges_copy(benchmark::State& state) { benchmark_deque_vector(state, std::ranges::copy); }
147BENCHMARK(BM_deque_vector_ranges_copy)->Apply(run_sizes);
148
149void BM_deque_deque_copy(benchmark::State& state) { benchmark_deque_deque(state, copy); }
150BENCHMARK(BM_deque_deque_copy)->Apply(run_sizes);
151
152void BM_deque_deque_ranges_copy(benchmark::State& state) { benchmark_deque_deque(state, std::ranges::copy); }
153BENCHMARK(BM_deque_deque_ranges_copy)->Apply(run_sizes);
154
155void BM_vector_deque_copy(benchmark::State& state) { benchmark_vector_deque(state, copy); }
156BENCHMARK(BM_vector_deque_copy)->Apply(run_sizes);
157
158void BM_vector_deque_ranges_copy(benchmark::State& state) { benchmark_vector_deque(state, std::ranges::copy); }
159BENCHMARK(BM_vector_deque_ranges_copy)->Apply(run_sizes);
160
161// move
162void BM_deque_vector_move(benchmark::State& state) { benchmark_deque_vector(state, move); }
163BENCHMARK(BM_deque_vector_move)->Apply(run_sizes);
164
165void BM_deque_vector_ranges_move(benchmark::State& state) { benchmark_deque_vector(state, std::ranges::move); }
166BENCHMARK(BM_deque_vector_ranges_move)->Apply(run_sizes);
167
168void BM_deque_deque_move(benchmark::State& state) { benchmark_deque_deque(state, move); }
169BENCHMARK(BM_deque_deque_move)->Apply(run_sizes);
170
171void BM_deque_deque_ranges_move(benchmark::State& state) { benchmark_deque_deque(state, std::ranges::move); }
172BENCHMARK(BM_deque_deque_ranges_move)->Apply(run_sizes);
173
174void BM_vector_deque_move(benchmark::State& state) { benchmark_vector_deque(state, move); }
175BENCHMARK(BM_vector_deque_move)->Apply(run_sizes);
176
177void BM_vector_deque_ranges_move(benchmark::State& state) { benchmark_vector_deque(state, std::ranges::move); }
178BENCHMARK(BM_vector_deque_ranges_move)->Apply(run_sizes);
179
180// copy_backward
181void BM_deque_vector_copy_backward(benchmark::State& state) { benchmark_deque_vector_backward(state, copy_backward); }
182BENCHMARK(BM_deque_vector_copy_backward)->Apply(run_sizes);
183
184void BM_deque_vector_ranges_copy_backward(benchmark::State& state) {
185 benchmark_deque_vector_backward(state, std::ranges::copy_backward);
186}
187BENCHMARK(BM_deque_vector_ranges_copy_backward)->Apply(run_sizes);
188
189void BM_deque_deque_copy_backward(benchmark::State& state) { benchmark_deque_deque_backward(state, copy_backward); }
190BENCHMARK(BM_deque_deque_copy_backward)->Apply(run_sizes);
191
192void BM_deque_deque_ranges_copy_backward(benchmark::State& state) {
193 benchmark_deque_deque_backward(state, std::ranges::copy_backward);
194}
195BENCHMARK(BM_deque_deque_ranges_copy_backward)->Apply(run_sizes);
196
197void BM_vector_deque_copy_backward(benchmark::State& state) { benchmark_vector_deque_backward(state, copy_backward); }
198BENCHMARK(BM_vector_deque_copy_backward)->Apply(run_sizes);
199
200void BM_vector_deque_ranges_copy_backward(benchmark::State& state) {
201 benchmark_vector_deque_backward(state, std::ranges::copy_backward);
202}
203BENCHMARK(BM_vector_deque_ranges_copy_backward)->Apply(run_sizes);
204
205// move_backward
206void BM_deque_vector_move_backward(benchmark::State& state) { benchmark_deque_vector_backward(state, move_backward); }
207BENCHMARK(BM_deque_vector_move_backward)->Apply(run_sizes);
208
209void BM_deque_vector_ranges_move_backward(benchmark::State& state) {
210 benchmark_deque_vector_backward(state, std::ranges::move_backward);
211}
212BENCHMARK(BM_deque_vector_ranges_move_backward)->Apply(run_sizes);
213
214void BM_deque_deque_move_backward(benchmark::State& state) { benchmark_deque_deque_backward(state, move_backward); }
215BENCHMARK(BM_deque_deque_move_backward)->Apply(run_sizes);
216
217void BM_deque_deque_ranges_move_backward(benchmark::State& state) {
218 benchmark_deque_deque_backward(state, std::ranges::move_backward);
219}
220BENCHMARK(BM_deque_deque_ranges_move_backward)->Apply(run_sizes);
221
222void BM_vector_deque_move_backward(benchmark::State& state) { benchmark_vector_deque_backward(state, move_backward); }
223BENCHMARK(BM_vector_deque_move_backward)->Apply(run_sizes);
224
225void BM_vector_deque_ranges_move_backward(benchmark::State& state) {
226 benchmark_vector_deque_backward(state, std::ranges::move_backward);
227}
228BENCHMARK(BM_vector_deque_ranges_move_backward)->Apply(run_sizes);
229
230} // namespace
231
232BENCHMARK_MAIN();
233