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 static_assert(can_call_parallel_sort_with_iterator<utils::RandomIterator<int>>); 235 static_assert(can_call_parallel_sort_with_iterator<typename std::vector<int>::iterator>); 236 static_assert(!can_call_parallel_sort_with_iterator<utils::ForwardIterator<int>>); 237 static_assert(!can_call_parallel_sort_with_iterator<utils::InputIterator<int>>); 238 239 static_assert(can_call_parallel_sort_with_iterator_and_compare<utils::RandomIterator<int>, CorrectCompare<int>>); 240 static_assert(can_call_parallel_sort_with_iterator_and_compare<typename std::vector<int>::iterator, CorrectCompare<int>>); 241 static_assert(!can_call_parallel_sort_with_iterator_and_compare<utils::ForwardIterator<int>, CorrectCompare<int>>); 242 static_assert(!can_call_parallel_sort_with_iterator_and_compare<utils::InputIterator<int>, CorrectCompare<int>>); 243 } 244 245 void test_psort_compare_constraints() { 246 using namespace test_concepts::compare; 247 using CorrectIterator = test_concepts::container_based_sequence::iterator; 248 using CorrectCBS = test_concepts::container_based_sequence::Correct; 249 static_assert(can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, Correct<int>>); 250 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, NoOperatorRoundBrackets<int>>); 251 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, WrongFirstInputOperatorRoundBrackets<int>>); 252 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, WrongSecondInputOperatorRoundBrackets<int>>); 253 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, WrongReturnOperatorRoundBrackets<int>>); 254 255 static_assert(can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, Correct<int>>); 256 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, NoOperatorRoundBrackets<int>>); 257 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, WrongFirstInputOperatorRoundBrackets<int>>); 258 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, WrongSecondInputOperatorRoundBrackets<int>>); 259 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, WrongReturnOperatorRoundBrackets<int>>); 260 } 261 262 void test_psort_cbs_constraints() { 263 using namespace test_concepts::container_based_sequence; 264 using CorrectCompare = test_concepts::compare::Correct<int>; 265 static_assert(can_call_parallel_sort_with_cbs<Correct>); 266 static_assert(!can_call_parallel_sort_with_cbs<NoBegin>); 267 static_assert(!can_call_parallel_sort_with_cbs<NoEnd>); 268 static_assert(!can_call_parallel_sort_with_cbs<ForwardIteratorCBS>); 269 270 static_assert(can_call_parallel_sort_with_cbs_and_compare<Correct, CorrectCompare>); 271 static_assert(!can_call_parallel_sort_with_cbs_and_compare<NoBegin, CorrectCompare>); 272 static_assert(!can_call_parallel_sort_with_cbs_and_compare<NoEnd, CorrectCompare>); 273 static_assert(!can_call_parallel_sort_with_cbs_and_compare<ForwardIteratorCBS, CorrectCompare>); 274 } 275 276 #endif // __TBB_CPP20_CONCEPTS_PRESENT 277 278 template<typename T> 279 struct minimal_span { 280 minimal_span(T* input_data, std::size_t input_size) 281 : data{input_data} 282 , size{input_size} 283 {} 284 285 T* begin() const { 286 return data; 287 } 288 T* end() const { 289 return data + size; 290 } 291 private: 292 T* data; 293 std::size_t size; 294 }; 295 296 //! Minimal array sorting test (less comparator) 297 //! \brief \ref error_guessing 298 TEST_CASE("Minimal array sorting test (less comparator)") { 299 parallel_sort_test_suite<std::vector<Minimal>, MinimalLessCompare>(); 300 } 301 302 //! Float array sorting test (default comparator) 303 //! \brief \ref error_guessing 304 TEST_CASE("Float array sorting test (default comparator)") { 305 parallel_sort_test_suite<std::vector<float>>(); 306 } 307 308 //! tbb::concurrent_vector<float> sorting test (less comparator) 309 //! \brief \ref error_guessing 310 TEST_CASE("tbb::concurrent_vector<float> sorting test (less comparator)") { 311 parallel_sort_test_suite<tbb::concurrent_vector<float>, std::less<float>>(); 312 } 313 314 //! tbb::concurrent_vector<float> sorting test (default comparator) 315 //! \brief \ref error_guessing 316 TEST_CASE("tbb::concurrent_vector<float> sorting test (default comparator)") { 317 parallel_sort_test_suite<tbb::concurrent_vector<float>>(); 318 } 319 320 //! Array of strings sorting test (less comparator) 321 //! \brief \ref error_guessing 322 TEST_CASE("Array of strings sorting test (less comparator)") { 323 parallel_sort_test_suite<std::vector<std::string>, std::less<std::string>>(); 324 } 325 326 //! Array of strings sorting test (default comparator) 327 //! \brief \ref error_guessing 328 TEST_CASE("Array of strings sorting test (default comparator)") { 329 parallel_sort_test_suite<std::vector<std::string>>(); 330 } 331 332 //! tbb::concurrent_vector<Minimal> sorting test (less comparator) 333 //! \brief \ref error_guessing 334 TEST_CASE("tbb::concurrent_vector<Minimal> sorting test (less comparator)") { 335 parallel_sort_test_suite<tbb::concurrent_vector<Minimal>, MinimalLessCompare>(); 336 } 337 338 constexpr std::size_t array_size = 10000; 339 340 template<typename SortFunctor> 341 void sort_array_test(const SortFunctor& sort_functor) { 342 int test_array[array_size]; 343 for (std::size_t i = 0; i < array_size; ++i) 344 test_array[i] = rand() % array_size; 345 346 sort_functor(test_array); 347 348 for (std::size_t i = 0; i < array_size - 1; ++i) 349 REQUIRE_MESSAGE(test_array[i] <= test_array[i + 1], "Testing data not sorted"); 350 } 351 352 //! Array sorting test (default comparator) 353 //! \brief \ref error_guessing 354 TEST_CASE("Array sorting test (default comparator)") { 355 for ( auto concurrency_level : utils::concurrency_range() ) { 356 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level); 357 sort_array_test([](int (&array)[array_size]) { 358 tbb::parallel_sort(array); 359 }); 360 } 361 } 362 363 //! Test array sorting via rvalue span (default comparator) 364 //! \brief \ref error_guessing 365 TEST_CASE("Test array sorting via rvalue span (default comparator)") { 366 sort_array_test([](int (&array)[array_size]) { 367 tbb::parallel_sort(minimal_span<int>{array, array_size}); 368 }); 369 } 370 371 //! Test array sorting via const span (default comparator) 372 //! \brief \ref error_guessing 373 TEST_CASE("Test array sorting via const span (default comparator)") { 374 sort_array_test([](int (&array)[array_size]) { 375 const minimal_span<int> span(array, array_size); 376 tbb::parallel_sort(span); 377 }); 378 } 379 380 //! Test rvalue container with stateful comparator 381 //! \brief \ref error_guessing 382 TEST_CASE("Test rvalue container with stateful comparator") { 383 // Create sorted range 384 std::vector<std::size_t> test_vector(array_size); 385 for (std::size_t i = 0; i < array_size; ++i) 386 test_vector[i] = i; 387 388 std::atomic<std::size_t> count{0}; 389 tbb::parallel_sort(std::move(test_vector), [&](std::size_t lhs, std::size_t rhs) { 390 ++count; 391 return lhs < rhs; 392 }); 393 394 // The comparator should be called at least (size - 1) times to check that the array is sorted 395 REQUIRE_MESSAGE(count >= array_size - 1, "Incorrect comparator calls count"); 396 } 397 398 //! Testing workers going to sleep 399 //! \brief \ref resource_usage 400 TEST_CASE("That all workers sleep when no work") { 401 int test_array[array_size]; 402 for (std::size_t i = 0; i < array_size; ++i) 403 test_array[i] = rand() % array_size; 404 405 tbb::parallel_sort(test_array); 406 TestCPUUserTime(utils::get_platform_max_threads()); 407 } 408 409 #if __TBB_CPP20_CONCEPTS_PRESENT 410 //! \brief \ref error_guessing 411 TEST_CASE("parallel_sort constraints") { 412 test_psort_iterator_constraints(); 413 test_psort_compare_constraints(); 414 test_psort_cbs_constraints(); 415 } 416 #endif // __TBB_CPP20_CONCEPTS_PRESENT 417