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 35 //! \file test_parallel_sort.cpp 36 //! \brief Test for [algorithms.parallel_sort] 37 38 /** Has tightly controlled interface so that we can verify 39 that parallel_sort uses only the required interface. */ 40 class Minimal { 41 int val; 42 public: 43 void set_val(int i) { val = i; } 44 static bool Less (const Minimal &a, const Minimal &b) { 45 return (a.val < b.val); 46 } 47 static bool AreEqual( Minimal &a, Minimal &b) { 48 return a.val == b.val; 49 } 50 }; 51 52 //! Defines a comparison function object for Minimal 53 class MinimalLessCompare { 54 public: 55 bool operator() (const Minimal &a, const Minimal &b) const { 56 return Minimal::Less(a,b); 57 } 58 }; 59 60 //! The default validate; but it uses operator== which is not required 61 template<typename Range> 62 void validate(Range test_range, Range sorted_range, std::size_t size) { 63 for (std::size_t i = 0; i < size; i++) { 64 REQUIRE( test_range[i] == sorted_range[i] ); 65 } 66 } 67 68 //! A validate() specialized to Minimal since it does not define an operator== 69 void validate(Minimal* test_range, Minimal* sorted_range, std::size_t size) { 70 for (std::size_t i = 0; i < size; i++) { 71 REQUIRE( Minimal::AreEqual(test_range[i], sorted_range[i]) ); 72 } 73 } 74 75 //! A validate() specialized to concurrent_vector<Minimal> since it does not define an operator== 76 void validate(tbb::concurrent_vector<Minimal>::iterator test_range, tbb::concurrent_vector<Minimal>::iterator sorted_range, std::size_t size) { 77 for (std::size_t i = 0; i < size; i++) { 78 REQUIRE( Minimal::AreEqual(test_range[i], sorted_range[i]) ); 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 RandomAccessIterator, typename Compare> 100 bool fill_ranges(RandomAccessIterator test_range_begin, RandomAccessIterator sorted_range_begin, 101 std::size_t size, const Compare &compare) { 102 103 static char test_case = 0; 104 const char num_cases = 3; 105 106 if (test_case < num_cases) { 107 // switch on the current test case, filling the test_list and sorted_list appropriately 108 switch(test_case) { 109 case 0: 110 /* use sin to generate the values */ 111 for (std::size_t i = 0; i < size; i++) { 112 set(test_range_begin[i], sin(float(i))); 113 set(sorted_range_begin[i], sin(float(i))); 114 } 115 break; 116 case 1: 117 /* presorted list */ 118 for (std::size_t i = 0; i < size; i++) { 119 set(test_range_begin[i], i); 120 set(sorted_range_begin[i], i); 121 } 122 break; 123 case 2: 124 /* reverse-sorted list */ 125 for (std::size_t i = 0; i < size; i++) { 126 set(test_range_begin[i], size - i); 127 set(sorted_range_begin[i], size - i); 128 } 129 break; 130 } 131 132 // pre-sort sorted_range for later validity testing 133 std::sort(sorted_range_begin, sorted_range_begin + size, compare); 134 test_case++; 135 return true; 136 } 137 test_case = 0; 138 return false; 139 } 140 141 //! The initialization routine specialized to the class string 142 /*! strings are created from floats. 143 */ 144 bool fill_ranges(std::string* iter, std::string* sorted_list, std::size_t size, const std::less<std::string> &compare) { 145 static char test_case = 0; 146 const char num_cases = 1; 147 148 if (test_case < num_cases) { 149 /* use sin to generate the values */ 150 for (std::size_t i = 0; i < size; i++) { 151 char buffer[20]; 152 // Getting rid of secure warning issued by VC 14 and newer 153 #if _MSC_VER && __STDC_SECURE_LIB__>=200411 154 sprintf_s(buffer, sizeof(buffer), "%f", float(sin(float(i)))); 155 #else 156 sprintf(buffer, "%f", float(sin(float(i)))); 157 #endif 158 sorted_list[i] = iter[i] = std::string(buffer); 159 } 160 161 std::sort(sorted_list, sorted_list + size, compare); 162 test_case++; 163 return true; 164 } 165 test_case = 0; 166 return false; 167 } 168 169 //! The default test routine. 170 /*! Tests all data set sizes from 0 to N, all grainsizes from 0 to G=10, and selects from 171 all possible interfaces to parallel_sort depending on whether a scratch space and 172 compare have been provided. 173 */ 174 template<typename ValueType, std::size_t Size> 175 struct parallel_sort_test { 176 static void run() { 177 std::less<ValueType> default_comp; 178 ValueType* array = new ValueType[Size]; 179 ValueType* sorted_array = new ValueType[Size]; 180 181 while (fill_ranges(array, sorted_array, Size, default_comp)) { 182 tbb::parallel_sort(array, array + Size); 183 validate(array, sorted_array, Size); 184 } 185 186 delete[] array; 187 delete[] sorted_array; 188 } 189 190 template<typename Comparator> 191 static void run(Comparator& comp) { 192 ValueType* array = new ValueType[Size]; 193 ValueType* sorted_array = new ValueType[Size]; 194 195 while (fill_ranges(array, sorted_array, Size, comp)) { 196 tbb::parallel_sort(array, array + Size, comp); 197 validate(array, sorted_array, Size); 198 } 199 200 delete[] array; 201 delete[] sorted_array; 202 } 203 }; 204 205 template<typename ValueType, std::size_t Size> 206 struct parallel_sort_test<tbb::concurrent_vector<ValueType>, Size> { 207 static void run() { 208 std::less<ValueType> default_comp; 209 tbb::concurrent_vector<ValueType> vector(Size); 210 tbb::concurrent_vector<ValueType> sorted_vector(Size); 211 212 while (fill_ranges(std::begin(vector), std::begin(sorted_vector), Size, default_comp)) { 213 tbb::parallel_sort(vector); 214 validate(std::begin(vector), std::begin(sorted_vector), Size); 215 } 216 } 217 218 template<typename Comparator> 219 static void run(Comparator& comp) { 220 tbb::concurrent_vector<ValueType> vector(Size); 221 tbb::concurrent_vector<ValueType> sorted_vector(Size); 222 223 while (fill_ranges(std::begin(vector), std::begin(sorted_vector), Size, comp)) { 224 tbb::parallel_sort(vector, comp); 225 validate(std::begin(vector), std::begin(sorted_vector), Size); 226 } 227 } 228 }; 229 230 template<typename ValueType, typename Comparator> 231 void parallel_sort_test_suite() { 232 Comparator comp; 233 for (auto concurrency_level : utils::concurrency_range()) { 234 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level); 235 parallel_sort_test<ValueType, /*Size*/0 >::run(comp); 236 parallel_sort_test<ValueType, /*Size*/1 >::run(comp); 237 parallel_sort_test<ValueType, /*Size*/10 >::run(comp); 238 parallel_sort_test<ValueType, /*Size*/9999 >::run(comp); 239 parallel_sort_test<ValueType, /*Size*/50000>::run(comp); 240 } 241 } 242 243 template<typename ValueType> 244 void parallel_sort_test_suite() { 245 for (auto concurrency_level : utils::concurrency_range()) { 246 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level); 247 parallel_sort_test<ValueType, /*Size*/0 >::run(); 248 parallel_sort_test<ValueType, /*Size*/1 >::run(); 249 parallel_sort_test<ValueType, /*Size*/10 >::run(); 250 parallel_sort_test<ValueType, /*Size*/9999 >::run(); 251 parallel_sort_test<ValueType, /*Size*/50000>::run(); 252 } 253 } 254 255 #if __TBB_CPP20_CONCEPTS_PRESENT 256 template <typename RandomAccessIterator> 257 concept can_call_parallel_sort_with_iterator = requires( RandomAccessIterator it ) { 258 tbb::parallel_sort(it, it); 259 }; 260 261 template <typename RandomAccessIterator, typename Compare> 262 concept can_call_parallel_sort_with_iterator_and_compare = requires( RandomAccessIterator it, const Compare& compare ) { 263 tbb::parallel_sort(it, it, compare); 264 }; 265 266 template <typename CBS> 267 concept can_call_parallel_sort_with_cbs = requires( CBS& cbs ) { 268 tbb::parallel_sort(cbs); 269 }; 270 271 template <typename CBS, typename Compare> 272 concept can_call_parallel_sort_with_cbs_and_compare = requires( CBS& cbs, const Compare& compare ) { 273 tbb::parallel_sort(cbs, compare); 274 }; 275 276 template <typename T> 277 using CorrectCompare = test_concepts::compare::Correct<T>; 278 279 void test_psort_iterator_constraints() { 280 static_assert(can_call_parallel_sort_with_iterator<utils::RandomIterator<int>>); 281 static_assert(can_call_parallel_sort_with_iterator<typename std::vector<int>::iterator>); 282 static_assert(!can_call_parallel_sort_with_iterator<utils::ForwardIterator<int>>); 283 static_assert(!can_call_parallel_sort_with_iterator<utils::InputIterator<int>>); 284 285 static_assert(can_call_parallel_sort_with_iterator_and_compare<utils::RandomIterator<int>, CorrectCompare<int>>); 286 static_assert(can_call_parallel_sort_with_iterator_and_compare<typename std::vector<int>::iterator, CorrectCompare<int>>); 287 static_assert(!can_call_parallel_sort_with_iterator_and_compare<utils::ForwardIterator<int>, CorrectCompare<int>>); 288 static_assert(!can_call_parallel_sort_with_iterator_and_compare<utils::InputIterator<int>, CorrectCompare<int>>); 289 } 290 291 void test_psort_compare_constraints() { 292 using namespace test_concepts::compare; 293 using CorrectIterator = test_concepts::container_based_sequence::iterator; 294 using CorrectCBS = test_concepts::container_based_sequence::Correct; 295 static_assert(can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, Correct<int>>); 296 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, NoOperatorRoundBrackets<int>>); 297 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, WrongFirstInputOperatorRoundBrackets<int>>); 298 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, WrongSecondInputOperatorRoundBrackets<int>>); 299 static_assert(!can_call_parallel_sort_with_iterator_and_compare<CorrectIterator, WrongReturnOperatorRoundBrackets<int>>); 300 301 static_assert(can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, Correct<int>>); 302 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, NoOperatorRoundBrackets<int>>); 303 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, WrongFirstInputOperatorRoundBrackets<int>>); 304 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, WrongSecondInputOperatorRoundBrackets<int>>); 305 static_assert(!can_call_parallel_sort_with_cbs_and_compare<CorrectCBS, WrongReturnOperatorRoundBrackets<int>>); 306 } 307 308 void test_psort_cbs_constraints() { 309 using namespace test_concepts::container_based_sequence; 310 using CorrectCompare = test_concepts::compare::Correct<int>; 311 static_assert(can_call_parallel_sort_with_cbs<Correct>); 312 static_assert(!can_call_parallel_sort_with_cbs<NoBegin>); 313 static_assert(!can_call_parallel_sort_with_cbs<NoEnd>); 314 static_assert(!can_call_parallel_sort_with_cbs<ForwardIteratorCBS>); 315 316 static_assert(can_call_parallel_sort_with_cbs_and_compare<Correct, CorrectCompare>); 317 static_assert(!can_call_parallel_sort_with_cbs_and_compare<NoBegin, CorrectCompare>); 318 static_assert(!can_call_parallel_sort_with_cbs_and_compare<NoEnd, CorrectCompare>); 319 static_assert(!can_call_parallel_sort_with_cbs_and_compare<ForwardIteratorCBS, CorrectCompare>); 320 } 321 322 #endif // __TBB_CPP20_CONCEPTS_PRESENT 323 324 //! Minimal array sorting test (less comparator) 325 //! \brief \ref error_guessing 326 TEST_CASE("Minimal array sorting test (less comparator)") { 327 parallel_sort_test_suite<Minimal, MinimalLessCompare>(); 328 } 329 330 //! Float array sorting test (default comparator) 331 //! \brief \ref error_guessing 332 TEST_CASE("Float array sorting test (default comparator)") { 333 parallel_sort_test_suite<float>(); 334 } 335 336 //! tbb::concurrent_vector<float> sorting test (less comparator) 337 //! \brief \ref error_guessing 338 TEST_CASE("tbb::concurrent_vector<float> sorting test (less comparator)") { 339 parallel_sort_test_suite<tbb::concurrent_vector<float>, std::less<float>>(); 340 } 341 342 //! tbb::concurrent_vector<float> sorting test (default comparator) 343 //! \brief \ref error_guessing 344 TEST_CASE("tbb::concurrent_vector<float> sorting test (default comparator)") { 345 parallel_sort_test_suite<tbb::concurrent_vector<float>>(); 346 } 347 348 //! Array of strings sorting test (less comparator) 349 //! \brief \ref error_guessing 350 TEST_CASE("Array of strings sorting test (less comparator)") { 351 parallel_sort_test_suite<std::string, std::less<std::string>>(); 352 } 353 354 //! Array of strings sorting test (default comparator) 355 //! \brief \ref error_guessing 356 TEST_CASE("Array of strings sorting test (default comparator)") { 357 parallel_sort_test_suite<std::string>(); 358 } 359 360 //! tbb::concurrent_vector<Minimal> sorting test (less comparator) 361 //! \brief \ref error_guessing 362 TEST_CASE("tbb::concurrent_vector<Minimal> sorting test (less comparator)") { 363 parallel_sort_test_suite<tbb::concurrent_vector<Minimal>, MinimalLessCompare>(); 364 } 365 366 const int vector_size = 10000; 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 374 int test_array[vector_size]; 375 for (int i = 0; i < vector_size; ++i) 376 test_array[i] = rand() % vector_size; 377 378 tbb::parallel_sort(test_array); 379 380 for(int i = 0; i < vector_size - 1; ++i) 381 REQUIRE_MESSAGE(test_array[i] <= test_array[i + 1], "Testing data not sorted"); 382 } 383 } 384 385 //! Testing workers going to sleep 386 //! \brief \ref resource_usage 387 TEST_CASE("That all workers sleep when no work") { 388 int test_array[vector_size]; 389 for (int i = 0; i < vector_size; ++i) 390 test_array[i] = rand() % vector_size; 391 392 tbb::parallel_sort(test_array); 393 TestCPUUserTime(utils::get_platform_max_threads()); 394 } 395 396 #if __TBB_CPP20_CONCEPTS_PRESENT 397 //! \brief \ref error_guessing 398 TEST_CASE("parallel_sort constraints") { 399 test_psort_iterator_constraints(); 400 test_psort_compare_constraints(); 401 test_psort_cbs_constraints(); 402 } 403 #endif // __TBB_CPP20_CONCEPTS_PRESENT 404