Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
parallel_sort.h
Go to the documentation of this file.
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 
18 
19 */
20 
21 #ifndef __TBB_parallel_sort_H
22 #define __TBB_parallel_sort_H
23 
24 #include "parallel_for.h"
25 #include "blocked_range.h"
27 #include <algorithm>
28 #include <iterator>
29 #include <functional>
30 #if __TBB_TASK_GROUP_CONTEXT
31  #include "tbb_profiling.h"
32 #endif
33 
34 namespace tbb {
35 
36 namespace interface9 {
38 namespace internal {
39 
41 
43 
46 template<typename RandomAccessIterator, typename Compare>
47 class quick_sort_range: private no_assign {
48 
49  inline size_t median_of_three(const RandomAccessIterator &array, size_t l, size_t m, size_t r) const {
50  return comp(array[l], array[m]) ? ( comp(array[m], array[r]) ? m : ( comp( array[l], array[r]) ? r : l ) )
51  : ( comp(array[r], array[m]) ? m : ( comp( array[r], array[l] ) ? r : l ) );
52  }
53 
54  inline size_t pseudo_median_of_nine( const RandomAccessIterator &array, const quick_sort_range &range ) const {
55  size_t offset = range.size/8u;
56  return median_of_three(array,
57  median_of_three(array, 0, offset, offset*2),
58  median_of_three(array, offset*3, offset*4, offset*5),
59  median_of_three(array, offset*6, offset*7, range.size - 1) );
60 
61  }
62 
63  size_t split_range( quick_sort_range& range ) {
64  using std::iter_swap;
65  RandomAccessIterator array = range.begin;
66  RandomAccessIterator key0 = range.begin;
67  size_t m = pseudo_median_of_nine(array, range);
68  if (m) iter_swap ( array, array+m );
69 
70  size_t i=0;
71  size_t j=range.size;
72  // Partition interval [i+1,j-1] with key *key0.
73  for(;;) {
74  __TBB_ASSERT( i<j, NULL );
75  // Loop must terminate since array[l]==*key0.
76  do {
77  --j;
78  __TBB_ASSERT( i<=j, "bad ordering relation?" );
79  } while( comp( *key0, array[j] ));
80  do {
81  __TBB_ASSERT( i<=j, NULL );
82  if( i==j ) goto partition;
83  ++i;
84  } while( comp( array[i],*key0 ));
85  if( i==j ) goto partition;
86  iter_swap( array+i, array+j );
87  }
88 partition:
89  // Put the partition key were it belongs
90  iter_swap( array+j, key0 );
91  // array[l..j) is less or equal to key.
92  // array(j..r) is greater or equal to key.
93  // array[j] is equal to key
94  i=j+1;
95  size_t new_range_size = range.size-i;
96  range.size = j;
97  return new_range_size;
98  }
99 
100 public:
101 
102  static const size_t grainsize = 500;
103  const Compare &comp;
104  size_t size;
105  RandomAccessIterator begin;
106 
107  quick_sort_range( RandomAccessIterator begin_, size_t size_, const Compare &comp_ ) :
108  comp(comp_), size(size_), begin(begin_) {}
109 
110  bool empty() const {return size==0;}
111  bool is_divisible() const {return size>=grainsize;}
112 
114  : comp(range.comp)
115  , size(split_range(range))
116  // +1 accounts for the pivot element, which is at its correct place
117  // already and, therefore, is not included into subranges.
118  , begin(range.begin+range.size+1) {}
119 };
120 
121 #if __TBB_TASK_GROUP_CONTEXT
122 
124 template<typename RandomAccessIterator, typename Compare>
126  const Compare &comp;
127 
128 public:
129  quick_sort_pretest_body(const Compare &_comp) : comp(_comp) {}
130 
131  void operator()( const blocked_range<RandomAccessIterator>& range ) const {
132  task &my_task = task::self();
133  RandomAccessIterator my_end = range.end();
134 
135  int i = 0;
136  for (RandomAccessIterator k = range.begin(); k != my_end; ++k, ++i) {
137  if ( i%64 == 0 && my_task.is_cancelled() ) break;
138 
139  // The k-1 is never out-of-range because the first chunk starts at begin+serial_cutoff+1
140  if ( comp( *(k), *(k-1) ) ) {
141  my_task.cancel_group_execution();
142  break;
143  }
144  }
145  }
146 
147 };
148 #endif /* __TBB_TASK_GROUP_CONTEXT */
149 
151 
152 template<typename RandomAccessIterator, typename Compare>
155  //SerialQuickSort( range.begin, range.size, range.comp );
156  std::sort( range.begin, range.begin + range.size, range.comp );
157  }
158 };
159 
161 
162 template<typename RandomAccessIterator, typename Compare>
163 void parallel_quick_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) {
164 #if __TBB_TASK_GROUP_CONTEXT
165  task_group_context my_context(PARALLEL_SORT);
166  const int serial_cutoff = 9;
167 
168  __TBB_ASSERT( begin + serial_cutoff < end, "min_parallel_size is smaller than serial cutoff?" );
169  RandomAccessIterator k = begin;
170  for ( ; k != begin + serial_cutoff; ++k ) {
171  if ( comp( *(k+1), *k ) ) {
172  goto do_parallel_quick_sort;
173  }
174  }
175 
179  my_context);
180 
181  if (my_context.is_group_execution_cancelled())
182 do_parallel_quick_sort:
183 #endif /* __TBB_TASK_GROUP_CONTEXT */
186  auto_partitioner() );
187 }
188 
189 } // namespace internal
191 } // namespace interfaceX
192 
205 
207 
210 template<typename RandomAccessIterator, typename Compare>
211 void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp) {
212  const int min_parallel_size = 500;
213  if( end > begin ) {
214  if (end - begin < min_parallel_size) {
215  std::sort(begin, end, comp);
216  } else {
218  }
219  }
220 }
221 
223 
224 template<typename RandomAccessIterator>
225 inline void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end ) {
226  parallel_sort( begin, end, std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >() );
227 }
228 
230 
231 template<typename Range, typename Compare>
232 void parallel_sort(Range& rng, const Compare& comp) {
234 }
235 
237 
238 template<typename Range>
239 void parallel_sort(Range& rng) {
241 }
242 
244 
245 template<typename T>
246 inline void parallel_sort( T * begin, T * end ) {
247  parallel_sort( begin, end, std::less< T >() );
248 }
250 
251 
252 } // namespace tbb
253 
254 #endif
255 
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp end
const_iterator begin() const
Beginning of range.
Definition: blocked_range.h:73
size_t split_range(quick_sort_range &range)
Definition: parallel_sort.h:63
Range used in quicksort to split elements into subranges based on a value.
Definition: parallel_sort.h:47
An auto partitioner.
Definition: partitioner.h:614
A range over which to iterate.
Definition: blocked_range.h:49
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
auto first(Container &c) -> decltype(begin(c))
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp begin
Used to form groups of tasks.
Definition: task.h:335
Base class for user-defined tasks.
Definition: task.h:592
static task &__TBB_EXPORTED_FUNC self()
The innermost task being executed or destroyed by the current thread at the moment.
Definition: task.cpp:205
Base class for types that should not be assigned.
Definition: tbb_stddef.h:324
void operator()(const blocked_range< RandomAccessIterator > &range) const
auto last(Container &c) -> decltype(begin(c))
const_iterator end() const
One past last value in range.
Definition: blocked_range.h:76
size_t median_of_three(const RandomAccessIterator &array, size_t l, size_t m, size_t r) const
Definition: parallel_sort.h:49
quick_sort_range(RandomAccessIterator begin_, size_t size_, const Compare &comp_)
The graph class.
void parallel_quick_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Wrapper method to initiate the sort by calling parallel_for.
Dummy type that distinguishes splitting constructor from copy constructor.
Definition: tbb_stddef.h:399
Body class used to sort elements in a range that is smaller than the grainsize.
void parallel_for(const Range &range, const Body &body)
Parallel iteration over range with default partitioner.
bool __TBB_EXPORTED_METHOD is_group_execution_cancelled() const
Returns true if the context received cancellation request.
void operator()(const quick_sort_range< RandomAccessIterator, Compare > &range) const
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Sorts the data in [begin,end) using the given comparator.
size_t pseudo_median_of_nine(const RandomAccessIterator &array, const quick_sort_range &range) const
Definition: parallel_sort.h:54
bool cancel_group_execution()
Initiates cancellation of all tasks in this cancellation group and its subordinate groups.
Definition: task.h:910
bool is_cancelled() const
Returns true if the context has received cancellation request.
Definition: task.h:913
quick_sort_range(quick_sort_range &range, split)
Body class used to test if elements in a range are presorted.

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.