141 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_replace = [](auto first, auto last, auto old, auto new_) { return std::replace(first, last, old, new_); };24 auto std_replace_if = [](auto first, auto last, auto old, auto new_) {25 auto pred = [&](auto element) {26 benchmark::DoNotOptimize(element);27 return element == old;28 };29 return std::replace_if(first, last, pred, new_);30 };31 auto ranges_replace_if = [](auto first, auto last, auto old, auto new_) {32 auto pred = [&](auto element) {33 benchmark::DoNotOptimize(element);34 return element == old;35 };36 return std::ranges::replace_if(first, last, pred, new_);37 };38 39 // Create a sequence of the form xxxxxxxxxxyyyyyyyyyy, replace40 // into zzzzzzzzzzzyyyyyyyyyy and then back.41 //42 // This measures the performance of replace() when replacing a large43 // contiguous sequence of equal values.44 {45 auto bm = []<class Container>(std::string name, auto replace) {46 benchmark::RegisterBenchmark(47 name,48 [replace](auto& st) {49 std::size_t const size = st.range(0);50 using ValueType = typename Container::value_type;51 Container c;52 ValueType x = Generate<ValueType>::random();53 ValueType y = random_different_from({x});54 ValueType z = random_different_from({x, y});55 std::fill_n(std::back_inserter(c), size / 2, x);56 std::fill_n(std::back_inserter(c), size / 2, y);57 58 for ([[maybe_unused]] auto _ : st) {59 benchmark::DoNotOptimize(c);60 benchmark::DoNotOptimize(x);61 benchmark::DoNotOptimize(z);62 replace(c.begin(), c.end(), x, z);63 benchmark::DoNotOptimize(c);64 std::swap(x, z);65 }66 })67 ->Arg(32)68 ->Arg(50) // non power-of-two69 ->Arg(1024)70 ->Arg(8192);71 };72 // {std,ranges}::replace73 bm.operator()<std::vector<int>>("std::replace(vector<int>) (prefix)", std_replace);74 bm.operator()<std::deque<int>>("std::replace(deque<int>) (prefix)", std_replace);75 bm.operator()<std::list<int>>("std::replace(list<int>) (prefix)", std_replace);76 bm.operator()<std::vector<int>>("rng::replace(vector<int>) (prefix)", std::ranges::replace);77 bm.operator()<std::deque<int>>("rng::replace(deque<int>) (prefix)", std::ranges::replace);78 bm.operator()<std::list<int>>("rng::replace(list<int>) (prefix)", std::ranges::replace);79 80 // {std,ranges}::replace_if81 bm.operator()<std::vector<int>>("std::replace_if(vector<int>) (prefix)", std_replace_if);82 bm.operator()<std::deque<int>>("std::replace_if(deque<int>) (prefix)", std_replace_if);83 bm.operator()<std::list<int>>("std::replace_if(list<int>) (prefix)", std_replace_if);84 bm.operator()<std::vector<int>>("rng::replace_if(vector<int>) (prefix)", ranges_replace_if);85 bm.operator()<std::deque<int>>("rng::replace_if(deque<int>) (prefix)", ranges_replace_if);86 bm.operator()<std::list<int>>("rng::replace_if(list<int>) (prefix)", ranges_replace_if);87 }88 89 // Sprinkle elements to replace inside the range, like xyxyxyxyxyxyxyxyxyxy.90 {91 auto bm = []<class Container>(std::string name, auto replace) {92 benchmark::RegisterBenchmark(93 name,94 [replace](auto& st) {95 std::size_t const size = st.range(0);96 using ValueType = typename Container::value_type;97 Container c;98 ValueType x = Generate<ValueType>::random();99 ValueType y = random_different_from({x});100 ValueType z = random_different_from({x, y});101 for (std::size_t i = 0; i != size; ++i) {102 c.push_back(i % 2 == 0 ? x : y);103 }104 105 for ([[maybe_unused]] auto _ : st) {106 benchmark::DoNotOptimize(c);107 benchmark::DoNotOptimize(x);108 benchmark::DoNotOptimize(z);109 replace(c.begin(), c.end(), x, z);110 benchmark::DoNotOptimize(c);111 std::swap(x, z);112 }113 })114 ->Arg(32)115 ->Arg(50) // non power-of-two116 ->Arg(1024)117 ->Arg(8192);118 };119 // {std,ranges}::replace120 bm.operator()<std::vector<int>>("std::replace(vector<int>) (sprinkled)", std_replace);121 bm.operator()<std::deque<int>>("std::replace(deque<int>) (sprinkled)", std_replace);122 bm.operator()<std::list<int>>("std::replace(list<int>) (sprinkled)", std_replace);123 bm.operator()<std::vector<int>>("rng::replace(vector<int>) (sprinkled)", std::ranges::replace);124 bm.operator()<std::deque<int>>("rng::replace(deque<int>) (sprinkled)", std::ranges::replace);125 bm.operator()<std::list<int>>("rng::replace(list<int>) (sprinkled)", std::ranges::replace);126 127 // {std,ranges}::replace_if128 bm.operator()<std::vector<int>>("std::replace_if(vector<int>) (sprinkled)", std_replace_if);129 bm.operator()<std::deque<int>>("std::replace_if(deque<int>) (sprinkled)", std_replace_if);130 bm.operator()<std::list<int>>("std::replace_if(list<int>) (sprinkled)", std_replace_if);131 bm.operator()<std::vector<int>>("rng::replace_if(vector<int>) (sprinkled)", ranges_replace_if);132 bm.operator()<std::deque<int>>("rng::replace_if(deque<int>) (sprinkled)", ranges_replace_if);133 bm.operator()<std::list<int>>("rng::replace_if(list<int>) (sprinkled)", ranges_replace_if);134 }135 136 benchmark::Initialize(&argc, argv);137 benchmark::RunSpecifiedBenchmarks();138 benchmark::Shutdown();139 return 0;140}141