168 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_remove = [](auto first, auto last, auto const& value) { return std::remove(first, last, value); };24 auto std_remove_if = [](auto first, auto last, auto const& value) {25 return std::remove_if(first, last, [&](auto element) {26 benchmark::DoNotOptimize(element);27 return element == value;28 });29 };30 auto ranges_remove_if = [](auto first, auto last, auto const& value) {31 return std::ranges::remove_if(first, last, [&](auto element) {32 benchmark::DoNotOptimize(element);33 return element == value;34 });35 };36 37 // Benchmark {std,ranges}::{remove,remove_if} on a sequence of the form xxxxxxxxxxyyyyyyyyyy38 // where we remove the prefix of x's from the sequence.39 //40 // We perform this benchmark in a batch because we need to restore the41 // state of the container after the operation.42 {43 auto bm = []<class Container>(std::string name, auto remove) {44 benchmark::RegisterBenchmark(45 name,46 [remove](auto& st) {47 std::size_t const size = st.range(0);48 constexpr std::size_t BatchSize = 10;49 using ValueType = typename Container::value_type;50 Container c[BatchSize];51 ValueType x = Generate<ValueType>::random();52 ValueType y = random_different_from({x});53 auto populate = [&](Container& cont) {54 auto half = cont.size() / 2;55 std::fill_n(std::fill_n(cont.begin(), half, x), half, y);56 };57 for (std::size_t i = 0; i != BatchSize; ++i) {58 c[i] = Container(size);59 populate(c[i]);60 }61 62 while (st.KeepRunningBatch(BatchSize)) {63 for (std::size_t i = 0; i != BatchSize; ++i) {64 benchmark::DoNotOptimize(c[i]);65 benchmark::DoNotOptimize(x);66 auto result = remove(c[i].begin(), c[i].end(), x);67 benchmark::DoNotOptimize(result);68 }69 70 st.PauseTiming();71 for (std::size_t i = 0; i != BatchSize; ++i) {72 populate(c[i]);73 }74 st.ResumeTiming();75 }76 })77 ->Arg(32)78 ->Arg(50) // non power-of-two79 ->Arg(1024)80 ->Arg(8192);81 };82 // {std,ranges}::remove83 bm.operator()<std::vector<int>>("std::remove(vector<int>) (prefix)", std_remove);84 bm.operator()<std::deque<int>>("std::remove(deque<int>) (prefix)", std_remove);85 bm.operator()<std::list<int>>("std::remove(list<int>) (prefix)", std_remove);86 bm.operator()<std::vector<int>>("rng::remove(vector<int>) (prefix)", std::ranges::remove);87 bm.operator()<std::deque<int>>("rng::remove(deque<int>) (prefix)", std::ranges::remove);88 bm.operator()<std::list<int>>("rng::remove(list<int>) (prefix)", std::ranges::remove);89 90 // {std,ranges}::remove_if91 bm.operator()<std::vector<int>>("std::remove_if(vector<int>) (prefix)", std_remove_if);92 bm.operator()<std::deque<int>>("std::remove_if(deque<int>) (prefix)", std_remove_if);93 bm.operator()<std::list<int>>("std::remove_if(list<int>) (prefix)", std_remove_if);94 bm.operator()<std::vector<int>>("rng::remove_if(vector<int>) (prefix)", ranges_remove_if);95 bm.operator()<std::deque<int>>("rng::remove_if(deque<int>) (prefix)", ranges_remove_if);96 bm.operator()<std::list<int>>("rng::remove_if(list<int>) (prefix)", ranges_remove_if);97 }98 99 // Benchmark {std,ranges}::remove on a sequence of the form xyxyxyxyxyxyxyxyxyxy100 // where we remove the x's from the sequence.101 //102 // We perform this benchmark in a batch because we need to restore the103 // state of the container after the operation.104 {105 auto bm = []<class Container>(std::string name, auto remove) {106 benchmark::RegisterBenchmark(107 name,108 [remove](auto& st) {109 std::size_t const size = st.range(0);110 constexpr std::size_t BatchSize = 10;111 using ValueType = typename Container::value_type;112 Container c[BatchSize];113 ValueType x = Generate<ValueType>::random();114 ValueType y = random_different_from({x});115 auto populate = [&](Container& cont) {116 auto out = cont.begin();117 for (std::size_t i = 0; i != cont.size(); ++i) {118 *out++ = (i % 2 == 0 ? x : y);119 }120 };121 for (std::size_t i = 0; i != BatchSize; ++i) {122 c[i] = Container(size);123 populate(c[i]);124 }125 126 while (st.KeepRunningBatch(BatchSize)) {127 for (std::size_t i = 0; i != BatchSize; ++i) {128 benchmark::DoNotOptimize(c[i]);129 benchmark::DoNotOptimize(x);130 auto result = remove(c[i].begin(), c[i].end(), x);131 benchmark::DoNotOptimize(result);132 }133 134 st.PauseTiming();135 for (std::size_t i = 0; i != BatchSize; ++i) {136 populate(c[i]);137 }138 st.ResumeTiming();139 }140 })141 ->Arg(32)142 ->Arg(50) // non power-of-two143 ->Arg(1024)144 ->Arg(8192);145 };146 // {std,ranges}::remove147 bm.operator()<std::vector<int>>("std::remove(vector<int>) (sprinkled)", std_remove);148 bm.operator()<std::deque<int>>("std::remove(deque<int>) (sprinkled)", std_remove);149 bm.operator()<std::list<int>>("std::remove(list<int>) (sprinkled)", std_remove);150 bm.operator()<std::vector<int>>("rng::remove(vector<int>) (sprinkled)", std::ranges::remove);151 bm.operator()<std::deque<int>>("rng::remove(deque<int>) (sprinkled)", std::ranges::remove);152 bm.operator()<std::list<int>>("rng::remove(list<int>) (sprinkled)", std::ranges::remove);153 154 // {std,ranges}::remove_if155 bm.operator()<std::vector<int>>("std::remove_if(vector<int>) (sprinkled)", std_remove_if);156 bm.operator()<std::deque<int>>("std::remove_if(deque<int>) (sprinkled)", std_remove_if);157 bm.operator()<std::list<int>>("std::remove_if(list<int>) (sprinkled)", std_remove_if);158 bm.operator()<std::vector<int>>("rng::remove_if(vector<int>) (sprinkled)", ranges_remove_if);159 bm.operator()<std::deque<int>>("rng::remove_if(deque<int>) (sprinkled)", ranges_remove_if);160 bm.operator()<std::list<int>>("rng::remove_if(list<int>) (sprinkled)", ranges_remove_if);161 }162 163 benchmark::Initialize(&argc, argv);164 benchmark::RunSpecifiedBenchmarks();165 benchmark::Shutdown();166 return 0;167}168