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// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11#include <algorithm>
12#include <cstddef>
13#include <deque>
14#include <iterator>
15#include <list>
16#include <string>
17#include <vector>
18
19#include "benchmark/benchmark.h"
20#include "../../GenerateInput.h"
21
22int main(int argc, char** argv) {
23 auto std_remove = [](auto first, auto last, auto const& value) { return std::remove(first, last, value); };
24 auto std_remove_if = [](auto first, auto last, auto const& value) {
25 return std::remove_if(first, last, [&](auto element) {
26 benchmark::DoNotOptimize(element);
27 return element == value;
28 });
29 };
30 auto ranges_remove_if = [](auto first, auto last, auto const& value) {
31 return std::ranges::remove_if(first, last, [&](auto element) {
32 benchmark::DoNotOptimize(element);
33 return element == value;
34 });
35 };
36
37 // Benchmark {std,ranges}::{remove,remove_if} on a sequence of the form xxxxxxxxxxyyyyyyyyyy
38 // where we remove the prefix of x's from the sequence.
39 //
40 // We perform this benchmark in a batch because we need to restore the
41 // state of the container after the operation.
42 {
43 auto bm = []<class Container>(std::string name, auto remove) {
44 benchmark::RegisterBenchmark(
45 name,
46 [remove](auto& st) {
47 std::size_t const size = st.range(0);
48 constexpr std::size_t BatchSize = 10;
49 using ValueType = typename Container::value_type;
50 Container c[BatchSize];
51 ValueType x = Generate<ValueType>::random();
52 ValueType y = random_different_from({x});
53 auto populate = [&](Container& cont) {
54 auto half = cont.size() / 2;
55 std::fill_n(std::fill_n(cont.begin(), half, x), half, y);
56 };
57 for (std::size_t i = 0; i != BatchSize; ++i) {
58 c[i] = Container(size);
59 populate(c[i]);
60 }
61
62 while (st.KeepRunningBatch(BatchSize)) {
63 for (std::size_t i = 0; i != BatchSize; ++i) {
64 benchmark::DoNotOptimize(c[i]);
65 benchmark::DoNotOptimize(x);
66 auto result = remove(c[i].begin(), c[i].end(), x);
67 benchmark::DoNotOptimize(result);
68 }
69
70 st.PauseTiming();
71 for (std::size_t i = 0; i != BatchSize; ++i) {
72 populate(c[i]);
73 }
74 st.ResumeTiming();
75 }
76 })
77 ->Arg(32)
78 ->Arg(50) // non power-of-two
79 ->Arg(1024)
80 ->Arg(8192);
81 };
82 // {std,ranges}::remove
83 bm.operator()<std::vector<int>>(name: "std::remove(vector<int>) (prefix)", remove: std_remove);
84 bm.operator()<std::deque<int>>(name: "std::remove(deque<int>) (prefix)", remove: std_remove);
85 bm.operator()<std::list<int>>(name: "std::remove(list<int>) (prefix)", remove: std_remove);
86 bm.operator()<std::vector<int>>("rng::remove(vector<int>) (prefix)", std::ranges::remove);
87 bm.operator()<std::deque<int>>("rng::remove(deque<int>) (prefix)", std::ranges::remove);
88 bm.operator()<std::list<int>>("rng::remove(list<int>) (prefix)", std::ranges::remove);
89
90 // {std,ranges}::remove_if
91 bm.operator()<std::vector<int>>(name: "std::remove_if(vector<int>) (prefix)", remove: std_remove_if);
92 bm.operator()<std::deque<int>>(name: "std::remove_if(deque<int>) (prefix)", remove: std_remove_if);
93 bm.operator()<std::list<int>>(name: "std::remove_if(list<int>) (prefix)", remove: std_remove_if);
94 bm.operator()<std::vector<int>>(name: "rng::remove_if(vector<int>) (prefix)", remove: ranges_remove_if);
95 bm.operator()<std::deque<int>>(name: "rng::remove_if(deque<int>) (prefix)", remove: ranges_remove_if);
96 bm.operator()<std::list<int>>(name: "rng::remove_if(list<int>) (prefix)", remove: ranges_remove_if);
97 }
98
99 // Benchmark {std,ranges}::remove on a sequence of the form xyxyxyxyxyxyxyxyxyxy
100 // where we remove the x's from the sequence.
101 //
102 // We perform this benchmark in a batch because we need to restore the
103 // state of the container after the operation.
104 {
105 auto bm = []<class Container>(std::string name, auto remove) {
106 benchmark::RegisterBenchmark(
107 name,
108 [remove](auto& st) {
109 std::size_t const size = st.range(0);
110 constexpr std::size_t BatchSize = 10;
111 using ValueType = typename Container::value_type;
112 Container c[BatchSize];
113 ValueType x = Generate<ValueType>::random();
114 ValueType y = random_different_from({x});
115 auto populate = [&](Container& cont) {
116 auto out = cont.begin();
117 for (std::size_t i = 0; i != cont.size(); ++i) {
118 *out++ = (i % 2 == 0 ? x : y);
119 }
120 };
121 for (std::size_t i = 0; i != BatchSize; ++i) {
122 c[i] = Container(size);
123 populate(c[i]);
124 }
125
126 while (st.KeepRunningBatch(BatchSize)) {
127 for (std::size_t i = 0; i != BatchSize; ++i) {
128 benchmark::DoNotOptimize(c[i]);
129 benchmark::DoNotOptimize(x);
130 auto result = remove(c[i].begin(), c[i].end(), x);
131 benchmark::DoNotOptimize(result);
132 }
133
134 st.PauseTiming();
135 for (std::size_t i = 0; i != BatchSize; ++i) {
136 populate(c[i]);
137 }
138 st.ResumeTiming();
139 }
140 })
141 ->Arg(32)
142 ->Arg(50) // non power-of-two
143 ->Arg(1024)
144 ->Arg(8192);
145 };
146 // {std,ranges}::remove
147 bm.operator()<std::vector<int>>(name: "std::remove(vector<int>) (sprinkled)", remove: std_remove);
148 bm.operator()<std::deque<int>>(name: "std::remove(deque<int>) (sprinkled)", remove: std_remove);
149 bm.operator()<std::list<int>>(name: "std::remove(list<int>) (sprinkled)", remove: std_remove);
150 bm.operator()<std::vector<int>>("rng::remove(vector<int>) (sprinkled)", std::ranges::remove);
151 bm.operator()<std::deque<int>>("rng::remove(deque<int>) (sprinkled)", std::ranges::remove);
152 bm.operator()<std::list<int>>("rng::remove(list<int>) (sprinkled)", std::ranges::remove);
153
154 // {std,ranges}::remove_if
155 bm.operator()<std::vector<int>>(name: "std::remove_if(vector<int>) (sprinkled)", remove: std_remove_if);
156 bm.operator()<std::deque<int>>(name: "std::remove_if(deque<int>) (sprinkled)", remove: std_remove_if);
157 bm.operator()<std::list<int>>(name: "std::remove_if(list<int>) (sprinkled)", remove: std_remove_if);
158 bm.operator()<std::vector<int>>(name: "rng::remove_if(vector<int>) (sprinkled)", remove: ranges_remove_if);
159 bm.operator()<std::deque<int>>(name: "rng::remove_if(deque<int>) (sprinkled)", remove: ranges_remove_if);
160 bm.operator()<std::list<int>>(name: "rng::remove_if(list<int>) (sprinkled)", remove: ranges_remove_if);
161 }
162
163 benchmark::Initialize(&argc, argv);
164 benchmark::RunSpecifiedBenchmarks();
165 benchmark::Shutdown();
166 return 0;
167}
168

source code of libcxx/test/benchmarks/algorithms/modifying/remove.bench.cpp