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#ifndef LIBCXX_ALGORITHMS_COMMON_H
10#define LIBCXX_ALGORITHMS_COMMON_H
11
12#include <algorithm>
13#include <numeric>
14#include <tuple>
15#include <vector>
16
17#include "../CartesianBenchmarks.h"
18#include "../GenerateInput.h"
19
20enum class ValueType { Uint32, Uint64, Pair, Tuple, String, Float };
21struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 6> {
22 static constexpr const char* Names[] = {
23 "uint32", "uint64", "pair<uint32, uint32>", "tuple<uint32, uint64, uint32>", "string", "float"};
24};
25
26using Types =
27 std::tuple<uint32_t,
28 uint64_t,
29 std::pair<uint32_t, uint32_t>,
30 std::tuple<uint32_t, uint64_t, uint32_t>,
31 std::string,
32 float>;
33
34template <class V>
35using Value = std::tuple_element_t<(int)V::value, Types>;
36
37enum class Order {
38 Random,
39 Ascending,
40 Descending,
41 SingleElement,
42 PipeOrgan,
43 Heap,
44 QuickSortAdversary,
45};
46struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 7> {
47 static constexpr const char* Names[] = {
48 "Random", "Ascending", "Descending", "SingleElement", "PipeOrgan", "Heap", "QuickSortAdversary"};
49};
50
51// fillAdversarialQuickSortInput fills the input vector with N int-like values.
52// These values are arranged in such a way that they would invoke O(N^2)
53// behavior on any quick sort implementation that satisifies certain conditions.
54// Details are available in the following paper:
55// "A Killer Adversary for Quicksort", M. D. McIlroy, Software-Practice &
56// Experience Volume 29 Issue 4 April 10, 1999 pp 341-344.
57// https://dl.acm.org/doi/10.5555/311868.311871.
58template <class T>
59void fillAdversarialQuickSortInput(T& V, size_t N) {
60 assert(N > 0);
61 // If an element is equal to gas, it indicates that the value of the element
62 // is still to be decided and may change over the course of time.
63 const unsigned int gas = N - 1;
64 V.resize(N);
65 for (unsigned int i = 0; i < N; ++i) {
66 V[i] = gas;
67 }
68 // Candidate for the pivot position.
69 int candidate = 0;
70 int nsolid = 0;
71 // Populate all positions in the generated input to gas.
72 std::vector<int> ascVals(V.size());
73 // Fill up with ascending values from 0 to V.size()-1. These will act as
74 // indices into V.
75 std::iota(first: ascVals.begin(), last: ascVals.end(), value: 0);
76 std::sort(ascVals.begin(), ascVals.end(), [&](int x, int y) {
77 if (V[x] == gas && V[y] == gas) {
78 // We are comparing two inputs whose value is still to be decided.
79 if (x == candidate) {
80 V[x] = nsolid++;
81 } else {
82 V[y] = nsolid++;
83 }
84 }
85 if (V[x] == gas) {
86 candidate = x;
87 } else if (V[y] == gas) {
88 candidate = y;
89 }
90 return V[x] < V[y];
91 });
92}
93
94template <typename T>
95void fillValues(std::vector<T>& V, size_t N, Order O) {
96 if (O == Order::SingleElement) {
97 V.resize(N, 0);
98 } else if (O == Order::QuickSortAdversary) {
99 fillAdversarialQuickSortInput(V, N);
100 } else {
101 while (V.size() < N)
102 V.push_back(V.size());
103 }
104}
105
106template <typename T>
107void fillValues(std::vector<std::pair<T, T> >& V, size_t N, Order O) {
108 if (O == Order::SingleElement) {
109 V.resize(N, std::make_pair(x: 0, y: 0));
110 } else {
111 while (V.size() < N)
112 // Half of array will have the same first element.
113 if (V.size() % 2) {
114 V.push_back(std::make_pair(V.size(), V.size()));
115 } else {
116 V.push_back(std::make_pair(0, V.size()));
117 }
118 }
119}
120
121template <typename T1, typename T2, typename T3>
122void fillValues(std::vector<std::tuple<T1, T2, T3> >& V, size_t N, Order O) {
123 if (O == Order::SingleElement) {
124 V.resize(N, std::make_tuple(args: 0, args: 0, args: 0));
125 } else {
126 while (V.size() < N)
127 // One third of array will have the same first element.
128 // One third of array will have the same first element and the same second element.
129 switch (V.size() % 3) {
130 case 0:
131 V.push_back(std::make_tuple(V.size(), V.size(), V.size()));
132 break;
133 case 1:
134 V.push_back(std::make_tuple(0, V.size(), V.size()));
135 break;
136 case 2:
137 V.push_back(std::make_tuple(0, 0, V.size()));
138 break;
139 }
140 }
141}
142
143inline void fillValues(std::vector<std::string>& V, size_t N, Order O) {
144 if (O == Order::SingleElement) {
145 V.resize(new_size: N, x: getRandomString(Len: 64));
146 } else {
147 while (V.size() < N)
148 V.push_back(x: getRandomString(Len: 64));
149 }
150}
151
152template <class T>
153void sortValues(T& V, Order O) {
154 switch (O) {
155 case Order::Random: {
156 std::random_device R;
157 std::mt19937 M(R());
158 std::shuffle(V.begin(), V.end(), M);
159 break;
160 }
161 case Order::Ascending:
162 std::sort(V.begin(), V.end());
163 break;
164 case Order::Descending:
165 std::sort(V.begin(), V.end(), std::greater<>());
166 break;
167 case Order::SingleElement:
168 // Nothing to do
169 break;
170 case Order::PipeOrgan:
171 std::sort(V.begin(), V.end());
172 std::reverse(V.begin() + V.size() / 2, V.end());
173 break;
174 case Order::Heap:
175 std::make_heap(V.begin(), V.end());
176 break;
177 case Order::QuickSortAdversary:
178 // Nothing to do
179 break;
180 }
181}
182
183constexpr size_t TestSetElements =
184#if !TEST_HAS_FEATURE(memory_sanitizer)
185 1 << 18;
186#else
187 1 << 14;
188#endif
189
190template <class ValueType>
191std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N, Order O) {
192 std::vector<std::vector<Value<ValueType> > > Ret;
193 const size_t NumCopies = std::max(a: size_t{1}, b: TestSetElements / N);
194 Ret.resize(NumCopies);
195 for (auto& V : Ret) {
196 fillValues(V, N, O);
197 sortValues(V, O);
198 }
199 return Ret;
200}
201
202template <class T, class U>
203TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies, U& Orig) {
204 state.PauseTiming();
205 for (auto& Copy : Copies)
206 Copy = Orig;
207 state.ResumeTiming();
208}
209
210enum class BatchSize {
211 CountElements,
212 CountBatch,
213};
214
215template <class ValueType, class F>
216void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O, BatchSize Count, F Body) {
217 auto Copies = makeOrderedValues<ValueType>(Quantity, O);
218 auto Orig = Copies;
219
220 const size_t Batch = Count == BatchSize::CountElements ? Copies.size() * Quantity : Copies.size();
221 while (state.KeepRunningBatch(n: Batch)) {
222 for (auto& Copy : Copies) {
223 Body(Copy);
224 benchmark::DoNotOptimize(Copy);
225 }
226 state.PauseTiming();
227 Copies = Orig;
228 state.ResumeTiming();
229 }
230}
231
232const std::vector<size_t> Quantities = {
233 1 << 0,
234 1 << 2,
235 1 << 4,
236 1 << 6,
237 1 << 8,
238 1 << 10,
239 1 << 14,
240// Running each benchmark in parallel consumes too much memory with MSAN
241// and can lead to the test process being killed.
242#if !TEST_HAS_FEATURE(memory_sanitizer)
243 1 << 18
244#endif
245};
246
247#endif // LIBCXX_ALGORITHMS_COMMON_H
248

source code of libcxx/benchmarks/algorithms/common.h