1 /*
2 Copyright (c) 2005-2022 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 #include "common/test.h"
18 #include "common/utils_concurrency_limit.h"
19 #include "common/cpu_usertime.h"
20 #include "common/concepts_common.h"
21 #include "common/iterator.h"
22
23 #include "tbb/parallel_sort.h"
24 #include "tbb/concurrent_vector.h"
25 #include "tbb/global_control.h"
26
27 #include <math.h>
28 #include <vector>
29 #include <functional>
30 #include <string>
31 #include <cstring>
32 #include <cstddef>
33 #include <iterator>
34 #include <type_traits>
35
36 //! \file test_parallel_sort.cpp
37 //! \brief Test for [algorithms.parallel_sort]
38
39 /** Has tightly controlled interface so that we can verify
40 that parallel_sort uses only the required interface. */
41 class Minimal {
42 int val;
43 public:
set_val(int i)44 void set_val(int i) { val = i; }
Less(const Minimal & a,const Minimal & b)45 static bool Less (const Minimal &a, const Minimal &b) {
46 return (a.val < b.val);
47 }
AreEqual(const Minimal & a,const Minimal & b)48 static bool AreEqual( const Minimal &a, const Minimal &b) {
49 return a.val == b.val;
50 }
51 };
52
53 //! Defines a comparison function object for Minimal
54 class MinimalLessCompare {
55 public:
operator ()(const Minimal & a,const Minimal & b) const56 bool operator() (const Minimal &a, const Minimal &b) const {
57 return Minimal::Less(a,b);
58 }
59 };
60
61 template<typename Value>
compare(const Value & lhs,const Value & rhs)62 bool compare(const Value& lhs, const Value& rhs) {
63 return lhs == rhs;
64 }
65
compare(const Minimal & lhs,const Minimal & rhs)66 bool compare(const Minimal& lhs, const Minimal& rhs) {
67 return Minimal::AreEqual(lhs, rhs);
68 }
69
70 template<typename Range>
validate(Range test_range,Range sorted_range)71 void validate(Range test_range, Range sorted_range) {
72 using value_type = typename std::iterator_traits<decltype(std::begin(test_range))>::value_type;
73 REQUIRE(
74 std::equal(std::begin(test_range), std::end(test_range), std::begin(sorted_range),
75 [](const value_type& tested, const value_type& reference) {
76 return compare(tested, reference);
77 }
78 )
79 );
80 }
81
82 //! The default initialization routine.
83 /*! This routine assumes that you can assign to the elements from a float.
84 It assumes that iter and sorted_list have already been allocated. It fills
85 them according to the current data set (tracked by a local static variable).
86 Returns true if a valid test has been setup, or false if there is no test to
87 perform.
88 */
89 template <typename RefType, typename ValueType>
set(RefType & ref,ValueType new_value)90 void set(RefType& ref, ValueType new_value) {
91 ref = static_cast<RefType>(new_value);
92 }
93
94 template <typename ValueType>
set(Minimal & minimal_ref,ValueType new_value)95 void set(Minimal& minimal_ref, ValueType new_value) {
96 minimal_ref.set_val(static_cast<int>(new_value));
97 }
98
99 template <typename KeyType>
set(std::string & string_ref,KeyType key)100 void set(std::string& string_ref, KeyType key) {
101 string_ref = std::to_string(static_cast<float>(key));
102 }
103
104
105 template <typename RandomAccessIterator, typename Compare>
fill_ranges(RandomAccessIterator test_range_begin,RandomAccessIterator sorted_range_begin,std::size_t size,const Compare & compare)106 bool fill_ranges(RandomAccessIterator test_range_begin, RandomAccessIterator sorted_range_begin,
107 std::size_t size, const Compare &compare) {
108
109 static char test_case = 0;
110 const char num_cases = 3;
111
112 if (test_case < num_cases) {
113 // switch on the current test case, filling the test_list and sorted_list appropriately
114 switch(test_case) {
115 case 0:
116 /* use sin to generate the values */
117 for (std::size_t i = 0; i < size; i++) {
118 set(test_range_begin[i], sin(float(i)));
119 set(sorted_range_begin[i], sin(float(i)));
120 }
121 break;
122 case 1:
123 /* presorted list */
124 for (std::size_t i = 0; i < size; i++) {
125 set(test_range_begin[i], i);
126 set(sorted_range_begin[i], i);
127 }
128 break;
129 case 2:
130 /* reverse-sorted list */
131 for (std::size_t i = 0; i < size; i++) {
132 set(test_range_begin[i], size - i);
133 set(sorted_range_begin[i], size - i);
134 }
135 break;
136 }
137
138 // pre-sort sorted_range for later validity testing
139 std::sort(sorted_range_begin, sorted_range_begin + size, compare);
140 test_case++;
141 return true;
142 }
143 test_case = 0;
144 return false;
145 }
146
147 //! The default test routine.
148 /*! Tests all data set sizes from 0 to N, all grainsizes from 0 to G=10, and selects from
149 all possible interfaces to parallel_sort depending on whether a scratch space and
150 compare have been provided.
151 */
152 template<typename ContainerType, std::size_t Size>
153 struct parallel_sort_test {
runparallel_sort_test154 static void run() {
155 std::less<typename ContainerType::value_type> default_comp;
156 ContainerType range(Size);
157 ContainerType sorted_range(Size);
158
159 while (fill_ranges(std::begin(range), std::begin(sorted_range), Size, default_comp)) {
160 tbb::parallel_sort(range);
161 validate(range, sorted_range);
162 }
163 }
164
165 template<typename Comparator>
runparallel_sort_test166 static void run(Comparator& comp) {
167 ContainerType range(Size);
168 ContainerType sorted_range(Size);
169
170 while (fill_ranges(std::begin(range), std::begin(sorted_range), Size, comp)) {
171 tbb::parallel_sort(range, comp);
172 validate(range, sorted_range);
173 }
174 }
175 };
176
177 template<typename ContainerType, typename Comparator>
parallel_sort_test_suite()178 void parallel_sort_test_suite() {
179 Comparator comp;
180 for (auto concurrency_level : utils::concurrency_range()) {
181 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level);
182 parallel_sort_test<ContainerType, /*Size*/0 >::run(comp);
183 parallel_sort_test<ContainerType, /*Size*/1 >::run(comp);
184 parallel_sort_test<ContainerType, /*Size*/10 >::run(comp);
185 parallel_sort_test<ContainerType, /*Size*/9999 >::run(comp);
186 parallel_sort_test<ContainerType, /*Size*/50000>::run(comp);
187 }
188 }
189
190 template<typename ContainerType>
parallel_sort_test_suite()191 void parallel_sort_test_suite() {
192 for (auto concurrency_level : utils::concurrency_range()) {
193 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level);
194 parallel_sort_test<ContainerType, /*Size*/0 >::run();
195 parallel_sort_test<ContainerType, /*Size*/1 >::run();
196 parallel_sort_test<ContainerType, /*Size*/10 >::run();
197 parallel_sort_test<ContainerType, /*Size*/9999 >::run();
198 parallel_sort_test<ContainerType, /*Size*/50000>::run();
199 }
200 }
201
202 #if __TBB_CPP20_CONCEPTS_PRESENT
203 template <typename RandomAccessIterator>
204 concept can_call_parallel_sort_with_iterator = requires( RandomAccessIterator it ) {
205 tbb::parallel_sort(it, it);
206 };
207
208 template <typename RandomAccessIterator, typename Compare>
209 concept can_call_parallel_sort_with_iterator_and_compare = requires( RandomAccessIterator it, const Compare& compare ) {
210 tbb::parallel_sort(it, it, compare);
211 };
212
213 template <typename CBS>
214 concept can_call_parallel_sort_with_cbs = requires( CBS& cbs ) {
215 tbb::parallel_sort(cbs);
216 };
217
218 template <typename CBS, typename Compare>
219 concept can_call_parallel_sort_with_cbs_and_compare = requires( CBS& cbs, const Compare& compare ) {
220 tbb::parallel_sort(cbs, compare);
221 };
222
223 template <typename T>
224 using CorrectCompare = test_concepts::compare::Correct<T>;
225
test_psort_iterator_constraints()226 void test_psort_iterator_constraints() {
227 using namespace test_concepts::parallel_sort_value;
228
229 static_assert(can_call_parallel_sort_with_iterator<utils::RandomIterator<int>>);
230 static_assert(can_call_parallel_sort_with_iterator<typename std::vector<int>::iterator>);
231 static_assert(!can_call_parallel_sort_with_iterator<utils::ForwardIterator<int>>);
232 static_assert(!can_call_parallel_sort_with_iterator<utils::InputIterator<int>>);
233 static_assert(!can_call_parallel_sort_with_iterator<utils::RandomIterator<NonMovableValue>>);
234 static_assert(!can_call_parallel_sort_with_iterator<utils::RandomIterator<NonMoveAssignableValue>>);
235 static_assert(!can_call_parallel_sort_with_iterator<utils::RandomIterator<NonComparableValue>>);
236 static_assert(!can_call_parallel_sort_with_iterator<test_concepts::ConstantIT<int>>);
237
238 static_assert(can_call_parallel_sort_with_iterator_and_compare<utils::RandomIterator<int>, CorrectCompare<int>>);
239 static_assert(can_call_parallel_sort_with_iterator_and_compare<typename std::vector<int>::iterator, CorrectCompare<int>>);
240 static_assert(!can_call_parallel_sort_with_iterator_and_compare<utils::ForwardIterator<int>, CorrectCompare<int>>);
241 static_assert(!can_call_parallel_sort_with_iterator_and_compare<utils::InputIterator<int>, CorrectCompare<int>>);
242 static_assert(!can_call_parallel_sort_with_iterator_and_compare<utils::RandomIterator<NonMovableValue>, CorrectCompare<NonMovableValue>>);
243 static_assert(!can_call_parallel_sort_with_iterator_and_compare<utils::RandomIterator<NonMoveAssignableValue>, CorrectCompare<NonMoveAssignableValue>>);
244 static_assert(!can_call_parallel_sort_with_iterator_and_compare<test_concepts::ConstantIT<int>, CorrectCompare<const int>>);
245 }
246
test_psort_compare_constraints()247 void test_psort_compare_constraints() {
248 using namespace test_concepts::compare;
249
250 using CorrectCBS = test_concepts::container_based_sequence::Correct;
251 using CorrectIterator = CorrectCBS::iterator;
252 static_assert(can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, Correct<int>>);
253 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, NoOperatorRoundBrackets<int>>);
254 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, WrongFirstInputOperatorRoundBrackets<int>>);
255 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, WrongSecondInputOperatorRoundBrackets<int>>);
256 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, WrongReturnOperatorRoundBrackets<int>>);
257
258 static_assert(can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, Correct<int>>);
259 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, NoOperatorRoundBrackets<int>>);
260 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, WrongFirstInputOperatorRoundBrackets<int>>);
261 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, WrongSecondInputOperatorRoundBrackets<int>>);
262 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, WrongReturnOperatorRoundBrackets<int>>);
263 }
264
test_psort_cbs_constraints()265 void test_psort_cbs_constraints() {
266 using namespace test_concepts::container_based_sequence;
267 using namespace test_concepts::parallel_sort_value;
268
269 static_assert(can_call_parallel_sort_with_cbs<Correct>);
270 static_assert(!can_call_parallel_sort_with_cbs<NoBegin>);
271 static_assert(!can_call_parallel_sort_with_cbs<NoEnd>);
272 static_assert(!can_call_parallel_sort_with_cbs<ForwardIteratorCBS>);
273 static_assert(!can_call_parallel_sort_with_cbs<ConstantCBS>);
274
275 static_assert(can_call_parallel_sort_with_cbs<CustomValueCBS<CorrectValue>>);
276 static_assert(!can_call_parallel_sort_with_cbs<CustomValueCBS<NonMovableValue>>);
277 static_assert(!can_call_parallel_sort_with_cbs<CustomValueCBS<NonMoveAssignableValue>>);
278 static_assert(!can_call_parallel_sort_with_cbs<CustomValueCBS<NonComparableValue>>);\
279
280 using CorrectCompare = test_concepts::compare::Correct<int>;
281 using NonMovableCompare = test_concepts::compare::Correct<NonMovableValue>;
282 using NonMoveAssignableCompare = test_concepts::compare::Correct<NonMoveAssignableValue>;
283 static_assert(can_call_parallel_sort_with_cbs_and_compare<Correct, CorrectCompare>);
284 static_assert(!can_call_parallel_sort_with_cbs_and_compare<NoBegin, CorrectCompare>);
285 static_assert(!can_call_parallel_sort_with_cbs_and_compare<NoEnd, CorrectCompare>);
286 static_assert(!can_call_parallel_sort_with_cbs_and_compare<ForwardIteratorCBS, CorrectCompare>);
287 static_assert(!can_call_parallel_sort_with_cbs_and_compare<ConstantCBS, CorrectCompare>);
288 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CustomValueCBS<NonMovableValue>, NonMovableCompare>);
289 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CustomValueCBS<NonMoveAssignableValue>, NonMoveAssignableCompare>);
290 }
291
292 #endif // __TBB_CPP20_CONCEPTS_PRESENT
293
294 template<typename T>
295 struct minimal_span {
minimal_spanminimal_span296 minimal_span(T* input_data, std::size_t input_size)
297 : data{input_data}
298 , size{input_size}
299 {}
300
beginminimal_span301 T* begin() const {
302 return data;
303 }
endminimal_span304 T* end() const {
305 return data + size;
306 }
307 private:
308 T* data;
309 std::size_t size;
310 };
311
312 //! Minimal array sorting test (less comparator)
313 //! \brief \ref error_guessing
314 TEST_CASE("Minimal array sorting test (less comparator)") {
315 parallel_sort_test_suite<std::vector<Minimal>, MinimalLessCompare>();
316 }
317
318 //! Float array sorting test (default comparator)
319 //! \brief \ref error_guessing
320 TEST_CASE("Float array sorting test (default comparator)") {
321 parallel_sort_test_suite<std::vector<float>>();
322 }
323
324 //! tbb::concurrent_vector<float> sorting test (less comparator)
325 //! \brief \ref error_guessing
326 TEST_CASE("tbb::concurrent_vector<float> sorting test (less comparator)") {
327 parallel_sort_test_suite<tbb::concurrent_vector<float>, std::less<float>>();
328 }
329
330 //! tbb::concurrent_vector<float> sorting test (default comparator)
331 //! \brief \ref error_guessing
332 TEST_CASE("tbb::concurrent_vector<float> sorting test (default comparator)") {
333 parallel_sort_test_suite<tbb::concurrent_vector<float>>();
334 }
335
336 //! Array of strings sorting test (less comparator)
337 //! \brief \ref error_guessing
338 TEST_CASE("Array of strings sorting test (less comparator)") {
339 parallel_sort_test_suite<std::vector<std::string>, std::less<std::string>>();
340 }
341
342 //! Array of strings sorting test (default comparator)
343 //! \brief \ref error_guessing
344 TEST_CASE("Array of strings sorting test (default comparator)") {
345 parallel_sort_test_suite<std::vector<std::string>>();
346 }
347
348 //! tbb::concurrent_vector<Minimal> sorting test (less comparator)
349 //! \brief \ref error_guessing
350 TEST_CASE("tbb::concurrent_vector<Minimal> sorting test (less comparator)") {
351 parallel_sort_test_suite<tbb::concurrent_vector<Minimal>, MinimalLessCompare>();
352 }
353
354 constexpr std::size_t array_size = 10000;
355
356 template<typename SortFunctor>
sort_array_test(const SortFunctor & sort_functor)357 void sort_array_test(const SortFunctor& sort_functor) {
358 int test_array[array_size];
359 for (std::size_t i = 0; i < array_size; ++i)
360 test_array[i] = rand() % array_size;
361
362 sort_functor(test_array);
363
364 for (std::size_t i = 0; i < array_size - 1; ++i)
365 REQUIRE_MESSAGE(test_array[i] <= test_array[i + 1], "Testing data not sorted");
366 }
367
368 //! Array sorting test (default comparator)
369 //! \brief \ref error_guessing
370 TEST_CASE("Array sorting test (default comparator)") {
371 for ( auto concurrency_level : utils::concurrency_range() ) {
372 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level);
__anon54e49e5e0202(int (&array)[array_size]) 373 sort_array_test([](int (&array)[array_size]) {
374 tbb::parallel_sort(array);
375 });
376 }
377 }
378
379 //! Test array sorting via rvalue span (default comparator)
380 //! \brief \ref error_guessing
381 TEST_CASE("Test array sorting via rvalue span (default comparator)") {
__anon54e49e5e0302(int (&array)[array_size]) 382 sort_array_test([](int (&array)[array_size]) {
383 tbb::parallel_sort(minimal_span<int>{array, array_size});
384 });
385 }
386
387 //! Test array sorting via const span (default comparator)
388 //! \brief \ref error_guessing
389 TEST_CASE("Test array sorting via const span (default comparator)") {
__anon54e49e5e0402(int (&array)[array_size]) 390 sort_array_test([](int (&array)[array_size]) {
391 const minimal_span<int> span(array, array_size);
392 tbb::parallel_sort(span);
393 });
394 }
395
396 //! Test rvalue container with stateful comparator
397 //! \brief \ref error_guessing
398 TEST_CASE("Test rvalue container with stateful comparator") {
399 // Create sorted range
400 std::vector<std::size_t> test_vector(array_size);
401 for (std::size_t i = 0; i < array_size; ++i)
402 test_vector[i] = i;
403
404 std::atomic<std::size_t> count{0};
__anon54e49e5e0502(std::size_t lhs, std::size_t rhs) 405 tbb::parallel_sort(std::move(test_vector), [&](std::size_t lhs, std::size_t rhs) {
406 ++count;
407 return lhs < rhs;
408 });
409
410 // The comparator should be called at least (size - 1) times to check that the array is sorted
411 REQUIRE_MESSAGE(count >= array_size - 1, "Incorrect comparator calls count");
412 }
413
414 //! Testing workers going to sleep
415 //! \brief \ref resource_usage
416 TEST_CASE("That all workers sleep when no work") {
417 int test_array[array_size];
418 for (std::size_t i = 0; i < array_size; ++i)
419 test_array[i] = rand() % array_size;
420
421 tbb::parallel_sort(test_array);
422 TestCPUUserTime(utils::get_platform_max_threads());
423 }
424
425 #if __TBB_CPP20_CONCEPTS_PRESENT
426 //! \brief \ref error_guessing
427 TEST_CASE("parallel_sort constraints") {
428 test_psort_iterator_constraints();
429 test_psort_compare_constraints();
430 test_psort_cbs_constraints();
431 }
432 #endif // __TBB_CPP20_CONCEPTS_PRESENT
433