227 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 <cassert>13#include <cstddef>14#include <deque>15#include <forward_list>16#include <list>17#include <string>18#include <vector>19 20#include <benchmark/benchmark.h>21#include "../../GenerateInput.h"22 23int main(int argc, char** argv) {24 auto std_find_end = [](auto first1, auto last1, auto first2, auto last2) {25 return std::find_end(first1, last1, first2, last2);26 };27 auto std_find_end_pred = [](auto first1, auto last1, auto first2, auto last2) {28 return std::find_end(first1, last1, first2, last2, [](auto x, auto y) {29 benchmark::DoNotOptimize(x);30 benchmark::DoNotOptimize(y);31 return x == y;32 });33 };34 auto ranges_find_end_pred = [](auto first1, auto last1, auto first2, auto last2) {35 return std::ranges::find_end(first1, last1, first2, last2, [](auto x, auto y) {36 benchmark::DoNotOptimize(x);37 benchmark::DoNotOptimize(y);38 return x == y;39 });40 };41 42 auto register_benchmarks = [&](auto bm, std::string comment) {43 // {std,ranges}::find_end(it1, it1, it2, it2)44 bm.template operator()<std::vector<int>>("std::find_end(vector<int>) (" + comment + ")", std_find_end);45 bm.template operator()<std::deque<int>>("std::find_end(deque<int>) (" + comment + ")", std_find_end);46 bm.template operator()<std::list<int>>("std::find_end(list<int>) (" + comment + ")", std_find_end);47 bm.template operator()<std::forward_list<int>>("std::find_end(forward_list<int>) (" + comment + ")", std_find_end);48 bm.template operator()<std::vector<int>>("rng::find_end(vector<int>) (" + comment + ")", std::ranges::find_end);49 bm.template operator()<std::deque<int>>("rng::find_end(deque<int>) (" + comment + ")", std::ranges::find_end);50 bm.template operator()<std::list<int>>("rng::find_end(list<int>) (" + comment + ")", std::ranges::find_end);51 bm.template operator()<std::forward_list<int>>(52 "rng::find_end(forward_list<int>) (" + comment + ")", std::ranges::find_end);53 54 // {std,ranges}::find_end(it1, it1, it2, it2, pred)55 bm.template operator()<std::vector<int>>("std::find_end(vector<int>, pred) (" + comment + ")", std_find_end_pred);56 bm.template operator()<std::deque<int>>("std::find_end(deque<int>, pred) (" + comment + ")", std_find_end_pred);57 bm.template operator()<std::list<int>>("std::find_end(list<int>, pred) (" + comment + ")", std_find_end_pred);58 bm.template operator()<std::forward_list<int>>(59 "std::find_end(forward_list<int>, pred) (" + comment + ")", std_find_end_pred);60 bm.template operator()<std::vector<int>>(61 "rng::find_end(vector<int>, pred) (" + comment + ")", ranges_find_end_pred);62 bm.template operator()<std::deque<int>>("rng::find_end(deque<int>, pred) (" + comment + ")", ranges_find_end_pred);63 bm.template operator()<std::list<int>>("rng::find_end(list<int>, pred) (" + comment + ")", ranges_find_end_pred);64 bm.template operator()<std::forward_list<int>>(65 "rng::find_end(forward_list<int>, pred) (" + comment + ")", ranges_find_end_pred);66 };67 68 // Benchmark {std,ranges}::find_end where we never find the needle, which is the69 // worst case.70 {71 auto bm = []<class Container>(std::string name, auto find_end) {72 benchmark::RegisterBenchmark(73 name,74 [find_end](auto& st) {75 std::size_t const size = st.range(0);76 using ValueType = typename Container::value_type;77 ValueType x = Generate<ValueType>::random();78 ValueType y = random_different_from({x});79 Container haystack(size, x);80 std::size_t n = size / 10; // needle size is 10% of the haystack, but we'll never find it81 assert(n > 0);82 Container needle(n, y);83 84 for ([[maybe_unused]] auto _ : st) {85 benchmark::DoNotOptimize(haystack);86 benchmark::DoNotOptimize(needle);87 auto result = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());88 benchmark::DoNotOptimize(result);89 }90 })91 ->Arg(1000) // non power-of-two92 ->Arg(1024)93 ->Arg(8192)94 ->Arg(1 << 20);95 };96 register_benchmarks(bm, "process all");97 }98 99 // Benchmark {std,ranges}::find_end where we intersperse "near matches" inside the haystack.100 {101 auto bm = []<class Container>(std::string name, auto find_end) {102 benchmark::RegisterBenchmark(103 name,104 [find_end](auto& st) {105 std::size_t const size = st.range(0);106 using ValueType = typename Container::value_type;107 ValueType x = Generate<ValueType>::random();108 ValueType y = random_different_from({x});109 Container haystack(size, x);110 std::size_t n = size / 10; // needle size is 10% of the haystack111 assert(n > 0);112 Container needle(n, y);113 114 // intersperse near-matches inside the haystack115 {116 auto first = haystack.begin();117 for (int i = 0; i != 10; ++i) {118 first = std::copy_n(needle.begin(), n - 1, first);119 ++first; // this causes the subsequence not to match because it has length n-1120 }121 }122 123 for ([[maybe_unused]] auto _ : st) {124 benchmark::DoNotOptimize(haystack);125 benchmark::DoNotOptimize(needle);126 auto result = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());127 benchmark::DoNotOptimize(result);128 }129 })130 ->Arg(1000) // non power-of-two131 ->Arg(1024)132 ->Arg(8192);133 };134 register_benchmarks(bm, "near matches");135 }136 137 // Special case: the two ranges are the same length (and they are equal, which is the worst case).138 {139 auto bm = []<class Container>(std::string name, auto find_end) {140 benchmark::RegisterBenchmark(141 name,142 [find_end](auto& st) {143 std::size_t const size = st.range(0);144 using ValueType = typename Container::value_type;145 ValueType x = Generate<ValueType>::random();146 Container haystack(size, x);147 Container needle(size, x);148 149 for ([[maybe_unused]] auto _ : st) {150 benchmark::DoNotOptimize(haystack);151 benchmark::DoNotOptimize(needle);152 auto result = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());153 benchmark::DoNotOptimize(result);154 }155 })156 ->Arg(1000) // non power-of-two157 ->Arg(1024)158 ->Arg(8192);159 };160 register_benchmarks(bm, "same length");161 }162 163 // Special case: the needle contains a single element (which we never find, i.e. the worst case).164 {165 auto bm = []<class Container>(std::string name, auto find_end) {166 benchmark::RegisterBenchmark(167 name,168 [find_end](auto& st) {169 std::size_t const size = st.range(0);170 using ValueType = typename Container::value_type;171 ValueType x = Generate<ValueType>::random();172 ValueType y = random_different_from({x});173 Container haystack(size, x);174 Container needle(1, y);175 176 for ([[maybe_unused]] auto _ : st) {177 benchmark::DoNotOptimize(haystack);178 benchmark::DoNotOptimize(needle);179 auto result = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());180 benchmark::DoNotOptimize(result);181 }182 })183 ->Arg(1000) // non power-of-two184 ->Arg(1024)185 ->Arg(8192);186 };187 register_benchmarks(bm, "single element");188 }189 190 // Special case: we have a match close to the end of the haystack (ideal case if we start searching from the end).191 {192 auto bm = []<class Container>(std::string name, auto find_end) {193 benchmark::RegisterBenchmark(194 name,195 [find_end](auto& st) {196 std::size_t const size = st.range(0);197 using ValueType = typename Container::value_type;198 ValueType x = Generate<ValueType>::random();199 ValueType y = random_different_from({x});200 Container haystack(size, x);201 std::size_t n = size / 10; // needle size is 10% of the haystack202 assert(n > 0);203 Container needle(n, y);204 205 // put the needle at 90% of the haystack206 std::ranges::copy(needle, std::next(haystack.begin(), (9 * size) / 10));207 208 for ([[maybe_unused]] auto _ : st) {209 benchmark::DoNotOptimize(haystack);210 benchmark::DoNotOptimize(needle);211 auto result = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());212 benchmark::DoNotOptimize(result);213 }214 })215 ->Arg(1000) // non power-of-two216 ->Arg(1024)217 ->Arg(8192);218 };219 register_benchmarks(bm, "match near end");220 }221 222 benchmark::Initialize(&argc, argv);223 benchmark::RunSpecifiedBenchmarks();224 benchmark::Shutdown();225 return 0;226}227