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: 44 void set_val(int i) { val = i; } 45 static bool Less (const Minimal &a, const Minimal &b) { 46 return (a.val < b.val); 47 } 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: 56 bool operator() (const Minimal &a, const Minimal &b) const { 57 return Minimal::Less(a,b); 58 } 59 }; 60 61 template<typename Value> 62 bool compare(const Value& lhs, const Value& rhs) { 63 return lhs == rhs; 64 } 65 66 bool compare(const Minimal& lhs, const Minimal& rhs) { 67 return Minimal::AreEqual(lhs, rhs); 68 } 69 70 template<typename 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> 90 void set(RefType& ref, ValueType new_value) { 91 ref = static_cast<RefType>(new_value); 92 } 93 94 template <typename ValueType> 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> 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> 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 { 154 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> 166 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> 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> 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 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 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 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 { 296 minimal_span(T* input_data, std::size_t input_size) 297 : data{input_data} 298 , size{input_size} 299 {} 300 301 T* begin() const { 302 return data; 303 } 304 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> 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); 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)") { 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)") { 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}; 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