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_copy = [](auto first, auto last, auto out) { return std::unique_copy(first, last, out); };
24 auto std_unique_copy_pred = [](auto first, auto last, auto out) {
25 return std::unique_copy(first, last, out, [](auto a, auto b) {
26 benchmark::DoNotOptimize(a);
27 benchmark::DoNotOptimize(b);
28 return a == b;
29 });
30 };
31 auto ranges_unique_copy_pred = [](auto first, auto last, auto out) {
32 return std::ranges::unique_copy(first, last, out, [](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 auto bm = []<class Container>(std::string name, auto unique_copy) {
43 benchmark::RegisterBenchmark(
44 name,
45 [unique_copy](auto& st) {
46 std::size_t const size = st.range(0);
47 using ValueType = typename Container::value_type;
48 Container c(size);
49 ValueType x = Generate<ValueType>::random();
50 ValueType y = random_different_from({x});
51 auto half = size / 2;
52 std::fill_n(std::fill_n(c.begin(), half, x), half, y);
53
54 std::vector<ValueType> out(size);
55
56 for ([[maybe_unused]] auto _ : st) {
57 benchmark::DoNotOptimize(c);
58 benchmark::DoNotOptimize(out);
59 auto result = unique_copy(c.begin(), c.end(), out.begin());
60 benchmark::DoNotOptimize(result);
61 }
62 })
63 ->Arg(32)
64 ->Arg(1024)
65 ->Arg(8192);
66 };
67 // {std,ranges}::unique_copy(it, it, out)
68 bm.operator()<std::vector<int>>(name: "std::unique_copy(vector<int>) (contiguous)", unique_copy: std_unique_copy);
69 bm.operator()<std::deque<int>>(name: "std::unique_copy(deque<int>) (contiguous)", unique_copy: std_unique_copy);
70 bm.operator()<std::list<int>>(name: "std::unique_copy(list<int>) (contiguous)", unique_copy: std_unique_copy);
71 bm.operator()<std::vector<int>>("rng::unique_copy(vector<int>) (contiguous)", std::ranges::unique_copy);
72 bm.operator()<std::deque<int>>("rng::unique_copy(deque<int>) (contiguous)", std::ranges::unique_copy);
73 bm.operator()<std::list<int>>("rng::unique_copy(list<int>) (contiguous)", std::ranges::unique_copy);
74
75 // {std,ranges}::unique_copy(it, it, out, pred)
76 bm.operator()<std::vector<int>>(name: "std::unique_copy(vector<int>, pred) (contiguous)", unique_copy: std_unique_copy_pred);
77 bm.operator()<std::deque<int>>(name: "std::unique_copy(deque<int>, pred) (contiguous)", unique_copy: std_unique_copy_pred);
78 bm.operator()<std::list<int>>(name: "std::unique_copy(list<int>, pred) (contiguous)", unique_copy: std_unique_copy_pred);
79 bm.operator()<std::vector<int>>(name: "rng::unique_copy(vector<int>, pred) (contiguous)", unique_copy: ranges_unique_copy_pred);
80 bm.operator()<std::deque<int>>(name: "rng::unique_copy(deque<int>, pred) (contiguous)", unique_copy: ranges_unique_copy_pred);
81 bm.operator()<std::list<int>>(name: "rng::unique_copy(list<int>, pred) (contiguous)", unique_copy: ranges_unique_copy_pred);
82 }
83
84 // Create a sequence of the form xxyyxxyyxxyyxxyyxxyy and unique
85 // adjacent equal elements.
86 {
87 auto bm = []<class Container>(std::string name, auto unique_copy) {
88 benchmark::RegisterBenchmark(
89 name,
90 [unique_copy](auto& st) {
91 std::size_t const size = st.range(0);
92 using ValueType = typename Container::value_type;
93 Container c(size);
94 ValueType x = Generate<ValueType>::random();
95 ValueType y = random_different_from({x});
96 auto populate = [&](Container& cont) {
97 assert(cont.size() % 4 == 0);
98 auto out = cont.begin();
99 for (std::size_t i = 0; i != cont.size(); i += 4) {
100 *out++ = x;
101 *out++ = x;
102 *out++ = y;
103 *out++ = y;
104 }
105 };
106 populate(c);
107
108 std::vector<ValueType> out(size);
109
110 for ([[maybe_unused]] auto _ : st) {
111 benchmark::DoNotOptimize(c);
112 benchmark::DoNotOptimize(out);
113 auto result = unique_copy(c.begin(), c.end(), out.begin());
114 benchmark::DoNotOptimize(result);
115 }
116 })
117 ->Arg(32)
118 ->Arg(50) // non power-of-two
119 ->Arg(1024)
120 ->Arg(8192);
121 };
122 // {std,ranges}::unique_copy(it, it, out)
123 bm.operator()<std::vector<int>>(name: "std::unique_copy(vector<int>) (sprinkled)", unique_copy: std_unique_copy);
124 bm.operator()<std::deque<int>>(name: "std::unique_copy(deque<int>) (sprinkled)", unique_copy: std_unique_copy);
125 bm.operator()<std::list<int>>(name: "std::unique_copy(list<int>) (sprinkled)", unique_copy: std_unique_copy);
126 bm.operator()<std::vector<int>>("rng::unique_copy(vector<int>) (sprinkled)", std::ranges::unique_copy);
127 bm.operator()<std::deque<int>>("rng::unique_copy(deque<int>) (sprinkled)", std::ranges::unique_copy);
128 bm.operator()<std::list<int>>("rng::unique_copy(list<int>) (sprinkled)", std::ranges::unique_copy);
129
130 // {std,ranges}::unique_copy(it, it, out, pred)
131 bm.operator()<std::vector<int>>(name: "std::unique_copy(vector<int>, pred) (sprinkled)", unique_copy: std_unique_copy_pred);
132 bm.operator()<std::deque<int>>(name: "std::unique_copy(deque<int>, pred) (sprinkled)", unique_copy: std_unique_copy_pred);
133 bm.operator()<std::list<int>>(name: "std::unique_copy(list<int>, pred) (sprinkled)", unique_copy: std_unique_copy_pred);
134 bm.operator()<std::vector<int>>(name: "rng::unique_copy(vector<int>, pred) (sprinkled)", unique_copy: ranges_unique_copy_pred);
135 bm.operator()<std::deque<int>>(name: "rng::unique_copy(deque<int>, pred) (sprinkled)", unique_copy: ranges_unique_copy_pred);
136 bm.operator()<std::list<int>>(name: "rng::unique_copy(list<int>, pred) (sprinkled)", unique_copy: ranges_unique_copy_pred);
137 }
138
139 benchmark::Initialize(&argc, argv);
140 benchmark::RunSpecifiedBenchmarks();
141 benchmark::Shutdown();
142 return 0;
143}
144

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