221 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 <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_search = [](auto first1, auto last1, auto first2, auto last2) {24 return std::search(first1, last1, first2, last2);25 };26 auto std_search_pred = [](auto first1, auto last1, auto first2, auto last2) {27 return std::search(first1, last1, first2, last2, [](auto x, auto y) {28 benchmark::DoNotOptimize(x);29 benchmark::DoNotOptimize(y);30 return x == y;31 });32 };33 auto ranges_search_pred = [](auto first1, auto last1, auto first2, auto last2) {34 return std::ranges::search(first1, last1, first2, last2, [](auto x, auto y) {35 benchmark::DoNotOptimize(x);36 benchmark::DoNotOptimize(y);37 return x == y;38 });39 };40 41 // Benchmark {std,ranges}::search where the needle is never found (worst case).42 {43 auto bm = []<class Container>(std::string name, auto search) {44 benchmark::RegisterBenchmark(45 name,46 [search](auto& st) {47 std::size_t const size = st.range(0);48 using ValueType = typename Container::value_type;49 ValueType x = Generate<ValueType>::random();50 ValueType y = random_different_from({x});51 Container haystack(size, x);52 Container needle(size / 10, y); // needle size is 10% of the haystack53 54 for ([[maybe_unused]] auto _ : st) {55 benchmark::DoNotOptimize(haystack);56 benchmark::DoNotOptimize(needle);57 auto result = search(haystack.begin(), haystack.end(), needle.begin(), needle.end());58 benchmark::DoNotOptimize(result);59 }60 })61 ->Arg(1000) // non power-of-two62 ->Arg(1024)63 ->Arg(8192)64 ->Arg(1 << 20);65 };66 // {std,ranges}::search67 bm.operator()<std::vector<int>>("std::search(vector<int>) (no match)", std_search);68 bm.operator()<std::deque<int>>("std::search(deque<int>) (no match)", std_search);69 bm.operator()<std::list<int>>("std::search(list<int>) (no match)", std_search);70 bm.operator()<std::vector<int>>("rng::search(vector<int>) (no match)", std::ranges::search);71 bm.operator()<std::deque<int>>("rng::search(deque<int>) (no match)", std::ranges::search);72 bm.operator()<std::list<int>>("rng::search(list<int>) (no match)", std::ranges::search);73 74 // {std,ranges}::search(pred)75 bm.operator()<std::vector<int>>("std::search(vector<int>, pred) (no match)", std_search_pred);76 bm.operator()<std::deque<int>>("std::search(deque<int>, pred) (no match)", std_search_pred);77 bm.operator()<std::list<int>>("std::search(list<int>, pred) (no match)", std_search_pred);78 bm.operator()<std::vector<int>>("rng::search(vector<int>, pred) (no match)", ranges_search_pred);79 bm.operator()<std::deque<int>>("rng::search(deque<int>, pred) (no match)", ranges_search_pred);80 bm.operator()<std::list<int>>("rng::search(list<int>, pred) (no match)", ranges_search_pred);81 }82 83 // Benchmark {std,ranges}::search where we intersperse "near matches" inside the haystack.84 {85 auto bm = []<class Container>(std::string name, auto search) {86 benchmark::RegisterBenchmark(87 name,88 [search](auto& st) {89 std::size_t const size = st.range(0);90 using ValueType = typename Container::value_type;91 ValueType x = Generate<ValueType>::random();92 ValueType y = random_different_from({x});93 Container haystack(size, x);94 std::size_t n = size / 10; // needle size is 10% of the haystack95 assert(n > 0);96 Container needle(n, y);97 98 // intersperse near-matches inside the haystack99 {100 auto first = haystack.begin();101 for (int i = 0; i != 10; ++i) {102 first = std::copy_n(needle.begin(), n - 1, first);103 ++first; // this causes the subsequence not to match because it has length n-1104 }105 }106 107 for ([[maybe_unused]] auto _ : st) {108 benchmark::DoNotOptimize(haystack);109 benchmark::DoNotOptimize(needle);110 auto result = search(haystack.begin(), haystack.end(), needle.begin(), needle.end());111 benchmark::DoNotOptimize(result);112 }113 })114 ->Arg(1000) // non power-of-two115 ->Arg(1024)116 ->Arg(8192);117 };118 // {std,ranges}::search119 bm.operator()<std::vector<int>>("std::search(vector<int>) (near matches)", std_search);120 bm.operator()<std::deque<int>>("std::search(deque<int>) (near matches)", std_search);121 bm.operator()<std::list<int>>("std::search(list<int>) (near matches)", std_search);122 bm.operator()<std::vector<int>>("rng::search(vector<int>) (near matches)", std::ranges::search);123 bm.operator()<std::deque<int>>("rng::search(deque<int>) (near matches)", std::ranges::search);124 bm.operator()<std::list<int>>("rng::search(list<int>) (near matches)", std::ranges::search);125 126 // {std,ranges}::search(pred)127 bm.operator()<std::vector<int>>("std::search(vector<int>, pred) (near matches)", std_search_pred);128 bm.operator()<std::deque<int>>("std::search(deque<int>, pred) (near matches)", std_search_pred);129 bm.operator()<std::list<int>>("std::search(list<int>, pred) (near matches)", std_search_pred);130 bm.operator()<std::vector<int>>("rng::search(vector<int>, pred) (near matches)", ranges_search_pred);131 bm.operator()<std::deque<int>>("rng::search(deque<int>, pred) (near matches)", ranges_search_pred);132 bm.operator()<std::list<int>>("rng::search(list<int>, pred) (near matches)", ranges_search_pred);133 }134 135 // Special case: the two ranges are the same length (and they are equal, which is the worst case).136 {137 auto bm = []<class Container>(std::string name, auto search) {138 benchmark::RegisterBenchmark(139 name,140 [search](auto& st) {141 std::size_t const size = st.range(0);142 using ValueType = typename Container::value_type;143 ValueType x = Generate<ValueType>::random();144 Container haystack(size, x);145 Container needle(size, x);146 147 for ([[maybe_unused]] auto _ : st) {148 benchmark::DoNotOptimize(haystack);149 benchmark::DoNotOptimize(needle);150 auto result = search(haystack.begin(), haystack.end(), needle.begin(), needle.end());151 benchmark::DoNotOptimize(result);152 }153 })154 ->Arg(1000) // non power-of-two155 ->Arg(1024)156 ->Arg(8192);157 };158 // {std,ranges}::search159 bm.operator()<std::vector<int>>("std::search(vector<int>) (same length)", std_search);160 bm.operator()<std::deque<int>>("std::search(deque<int>) (same length)", std_search);161 bm.operator()<std::list<int>>("std::search(list<int>) (same length)", std_search);162 bm.operator()<std::vector<int>>("rng::search(vector<int>) (same length)", std::ranges::search);163 bm.operator()<std::deque<int>>("rng::search(deque<int>) (same length)", std::ranges::search);164 bm.operator()<std::list<int>>("rng::search(list<int>) (same length)", std::ranges::search);165 166 // {std,ranges}::search(pred)167 bm.operator()<std::vector<int>>("std::search(vector<int>, pred) (same length)", std_search_pred);168 bm.operator()<std::deque<int>>("std::search(deque<int>, pred) (same length)", std_search_pred);169 bm.operator()<std::list<int>>("std::search(list<int>, pred) (same length)", std_search_pred);170 bm.operator()<std::vector<int>>("rng::search(vector<int>, pred) (same length)", ranges_search_pred);171 bm.operator()<std::deque<int>>("rng::search(deque<int>, pred) (same length)", ranges_search_pred);172 bm.operator()<std::list<int>>("rng::search(list<int>, pred) (same length)", ranges_search_pred);173 }174 175 // Special case: the needle contains a single element (which we never find, i.e. the worst case).176 {177 auto bm = []<class Container>(std::string name, auto search) {178 benchmark::RegisterBenchmark(179 name,180 [search](auto& st) {181 std::size_t const size = st.range(0);182 using ValueType = typename Container::value_type;183 ValueType x = Generate<ValueType>::random();184 ValueType y = random_different_from({x});185 Container haystack(size, x);186 Container needle(1, y);187 188 for ([[maybe_unused]] auto _ : st) {189 benchmark::DoNotOptimize(haystack);190 benchmark::DoNotOptimize(needle);191 auto result = search(haystack.begin(), haystack.end(), needle.begin(), needle.end());192 benchmark::DoNotOptimize(result);193 }194 })195 ->Arg(1000) // non power-of-two196 ->Arg(1024)197 ->Arg(8192);198 };199 // {std,ranges}::search200 bm.operator()<std::vector<int>>("std::search(vector<int>) (single element)", std_search);201 bm.operator()<std::deque<int>>("std::search(deque<int>) (single element)", std_search);202 bm.operator()<std::list<int>>("std::search(list<int>) (single element)", std_search);203 bm.operator()<std::vector<int>>("rng::search(vector<int>) (single element)", std::ranges::search);204 bm.operator()<std::deque<int>>("rng::search(deque<int>) (single element)", std::ranges::search);205 bm.operator()<std::list<int>>("rng::search(list<int>) (single element)", std::ranges::search);206 207 // {std,ranges}::search(pred)208 bm.operator()<std::vector<int>>("std::search(vector<int>, pred) (single element)", std_search_pred);209 bm.operator()<std::deque<int>>("std::search(deque<int>, pred) (single element)", std_search_pred);210 bm.operator()<std::list<int>>("std::search(list<int>, pred) (single element)", std_search_pred);211 bm.operator()<std::vector<int>>("rng::search(vector<int>, pred) (single element)", ranges_search_pred);212 bm.operator()<std::deque<int>>("rng::search(deque<int>, pred) (single element)", ranges_search_pred);213 bm.operator()<std::list<int>>("rng::search(list<int>, pred) (single element)", ranges_search_pred);214 }215 216 benchmark::Initialize(&argc, argv);217 benchmark::RunSpecifiedBenchmarks();218 benchmark::Shutdown();219 return 0;220}221