oneapi/tbb/parallel_sort.h

0001 /*
0002     Copyright (c) 2005-2021 Intel Corporation
0003
0004     Licensed under the Apache License, Version 2.0 (the "License");
0005     you may not use this file except in compliance with the License.
0006     You may obtain a copy of the License at
0007
0008         http://www.apache.org/licenses/LICENSE-2.0
0009
0010     Unless required by applicable law or agreed to in writing, software
0011     distributed under the License is distributed on an "AS IS" BASIS,
0012     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013     See the License for the specific language governing permissions and
0014     limitations under the License.
0015 */
0016
0017 #ifndef __TBB_parallel_sort_H
0018 #define __TBB_parallel_sort_H
0019
0020 #include "detail/_namespace_injection.h"
0021 #include "parallel_for.h"
0022 #include "blocked_range.h"
0023 #include "profiling.h"
0024
0025 #include <algorithm>
0026 #include <iterator>
0027 #include <functional>
0028 #include <cstddef>
0029
0030 namespace tbb {
0031 namespace detail {
0032 #if __TBB_CPP20_CONCEPTS_PRESENT
0033 inline namespace d0 {
0034
0035 // TODO: consider using std::strict_weak_order concept
0036 template <typename Compare, typename Iterator>
0037 concept compare = requires( const std::remove_reference_t<Compare>& comp, typename std::iterator_traits<Iterator>::reference value ) {
0038     // Forward via iterator_traits::reference
0039     { comp(typename std::iterator_traits<Iterator>::reference(value),
0040            typename std::iterator_traits<Iterator>::reference(value)) } -> std::convertible_to<bool>;
0041 };
0042
0043 // Inspired by std::__PartiallyOrderedWith exposition only concept
0044 template <typename T>
0045 concept less_than_comparable = requires( const std::remove_reference_t<T>& lhs,
0046                                          const std::remove_reference_t<T>& rhs ) {
0047     { lhs < rhs } -> boolean_testable;
0048 };
0049
0050 } // namespace d0
0051 #endif // __TBB_CPP20_CONCEPTS_PRESENT
0052 namespace d1 {
0053
0054 //! Range used in quicksort to split elements into subranges based on a value.
0055 /** The split operation selects a splitter and places all elements less than or equal
0056     to the value in the first range and the remaining elements in the second range.
0057     @ingroup algorithms */
0058 template<typename RandomAccessIterator, typename Compare>
0059 class quick_sort_range {
0060     std::size_t median_of_three( const RandomAccessIterator& array, std::size_t l, std::size_t m, std::size_t r ) const {
0061         return comp(array[l], array[m]) ? ( comp(array[m], array[r]) ? m : ( comp(array[l], array[r]) ? r : l ) )
0062                                         : ( comp(array[r], array[m]) ? m : ( comp(array[r], array[l]) ? r : l ) );
0063     }
0064
0065     std::size_t pseudo_median_of_nine( const RandomAccessIterator& array, const quick_sort_range& range ) const {
0066         std::size_t offset = range.size / 8u;
0067         return median_of_three(array,
0068                                median_of_three(array, 0 , offset, offset * 2),
0069                                median_of_three(array, offset * 3, offset * 4, offset * 5),
0070                                median_of_three(array, offset * 6, offset * 7, range.size - 1));
0071
0072     }
0073
0074     std::size_t split_range( quick_sort_range& range ) {
0075         RandomAccessIterator array = range.begin;
0076         RandomAccessIterator first_element = range.begin;
0077         std::size_t m = pseudo_median_of_nine(array, range);
0078         if( m != 0 ) std::iter_swap(array, array + m);
0079
0080         std::size_t i = 0;
0081         std::size_t j = range.size;
0082         // Partition interval [i + 1,j - 1] with key *first_element.
0083         for(;;) {
0084             __TBB_ASSERT( i < j, nullptr );
0085             // Loop must terminate since array[l] == *first_element.
0086             do {
0087                 --j;
0088                 __TBB_ASSERT( i <= j, "bad ordering relation?" );
0089             } while( comp(*first_element, array[j]) );
0090             do {
0091                 __TBB_ASSERT( i <= j, nullptr );
0092                 if( i == j ) goto partition;
0093                 ++i;
0094             } while( comp(array[i], *first_element) );
0095             if( i == j ) goto partition;
0096             std::iter_swap(array + i, array + j);
0097         }
0098 partition:
0099         // Put the partition key were it belongs
0100         std::iter_swap(array + j, first_element);
0101         // array[l..j) is less or equal to key.
0102         // array(j..r) is greater or equal to key.
0103         // array[j] is equal to key
0104         i = j + 1;
0105         std::size_t new_range_size = range.size - i;
0106         range.size = j;
0107         return new_range_size;
0108     }
0109
0110 public:
0111     quick_sort_range() = default;
0112     quick_sort_range( const quick_sort_range& ) = default;
0113     void operator=( const quick_sort_range& ) = delete;
0114
0115     static constexpr std::size_t grainsize = 500;
0116     const Compare& comp;
0117     std::size_t size;
0118     RandomAccessIterator begin;
0119
0120     quick_sort_range( RandomAccessIterator begin_, std::size_t size_, const Compare& comp_ ) :
0121         comp(comp_), size(size_), begin(begin_) {}
0122
0123     bool empty() const { return size == 0; }
0124     bool is_divisible() const { return size >= grainsize; }
0125
0126     quick_sort_range( quick_sort_range& range, split )
0127         : comp(range.comp)
0128         , size(split_range(range))
0129           // +1 accounts for the pivot element, which is at its correct place
0130           // already and, therefore, is not included into subranges.
0131         , begin(range.begin + range.size + 1) {}
0132 };
0133
0134 //! Body class used to test if elements in a range are presorted
0135 /** @ingroup algorithms */
0136 template<typename RandomAccessIterator, typename Compare>
0137 class quick_sort_pretest_body {
0138     const Compare& comp;
0139     task_group_context& context;
0140
0141 public:
0142     quick_sort_pretest_body() = default;
0143     quick_sort_pretest_body( const quick_sort_pretest_body& ) = default;
0144     void operator=( const quick_sort_pretest_body& ) = delete;
0145
0146     quick_sort_pretest_body( const Compare& _comp, task_group_context& _context ) : comp(_comp), context(_context) {}
0147
0148     void operator()( const blocked_range<RandomAccessIterator>& range ) const {
0149         RandomAccessIterator my_end = range.end();
0150
0151         int i = 0;
0152         //TODO: consider using std::is_sorted() for each 64 iterations (requires performance measurements)
0153         for( RandomAccessIterator k = range.begin(); k != my_end; ++k, ++i ) {
0154             if( i % 64 == 0 && context.is_group_execution_cancelled() ) break;
0155
0156             // The k - 1 is never out-of-range because the first chunk starts at begin+serial_cutoff+1
0157             if( comp(*(k), *(k - 1)) ) {
0158                 context.cancel_group_execution();
0159                 break;
0160             }
0161         }
0162     }
0163 };
0164
0165 //! Body class used to sort elements in a range that is smaller than the grainsize.
0166 /** @ingroup algorithms */
0167 template<typename RandomAccessIterator, typename Compare>
0168 struct quick_sort_body {
0169     void operator()( const quick_sort_range<RandomAccessIterator,Compare>& range ) const {
0170         std::sort(range.begin, range.begin + range.size, range.comp);
0171     }
0172 };
0173
0174 //! Method to perform parallel_for based quick sort.
0175 /** @ingroup algorithms */
0176 template<typename RandomAccessIterator, typename Compare>
0177 void do_parallel_quick_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) {
0178     parallel_for(quick_sort_range<RandomAccessIterator,Compare>(begin, end - begin, comp),
0179                  quick_sort_body<RandomAccessIterator,Compare>(),
0180                  auto_partitioner());
0181 }
0182
0183 //! Wrapper method to initiate the sort by calling parallel_for.
0184 /** @ingroup algorithms */
0185 template<typename RandomAccessIterator, typename Compare>
0186 void parallel_quick_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) {
0187     task_group_context my_context(PARALLEL_SORT);
0188     constexpr int serial_cutoff = 9;
0189
0190     __TBB_ASSERT( begin + serial_cutoff < end, "min_parallel_size is smaller than serial cutoff?" );
0191     RandomAccessIterator k = begin;
0192     for( ; k != begin + serial_cutoff; ++k ) {
0193         if( comp(*(k + 1), *k) ) {
0194             do_parallel_quick_sort(begin, end, comp);
0195             return;
0196         }
0197     }
0198
0199     // Check is input range already sorted
0200     parallel_for(blocked_range<RandomAccessIterator>(k + 1, end),
0201                  quick_sort_pretest_body<RandomAccessIterator, Compare>(comp, my_context),
0202                  auto_partitioner(),
0203                  my_context);
0204
0205     if( my_context.is_group_execution_cancelled() )
0206         do_parallel_quick_sort(begin, end, comp);
0207 }
0208
0209 /** \page parallel_sort_iter_req Requirements on iterators for parallel_sort
0210     Requirements on the iterator type \c It and its value type \c T for \c parallel_sort:
0211
0212     - \code void iter_swap( It a, It b ) \endcode Swaps the values of the elements the given
0213     iterators \c a and \c b are pointing to. \c It should be a random access iterator.
0214
0215     - \code bool Compare::operator()( const T& x, const T& y ) \endcode True if x comes before y;
0216 **/
0217
0218 /** \name parallel_sort
0219     See also requirements on \ref parallel_sort_iter_req "iterators for parallel_sort". **/
0220 //@{
0221
0222 #if __TBB_CPP20_CONCEPTS_PRESENT
0223 template<typename It>
0224 using iter_value_type = typename std::iterator_traits<It>::value_type;
0225
0226 template<typename Range>
0227 using range_value_type = typename std::iterator_traits<range_iterator_type<Range>>::value_type;
0228 #endif
0229
0230 //! Sorts the data in [begin,end) using the given comparator
0231 /** The compare function object is used for all comparisons between elements during sorting.
0232     The compare object must define a bool operator() function.
0233     @ingroup algorithms **/
0234 template<typename RandomAccessIterator, typename Compare>
0235     __TBB_requires(std::random_access_iterator<RandomAccessIterator> &&
0236                    compare<Compare, RandomAccessIterator> &&
0237                    std::movable<iter_value_type<RandomAccessIterator>>)
0238 void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) {
0239     constexpr int min_parallel_size = 500;
0240     if( end > begin ) {
0241         if( end - begin < min_parallel_size ) {
0242             std::sort(begin, end, comp);
0243         } else {
0244             parallel_quick_sort(begin, end, comp);
0245         }
0246     }
0247 }
0248
0249 //! Sorts the data in [begin,end) with a default comparator \c std::less
0250 /** @ingroup algorithms **/
0251 template<typename RandomAccessIterator>
0252     __TBB_requires(std::random_access_iterator<RandomAccessIterator> &&
0253                    less_than_comparable<iter_value_type<RandomAccessIterator>> &&
0254                    std::movable<iter_value_type<RandomAccessIterator>>)
0255 void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end ) {
0256     parallel_sort(begin, end, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
0257 }
0258
0259 //! Sorts the data in rng using the given comparator
0260 /** @ingroup algorithms **/
0261 template<typename Range, typename Compare>
0262     __TBB_requires(container_based_sequence<Range, std::random_access_iterator_tag> &&
0263                    compare<Compare, range_iterator_type<Range>> &&
0264                    std::movable<range_value_type<Range>>)
0265 void parallel_sort( Range&& rng, const Compare& comp ) {
0266     parallel_sort(std::begin(rng), std::end(rng), comp);
0267 }
0268
0269 //! Sorts the data in rng with a default comparator \c std::less
0270 /** @ingroup algorithms **/
0271 template<typename Range>
0272     __TBB_requires(container_based_sequence<Range, std::random_access_iterator_tag> &&
0273                    less_than_comparable<range_value_type<Range>> &&
0274                    std::movable<range_value_type<Range>>)
0275 void parallel_sort( Range&& rng ) {
0276     parallel_sort(std::begin(rng), std::end(rng));
0277 }
0278 //@}
0279
0280 } // namespace d1
0281 } // namespace detail
0282
0283 inline namespace v1 {
0284     using detail::d1::parallel_sort;
0285 } // namespace v1
0286 } // namespace tbb
0287
0288 #endif /*__TBB_parallel_sort_H*/