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 "count_new.h"
20#include "benchmark/benchmark.h"
21#include "../../GenerateInput.h"
22
23auto compute_median(auto first, auto last) {
24 std::vector v(first, last);
25 auto middle = v.begin() + v.size() / 2;
26 std::nth_element(v.begin(), middle, v.end());
27 return *middle;
28}
29
30int main(int argc, char** argv) {
31 auto std_stable_partition = [](auto first, auto last, auto pred) { return std::stable_partition(first, last, pred); };
32
33 // Benchmark {std,ranges}::stable_partition on a fully unpartitionned sequence, i.e. a lot of elements
34 // have to be moved around in order to partition the range.
35 {
36 auto bm = []<class Container>(std::string name, auto stable_partition) {
37 benchmark::RegisterBenchmark(
38 name,
39 [stable_partition](auto& st) {
40 std::size_t const size = st.range(0);
41 using ValueType = typename Container::value_type;
42 Container c;
43 std::generate_n(std::back_inserter(c), size, [] { return Generate<ValueType>::random(); });
44
45 ValueType median = compute_median(c.begin(), c.end());
46 auto pred1 = [median](auto const& element) { return element < median; };
47 auto pred2 = [median](auto const& element) { return element > median; };
48 bool toggle = false;
49
50 for ([[maybe_unused]] auto _ : st) {
51 benchmark::DoNotOptimize(c);
52 // By toggling the predicate, we have to move almost all elements in the sequence
53 // to restore the partition.
54 if (toggle) {
55 auto result = stable_partition(c.begin(), c.end(), pred1);
56 benchmark::DoNotOptimize(result);
57 } else {
58 auto result = stable_partition(c.begin(), c.end(), pred2);
59 benchmark::DoNotOptimize(result);
60 }
61 toggle = !toggle;
62 }
63 })
64 ->Arg(32)
65 ->Arg(50) // non power-of-two
66 ->Arg(1024)
67 ->Arg(8192);
68 };
69
70 // std::stable_partition
71 bm.operator()<std::vector<int>>(name: "std::stable_partition(vector<int>) (dense)", stable_partition: std_stable_partition);
72 bm.operator()<std::deque<int>>(name: "std::stable_partition(deque<int>) (dense)", stable_partition: std_stable_partition);
73 bm.operator()<std::list<int>>(name: "std::stable_partition(list<int>) (dense)", stable_partition: std_stable_partition);
74
75 // ranges::stable_partition
76 bm.operator()<std::vector<int>>("rng::stable_partition(vector<int>) (dense)", std::ranges::stable_partition);
77 bm.operator()<std::deque<int>>("rng::stable_partition(deque<int>) (dense)", std::ranges::stable_partition);
78 bm.operator()<std::list<int>>("rng::stable_partition(list<int>) (dense)", std::ranges::stable_partition);
79 }
80
81 // Benchmark {std,ranges}::stable_partition on a mostly partitioned sequence, i.e. only 10% of the elements
82 // have to be moved around in order to partition the range.
83 {
84 auto bm = []<class Container>(std::string name, auto stable_partition) {
85 benchmark::RegisterBenchmark(
86 name,
87 [stable_partition](auto& st) {
88 std::size_t const size = st.range(0);
89 using ValueType = typename Container::value_type;
90 Container c;
91 std::generate_n(std::back_inserter(c), size, [] { return Generate<ValueType>::random(); });
92 ValueType median = compute_median(c.begin(), c.end());
93 auto pred = [median](auto const& element) { return element < median; };
94 std::partition(c.begin(), c.end(), pred);
95
96 // Between iterations, we swap 5% of the elements to the left of the median with 5% of the elements
97 // to the right of the median. This ensures that the range is slightly unpartitioned.
98 auto median_it = std::partition_point(c.begin(), c.end(), pred);
99 auto low = std::next(c.begin(), std::distance(c.begin(), median_it) - (size / 20));
100 auto high = std::next(median_it, size / 20);
101 auto shuffle = [&] { std::swap_ranges(low, median_it, high); };
102 shuffle();
103 assert(!std::is_partitioned(c.begin(), c.end(), pred));
104
105 for ([[maybe_unused]] auto _ : st) {
106 benchmark::DoNotOptimize(c);
107 auto result = stable_partition(c.begin(), c.end(), pred);
108 benchmark::DoNotOptimize(result);
109 shuffle();
110 }
111 })
112 ->Arg(32)
113 ->Arg(50) // non power-of-two
114 ->Arg(1024)
115 ->Arg(8192);
116 };
117
118 // std::stable_partition
119 bm.operator()<std::vector<int>>(name: "std::stable_partition(vector<int>) (sparse)", stable_partition: std_stable_partition);
120 bm.operator()<std::deque<int>>(name: "std::stable_partition(deque<int>) (sparse)", stable_partition: std_stable_partition);
121 bm.operator()<std::list<int>>(name: "std::stable_partition(list<int>) (sparse)", stable_partition: std_stable_partition);
122
123 // ranges::stable_partition
124 bm.operator()<std::vector<int>>("rng::stable_partition(vector<int>) (sparse)", std::ranges::stable_partition);
125 bm.operator()<std::deque<int>>("rng::stable_partition(deque<int>) (sparse)", std::ranges::stable_partition);
126 bm.operator()<std::list<int>>("rng::stable_partition(list<int>) (sparse)", std::ranges::stable_partition);
127 }
128
129 // Benchmark {std,ranges}::stable_partition when memory allocation fails. The algorithm must fall back to
130 // a different algorithm that has different complexity guarantees.
131 {
132 auto bm = []<class Container>(std::string name, auto stable_partition) {
133 benchmark::RegisterBenchmark(
134 name,
135 [stable_partition](auto& st) {
136 std::size_t const size = st.range(0);
137 using ValueType = typename Container::value_type;
138 Container c;
139 std::generate_n(std::back_inserter(c), size, [] { return Generate<ValueType>::random(); });
140
141 ValueType median = compute_median(c.begin(), c.end());
142 auto pred1 = [median](auto const& element) { return element < median; };
143 auto pred2 = [median](auto const& element) { return element > median; };
144 bool toggle = false;
145
146 for ([[maybe_unused]] auto _ : st) {
147 benchmark::DoNotOptimize(c);
148 // Disable the ability to allocate memory inside this block
149 globalMemCounter.reset();
150 globalMemCounter.throw_after = 0;
151
152 if (toggle) {
153 auto result = stable_partition(c.begin(), c.end(), pred1);
154 benchmark::DoNotOptimize(result);
155 } else {
156 auto result = stable_partition(c.begin(), c.end(), pred2);
157 benchmark::DoNotOptimize(result);
158 }
159 toggle = !toggle;
160 }
161 })
162 ->Arg(32)
163 ->Arg(50) // non power-of-two
164 ->Arg(1024)
165 ->Arg(8192);
166 };
167
168 // std::stable_partition
169 bm.operator()<std::vector<int>>(name: "std::stable_partition(vector<int>) (alloc fails)", stable_partition: std_stable_partition);
170 bm.operator()<std::deque<int>>(name: "std::stable_partition(deque<int>) (alloc fails)", stable_partition: std_stable_partition);
171 bm.operator()<std::list<int>>(name: "std::stable_partition(list<int>) (alloc fails)", stable_partition: std_stable_partition);
172
173 // ranges::stable_partition
174 bm.operator()<std::vector<int>>("rng::stable_partition(vector<int>) (alloc fails)", std::ranges::stable_partition);
175 bm.operator()<std::deque<int>>("rng::stable_partition(deque<int>) (alloc fails)", std::ranges::stable_partition);
176 bm.operator()<std::list<int>>("rng::stable_partition(list<int>) (alloc fails)", std::ranges::stable_partition);
177 }
178
179 benchmark::Initialize(&argc, argv);
180 benchmark::RunSpecifiedBenchmarks();
181 benchmark::Shutdown();
182 return 0;
183}
184

source code of libcxx/test/benchmarks/algorithms/partitions/stable_partition.bench.cpp