1 /* 2 Copyright (c) 2005-2020 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 21 #include "tbb/parallel_sort.h" 22 #include "tbb/concurrent_vector.h" 23 #include "tbb/global_control.h" 24 25 #include <math.h> 26 #include <vector> 27 #include <functional> 28 #include <string> 29 #include <cstring> 30 #include <cstddef> 31 #include <cstdio> 32 33 //! \file test_parallel_sort.cpp 34 //! \brief Test for [algorithms.parallel_sort] 35 36 /** Has tightly controlled interface so that we can verify 37 that parallel_sort uses only the required interface. */ 38 class Minimal { 39 int val; 40 public: 41 void set_val(int i) { val = i; } 42 static bool Less (const Minimal &a, const Minimal &b) { 43 return (a.val < b.val); 44 } 45 static bool AreEqual( Minimal &a, Minimal &b) { 46 return a.val == b.val; 47 } 48 }; 49 50 //! Defines a comparison function object for Minimal 51 class MinimalLessCompare { 52 public: 53 bool operator() (const Minimal &a, const Minimal &b) const { 54 return Minimal::Less(a,b); 55 } 56 }; 57 58 //! The default validate; but it uses operator== which is not required 59 template<typename Range> 60 void validate(Range test_range, Range sorted_range, std::size_t size) { 61 for (std::size_t i = 0; i < size; i++) { 62 REQUIRE( test_range[i] == sorted_range[i] ); 63 } 64 } 65 66 //! A validate() specialized to Minimal since it does not define an operator== 67 void validate(Minimal* test_range, Minimal* sorted_range, std::size_t size) { 68 for (std::size_t i = 0; i < size; i++) { 69 REQUIRE( Minimal::AreEqual(test_range[i], sorted_range[i]) ); 70 } 71 } 72 73 //! A validate() specialized to concurrent_vector<Minimal> since it does not define an operator== 74 void validate(tbb::concurrent_vector<Minimal>::iterator test_range, tbb::concurrent_vector<Minimal>::iterator sorted_range, std::size_t size) { 75 for (std::size_t i = 0; i < size; i++) { 76 REQUIRE( Minimal::AreEqual(test_range[i], sorted_range[i]) ); 77 } 78 } 79 80 //! The default initialization routine. 81 /*! This routine assumes that you can assign to the elements from a float. 82 It assumes that iter and sorted_list have already been allocated. It fills 83 them according to the current data set (tracked by a local static variable). 84 Returns true if a valid test has been setup, or false if there is no test to 85 perform. 86 */ 87 template <typename RefType, typename ValueType> 88 void set(RefType& ref, ValueType new_value) { 89 ref = static_cast<RefType>(new_value); 90 } 91 92 template <typename ValueType> 93 void set(Minimal& minimal_ref, ValueType new_value) { 94 minimal_ref.set_val(static_cast<int>(new_value)); 95 } 96 97 template <typename RandomAccessIterator, typename Compare> 98 bool fill_ranges(RandomAccessIterator test_range_begin, RandomAccessIterator sorted_range_begin, 99 std::size_t size, const Compare &compare) { 100 101 static char test_case = 0; 102 const char num_cases = 3; 103 104 if (test_case < num_cases) { 105 // switch on the current test case, filling the test_list and sorted_list appropriately 106 switch(test_case) { 107 case 0: 108 /* use sin to generate the values */ 109 for (std::size_t i = 0; i < size; i++) { 110 set(test_range_begin[i], sin(float(i))); 111 set(sorted_range_begin[i], sin(float(i))); 112 } 113 break; 114 case 1: 115 /* presorted list */ 116 for (std::size_t i = 0; i < size; i++) { 117 set(test_range_begin[i], i); 118 set(sorted_range_begin[i], i); 119 } 120 break; 121 case 2: 122 /* reverse-sorted list */ 123 for (std::size_t i = 0; i < size; i++) { 124 set(test_range_begin[i], size - i); 125 set(sorted_range_begin[i], size - i); 126 } 127 break; 128 } 129 130 // pre-sort sorted_range for later validity testing 131 std::sort(sorted_range_begin, sorted_range_begin + size, compare); 132 test_case++; 133 return true; 134 } 135 test_case = 0; 136 return false; 137 } 138 139 //! The initialization routine specialized to the class string 140 /*! strings are created from floats. 141 */ 142 bool fill_ranges(std::string* iter, std::string* sorted_list, std::size_t size, const std::less<std::string> &compare) { 143 static char test_case = 0; 144 const char num_cases = 1; 145 146 if (test_case < num_cases) { 147 /* use sin to generate the values */ 148 for (std::size_t i = 0; i < size; i++) { 149 char buffer[20]; 150 // Getting rid of secure warning issued by VC 14 and newer 151 #if _MSC_VER && __STDC_SECURE_LIB__>=200411 152 sprintf_s(buffer, sizeof(buffer), "%f", float(sin(float(i)))); 153 #else 154 sprintf(buffer, "%f", float(sin(float(i)))); 155 #endif 156 sorted_list[i] = iter[i] = std::string(buffer); 157 } 158 159 std::sort(sorted_list, sorted_list + size, compare); 160 test_case++; 161 return true; 162 } 163 test_case = 0; 164 return false; 165 } 166 167 //! The default test routine. 168 /*! Tests all data set sizes from 0 to N, all grainsizes from 0 to G=10, and selects from 169 all possible interfaces to parallel_sort depending on whether a scratch space and 170 compare have been provided. 171 */ 172 template<typename ValueType, std::size_t Size> 173 struct parallel_sort_test { 174 static void run() { 175 std::less<ValueType> default_comp; 176 ValueType* array = new ValueType[Size]; 177 ValueType* sorted_array = new ValueType[Size]; 178 179 while (fill_ranges(array, sorted_array, Size, default_comp)) { 180 tbb::parallel_sort(array, array + Size); 181 validate(array, sorted_array, Size); 182 } 183 184 delete[] array; 185 delete[] sorted_array; 186 } 187 188 template<typename Comparator> 189 static void run(Comparator& comp) { 190 ValueType* array = new ValueType[Size]; 191 ValueType* sorted_array = new ValueType[Size]; 192 193 while (fill_ranges(array, sorted_array, Size, comp)) { 194 tbb::parallel_sort(array, array + Size, comp); 195 validate(array, sorted_array, Size); 196 } 197 198 delete[] array; 199 delete[] sorted_array; 200 } 201 }; 202 203 template<typename ValueType, std::size_t Size> 204 struct parallel_sort_test<tbb::concurrent_vector<ValueType>, Size> { 205 static void run() { 206 std::less<ValueType> default_comp; 207 tbb::concurrent_vector<ValueType> vector(Size); 208 tbb::concurrent_vector<ValueType> sorted_vector(Size); 209 210 while (fill_ranges(std::begin(vector), std::begin(sorted_vector), Size, default_comp)) { 211 tbb::parallel_sort(vector); 212 validate(std::begin(vector), std::begin(sorted_vector), Size); 213 } 214 } 215 216 template<typename Comparator> 217 static void run(Comparator& comp) { 218 tbb::concurrent_vector<ValueType> vector(Size); 219 tbb::concurrent_vector<ValueType> sorted_vector(Size); 220 221 while (fill_ranges(std::begin(vector), std::begin(sorted_vector), Size, comp)) { 222 tbb::parallel_sort(vector, comp); 223 validate(std::begin(vector), std::begin(sorted_vector), Size); 224 } 225 } 226 }; 227 228 template<typename ValueType, typename Comparator> 229 void parallel_sort_test_suite() { 230 Comparator comp; 231 for (auto concurrency_level : utils::concurrency_range()) { 232 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level); 233 parallel_sort_test<ValueType, /*Size*/0 >::run(comp); 234 parallel_sort_test<ValueType, /*Size*/1 >::run(comp); 235 parallel_sort_test<ValueType, /*Size*/10 >::run(comp); 236 parallel_sort_test<ValueType, /*Size*/9999 >::run(comp); 237 parallel_sort_test<ValueType, /*Size*/50000>::run(comp); 238 } 239 } 240 241 template<typename ValueType> 242 void parallel_sort_test_suite() { 243 for (auto concurrency_level : utils::concurrency_range()) { 244 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level); 245 parallel_sort_test<ValueType, /*Size*/0 >::run(); 246 parallel_sort_test<ValueType, /*Size*/1 >::run(); 247 parallel_sort_test<ValueType, /*Size*/10 >::run(); 248 parallel_sort_test<ValueType, /*Size*/9999 >::run(); 249 parallel_sort_test<ValueType, /*Size*/50000>::run(); 250 } 251 } 252 253 //! Minimal array sorting test (less comparator) 254 //! \brief \ref error_guessing 255 TEST_CASE("Minimal array sorting test (less comparator)") { 256 parallel_sort_test_suite<Minimal, MinimalLessCompare>(); 257 } 258 259 //! Float array sorting test (default comparator) 260 //! \brief \ref error_guessing 261 TEST_CASE("Float array sorting test (default comparator)") { 262 parallel_sort_test_suite<float>(); 263 } 264 265 //! tbb::concurrent_vector<float> sorting test (less comparator) 266 //! \brief \ref error_guessing 267 TEST_CASE("tbb::concurrent_vector<float> sorting test (less comparator)") { 268 parallel_sort_test_suite<tbb::concurrent_vector<float>, std::less<float>>(); 269 } 270 271 //! tbb::concurrent_vector<float> sorting test (default comparator) 272 //! \brief \ref error_guessing 273 TEST_CASE("tbb::concurrent_vector<float> sorting test (default comparator)") { 274 parallel_sort_test_suite<tbb::concurrent_vector<float>>(); 275 } 276 277 //! Array of strings sorting test (less comparator) 278 //! \brief \ref error_guessing 279 TEST_CASE("Array of strings sorting test (less comparator)") { 280 parallel_sort_test_suite<std::string, std::less<std::string>>(); 281 } 282 283 //! Array of strings sorting test (default comparator) 284 //! \brief \ref error_guessing 285 TEST_CASE("Array of strings sorting test (default comparator)") { 286 parallel_sort_test_suite<std::string>(); 287 } 288 289 //! tbb::concurrent_vector<Minimal> sorting test (less comparator) 290 //! \brief \ref error_guessing 291 TEST_CASE("tbb::concurrent_vector<Minimal> sorting test (less comparator)") { 292 parallel_sort_test_suite<tbb::concurrent_vector<Minimal>, MinimalLessCompare>(); 293 } 294 295 const int vector_size = 10000; 296 297 //! Array sorting test (default comparator) 298 //! \brief \ref error_guessing 299 TEST_CASE("Array sorting test (default comparator)") { 300 for ( auto concurrency_level : utils::concurrency_range() ) { 301 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level); 302 303 int test_array[vector_size]; 304 for (int i = 0; i < vector_size; ++i) 305 test_array[i] = rand() % vector_size; 306 307 tbb::parallel_sort(test_array); 308 309 for(int i = 0; i < vector_size - 1; ++i) 310 REQUIRE_MESSAGE(test_array[i] <= test_array[i + 1], "Testing data not sorted"); 311 } 312 } 313 314 //! Testing workers going to sleep 315 //! \brief \ref resource_usage 316 TEST_CASE("That all workers sleep when no work") { 317 int test_array[vector_size]; 318 for (int i = 0; i < vector_size; ++i) 319 test_array[i] = rand() % vector_size; 320 321 tbb::parallel_sort(test_array); 322 TestCPUUserTime(utils::get_platform_max_threads()); 323 } 324