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

Copyright © 2005-2020 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.