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 <array>
13#include <cstddef>
14#include <deque>
15#include <string>
16#include <vector>
17
18#include "benchmark/benchmark.h"
19#include "common.h"
20#include "count_new.h"
21
22int main(int argc, char** argv) {
23 auto std_stable_sort = [](auto first, auto last) { return std::stable_sort(first, last); };
24
25 // Benchmark {std,ranges}::stable_sort on various types of data
26 //
27 // We perform this benchmark in a batch because we need to restore the
28 // state of the container after the operation.
29 //
30 // Also note that we intentionally don't benchmark the predicated version of the algorithm
31 // because that makes the benchmark run too slowly.
32 {
33 auto bm = []<class Container>(std::string name, auto stable_sort, auto generate_data) {
34 benchmark::RegisterBenchmark(
35 name,
36 [stable_sort, generate_data](auto& st) {
37 std::size_t const size = st.range(0);
38 constexpr std::size_t BatchSize = 32;
39 using ValueType = typename Container::value_type;
40 std::vector<ValueType> data = generate_data(size);
41 std::array<Container, BatchSize> c;
42 std::fill_n(c.begin(), BatchSize, Container(data.begin(), data.end()));
43
44 while (st.KeepRunningBatch(BatchSize)) {
45 for (std::size_t i = 0; i != BatchSize; ++i) {
46 benchmark::DoNotOptimize(c[i]);
47 stable_sort(c[i].begin(), c[i].end());
48 benchmark::DoNotOptimize(c[i]);
49 }
50
51 st.PauseTiming();
52 for (std::size_t i = 0; i != BatchSize; ++i) {
53 std::copy(data.begin(), data.end(), c[i].begin());
54 }
55 st.ResumeTiming();
56 }
57 })
58 ->Arg(8)
59 ->Arg(1024)
60 ->Arg(8192);
61 };
62
63 auto register_bm = [&](auto generate, std::string variant) {
64 auto gen2 = [generate](auto size) {
65 std::vector<int> data = generate(size);
66 std::vector<support::NonIntegral> real_data(data.begin(), data.end());
67 return real_data;
68 };
69 auto name = [variant](std::string op) { return op + " (" + variant + ")"; };
70 bm.operator()<std::vector<int>>(name("std::stable_sort(vector<int>)"), std_stable_sort, generate);
71 bm.operator()<std::vector<support::NonIntegral>>(
72 name("std::stable_sort(vector<NonIntegral>)"), std_stable_sort, gen2);
73 bm.operator()<std::deque<int>>(name("std::stable_sort(deque<int>)"), std_stable_sort, generate);
74
75 bm.operator()<std::vector<int>>(name("rng::stable_sort(vector<int>)"), std::ranges::stable_sort, generate);
76 bm.operator()<std::vector<support::NonIntegral>>(
77 name("rng::stable_sort(vector<NonIntegral>)"), std::ranges::stable_sort, gen2);
78 bm.operator()<std::deque<int>>(name("rng::stable_sort(deque<int>)"), std::ranges::stable_sort, generate);
79 };
80
81 register_bm(support::quicksort_adversarial_data<int>, "qsort adversarial");
82 register_bm(support::ascending_sorted_data<int>, "ascending");
83 register_bm(support::descending_sorted_data<int>, "descending");
84 register_bm(support::pipe_organ_data<int>, "pipe-organ");
85 register_bm(support::heap_data<int>, "heap");
86 register_bm(support::shuffled_data<int>, "shuffled");
87 register_bm(support::single_element_data<int>, "repeated");
88 }
89
90 // Benchmark {std,ranges}::stable_sort when memory allocation fails. The algorithm must fall back to
91 // a different algorithm that has different complexity guarantees.
92 {
93 auto bm = []<class Container>(std::string name, auto stable_sort, auto generate_data) {
94 benchmark::RegisterBenchmark(
95 name,
96 [stable_sort, generate_data](auto& st) {
97 std::size_t const size = st.range(0);
98 constexpr std::size_t BatchSize = 32;
99 using ValueType = typename Container::value_type;
100 std::vector<ValueType> data = generate_data(size);
101 std::array<Container, BatchSize> c;
102 std::fill_n(c.begin(), BatchSize, Container(data.begin(), data.end()));
103
104 while (st.KeepRunningBatch(BatchSize)) {
105 for (std::size_t i = 0; i != BatchSize; ++i) {
106 benchmark::DoNotOptimize(c[i]);
107 // Disable the ability to allocate memory inside this block
108 globalMemCounter.throw_after = 0;
109
110 stable_sort(c[i].begin(), c[i].end());
111 benchmark::DoNotOptimize(c[i]);
112
113 globalMemCounter.reset();
114 }
115
116 st.PauseTiming();
117 for (std::size_t i = 0; i != BatchSize; ++i) {
118 std::copy(data.begin(), data.end(), c[i].begin());
119 }
120 st.ResumeTiming();
121 }
122 })
123 ->Arg(8)
124 ->Arg(1024)
125 ->Arg(8192);
126 };
127
128 auto register_bm = [&](auto generate, std::string variant) {
129 auto gen2 = [generate](auto size) {
130 std::vector<int> data = generate(size);
131 std::vector<support::NonIntegral> real_data(data.begin(), data.end());
132 return real_data;
133 };
134 auto name = [variant](std::string op) { return op + " (alloc fails, " + variant + ")"; };
135 bm.operator()<std::vector<int>>(name("std::stable_sort(vector<int>)"), std_stable_sort, generate);
136 bm.operator()<std::vector<support::NonIntegral>>(
137 name("std::stable_sort(vector<NonIntegral>)"), std_stable_sort, gen2);
138 bm.operator()<std::deque<int>>(name("std::stable_sort(deque<int>)"), std_stable_sort, generate);
139
140 bm.operator()<std::vector<int>>(name("rng::stable_sort(vector<int>)"), std::ranges::stable_sort, generate);
141 bm.operator()<std::vector<support::NonIntegral>>(
142 name("rng::stable_sort(vector<NonIntegral>)"), std::ranges::stable_sort, gen2);
143 bm.operator()<std::deque<int>>(name("rng::stable_sort(deque<int>)"), std::ranges::stable_sort, generate);
144 };
145
146 register_bm(support::quicksort_adversarial_data<int>, "qsort adversarial");
147 register_bm(support::ascending_sorted_data<int>, "ascending");
148 register_bm(support::descending_sorted_data<int>, "descending");
149 register_bm(support::pipe_organ_data<int>, "pipe-organ");
150 register_bm(support::heap_data<int>, "heap");
151 register_bm(support::shuffled_data<int>, "shuffled");
152 register_bm(support::single_element_data<int>, "repeated");
153 }
154
155 benchmark::Initialize(&argc, argv);
156 benchmark::RunSpecifiedBenchmarks();
157 benchmark::Shutdown();
158 return 0;
159}
160

source code of libcxx/test/benchmarks/algorithms/sorting/stable_sort.bench.cpp