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

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