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