Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
Loading...
Searching...
No Matches
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
33namespace tbb {
34
35namespace interface9 {
37namespace internal {
38
40
42
45template<typename RandomAccessIterator, typename Compare>
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 }
87partition:
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
99public:
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
122
123template<typename RandomAccessIterator, typename Compare>
125 const Compare &comp;
126
127public:
128 quick_sort_pretest_body(const Compare &_comp) : comp(_comp) {}
129
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
151template<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
161template<typename RandomAccessIterator, typename Compare>
162void 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
175 parallel_for( blocked_range<RandomAccessIterator>(k+1, end),
178 my_context);
179
180 if (my_context.is_group_execution_cancelled())
181do_parallel_quick_sort:
182#endif /* __TBB_TASK_GROUP_CONTEXT */
186}
187
188} // namespace internal
190} // namespace interfaceX
191
204
206
209template<typename RandomAccessIterator, typename Compare>
210void 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
223template<typename RandomAccessIterator>
224inline void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end ) {
225 parallel_sort( begin, end, std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >() );
226}
227
229
230template<typename Range, typename Compare>
231void parallel_sort(Range& rng, const Compare& comp) {
233}
234
236
237template<typename Range>
238void parallel_sort(Range& rng) {
240}
241
243
244template<typename T>
245inline 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
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition tbb_stddef.h:165
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
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
void parallel_quick_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Wrapper method to initiate the sort by calling parallel_for.
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end, const Compare &comp)
Sorts the data in [begin,end) using the given comparator.
The graph class.
auto last(Container &c) -> decltype(begin(c))
auto first(Container &c) -> decltype(begin(c))
A range over which to iterate.
const_iterator begin() const
Beginning of range.
const_iterator end() const
One past last value in range.
Range used in quicksort to split elements into subranges based on a value.
size_t median_of_three(const RandomAccessIterator &array, size_t l, size_t m, size_t r) const
quick_sort_range(quick_sort_range &range, split)
size_t split_range(quick_sort_range &range)
size_t pseudo_median_of_nine(const RandomAccessIterator &array, const quick_sort_range &range) const
quick_sort_range(RandomAccessIterator begin_, size_t size_, const Compare &comp_)
Body class used to test if elements in a range are presorted.
void operator()(const blocked_range< RandomAccessIterator > &range) const
Body class used to sort elements in a range that is smaller than the grainsize.
void operator()(const quick_sort_range< RandomAccessIterator, Compare > &range) const
An auto partitioner.
Used to form groups of tasks.
Definition task.h:358
bool __TBB_EXPORTED_METHOD is_group_execution_cancelled() const
Returns true if the context received cancellation request.
Base class for user-defined tasks.
Definition task.h:615
bool cancel_group_execution()
Initiates cancellation of all tasks in this cancellation group and its subordinate groups.
Definition task.h:971
bool is_cancelled() const
Returns true if the context has received cancellation request.
Definition task.h:974
static task &__TBB_EXPORTED_FUNC self()
The innermost task being executed or destroyed by the current thread at the moment.
Definition task.cpp:201
Base class for types that should not be assigned.
Definition tbb_stddef.h:322
Dummy type that distinguishes splitting constructor from copy constructor.
Definition tbb_stddef.h:416

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.