1 /* 2 Copyright (c) 2005-2021 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 #include "detail/_namespace_injection.h" 21 #include "parallel_for.h" 22 #include "blocked_range.h" 23 #include "profiling.h" 24 25 #include <algorithm> 26 #include <iterator> 27 #include <functional> 28 #include <cstddef> 29 30 namespace tbb { 31 namespace detail { 32 namespace d1 { 33 34 //! Range used in quicksort to split elements into subranges based on a value. 35 /** The split operation selects a splitter and places all elements less than or equal 36 to the value in the first range and the remaining elements in the second range. 37 @ingroup algorithms */ 38 template<typename RandomAccessIterator, typename Compare> 39 class quick_sort_range { 40 std::size_t median_of_three( const RandomAccessIterator& array, std::size_t l, std::size_t m, std::size_t r ) const { 41 return comp(array[l], array[m]) ? ( comp(array[m], array[r]) ? m : ( comp(array[l], array[r]) ? r : l ) ) 42 : ( comp(array[r], array[m]) ? m : ( comp(array[r], array[l]) ? r : l ) ); 43 } 44 45 std::size_t pseudo_median_of_nine( const RandomAccessIterator& array, const quick_sort_range& range ) const { 46 std::size_t offset = range.size / 8u; 47 return median_of_three(array, 48 median_of_three(array, 0 , offset, offset * 2), 49 median_of_three(array, offset * 3, offset * 4, offset * 5), 50 median_of_three(array, offset * 6, offset * 7, range.size - 1)); 51 52 } 53 54 std::size_t split_range( quick_sort_range& range ) { 55 RandomAccessIterator array = range.begin; 56 RandomAccessIterator first_element = range.begin; 57 std::size_t m = pseudo_median_of_nine(array, range); 58 if( m != 0 ) std::iter_swap(array, array + m); 59 60 std::size_t i = 0; 61 std::size_t j = range.size; 62 // Partition interval [i + 1,j - 1] with key *first_element. 63 for(;;) { 64 __TBB_ASSERT( i < j, nullptr ); 65 // Loop must terminate since array[l] == *first_element. 66 do { 67 --j; 68 __TBB_ASSERT( i <= j, "bad ordering relation?" ); 69 } while( comp(*first_element, array[j]) ); 70 do { 71 __TBB_ASSERT( i <= j, nullptr ); 72 if( i == j ) goto partition; 73 ++i; 74 } while( comp(array[i], *first_element) ); 75 if( i == j ) goto partition; 76 std::iter_swap(array + i, array + j); 77 } 78 partition: 79 // Put the partition key were it belongs 80 std::iter_swap(array + j, first_element); 81 // array[l..j) is less or equal to key. 82 // array(j..r) is greater or equal to key. 83 // array[j] is equal to key 84 i = j + 1; 85 std::size_t new_range_size = range.size - i; 86 range.size = j; 87 return new_range_size; 88 } 89 90 public: 91 quick_sort_range() = default; 92 quick_sort_range( const quick_sort_range& ) = default; 93 void operator=( const quick_sort_range& ) = delete; 94 95 static constexpr std::size_t grainsize = 500; 96 const Compare& comp; 97 std::size_t size; 98 RandomAccessIterator begin; 99 100 quick_sort_range( RandomAccessIterator begin_, std::size_t size_, const Compare& comp_ ) : 101 comp(comp_), size(size_), begin(begin_) {} 102 103 bool empty() const { return size == 0; } 104 bool is_divisible() const { return size >= grainsize; } 105 106 quick_sort_range( quick_sort_range& range, split ) 107 : comp(range.comp) 108 , size(split_range(range)) 109 // +1 accounts for the pivot element, which is at its correct place 110 // already and, therefore, is not included into subranges. 111 , begin(range.begin + range.size + 1) {} 112 }; 113 114 //! Body class used to test if elements in a range are presorted 115 /** @ingroup algorithms */ 116 template<typename RandomAccessIterator, typename Compare> 117 class quick_sort_pretest_body { 118 const Compare& comp; 119 task_group_context& context; 120 121 public: 122 quick_sort_pretest_body() = default; 123 quick_sort_pretest_body( const quick_sort_pretest_body& ) = default; 124 void operator=( const quick_sort_pretest_body& ) = delete; 125 126 quick_sort_pretest_body( const Compare& _comp, task_group_context& _context ) : comp(_comp), context(_context) {} 127 128 void operator()( const blocked_range<RandomAccessIterator>& range ) const { 129 RandomAccessIterator my_end = range.end(); 130 131 int i = 0; 132 //TODO: consider using std::is_sorted() for each 64 iterations (requires performance measurements) 133 for( RandomAccessIterator k = range.begin(); k != my_end; ++k, ++i ) { 134 if( i % 64 == 0 && context.is_group_execution_cancelled() ) break; 135 136 // The k - 1 is never out-of-range because the first chunk starts at begin+serial_cutoff+1 137 if( comp(*(k), *(k - 1)) ) { 138 context.cancel_group_execution(); 139 break; 140 } 141 } 142 } 143 }; 144 145 //! Body class used to sort elements in a range that is smaller than the grainsize. 146 /** @ingroup algorithms */ 147 template<typename RandomAccessIterator, typename Compare> 148 struct quick_sort_body { 149 void operator()( const quick_sort_range<RandomAccessIterator,Compare>& range ) const { 150 std::sort(range.begin, range.begin + range.size, range.comp); 151 } 152 }; 153 154 //! Method to perform parallel_for based quick sort. 155 /** @ingroup algorithms */ 156 template<typename RandomAccessIterator, typename Compare> 157 void do_parallel_quick_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) { 158 parallel_for(quick_sort_range<RandomAccessIterator,Compare>(begin, end - begin, comp), 159 quick_sort_body<RandomAccessIterator,Compare>(), 160 auto_partitioner()); 161 } 162 163 //! Wrapper method to initiate the sort by calling parallel_for. 164 /** @ingroup algorithms */ 165 template<typename RandomAccessIterator, typename Compare> 166 void parallel_quick_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) { 167 task_group_context my_context(PARALLEL_SORT); 168 constexpr int serial_cutoff = 9; 169 170 __TBB_ASSERT( begin + serial_cutoff < end, "min_parallel_size is smaller than serial cutoff?" ); 171 RandomAccessIterator k = begin; 172 for( ; k != begin + serial_cutoff; ++k ) { 173 if( comp(*(k + 1), *k) ) { 174 do_parallel_quick_sort(begin, end, comp); 175 } 176 } 177 178 // Check is input range already sorted 179 parallel_for(blocked_range<RandomAccessIterator>(k + 1, end), 180 quick_sort_pretest_body<RandomAccessIterator, Compare>(comp, my_context), 181 auto_partitioner(), 182 my_context); 183 184 if( my_context.is_group_execution_cancelled() ) 185 do_parallel_quick_sort(begin, end, comp); 186 } 187 188 /** \page parallel_sort_iter_req Requirements on iterators for parallel_sort 189 Requirements on the iterator type \c It and its value type \c T for \c parallel_sort: 190 191 - \code void iter_swap( It a, It b ) \endcode Swaps the values of the elements the given 192 iterators \c a and \c b are pointing to. \c It should be a random access iterator. 193 194 - \code bool Compare::operator()( const T& x, const T& y ) \endcode True if x comes before y; 195 **/ 196 197 /** \name parallel_sort 198 See also requirements on \ref parallel_sort_iter_req "iterators for parallel_sort". **/ 199 //@{ 200 201 //! Sorts the data in [begin,end) using the given comparator 202 /** The compare function object is used for all comparisons between elements during sorting. 203 The compare object must define a bool operator() function. 204 @ingroup algorithms **/ 205 template<typename RandomAccessIterator, typename Compare> 206 void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) { 207 constexpr int min_parallel_size = 500; 208 if( end > begin ) { 209 if( end - begin < min_parallel_size ) { 210 std::sort(begin, end, comp); 211 } else { 212 parallel_quick_sort(begin, end, comp); 213 } 214 } 215 } 216 217 //! Sorts the data in [begin,end) with a default comparator \c std::less<RandomAccessIterator> 218 /** @ingroup algorithms **/ 219 template<typename RandomAccessIterator> 220 void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end ) { 221 parallel_sort(begin, end, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>()); 222 } 223 224 //! Sorts the data in rng using the given comparator 225 /** @ingroup algorithms **/ 226 template<typename Range, typename Compare> 227 void parallel_sort( Range& rng, const Compare& comp ) { 228 parallel_sort(std::begin(rng), std::end(rng), comp); 229 } 230 231 //! Sorts the data in rng with a default comparator \c std::less<RandomAccessIterator> 232 /** @ingroup algorithms **/ 233 template<typename Range> 234 void parallel_sort( Range& rng ) { 235 parallel_sort(std::begin(rng), std::end(rng)); 236 } 237 //@} 238 239 } // namespace d1 240 } // namespace detail 241 242 inline namespace v1 { 243 using detail::d1::parallel_sort; 244 } // namespace v1 245 } // namespace tbb 246 247 #endif /*__TBB_parallel_sort_H*/ 248