172 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_unique = [](auto first, auto last) { return std::unique(first, last); };24 auto std_unique_pred = [](auto first, auto last) {25 return std::unique(first, last, [](auto a, auto b) {26 benchmark::DoNotOptimize(a);27 benchmark::DoNotOptimize(b);28 return a == b;29 });30 };31 auto ranges_unique_pred = [](auto first, auto last) {32 return std::ranges::unique(first, last, [](auto a, auto b) {33 benchmark::DoNotOptimize(a);34 benchmark::DoNotOptimize(b);35 return a == b;36 });37 };38 39 // Create a sequence of the form xxxxxxxxxxyyyyyyyyyy and unique the40 // adjacent equal elements.41 //42 // We perform this benchmark in a batch because we need to restore the43 // state of the container after the operation.44 {45 auto bm = []<class Container>(std::string name, auto unique) {46 benchmark::RegisterBenchmark(47 name,48 [unique](auto& st) {49 std::size_t const size = st.range(0);50 constexpr std::size_t BatchSize = 10;51 using ValueType = typename Container::value_type;52 Container c[BatchSize];53 ValueType x = Generate<ValueType>::random();54 ValueType y = random_different_from({x});55 auto populate = [&](Container& cont) {56 auto half = cont.size() / 2;57 std::fill_n(std::fill_n(cont.begin(), half, x), half, y);58 };59 for (std::size_t i = 0; i != BatchSize; ++i) {60 c[i] = Container(size);61 populate(c[i]);62 }63 64 while (st.KeepRunningBatch(BatchSize)) {65 for (std::size_t i = 0; i != BatchSize; ++i) {66 benchmark::DoNotOptimize(c[i]);67 auto result = unique(c[i].begin(), c[i].end());68 benchmark::DoNotOptimize(result);69 }70 71 st.PauseTiming();72 for (std::size_t i = 0; i != BatchSize; ++i) {73 populate(c[i]);74 }75 st.ResumeTiming();76 }77 })78 ->Arg(32)79 ->Arg(52) // non power-of-two80 ->Arg(1024)81 ->Arg(8192);82 };83 // {std,ranges}::unique(it, it)84 bm.operator()<std::vector<int>>("std::unique(vector<int>) (contiguous)", std_unique);85 bm.operator()<std::deque<int>>("std::unique(deque<int>) (contiguous)", std_unique);86 bm.operator()<std::list<int>>("std::unique(list<int>) (contiguous)", std_unique);87 bm.operator()<std::vector<int>>("rng::unique(vector<int>) (contiguous)", std::ranges::unique);88 bm.operator()<std::deque<int>>("rng::unique(deque<int>) (contiguous)", std::ranges::unique);89 bm.operator()<std::list<int>>("rng::unique(list<int>) (contiguous)", std::ranges::unique);90 91 // {std,ranges}::unique(it, it, pred)92 bm.operator()<std::vector<int>>("std::unique(vector<int>, pred) (contiguous)", std_unique_pred);93 bm.operator()<std::deque<int>>("std::unique(deque<int>, pred) (contiguous)", std_unique_pred);94 bm.operator()<std::list<int>>("std::unique(list<int>, pred) (contiguous)", std_unique_pred);95 bm.operator()<std::vector<int>>("rng::unique(vector<int>, pred) (contiguous)", ranges_unique_pred);96 bm.operator()<std::deque<int>>("rng::unique(deque<int>, pred) (contiguous)", ranges_unique_pred);97 bm.operator()<std::list<int>>("rng::unique(list<int>, pred) (contiguous)", ranges_unique_pred);98 }99 100 // Create a sequence of the form xxyyxxyyxxyyxxyyxxyy and unique101 // adjacent equal elements.102 //103 // We perform this benchmark in a batch because we need to restore the104 // state of the container after the operation.105 {106 auto bm = []<class Container>(std::string name, auto unique) {107 benchmark::RegisterBenchmark(108 name,109 [unique](auto& st) {110 std::size_t const size = st.range(0);111 constexpr std::size_t BatchSize = 10;112 using ValueType = typename Container::value_type;113 Container c[BatchSize];114 ValueType x = Generate<ValueType>::random();115 ValueType y = random_different_from({x});116 auto populate = [&](Container& cont) {117 assert(cont.size() % 4 == 0);118 auto out = cont.begin();119 for (std::size_t i = 0; i != cont.size(); i += 4) {120 *out++ = x;121 *out++ = x;122 *out++ = y;123 *out++ = y;124 }125 };126 for (std::size_t i = 0; i != BatchSize; ++i) {127 c[i] = Container(size);128 populate(c[i]);129 }130 131 while (st.KeepRunningBatch(BatchSize)) {132 for (std::size_t i = 0; i != BatchSize; ++i) {133 benchmark::DoNotOptimize(c[i]);134 auto result = unique(c[i].begin(), c[i].end());135 benchmark::DoNotOptimize(result);136 }137 138 st.PauseTiming();139 for (std::size_t i = 0; i != BatchSize; ++i) {140 populate(c[i]);141 }142 st.ResumeTiming();143 }144 })145 ->Arg(32)146 ->Arg(52) // non power-of-two147 ->Arg(1024)148 ->Arg(8192);149 };150 // {std,ranges}::unique(it, it)151 bm.operator()<std::vector<int>>("std::unique(vector<int>) (sprinkled)", std_unique);152 bm.operator()<std::deque<int>>("std::unique(deque<int>) (sprinkled)", std_unique);153 bm.operator()<std::list<int>>("std::unique(list<int>) (sprinkled)", std_unique);154 bm.operator()<std::vector<int>>("rng::unique(vector<int>) (sprinkled)", std::ranges::unique);155 bm.operator()<std::deque<int>>("rng::unique(deque<int>) (sprinkled)", std::ranges::unique);156 bm.operator()<std::list<int>>("rng::unique(list<int>) (sprinkled)", std::ranges::unique);157 158 // {std,ranges}::unique(it, it, pred)159 bm.operator()<std::vector<int>>("std::unique(vector<int>, pred) (sprinkled)", std_unique_pred);160 bm.operator()<std::deque<int>>("std::unique(deque<int>, pred) (sprinkled)", std_unique_pred);161 bm.operator()<std::list<int>>("std::unique(list<int>, pred) (sprinkled)", std_unique_pred);162 bm.operator()<std::vector<int>>("rng::unique(vector<int>, pred) (sprinkled)", ranges_unique_pred);163 bm.operator()<std::deque<int>>("rng::unique(deque<int>, pred) (sprinkled)", ranges_unique_pred);164 bm.operator()<std::list<int>>("rng::unique(list<int>, pred) (sprinkled)", ranges_unique_pred);165 }166 167 benchmark::Initialize(&argc, argv);168 benchmark::RunSpecifiedBenchmarks();169 benchmark::Shutdown();170 return 0;171}172