1/*
2 Copyright (c) 2005-2019 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 "tbb/parallel_sort.h"
18#include "tbb/task_scheduler_init.h"
19#include "tbb/concurrent_vector.h"
20#include "harness.h"
21#include <math.h>
22#include <vector>
23#include <exception>
24#include <algorithm>
25#include <iterator>
26#include <functional>
27#include <string>
28#include <cstring>
29
30/** Has tightly controlled interface so that we can verify
31 that parallel_sort uses only the required interface. */
32class Minimal {
33 int val;
34public:
35 Minimal() {}
36 void set_val(int i) { val = i; }
37 static bool CompareWith (const Minimal &a, const Minimal &b) {
38 return (a.val < b.val);
39 }
40 static bool AreEqual( Minimal &a, Minimal &b) {
41 return a.val == b.val;
42 }
43};
44
45//! Defines a comparison function object for Minimal
46class MinimalCompare {
47public:
48 bool operator() (const Minimal &a, const Minimal &b) const {
49 return Minimal::CompareWith(a,b);
50 }
51};
52
53//! The default validate; but it uses operator== which is not required
54template<typename RandomAccessIterator>
55bool Validate(RandomAccessIterator a, RandomAccessIterator b, size_t n) {
56 for (size_t i = 0; i < n; i++) {
57 ASSERT( a[i] == b[i], NULL );
58 }
59 return true;
60}
61
62//! A Validate specialized to string for debugging-only
63template<>
64bool Validate<std::string *>(std::string * a, std::string * b, size_t n) {
65 for (size_t i = 0; i < n; i++) {
66 if ( Verbose && a[i] != b[i]) {
67 for (size_t j = 0; j < n; j++) {
68 REPORT("a[%llu] == %s and b[%llu] == %s\n", static_cast<unsigned long long>(j), a[j].c_str(), static_cast<unsigned long long>(j), b[j].c_str());
69 }
70 }
71 ASSERT( a[i] == b[i], NULL );
72 }
73 return true;
74}
75
76//! A Validate specialized to Minimal since it does not define an operator==
77template<>
78bool Validate<Minimal *>(Minimal *a, Minimal *b, size_t n) {
79 for (size_t i = 0; i < n; i++) {
80 ASSERT( Minimal::AreEqual(a[i],b[i]), NULL );
81 }
82 return true;
83}
84
85//! A Validate specialized to concurrent_vector<Minimal> since it does not define an operator==
86template<>
87bool Validate<tbb::concurrent_vector<Minimal>::iterator>(tbb::concurrent_vector<Minimal>::iterator a,
88 tbb::concurrent_vector<Minimal>::iterator b, size_t n) {
89 for (size_t i = 0; i < n; i++) {
90 ASSERT( Minimal::AreEqual(a[i],b[i]), NULL );
91 }
92 return true;
93}
94
95//! used in Verbose mode for identifying which data set is being used
96static std::string test_type;
97
98//! The default initialization routine.
99/*! This routine assumes that you can assign to the elements from a float.
100 It assumes that iter and sorted_list have already been allocated. It fills
101 them according to the current data set (tracked by a local static variable).
102 Returns true if a valid test has been setup, or false if there is no test to
103 perform.
104*/
105
106template < typename RandomAccessIterator, typename Compare >
107bool init_iter(RandomAccessIterator iter, RandomAccessIterator sorted_list, size_t n, const Compare &compare, bool reset) {
108 static char test_case = 0;
109 const char num_cases = 3;
110
111 if (reset) test_case = 0;
112
113 if (test_case < num_cases) {
114 // switch on the current test case, filling the iter and sorted_list appropriately
115 switch(test_case) {
116 case 0:
117 /* use sin to generate the values */
118 test_type = "sin";
119 for (size_t i = 0; i < n; i++)
120 iter[i] = sorted_list[i] = static_cast<typename std::iterator_traits< RandomAccessIterator >::value_type>(sin(float(i)));
121 break;
122 case 1:
123 /* presorted list */
124 test_type = "pre-sorted";
125 for (size_t i = 0; i < n; i++)
126 iter[i] = sorted_list[i] = static_cast<typename std::iterator_traits< RandomAccessIterator >::value_type>(i);
127 break;
128 case 2:
129 /* reverse-sorted list */
130 test_type = "reverse-sorted";
131 for (size_t i = 0; i < n; i++)
132 iter[i] = sorted_list[i] = static_cast<typename std::iterator_traits< RandomAccessIterator >::value_type>(n - i);
133 break;
134 }
135
136 // pre-sort sorted_list for later validity testing
137 std::sort(sorted_list, sorted_list + n, compare);
138 test_case++;
139 return true;
140 }
141 return false;
142}
143
144template < typename T, typename Compare >
145bool init_iter(T * iter, T * sorted_list, size_t n, const Compare &compare, bool reset) {
146 static char test_case = 0;
147 const char num_cases = 3;
148
149 if (reset) test_case = 0;
150
151 if (test_case < num_cases) {
152 // switch on the current test case, filling the iter and sorted_list appropriately
153 switch(test_case) {
154 case 0:
155 /* use sin to generate the values */
156 test_type = "sin";
157 for (size_t i = 0; i < n; i++) {
158 iter[i] = T(sin(float(i)));
159 sorted_list[i] = T(sin(float(i)));
160 }
161 break;
162 case 1:
163 /* presorted list */
164 test_type = "pre-sorted";
165 for (size_t i = 0; i < n; i++) {
166 iter[i] = T(i);
167 sorted_list[i] = T(i);
168 }
169 break;
170 case 2:
171 /* reverse-sorted list */
172 test_type = "reverse-sorted";
173 for (size_t i = 0; i < n; i++) {
174 iter[i] = T(n - i);
175 sorted_list[i] = T(n - i);
176 }
177 break;
178 }
179
180 // pre-sort sorted_list for later validity testing
181 std::sort(sorted_list, sorted_list + n, compare);
182 test_case++;
183 return true;
184 }
185 return false;
186}
187
188
189//! The initialization routine specialized to the class Minimal
190/*! Minimal cannot have floats assigned to it. This function uses the set_val method
191*/
192
193template < >
194bool init_iter(Minimal* iter, Minimal * sorted_list, size_t n, const MinimalCompare &compare, bool reset) {
195 static char test_case = 0;
196 const char num_cases = 3;
197
198 if (reset) test_case = 0;
199
200 if (test_case < num_cases) {
201 switch(test_case) {
202 case 0:
203 /* use sin to generate the values */
204 test_type = "sin";
205 for (size_t i = 0; i < n; i++) {
206 iter[i].set_val( int( sin( float(i) ) * 1000.f) );
207 sorted_list[i].set_val( int ( sin( float(i) ) * 1000.f) );
208 }
209 break;
210 case 1:
211 /* presorted list */
212 test_type = "pre-sorted";
213 for (size_t i = 0; i < n; i++) {
214 iter[i].set_val( int(i) );
215 sorted_list[i].set_val( int(i) );
216 }
217 break;
218 case 2:
219 /* reverse-sorted list */
220 test_type = "reverse-sorted";
221 for (size_t i = 0; i < n; i++) {
222 iter[i].set_val( int(n-i) );
223 sorted_list[i].set_val( int(n-i) );
224 }
225 break;
226 }
227 std::sort(sorted_list, sorted_list + n, compare);
228 test_case++;
229 return true;
230 }
231 return false;
232}
233
234//! The initialization routine specialized to the class concurrent_vector<Minimal>
235/*! Minimal cannot have floats assigned to it. This function uses the set_val method
236*/
237
238template < >
239bool init_iter(tbb::concurrent_vector<Minimal>::iterator iter, tbb::concurrent_vector<Minimal>::iterator sorted_list,
240 size_t n, const MinimalCompare &compare, bool reset) {
241 static char test_case = 0;
242 const char num_cases = 3;
243
244 if (reset) test_case = 0;
245
246 if (test_case < num_cases) {
247 switch(test_case) {
248 case 0:
249 /* use sin to generate the values */
250 test_type = "sin";
251 for (size_t i = 0; i < n; i++) {
252 iter[i].set_val( int( sin( float(i) ) * 1000.f) );
253 sorted_list[i].set_val( int ( sin( float(i) ) * 1000.f) );
254 }
255 break;
256 case 1:
257 /* presorted list */
258 test_type = "pre-sorted";
259 for (size_t i = 0; i < n; i++) {
260 iter[i].set_val( int(i) );
261 sorted_list[i].set_val( int(i) );
262 }
263 break;
264 case 2:
265 /* reverse-sorted list */
266 test_type = "reverse-sorted";
267 for (size_t i = 0; i < n; i++) {
268 iter[i].set_val( int(n-i) );
269 sorted_list[i].set_val( int(n-i) );
270 }
271 break;
272 }
273 std::sort(sorted_list, sorted_list + n, compare);
274 test_case++;
275 return true;
276 }
277 return false;
278}
279
280//! The initialization routine specialized to the class string
281/*! strings are created from floats.
282*/
283
284template<>
285bool init_iter(std::string *iter, std::string *sorted_list, size_t n, const std::less<std::string> &compare, bool reset) {
286 static char test_case = 0;
287 const char num_cases = 1;
288
289 if (reset) test_case = 0;
290
291 if (test_case < num_cases) {
292 switch(test_case) {
293 case 0:
294 /* use sin to generate the values */
295 test_type = "sin";
296 for (size_t i = 0; i < n; i++) {
297 char buffer[20];
298// Getting rid of secure warning issued by VC 14 and newer
299#if _MSC_VER && __STDC_SECURE_LIB__>=200411
300 sprintf_s(buffer, sizeof(buffer), "%f", float(sin(float(i))));
301#else
302 sprintf(buffer, "%f", float(sin(float(i))));
303#endif
304 sorted_list[i] = iter[i] = std::string(buffer);
305 }
306 break;
307 }
308 std::sort(sorted_list, sorted_list + n, compare);
309 test_case++;
310 return true;
311 }
312 return false;
313}
314
315//! The current number of threads in use (for Verbose only)
316static size_t current_p;
317
318//! The current data type being sorted (for Verbose only)
319static std::string current_type;
320
321//! The default test routine.
322/*! Tests all data set sizes from 0 to N, all grainsizes from 0 to G=10, and selects from
323 all possible interfaces to parallel_sort depending on whether a scratch space and
324 compare have been provided.
325*/
326template<typename RandomAccessIterator, typename Compare>
327bool parallel_sortTest(size_t n, RandomAccessIterator iter, RandomAccessIterator sorted_list, const Compare *comp) {
328 bool passed = true;
329
330 Compare local_comp;
331
332 init_iter(iter, sorted_list, n, local_comp, true);
333 do {
334 REMARK("%s %s p=%llu n=%llu :",current_type.c_str(), test_type.c_str(),
335 static_cast<unsigned long long>(current_p), static_cast<unsigned long long>(n));
336 if (comp != NULL) {
337 tbb::parallel_sort(iter, iter + n, local_comp );
338 } else {
339 tbb::parallel_sort(iter, iter + n );
340 }
341 if (!Validate(iter, sorted_list, n))
342 passed = false;
343 REMARK("passed\n");
344 } while (init_iter(iter, sorted_list, n, local_comp, false));
345 return passed;
346}
347
348//! The test routine specialize to Minimal, since it does not have a less defined for it
349template<>
350bool parallel_sortTest(size_t n, Minimal * iter, Minimal * sorted_list, const MinimalCompare *compare) {
351 bool passed = true;
352
353 if (compare == NULL) return passed;
354
355 init_iter(iter, sorted_list, n, *compare, true);
356 do {
357 REMARK("%s %s p=%llu n=%llu :",current_type.c_str(), test_type.c_str(),
358 static_cast<unsigned long long>(current_p), static_cast<unsigned long long>(n));
359
360 tbb::parallel_sort(iter, iter + n, *compare );
361
362 if (!Validate(iter, sorted_list, n))
363 passed = false;
364 REMARK("passed\n");
365 } while (init_iter(iter, sorted_list, n, *compare, false));
366 return passed;
367}
368
369//! The test routine specialize to concurrent_vector of Minimal, since it does not have a less defined for it
370template<>
371bool parallel_sortTest(size_t n, tbb::concurrent_vector<Minimal>::iterator iter,
372 tbb::concurrent_vector<Minimal>::iterator sorted_list, const MinimalCompare *compare) {
373 bool passed = true;
374
375 if (compare == NULL) return passed;
376
377 init_iter(iter, sorted_list, n, *compare, true);
378 do {
379 REMARK("%s %s p=%llu n=%llu :",current_type.c_str(), test_type.c_str(),
380 static_cast<unsigned long long>(current_p), static_cast<unsigned long long>(n));
381
382 tbb::parallel_sort(iter, iter + n, *compare );
383
384 if (!Validate(iter, sorted_list, n))
385 passed = false;
386 REMARK("passed\n");
387 } while (init_iter(iter, sorted_list, n, *compare, false));
388 return passed;
389}
390
391//! The main driver for the tests.
392/*! Minimal, float and string types are used. All interfaces to parallel_sort that are usable
393 by each type are tested.
394*/
395void Flog() {
396 // For each type create:
397 // the list to be sorted by parallel_sort (array)
398 // the list to be sort by STL sort (array_2)
399 // and a less function object
400
401 const size_t N = 50000;
402
403 Minimal *minimal_array = new Minimal[N];
404 Minimal *minimal_array_2 = new Minimal[N];
405 MinimalCompare minimal_less;
406
407 float *float_array = new float[N];
408 float *float_array_2 = new float[N];
409 std::less<float> float_less;
410
411 tbb::concurrent_vector<float> float_cv1;
412 tbb::concurrent_vector<float> float_cv2;
413 float_cv1.grow_to_at_least(N);
414 float_cv2.grow_to_at_least(N);
415
416 std::string *string_array = new std::string[N];
417 std::string *string_array_2 = new std::string[N];
418 std::less<std::string> string_less;
419
420 tbb::concurrent_vector<Minimal> minimal_cv1;
421 tbb::concurrent_vector<Minimal> minimal_cv2;
422 minimal_cv1.grow_to_at_least(N);
423 minimal_cv2.grow_to_at_least(N);
424
425
426 // run the appropriate tests for each type
427
428 current_type = "Minimal(less)";
429 parallel_sortTest(0, minimal_array, minimal_array_2, &minimal_less);
430 parallel_sortTest(1, minimal_array, minimal_array_2, &minimal_less);
431 parallel_sortTest(10, minimal_array, minimal_array_2, &minimal_less);
432 parallel_sortTest(9999, minimal_array, minimal_array_2, &minimal_less);
433 parallel_sortTest(50000, minimal_array, minimal_array_2, &minimal_less);
434
435 current_type = "float (no less)";
436 parallel_sortTest(0, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
437 parallel_sortTest(1, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
438 parallel_sortTest(10, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
439 parallel_sortTest(9999, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
440 parallel_sortTest(50000, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
441
442 current_type = "float (less)";
443 parallel_sortTest(0, float_array, float_array_2, &float_less);
444 parallel_sortTest(1, float_array, float_array_2, &float_less);
445 parallel_sortTest(10, float_array, float_array_2, &float_less);
446 parallel_sortTest(9999, float_array, float_array_2, &float_less);
447 parallel_sortTest(50000, float_array, float_array_2, &float_less);
448
449 current_type = "concurrent_vector<float> (no less)";
450 parallel_sortTest(0, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
451 parallel_sortTest(1, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
452 parallel_sortTest(10, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
453 parallel_sortTest(9999, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
454 parallel_sortTest(50000, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
455
456 current_type = "concurrent_vector<float> (less)";
457 parallel_sortTest(0, float_cv1.begin(), float_cv2.begin(), &float_less);
458 parallel_sortTest(1, float_cv1.begin(), float_cv2.begin(), &float_less);
459 parallel_sortTest(10, float_cv1.begin(), float_cv2.begin(), &float_less);
460 parallel_sortTest(9999, float_cv1.begin(), float_cv2.begin(), &float_less);
461 parallel_sortTest(50000, float_cv1.begin(), float_cv2.begin(), &float_less);
462
463 current_type = "string (no less)";
464 parallel_sortTest(0, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
465 parallel_sortTest(1, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
466 parallel_sortTest(10, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
467 parallel_sortTest(9999, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
468 parallel_sortTest(50000, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
469
470 current_type = "string (less)";
471 parallel_sortTest(0, string_array, string_array_2, &string_less);
472 parallel_sortTest(1, string_array, string_array_2, &string_less);
473 parallel_sortTest(10, string_array, string_array_2, &string_less);
474 parallel_sortTest(9999, string_array, string_array_2, &string_less);
475 parallel_sortTest(50000, string_array, string_array_2, &string_less);
476
477 current_type = "concurrent_vector<Minimal> (less)";
478 parallel_sortTest(0, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
479 parallel_sortTest(1, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
480 parallel_sortTest(10, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
481 parallel_sortTest(9999, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
482 parallel_sortTest(50000, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
483
484 delete [] minimal_array;
485 delete [] minimal_array_2;
486
487 delete [] float_array;
488 delete [] float_array_2;
489
490 delete [] string_array;
491 delete [] string_array_2;
492}
493
494const int elements = 10000;
495
496void rand_vec(std::vector<int> &v) {
497 for (int i=0; i<elements; ++i) {
498 (v.push_back(rand()%elements*10));
499 }
500}
501
502void range_sort_test() {
503 std::vector<int> v;
504
505 typedef std::vector<int>::iterator itor;
506 // iterator checks
507 rand_vec(v);
508 tbb::parallel_sort(v.begin(), v.end());
509 for(itor a=v.begin(); a<v.end()-1; ++a) ASSERT(*a <= *(a+1), "v not sorted");
510 v.clear();
511
512 rand_vec(v);
513 tbb::parallel_sort(v.begin(), v.end(), std::greater<int>());
514 for(itor a=v.begin(); a<v.end()-1; ++a) ASSERT(*a >= *(a+1), "v not sorted");
515 v.clear();
516
517 // range checks
518 rand_vec(v);
519 tbb::parallel_sort(v);
520 for(itor a=v.begin(); a<v.end()-1; ++a) ASSERT(*a <= *(a+1), "v not sorted");
521 v.clear();
522
523 rand_vec(v);
524 tbb::parallel_sort(v, std::greater<int>());
525 for(itor a=v.begin(); a<v.end()-1; ++a) ASSERT(*a >= *(a+1), "v not sorted");
526 v.clear();
527
528 // array tests
529 int arr[elements];
530 for(int i=0; i<elements; ++i) arr[i] = rand()%(elements*10);
531 tbb::parallel_sort(arr);
532 for(int i=0; i<elements-1; ++i) ASSERT(arr[i] <= arr[i+1], "arr not sorted");
533}
534
535#include <cstdio>
536#include "harness_cpu.h"
537
538int TestMain () {
539 if( MinThread<1 ) {
540 REPORT("Usage: number of threads must be positive\n");
541 exit(1);
542 }
543 for( int p=MinThread; p<=MaxThread; ++p ) {
544 if( p>0 ) {
545 tbb::task_scheduler_init init( p );
546 current_p = p;
547 Flog();
548 range_sort_test();
549
550 // Test that all workers sleep when no work
551 TestCPUUserTime(p);
552 }
553 }
554 return Harness::Done;
555}
556
557