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