236 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 <list>15#include <ranges>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_find = [](auto first, auto last, auto const& value) { return std::find(first, last, value); };24 auto std_find_if = [](auto first, auto last, auto const& value) {25 return std::find_if(first, last, [&](auto element) {26 benchmark::DoNotOptimize(element);27 return element == value;28 });29 };30 auto std_find_if_not = [](auto first, auto last, auto const& value) {31 return std::find_if_not(first, last, [&](auto element) {32 benchmark::DoNotOptimize(element);33 return element != value;34 });35 };36 37 auto ranges_find = [](auto first, auto last, auto const& value) { return std::ranges::find(first, last, value); };38 auto ranges_find_if = [](auto first, auto last, auto const& value) {39 return std::ranges::find_if(first, last, [&](auto element) {40 benchmark::DoNotOptimize(element);41 return element == value;42 });43 };44 auto ranges_find_if_not = [](auto first, auto last, auto const& value) {45 return std::ranges::find_if_not(first, last, [&](auto element) {46 benchmark::DoNotOptimize(element);47 return element != value;48 });49 };50 51 auto register_benchmarks = [&](auto bm, std::string comment) {52 // find53 bm.template operator()<std::vector<char>>("std::find(vector<char>) (" + comment + ")", std_find);54 bm.template operator()<std::vector<int>>("std::find(vector<int>) (" + comment + ")", std_find);55 bm.template operator()<std::vector<long long>>("std::find(vector<long long>) (" + comment + ")", std_find);56 bm.template operator()<std::deque<int>>("std::find(deque<int>) (" + comment + ")", std_find);57 bm.template operator()<std::list<int>>("std::find(list<int>) (" + comment + ")", std_find);58 59 bm.template operator()<std::vector<char>>("rng::find(vector<char>) (" + comment + ")", ranges_find);60 bm.template operator()<std::vector<int>>("rng::find(vector<int>) (" + comment + ")", ranges_find);61 bm.template operator()<std::deque<int>>("rng::find(deque<int>) (" + comment + ")", ranges_find);62 bm.template operator()<std::list<int>>("rng::find(list<int>) (" + comment + ")", ranges_find);63 64 // find_if65 bm.template operator()<std::vector<char>>("std::find_if(vector<char>) (" + comment + ")", std_find_if);66 bm.template operator()<std::vector<int>>("std::find_if(vector<int>) (" + comment + ")", std_find_if);67 bm.template operator()<std::deque<int>>("std::find_if(deque<int>) (" + comment + ")", std_find_if);68 bm.template operator()<std::list<int>>("std::find_if(list<int>) (" + comment + ")", std_find_if);69 70 bm.template operator()<std::vector<char>>("rng::find_if(vector<char>) (" + comment + ")", ranges_find_if);71 bm.template operator()<std::vector<int>>("rng::find_if(vector<int>) (" + comment + ")", ranges_find_if);72 bm.template operator()<std::deque<int>>("rng::find_if(deque<int>) (" + comment + ")", ranges_find_if);73 bm.template operator()<std::list<int>>("rng::find_if(list<int>) (" + comment + ")", ranges_find_if);74 75 // find_if_not76 bm.template operator()<std::vector<char>>("std::find_if_not(vector<char>) (" + comment + ")", std_find_if_not);77 bm.template operator()<std::vector<int>>("std::find_if_not(vector<int>) (" + comment + ")", std_find_if_not);78 bm.template operator()<std::deque<int>>("std::find_if_not(deque<int>) (" + comment + ")", std_find_if_not);79 bm.template operator()<std::list<int>>("std::find_if_not(list<int>) (" + comment + ")", std_find_if_not);80 81 bm.template operator()<std::vector<char>>("rng::find_if_not(vector<char>) (" + comment + ")", ranges_find_if_not);82 bm.template operator()<std::vector<int>>("rng::find_if_not(vector<int>) (" + comment + ")", ranges_find_if_not);83 bm.template operator()<std::deque<int>>("rng::find_if_not(deque<int>) (" + comment + ")", ranges_find_if_not);84 bm.template operator()<std::list<int>>("rng::find_if_not(list<int>) (" + comment + ")", ranges_find_if_not);85 };86 87 auto register_nested_container_benchmarks = [&](auto bm, std::string comment) {88 // ranges_find89 bm.template operator()<std::vector<std::vector<char>>>(90 "rng::find(join_view(vector<vector<char>>)) (" + comment + ")", ranges_find);91 bm.template operator()<std::vector<std::vector<int>>>(92 "rng::find(join_view(vector<vector<int>>)) (" + comment + ")", ranges_find);93 bm.template operator()<std::list<std::vector<int>>>(94 "rng::find(join_view(list<vector<int>>)) (" + comment + ")", ranges_find);95 bm.template operator()<std::vector<std::list<int>>>(96 "rng::find(join_view(vector<list<int>>)) (" + comment + ")", ranges_find);97 bm.template operator()<std::deque<std::deque<int>>>(98 "rng::find(join_view(deque<deque<int>>)) (" + comment + ")", ranges_find);99 };100 101 // Benchmark {std,ranges}::{find,find_if,find_if_not}(normal container) where we102 // bail out after 25% of elements103 {104 auto bm = []<class Container>(std::string name, auto find) {105 benchmark::RegisterBenchmark(106 name,107 [find](auto& st) {108 std::size_t const size = st.range(0);109 using ValueType = typename Container::value_type;110 ValueType x = Generate<ValueType>::random();111 ValueType y = random_different_from({x});112 Container c(size, x);113 114 // put the element we're searching for at 25% of the sequence115 *std::next(c.begin(), size / 4) = y;116 117 for ([[maybe_unused]] auto _ : st) {118 benchmark::DoNotOptimize(c);119 benchmark::DoNotOptimize(y);120 auto result = find(c.begin(), c.end(), y);121 benchmark::DoNotOptimize(result);122 }123 })124 ->Arg(8)125 ->Arg(1024)126 ->Arg(8192)127 ->Arg(1 << 15);128 };129 register_benchmarks(bm, "bail 25%");130 }131 132 // Benchmark {std,ranges}::{find,find_if,find_if_not}(normal container) where we process the whole sequence133 {134 auto bm = []<class Container>(std::string name, auto find) {135 benchmark::RegisterBenchmark(136 name,137 [find](auto& st) {138 std::size_t const size = st.range(0);139 using ValueType = typename Container::value_type;140 ValueType x = Generate<ValueType>::random();141 ValueType y = random_different_from({x});142 Container c(size, x);143 144 for ([[maybe_unused]] auto _ : st) {145 benchmark::DoNotOptimize(c);146 benchmark::DoNotOptimize(y);147 auto result = find(c.begin(), c.end(), y);148 benchmark::DoNotOptimize(result);149 }150 })151 ->Arg(8)152 ->Arg(50) // non power-of-two153 ->Arg(1024)154 ->Arg(8192)155 ->Arg(1 << 15);156 };157 register_benchmarks(bm, "process all");158 }159 160 // Benchmark {std,ranges}::{find,find_if,find_if_not}(join(normal container)) where we process the whole sequence161 {162 auto bm = []<class Container>(std::string name, auto find) {163 benchmark::RegisterBenchmark(164 name,165 [find](auto& st) {166 std::size_t const size = st.range(0);167 std::size_t const seg_size = 256;168 std::size_t const segments = (size + seg_size - 1) / seg_size;169 using C1 = typename Container::value_type;170 using ValueType = typename C1::value_type;171 ValueType x = Generate<ValueType>::random();172 ValueType y = random_different_from({x});173 Container c(segments);174 auto n = size;175 for (auto it = c.begin(); it != c.end(); it++) {176 it->resize(std::min(seg_size, n), x);177 n -= it->size();178 }179 180 auto view = c | std::views::join;181 182 for ([[maybe_unused]] auto _ : st) {183 benchmark::DoNotOptimize(c);184 benchmark::DoNotOptimize(y);185 auto result = find(view.begin(), view.end(), y);186 benchmark::DoNotOptimize(result);187 }188 })189 ->Arg(8)190 ->Arg(50) // non power-of-two191 ->Arg(1024)192 ->Arg(8192)193 ->Arg(1 << 15);194 };195 register_nested_container_benchmarks(bm, "process all");196 }197 198 // Benchmark {std,ranges}::{find,find_if,find_if_not}(vector<bool>) where we process the whole sequence199 {200 auto bm = [](std::string name, auto find) {201 benchmark::RegisterBenchmark(202 name,203 [find](auto& st) {204 std::size_t const size = st.range(0);205 std::vector<bool> c(size, true);206 bool y = false;207 208 for ([[maybe_unused]] auto _ : st) {209 benchmark::DoNotOptimize(c);210 benchmark::DoNotOptimize(y);211 auto result = find(c.begin(), c.end(), y);212 benchmark::DoNotOptimize(result);213 }214 })215 ->Arg(8)216 ->Arg(50) // non power-of-two217 ->Arg(1024)218 ->Arg(8192)219 ->Arg(1 << 20);220 };221 bm("std::find(vector<bool>) (process all)", std_find);222 bm("rng::find(vector<bool>) (process all)", ranges_find);223 224 bm("std::find_if(vector<bool>) (process all)", std_find_if);225 bm("rng::find_if(vector<bool>) (process all)", ranges_find_if);226 227 bm("std::find_if_not(vector<bool>) (process all)", std_find_if_not);228 bm("rng::find_if_not(vector<bool>) (process all)", ranges_find_if_not);229 }230 231 benchmark::Initialize(&argc, argv);232 benchmark::RunSpecifiedBenchmarks();233 benchmark::Shutdown();234 return 0;235}236