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, c++20
10
11#include <algorithm>
12#include <cstddef>
13#include <deque>
14#include <forward_list>
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 ranges_find_last_if = [](auto first, auto last, auto const& value) {
24 return std::ranges::find_last_if(first, last, [&](auto element) {
25 benchmark::DoNotOptimize(element);
26 return element == value;
27 });
28 };
29 auto ranges_find_last_if_not = [](auto first, auto last, auto const& value) {
30 return std::ranges::find_last_if_not(first, last, [&](auto element) {
31 benchmark::DoNotOptimize(element);
32 return element != value;
33 });
34 };
35
36 // Benchmark ranges::{find_last,find_last_if,find_last_if_not} where the last element
37 // is found 10% into the sequence
38 {
39 auto bm = []<class Container>(std::string name, auto find_last) {
40 benchmark::RegisterBenchmark(
41 name,
42 [find_last](auto& st) {
43 std::size_t const size = st.range(0);
44 using ValueType = typename Container::value_type;
45 ValueType x = Generate<ValueType>::random();
46 ValueType y = random_different_from({x});
47 Container c(size, x);
48
49 // put the element we're searching for at 10% of the sequence
50 *std::next(c.begin(), size / 10) = y;
51
52 for ([[maybe_unused]] auto _ : st) {
53 benchmark::DoNotOptimize(c);
54 benchmark::DoNotOptimize(y);
55 auto result = find_last(c.begin(), c.end(), y);
56 benchmark::DoNotOptimize(result);
57 }
58 })
59 ->Arg(8)
60 ->Arg(50) // non power-of-two
61 ->Arg(1024)
62 ->Arg(8192)
63 ->Arg(1 << 20);
64 };
65
66 // find_last
67 bm.operator()<std::vector<char>>("rng::find_last(vector<char>) (bail 10%)", std::ranges::find_last);
68 bm.operator()<std::vector<int>>("rng::find_last(vector<int>) (bail 10%)", std::ranges::find_last);
69 bm.operator()<std::deque<int>>("rng::find_last(deque<int>) (bail 10%)", std::ranges::find_last);
70 bm.operator()<std::list<int>>("rng::find_last(list<int>) (bail 10%)", std::ranges::find_last);
71 bm.operator()<std::forward_list<int>>("rng::find_last(forward_list<int>) (bail 10%)", std::ranges::find_last);
72
73 // find_last_if
74 bm.operator()<std::vector<char>>(name: "rng::find_last_if(vector<char>) (bail 10%)", find_last: ranges_find_last_if);
75 bm.operator()<std::vector<int>>(name: "rng::find_last_if(vector<int>) (bail 10%)", find_last: ranges_find_last_if);
76 bm.operator()<std::deque<int>>(name: "rng::find_last_if(deque<int>) (bail 10%)", find_last: ranges_find_last_if);
77 bm.operator()<std::list<int>>(name: "rng::find_last_if(list<int>) (bail 10%)", find_last: ranges_find_last_if);
78 bm.operator()<std::forward_list<int>>(name: "rng::find_last_if(forward_list<int>) (bail 10%)", find_last: ranges_find_last_if);
79
80 // find_last_if_not
81 bm.operator()<std::vector<char>>(name: "rng::find_last_if_not(vector<char>) (bail 10%)", find_last: ranges_find_last_if_not);
82 bm.operator()<std::vector<int>>(name: "rng::find_last_if_not(vector<int>) (bail 10%)", find_last: ranges_find_last_if_not);
83 bm.operator()<std::deque<int>>(name: "rng::find_last_if_not(deque<int>) (bail 10%)", find_last: ranges_find_last_if_not);
84 bm.operator()<std::list<int>>(name: "rng::find_last_if_not(list<int>) (bail 10%)", find_last: ranges_find_last_if_not);
85 bm.operator()<std::forward_list<int>>(
86 name: "rng::find_last_if_not(forward_list<int>) (bail 10%)", find_last: ranges_find_last_if_not);
87 }
88
89 // Benchmark ranges::{find_last,find_last_if,find_last_if_not} where the last element
90 // is found 90% into the sequence (i.e. near the end)
91 {
92 auto bm = []<class Container>(std::string name, auto find_last) {
93 benchmark::RegisterBenchmark(
94 name,
95 [find_last](auto& st) {
96 std::size_t const size = st.range(0);
97 using ValueType = typename Container::value_type;
98 ValueType x = Generate<ValueType>::random();
99 ValueType y = random_different_from({x});
100 Container c(size, x);
101
102 // put the element we're searching for at 90% of the sequence
103 *std::next(c.begin(), (9 * size) / 10) = y;
104
105 for ([[maybe_unused]] auto _ : st) {
106 benchmark::DoNotOptimize(c);
107 benchmark::DoNotOptimize(y);
108 auto result = find_last(c.begin(), c.end(), y);
109 benchmark::DoNotOptimize(result);
110 }
111 })
112 ->Arg(8)
113 ->Arg(50) // non power-of-two
114 ->Arg(1024)
115 ->Arg(8192)
116 ->Arg(1 << 20);
117 };
118 // find_last
119 bm.operator()<std::vector<char>>("rng::find_last(vector<char>) (bail 90%)", std::ranges::find_last);
120 bm.operator()<std::vector<int>>("rng::find_last(vector<int>) (bail 90%)", std::ranges::find_last);
121 bm.operator()<std::deque<int>>("rng::find_last(deque<int>) (bail 90%)", std::ranges::find_last);
122 bm.operator()<std::list<int>>("rng::find_last(list<int>) (bail 90%)", std::ranges::find_last);
123 bm.operator()<std::forward_list<int>>("rng::find_last(forward_list<int>) (bail 90%)", std::ranges::find_last);
124
125 // find_last_if
126 bm.operator()<std::vector<char>>(name: "rng::find_last_if(vector<char>) (bail 90%)", find_last: ranges_find_last_if);
127 bm.operator()<std::vector<int>>(name: "rng::find_last_if(vector<int>) (bail 90%)", find_last: ranges_find_last_if);
128 bm.operator()<std::deque<int>>(name: "rng::find_last_if(deque<int>) (bail 90%)", find_last: ranges_find_last_if);
129 bm.operator()<std::list<int>>(name: "rng::find_last_if(list<int>) (bail 90%)", find_last: ranges_find_last_if);
130 bm.operator()<std::forward_list<int>>(name: "rng::find_last_if(forward_list<int>) (bail 90%)", find_last: ranges_find_last_if);
131
132 // find_last_if_not
133 bm.operator()<std::vector<char>>(name: "rng::find_last_if_not(vector<char>) (bail 90%)", find_last: ranges_find_last_if_not);
134 bm.operator()<std::vector<int>>(name: "rng::find_last_if_not(vector<int>) (bail 90%)", find_last: ranges_find_last_if_not);
135 bm.operator()<std::deque<int>>(name: "rng::find_last_if_not(deque<int>) (bail 90%)", find_last: ranges_find_last_if_not);
136 bm.operator()<std::list<int>>(name: "rng::find_last_if_not(list<int>) (bail 90%)", find_last: ranges_find_last_if_not);
137 bm.operator()<std::forward_list<int>>(
138 name: "rng::find_last_if_not(forward_list<int>) (bail 90%)", find_last: ranges_find_last_if_not);
139 }
140
141 benchmark::Initialize(&argc, argv);
142 benchmark::RunSpecifiedBenchmarks();
143 benchmark::Shutdown();
144 return 0;
145}
146

source code of libcxx/test/benchmarks/algorithms/nonmodifying/find_last.bench.cpp