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-exception
6//
7//===----------------------------------------------------------------------===//
8
9// UNSUPPORTED: c++03, c++11, c++14, c++17
10
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 the
40 // adjacent equal elements.
41 //
42 // We perform this benchmark in a batch because we need to restore the
43 // 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(50) // non power-of-two
80 ->Arg(1024)
81 ->Arg(8192);
82 };
83 // {std,ranges}::unique(it, it)
84 bm.operator()<std::vector<int>>(name: "std::unique(vector<int>) (contiguous)", unique: std_unique);
85 bm.operator()<std::deque<int>>(name: "std::unique(deque<int>) (contiguous)", unique: std_unique);
86 bm.operator()<std::list<int>>(name: "std::unique(list<int>) (contiguous)", unique: 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>>(name: "std::unique(vector<int>, pred) (contiguous)", unique: std_unique_pred);
93 bm.operator()<std::deque<int>>(name: "std::unique(deque<int>, pred) (contiguous)", unique: std_unique_pred);
94 bm.operator()<std::list<int>>(name: "std::unique(list<int>, pred) (contiguous)", unique: std_unique_pred);
95 bm.operator()<std::vector<int>>(name: "rng::unique(vector<int>, pred) (contiguous)", unique: ranges_unique_pred);
96 bm.operator()<std::deque<int>>(name: "rng::unique(deque<int>, pred) (contiguous)", unique: ranges_unique_pred);
97 bm.operator()<std::list<int>>(name: "rng::unique(list<int>, pred) (contiguous)", unique: ranges_unique_pred);
98 }
99
100 // Create a sequence of the form xxyyxxyyxxyyxxyyxxyy and unique
101 // adjacent equal elements.
102 //
103 // We perform this benchmark in a batch because we need to restore the
104 // 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(50) // non power-of-two
147 ->Arg(1024)
148 ->Arg(8192);
149 };
150 // {std,ranges}::unique(it, it)
151 bm.operator()<std::vector<int>>(name: "std::unique(vector<int>) (sprinkled)", unique: std_unique);
152 bm.operator()<std::deque<int>>(name: "std::unique(deque<int>) (sprinkled)", unique: std_unique);
153 bm.operator()<std::list<int>>(name: "std::unique(list<int>) (sprinkled)", unique: 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>>(name: "std::unique(vector<int>, pred) (sprinkled)", unique: std_unique_pred);
160 bm.operator()<std::deque<int>>(name: "std::unique(deque<int>, pred) (sprinkled)", unique: std_unique_pred);
161 bm.operator()<std::list<int>>(name: "std::unique(list<int>, pred) (sprinkled)", unique: std_unique_pred);
162 bm.operator()<std::vector<int>>(name: "rng::unique(vector<int>, pred) (sprinkled)", unique: ranges_unique_pred);
163 bm.operator()<std::deque<int>>(name: "rng::unique(deque<int>, pred) (sprinkled)", unique: ranges_unique_pred);
164 bm.operator()<std::list<int>>(name: "rng::unique(list<int>, pred) (sprinkled)", unique: ranges_unique_pred);
165 }
166
167 benchmark::Initialize(&argc, argv);
168 benchmark::RunSpecifiedBenchmarks();
169 benchmark::Shutdown();
170 return 0;
171}
172

source code of libcxx/test/benchmarks/algorithms/modifying/unique.bench.cpp