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_is_permutation_3leg = [](auto first1, auto last1, auto first2, auto) {
24 return std::is_permutation(first1, last1, first2);
25 };
26 auto std_is_permutation_4leg = [](auto first1, auto last1, auto first2, auto last2) {
27 return std::is_permutation(first1, last1, first2, last2);
28 };
29 auto std_is_permutation_3leg_pred = [](auto first1, auto last1, auto first2, auto) {
30 return std::is_permutation(first1, last1, first2, [](auto x, auto y) {
31 benchmark::DoNotOptimize(x);
32 benchmark::DoNotOptimize(y);
33 return x == y;
34 });
35 };
36 auto std_is_permutation_4leg_pred = [](auto first1, auto last1, auto first2, auto last2) {
37 return std::is_permutation(first1, last1, first2, last2, [](auto x, auto y) {
38 benchmark::DoNotOptimize(x);
39 benchmark::DoNotOptimize(y);
40 return x == y;
41 });
42 };
43 auto ranges_is_permutation_4leg_pred = [](auto first1, auto last1, auto first2, auto last2) {
44 return std::ranges::is_permutation(first1, last1, first2, last2, [](auto x, auto y) {
45 benchmark::DoNotOptimize(x);
46 benchmark::DoNotOptimize(y);
47 return x == y;
48 });
49 };
50
51 auto register_benchmarks = [&](auto bm, std::string comment) {
52 // std::is_permutation(it, it, it)
53 bm.template operator()<std::vector<int>>(
54 "std::is_permutation(vector<int>) (3leg) (" + comment + ")", std_is_permutation_3leg);
55 bm.template operator()<std::deque<int>>(
56 "std::is_permutation(deque<int>) (3leg) (" + comment + ")", std_is_permutation_3leg);
57 bm.template operator()<std::list<int>>(
58 "std::is_permutation(list<int>) (3leg) (" + comment + ")", std_is_permutation_3leg);
59
60 // std::is_permutation(it, it, it, pred)
61 bm.template operator()<std::vector<int>>(
62 "std::is_permutation(vector<int>) (3leg, pred) (" + comment + ")", std_is_permutation_3leg_pred);
63 bm.template operator()<std::deque<int>>(
64 "std::is_permutation(deque<int>) (3leg, pred) (" + comment + ")", std_is_permutation_3leg_pred);
65 bm.template operator()<std::list<int>>(
66 "std::is_permutation(list<int>) (3leg, pred) (" + comment + ")", std_is_permutation_3leg_pred);
67
68 // {std,ranges}::is_permutation(it, it, it, it)
69 bm.template operator()<std::vector<int>>(
70 "std::is_permutation(vector<int>) (4leg) (" + comment + ")", std_is_permutation_4leg);
71 bm.template operator()<std::deque<int>>(
72 "std::is_permutation(deque<int>) (4leg) (" + comment + ")", std_is_permutation_4leg);
73 bm.template operator()<std::list<int>>(
74 "std::is_permutation(list<int>) (4leg) (" + comment + ")", std_is_permutation_4leg);
75 bm.template operator()<std::vector<int>>(
76 "rng::is_permutation(vector<int>) (4leg) (" + comment + ")", std::ranges::is_permutation);
77 bm.template operator()<std::deque<int>>(
78 "rng::is_permutation(deque<int>) (4leg) (" + comment + ")", std::ranges::is_permutation);
79 bm.template operator()<std::list<int>>(
80 "rng::is_permutation(list<int>) (4leg) (" + comment + ")", std::ranges::is_permutation);
81
82 // {std,ranges}::is_permutation(it, it, it, it, pred)
83 bm.template operator()<std::vector<int>>(
84 "std::is_permutation(vector<int>) (4leg, pred) (" + comment + ")", std_is_permutation_4leg_pred);
85 bm.template operator()<std::deque<int>>(
86 "std::is_permutation(deque<int>) (4leg, pred) (" + comment + ")", std_is_permutation_4leg_pred);
87 bm.template operator()<std::list<int>>(
88 "std::is_permutation(list<int>) (4leg, pred) (" + comment + ")", std_is_permutation_4leg_pred);
89 bm.template operator()<std::vector<int>>(
90 "rng::is_permutation(vector<int>) (4leg, pred) (" + comment + ")", ranges_is_permutation_4leg_pred);
91 bm.template operator()<std::deque<int>>(
92 "rng::is_permutation(deque<int>) (4leg, pred) (" + comment + ")", ranges_is_permutation_4leg_pred);
93 bm.template operator()<std::list<int>>(
94 "rng::is_permutation(list<int>) (4leg, pred) (" + comment + ")", ranges_is_permutation_4leg_pred);
95 };
96
97 // Benchmark {std,ranges}::is_permutation where both sequences share a common prefix (this can be optimized).
98 {
99 auto bm = []<class Container>(std::string name, auto is_permutation) {
100 benchmark::RegisterBenchmark(
101 name,
102 [is_permutation](auto& st) {
103 std::size_t const size = st.range(0);
104 using ValueType = typename Container::value_type;
105 ValueType x = Generate<ValueType>::random();
106 ValueType y = random_different_from({x});
107 Container c1(size, x);
108 Container c2(size, x);
109 c2.back() = y;
110
111 for ([[maybe_unused]] auto _ : st) {
112 benchmark::DoNotOptimize(c1);
113 benchmark::DoNotOptimize(c2);
114 auto result = is_permutation(c1.begin(), c1.end(), c2.begin(), c2.end());
115 benchmark::DoNotOptimize(result);
116 }
117 })
118 ->Arg(8)
119 ->Arg(1024)
120 ->Arg(8192);
121 };
122 register_benchmarks(bm, "common prefix");
123 }
124
125 // Benchmark {std,ranges}::is_permutation on fully shuffled sequences.
126 {
127 auto bm = []<class Container>(std::string name, auto is_permutation) {
128 benchmark::RegisterBenchmark(
129 name,
130 [is_permutation](auto& st) {
131 std::size_t const size = st.range(0);
132 using ValueType = typename Container::value_type;
133 std::vector<ValueType> data;
134 std::generate_n(std::back_inserter(data), size, [] { return Generate<ValueType>::random(); });
135 Container c1(data.begin(), data.end());
136
137 std::mt19937 rng;
138 std::shuffle(data.begin(), data.end(), rng);
139 Container c2(data.begin(), data.end());
140
141 for ([[maybe_unused]] auto _ : st) {
142 benchmark::DoNotOptimize(c1);
143 benchmark::DoNotOptimize(c2);
144 auto result = is_permutation(c1.begin(), c1.end(), c2.begin(), c2.end());
145 benchmark::DoNotOptimize(result);
146 }
147 })
148 ->Arg(8)
149 ->Arg(1024); // this one is very slow, no need for large sequences
150 };
151 register_benchmarks(bm, "shuffled");
152 }
153
154 benchmark::Initialize(&argc, argv);
155 benchmark::RunSpecifiedBenchmarks();
156 benchmark::Shutdown();
157 return 0;
158}
159

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