parallel_sort.h
Go to the documentation of this file.
/*
Copyright (c) 2005-2020 Intel Corporation
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
#ifndef __TBB_parallel_sort_H
#define __TBB_parallel_sort_H
#define __TBB_parallel_sort_H_include_area
#include "internal/_warning_suppress_enable_notice.h"
#include "parallel_for.h"
#include "blocked_range.h"
#include "internal/_range_iterator.h"
#include <algorithm>
#include <iterator>
#include <functional>
#if __TBB_TASK_GROUP_CONTEXT
#include "tbb_profiling.h"
#endif
namespace tbb {
namespace interface9 {
namespace internal {
using tbb::internal::no_assign;
template<typename RandomAccessIterator, typename Compare>
class quick_sort_range: private no_assign {
inline size_t median_of_three(const RandomAccessIterator &array, size_t l, size_t m, size_t r) const {
return comp(array[l], array[m]) ? ( comp(array[m], array[r]) ? m : ( comp( array[l], array[r]) ? r : l ) )
: ( comp(array[r], array[m]) ? m : ( comp( array[r], array[l] ) ? r : l ) );
}
inline size_t pseudo_median_of_nine( const RandomAccessIterator &array, const quick_sort_range &range ) const {
size_t offset = range.size/8u;
return median_of_three(array,
median_of_three(array, 0, offset, offset*2),
median_of_three(array, offset*3, offset*4, offset*5),
median_of_three(array, offset*6, offset*7, range.size - 1) );
}
size_t split_range( quick_sort_range& range ) {
using std::iter_swap;
RandomAccessIterator array = range.begin;
RandomAccessIterator key0 = range.begin;
size_t m = pseudo_median_of_nine(array, range);
if (m) iter_swap ( array, array+m );
size_t i=0;
size_t j=range.size;
// Partition interval [i+1,j-1] with key *key0.
for(;;) {
__TBB_ASSERT( i<j, NULL );
// Loop must terminate since array[l]==*key0.
do {
--j;
__TBB_ASSERT( i<=j, "bad ordering relation?" );
} while( comp( *key0, array[j] ));
do {
__TBB_ASSERT( i<=j, NULL );
if( i==j ) goto partition;
++i;
} while( comp( array[i],*key0 ));
if( i==j ) goto partition;
iter_swap( array+i, array+j );
}
partition:
// Put the partition key were it belongs
iter_swap( array+j, key0 );
// array[l..j) is less or equal to key.
// array(j..r) is greater or equal to key.
// array[j] is equal to key
i=j+1;
size_t new_range_size = range.size-i;
range.size = j;
return new_range_size;
}
public:
static const size_t grainsize = 500;
const Compare &comp;
size_t size;
RandomAccessIterator begin;
quick_sort_range( RandomAccessIterator begin_, size_t size_, const Compare &comp_ ) :
comp(comp_), size(size_), begin(begin_) {}
bool empty() const {return size==0;}
bool is_divisible() const {return size>=grainsize;}
quick_sort_range( quick_sort_range& range, split )
: comp(range.comp)
, size(split_range(range))
// +1 accounts for the pivot element, which is at its correct place
// already and, therefore, is not included into subranges.
, begin(range.begin+range.size+1) {}
};
#if __TBB_TASK_GROUP_CONTEXT
template<typename RandomAccessIterator, typename Compare>
class quick_sort_pretest_body : no_assign {
const Compare &comp;
public:
quick_sort_pretest_body(const Compare &_comp) : comp(_comp) {}
void operator()( const blocked_range<RandomAccessIterator>& range ) const {
task &my_task = task::self();
RandomAccessIterator my_end = range.end();
int i = 0;
for (RandomAccessIterator k = range.begin(); k != my_end; ++k, ++i) {
if ( i%64 == 0 && my_task.is_cancelled() ) break;
// The k-1 is never out-of-range because the first chunk starts at begin+serial_cutoff+1
if ( comp( *(k), *(k-1) ) ) {
my_task.cancel_group_execution();
break;
}
}
}
};
#endif /* __TBB_TASK_GROUP_CONTEXT */
template<typename RandomAccessIterator, typename Compare>
struct quick_sort_body {
void operator()( const quick_sort_range<RandomAccessIterator,Compare>& range ) const {
//SerialQuickSort( range.begin, range.size, range.comp );
std::sort( range.begin, range.begin + range.size, range.comp );
}
};
template<typename RandomAccessIterator, typename Compare>
void parallel_quick_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) {
#if __TBB_TASK_GROUP_CONTEXT
task_group_context my_context(PARALLEL_SORT);
const int serial_cutoff = 9;
__TBB_ASSERT( begin + serial_cutoff < end, "min_parallel_size is smaller than serial cutoff?" );
RandomAccessIterator k = begin;
for ( ; k != begin + serial_cutoff; ++k ) {
if ( comp( *(k+1), *k ) ) {
goto do_parallel_quick_sort;
}
}
parallel_for( blocked_range<RandomAccessIterator>(k+1, end),
quick_sort_pretest_body<RandomAccessIterator,Compare>(comp),
auto_partitioner(),
my_context);
if (my_context.is_group_execution_cancelled())
do_parallel_quick_sort:
#endif /* __TBB_TASK_GROUP_CONTEXT */
parallel_for( quick_sort_range<RandomAccessIterator,Compare>(begin, end-begin, comp ),
quick_sort_body<RandomAccessIterator,Compare>(),
auto_partitioner() );
}
} // namespace internal
} // namespace interfaceX
template<typename RandomAccessIterator, typename Compare>
void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp) {
const int min_parallel_size = 500;
if( end > begin ) {
if (end - begin < min_parallel_size) {
std::sort(begin, end, comp);
} else {
interface9::internal::parallel_quick_sort(begin, end, comp);
}
}
}
template<typename RandomAccessIterator>
inline void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end ) {
parallel_sort( begin, end, std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >() );
}
template<typename Range, typename Compare>
void parallel_sort(Range& rng, const Compare& comp) {
parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng), comp);
}
template<typename Range>
void parallel_sort(Range& rng) {
parallel_sort(tbb::internal::first(rng), tbb::internal::last(rng));
}
template<typename T>
inline void parallel_sort( T * begin, T * end ) {
parallel_sort( begin, end, std::less< T >() );
}
} // namespace tbb
#include "internal/_warning_suppress_disable_notice.h"
#undef __TBB_parallel_sort_H_include_area
#endif
blocked_range.h
_range_iterator.h
_warning_suppress_disable_notice.h
_warning_suppress_enable_notice.h
tbb_profiling.h
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
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
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::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::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::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
The graph class.
Definition: serial/tbb/parallel_for.h:46
tbb::internal::last
auto last(Container &c) -> decltype(begin(c))
Definition: _range_iterator.h:40
tbb::internal::first
auto first(Container &c) -> decltype(begin(c))
Definition: _range_iterator.h:34
internal
Definition: _flow_graph_async_msg_impl.h:24
tbb::blocked_range
A range over which to iterate.
Definition: blocked_range.h:45
tbb::blocked_range::begin
const_iterator begin() const
Beginning of range.
Definition: blocked_range.h:69
tbb::blocked_range::end
const_iterator end() const
One past last value in range.
Definition: blocked_range.h:72
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::interface9::internal::quick_sort_range::size
size_t size
Definition: parallel_sort.h:103
tbb::interface9::internal::quick_sort_range::comp
const Compare & comp
Definition: parallel_sort.h:102
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_range::is_divisible
bool is_divisible() const
Definition: parallel_sort.h:110
tbb::interface9::internal::quick_sort_range::quick_sort_range
quick_sort_range(quick_sort_range &range, split)
Definition: parallel_sort.h:112
tbb::interface9::internal::quick_sort_range::split_range
size_t split_range(quick_sort_range &range)
Definition: parallel_sort.h:62
tbb::interface9::internal::quick_sort_range::empty
bool empty() const
Definition: parallel_sort.h:109
tbb::interface9::internal::quick_sort_range::begin
RandomAccessIterator begin
Definition: parallel_sort.h:104
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::interface9::internal::quick_sort_range::quick_sort_range
quick_sort_range(RandomAccessIterator begin_, size_t size_, const Compare &comp_)
Definition: parallel_sort.h:106
tbb::interface9::internal::quick_sort_range::grainsize
static const size_t grainsize
Definition: parallel_sort.h:101
tbb::interface9::internal::quick_sort_pretest_body
Body class used to test if elements in a range are presorted.
Definition: parallel_sort.h:124
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_pretest_body::comp
const Compare & comp
Definition: parallel_sort.h:125
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_body
Body class used to sort elements in a range that is smaller than the grainsize.
Definition: parallel_sort.h:152
tbb::interface9::internal::quick_sort_body::operator()
void operator()(const quick_sort_range< RandomAccessIterator, Compare > &range) const
Definition: parallel_sort.h:153
tbb::auto_partitioner
An auto partitioner.
Definition: partitioner.h:613
tbb::task_group_context
Used to form groups of tasks.
Definition: task.h:358
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::task
Base class for user-defined tasks.
Definition: task.h:615
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
tbb::task::is_cancelled
bool is_cancelled() const
Returns true if the context has received cancellation request.
Definition: task.h:974
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
tbb::internal::no_assign
Base class for types that should not be assigned.
Definition: tbb_stddef.h:322
tbb::split
Dummy type that distinguishes splitting constructor from copy constructor.
Definition: tbb_stddef.h:416
parallel_for.h

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.