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_copy = [](auto first, auto last, auto out, auto const& value) {
24 return std::remove_copy(first, last, out, value);
25 };
26 auto std_remove_copy_if = [](auto first, auto last, auto out, auto const& value) {
27 return std::remove_copy_if(first, last, out, [&](auto element) {
28 benchmark::DoNotOptimize(element);
29 return element == value;
30 });
31 };
32 auto ranges_remove_copy_if = [](auto first, auto last, auto out, auto const& value) {
33 return std::ranges::remove_copy_if(first, last, out, [&](auto element) {
34 benchmark::DoNotOptimize(element);
35 return element == value;
36 });
37 };
38
39 // Benchmark {std,ranges}::{remove_copy,remove_copy_if} on a sequence of the form xxxxxxxxxxyyyyyyyyyy
40 // where we remove the prefix of x's from the sequence.
41 {
42 auto bm = []<class Container>(std::string name, auto remove_copy) {
43 benchmark::RegisterBenchmark(
44 name,
45 [remove_copy](auto& st) {
46 std::size_t const size = st.range(0);
47 using ValueType = typename Container::value_type;
48 Container c;
49 ValueType x = Generate<ValueType>::random();
50 ValueType y = random_different_from({x});
51 std::fill_n(std::back_inserter(c), size / 2, x);
52 std::fill_n(std::back_inserter(c), size / 2, y);
53
54 std::vector<ValueType> out(size);
55
56 for ([[maybe_unused]] auto _ : st) {
57 benchmark::DoNotOptimize(c);
58 benchmark::DoNotOptimize(out);
59 benchmark::DoNotOptimize(x);
60 auto result = remove_copy(c.begin(), c.end(), out.begin(), x);
61 benchmark::DoNotOptimize(result);
62 }
63 })
64 ->Arg(32)
65 ->Arg(50) // non power-of-two
66 ->Arg(1024)
67 ->Arg(8192);
68 };
69 // {std,ranges}::remove_copy
70 bm.operator()<std::vector<int>>(name: "std::remove_copy(vector<int>) (prefix)", remove_copy: std_remove_copy);
71 bm.operator()<std::deque<int>>(name: "std::remove_copy(deque<int>) (prefix)", remove_copy: std_remove_copy);
72 bm.operator()<std::list<int>>(name: "std::remove_copy(list<int>) (prefix)", remove_copy: std_remove_copy);
73 bm.operator()<std::vector<int>>("rng::remove_copy(vector<int>) (prefix)", std::ranges::remove_copy);
74 bm.operator()<std::deque<int>>("rng::remove_copy(deque<int>) (prefix)", std::ranges::remove_copy);
75 bm.operator()<std::list<int>>("rng::remove_copy(list<int>) (prefix)", std::ranges::remove_copy);
76
77 // {std,ranges}::remove_copy_if
78 bm.operator()<std::vector<int>>(name: "std::remove_copy_if(vector<int>) (prefix)", remove_copy: std_remove_copy_if);
79 bm.operator()<std::deque<int>>(name: "std::remove_copy_if(deque<int>) (prefix)", remove_copy: std_remove_copy_if);
80 bm.operator()<std::list<int>>(name: "std::remove_copy_if(list<int>) (prefix)", remove_copy: std_remove_copy_if);
81 bm.operator()<std::vector<int>>(name: "rng::remove_copy_if(vector<int>) (prefix)", remove_copy: ranges_remove_copy_if);
82 bm.operator()<std::deque<int>>(name: "rng::remove_copy_if(deque<int>) (prefix)", remove_copy: ranges_remove_copy_if);
83 bm.operator()<std::list<int>>(name: "rng::remove_copy_if(list<int>) (prefix)", remove_copy: ranges_remove_copy_if);
84 }
85
86 // Benchmark {std,ranges}::{remove_copy,remove_copy_if} on a sequence of the form xyxyxyxyxyxyxyxyxyxy
87 // where we remove the x's from the sequence.
88 {
89 auto bm = []<class Container>(std::string name, auto remove_copy) {
90 benchmark::RegisterBenchmark(
91 name,
92 [remove_copy](auto& st) {
93 std::size_t const size = st.range(0);
94 using ValueType = typename Container::value_type;
95 Container c;
96 ValueType x = Generate<ValueType>::random();
97 ValueType y = random_different_from({x});
98 for (std::size_t i = 0; i != size; ++i) {
99 c.push_back(i % 2 == 0 ? x : y);
100 }
101
102 std::vector<ValueType> out(size);
103
104 for ([[maybe_unused]] auto _ : st) {
105 benchmark::DoNotOptimize(c);
106 benchmark::DoNotOptimize(out);
107 benchmark::DoNotOptimize(x);
108 auto result = remove_copy(c.begin(), c.end(), out.begin(), x);
109 benchmark::DoNotOptimize(result);
110 }
111 })
112 ->Arg(32)
113 ->Arg(50) // non power-of-two
114 ->Arg(1024)
115 ->Arg(8192);
116 };
117 // {std,ranges}::remove_copy
118 bm.operator()<std::vector<int>>(name: "std::remove_copy(vector<int>) (sprinkled)", remove_copy: std_remove_copy);
119 bm.operator()<std::deque<int>>(name: "std::remove_copy(deque<int>) (sprinkled)", remove_copy: std_remove_copy);
120 bm.operator()<std::list<int>>(name: "std::remove_copy(list<int>) (sprinkled)", remove_copy: std_remove_copy);
121 bm.operator()<std::vector<int>>("rng::remove_copy(vector<int>) (sprinkled)", std::ranges::remove_copy);
122 bm.operator()<std::deque<int>>("rng::remove_copy(deque<int>) (sprinkled)", std::ranges::remove_copy);
123 bm.operator()<std::list<int>>("rng::remove_copy(list<int>) (sprinkled)", std::ranges::remove_copy);
124
125 // {std,ranges}::remove_copy_if
126 bm.operator()<std::vector<int>>(name: "std::remove_copy_if(vector<int>) (sprinkled)", remove_copy: std_remove_copy_if);
127 bm.operator()<std::deque<int>>(name: "std::remove_copy_if(deque<int>) (sprinkled)", remove_copy: std_remove_copy_if);
128 bm.operator()<std::list<int>>(name: "std::remove_copy_if(list<int>) (sprinkled)", remove_copy: std_remove_copy_if);
129 bm.operator()<std::vector<int>>(name: "rng::remove_copy_if(vector<int>) (sprinkled)", remove_copy: ranges_remove_copy_if);
130 bm.operator()<std::deque<int>>(name: "rng::remove_copy_if(deque<int>) (sprinkled)", remove_copy: ranges_remove_copy_if);
131 bm.operator()<std::list<int>>(name: "rng::remove_copy_if(list<int>) (sprinkled)", remove_copy: ranges_remove_copy_if);
132 }
133
134 benchmark::Initialize(&argc, argv);
135 benchmark::RunSpecifiedBenchmarks();
136 benchmark::Shutdown();
137 return 0;
138}
139

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