159 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++14, c++1710 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 sequences150 };151 register_benchmarks(bm, "shuffled");152 }153 154 benchmark::Initialize(&argc, argv);155 benchmark::RunSpecifiedBenchmarks();156 benchmark::Shutdown();157 return 0;158}159