146 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++17, c++2010 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 element37 // is found 10% into the sequence38 {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 sequence50 *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-two61 ->Arg(1024)62 ->Arg(8192)63 ->Arg(1 << 20);64 };65 66 // find_last67 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_if74 bm.operator()<std::vector<char>>("rng::find_last_if(vector<char>) (bail 10%)", ranges_find_last_if);75 bm.operator()<std::vector<int>>("rng::find_last_if(vector<int>) (bail 10%)", ranges_find_last_if);76 bm.operator()<std::deque<int>>("rng::find_last_if(deque<int>) (bail 10%)", ranges_find_last_if);77 bm.operator()<std::list<int>>("rng::find_last_if(list<int>) (bail 10%)", ranges_find_last_if);78 bm.operator()<std::forward_list<int>>("rng::find_last_if(forward_list<int>) (bail 10%)", ranges_find_last_if);79 80 // find_last_if_not81 bm.operator()<std::vector<char>>("rng::find_last_if_not(vector<char>) (bail 10%)", ranges_find_last_if_not);82 bm.operator()<std::vector<int>>("rng::find_last_if_not(vector<int>) (bail 10%)", ranges_find_last_if_not);83 bm.operator()<std::deque<int>>("rng::find_last_if_not(deque<int>) (bail 10%)", ranges_find_last_if_not);84 bm.operator()<std::list<int>>("rng::find_last_if_not(list<int>) (bail 10%)", ranges_find_last_if_not);85 bm.operator()<std::forward_list<int>>(86 "rng::find_last_if_not(forward_list<int>) (bail 10%)", ranges_find_last_if_not);87 }88 89 // Benchmark ranges::{find_last,find_last_if,find_last_if_not} where the last element90 // 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 sequence103 *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-two114 ->Arg(1024)115 ->Arg(8192)116 ->Arg(1 << 20);117 };118 // find_last119 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_if126 bm.operator()<std::vector<char>>("rng::find_last_if(vector<char>) (bail 90%)", ranges_find_last_if);127 bm.operator()<std::vector<int>>("rng::find_last_if(vector<int>) (bail 90%)", ranges_find_last_if);128 bm.operator()<std::deque<int>>("rng::find_last_if(deque<int>) (bail 90%)", ranges_find_last_if);129 bm.operator()<std::list<int>>("rng::find_last_if(list<int>) (bail 90%)", ranges_find_last_if);130 bm.operator()<std::forward_list<int>>("rng::find_last_if(forward_list<int>) (bail 90%)", ranges_find_last_if);131 132 // find_last_if_not133 bm.operator()<std::vector<char>>("rng::find_last_if_not(vector<char>) (bail 90%)", ranges_find_last_if_not);134 bm.operator()<std::vector<int>>("rng::find_last_if_not(vector<int>) (bail 90%)", ranges_find_last_if_not);135 bm.operator()<std::deque<int>>("rng::find_last_if_not(deque<int>) (bail 90%)", ranges_find_last_if_not);136 bm.operator()<std::list<int>>("rng::find_last_if_not(list<int>) (bail 90%)", ranges_find_last_if_not);137 bm.operator()<std::forward_list<int>>(138 "rng::find_last_if_not(forward_list<int>) (bail 90%)", ranges_find_last_if_not);139 }140 141 benchmark::Initialize(&argc, argv);142 benchmark::RunSpecifiedBenchmarks();143 benchmark::Shutdown();144 return 0;145}146