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 <cassert>
13#include <cstddef>
14#include <deque>
15#include <iterator>
16#include <list>
17#include <string>
18#include <vector>
19
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_partition = [](auto first, auto last, auto pred) { return std::partition(first, last, pred); };
32
33 // Benchmark {std,ranges}::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 partition) {
37 benchmark::RegisterBenchmark(
38 name,
39 [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 = partition(c.begin(), c.end(), pred1);
56 benchmark::DoNotOptimize(result);
57 } else {
58 auto result = 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::partition
71 bm.operator()<std::vector<int>>(name: "std::partition(vector<int>) (dense)", partition: std_partition);
72 bm.operator()<std::deque<int>>(name: "std::partition(deque<int>) (dense)", partition: std_partition);
73 bm.operator()<std::list<int>>(name: "std::partition(list<int>) (dense)", partition: std_partition);
74
75 // ranges::partition
76 bm.operator()<std::vector<int>>("rng::partition(vector<int>) (dense)", std::ranges::partition);
77 bm.operator()<std::deque<int>>("rng::partition(deque<int>) (dense)", std::ranges::partition);
78 bm.operator()<std::list<int>>("rng::partition(list<int>) (dense)", std::ranges::partition);
79 }
80
81 // Benchmark {std,ranges}::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 partition) {
85 benchmark::RegisterBenchmark(
86 name,
87 [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 = 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::partition
119 bm.operator()<std::vector<int>>(name: "std::partition(vector<int>) (sparse)", partition: std_partition);
120 bm.operator()<std::deque<int>>(name: "std::partition(deque<int>) (sparse)", partition: std_partition);
121 bm.operator()<std::list<int>>(name: "std::partition(list<int>) (sparse)", partition: std_partition);
122
123 // ranges::partition
124 bm.operator()<std::vector<int>>("rng::partition(vector<int>) (sparse)", std::ranges::partition);
125 bm.operator()<std::deque<int>>("rng::partition(deque<int>) (sparse)", std::ranges::partition);
126 bm.operator()<std::list<int>>("rng::partition(list<int>) (sparse)", std::ranges::partition);
127 }
128
129 benchmark::Initialize(&argc, argv);
130 benchmark::RunSpecifiedBenchmarks();
131 benchmark::Shutdown();
132 return 0;
133}
134

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