ParallelSort< SORTCLASS, FLAGS, PARALLELIZATION_THRESHOLD > Class Template Reference

#include <parallelsort.h>

Inheritance diagram for ParallelSort< SORTCLASS, FLAGS, PARALLELIZATION_THRESHOLD >:

Detailed Description

template<typename SORTCLASS, BASESORTFLAGS FLAGS = BASESORTFLAGS::NONE, Int PARALLELIZATION_THRESHOLD = 10000>
class maxon::ParallelSort< SORTCLASS, FLAGS, PARALLELIZATION_THRESHOLD >

Template for sorting arrays and searching in sorted arrays

To use this template derive a class from it and define the member 'LessThan' that implements an element comparison. If you do searching the member 'IsEqual' needs to be implemented that does an element comparison with the search key as the first argument. If the search key is different from the element type a second LessThan routine is needed (comparing SEARCHKEY to an element).

Template Parameters
SORTCLASSThe class itself. This has to be a derived class of BaseSort.
FLAGSSee BASESORTFLAGS.
PARALLELIZATION_THRESHOLDThe minimum number of elements to start parallel sorting. if less elements are sorted a regular BaseSort will be used.
Note
Note that the classes that will be sorted have special requirements regarding copy and move constructors .

Example for traditional C-style arrays:

class Sort1 : public ParallelSort<Sort1>
{
public:
static inline Bool LessThan(Int a, Int b)
{
return a < b;
}
};
...
Int array1[100];
...
Sort1 sort1;
sort1.Sort(&array1[0], &array1[100]); // note that the 'end' iterator is the last element + 1 and not the last element!
sort1.Sort(array1, 100); // even easier
maxon::Bool Bool
Definition: ge_sys_math.h:55
maxon::Int Int
Definition: ge_sys_math.h:64
Bool LessThan(UInt a1, UInt a2, UInt b1, UInt b2)
Definition: integer.h:151
Note
LessThan can be a member of the sort class itself (not static), but needs to be const in that case.

Example for arrays:

class Sort2 : public ParallelSort<Sort2>
{
public:
static inline Bool LessThan(Int a, Int b)
{
return a < b;
}
};
...
BlockArray<Int> array2;
...
Sort2 sort2;
sort2.Sort(array2.Begin(), array2.End()); // do not write Sort(&array2[0], &array2[array2.GetCount()]) as this will create a debug assert (the second array access is illegal)
sort2.Sort(array2); // any arrays derived from BaseArray can be passed directly

Example for arbitrary structures with multiple sort criteria:

class MyStruct
{
public:
String _str;
Int _index;
Float _weight;
};
class Sort3 : public ParallelSort<Sort3>
{
public:
static inline Bool LessThan(const MyStruct& a, const MyStruct& b)
{
if (a._weight < b._weight) return true;
if (a._weight > b._weight) return false;
return a._index < b._index; // if weights are identical sort by index
}
};
...
BlockArray<MyStruct> array3;
...
Sort3 sort3;
sort3.Sort(array3);
Definition: c4d_string.h:39
maxon::Float Float
Definition: ge_sys_math.h:66

Searching Example:

class MyStruct
{
public:
String _str;
Int _index;
Float _weight;
};
class MySearch : public ParallelSort<MySearch>
{
public:
// for sorting: compare array element to array element
static inline Bool LessThan(const MyStruct& a, const MyStruct& b)
{
if (a._weight < b._weight) return true;
if (a._weight > b._weight) return false;
return a._index < b._index; // if weights are identical sort by index
}
// for searching: compare search key to array element
static inline Bool LessThan(Float weight, const MyStruct& b)
{
return weight < b._weight;
}
// for searching: compare search key to array element
static inline Bool IsEqual(Float weight, const MyStruct& b)
{
return weight == b._weight;
}
};
...
BlockArray<MyStruct> array4;
...
MySearch search;
search.Sort(array4);
...
// array is now sorted, we can search it
MyStruct* result = search.Find(5.0, array4);
PyObject PyObject * result
Definition: abstract.h:43
MAXON_ATTRIBUTE_FORCE_INLINE Bool IsEqual(PREDICATE &&predicate, const T1 &a, const T2 &b)
Definition: collection.h:102

Public Types

using Super = BaseSort< SORTCLASS, FLAGS >
 

Public Member Functions

template<typename ITERATOR >
void Sort (ITERATOR start, ITERATOR end, JobQueueInterface *queue=JOBQUEUE_CURRENT) const
 
template<typename ITERATOR >
void Sort (ITERATOR start, Int count, JobQueueInterface *queue=JOBQUEUE_CURRENT) const
 
template<typename ARRAY >
void Sort (ARRAY &arr, JobQueueInterface *queue=JOBQUEUE_CURRENT) const
 
- Public Member Functions inherited from BaseSort< SORTCLASS, BASESORTFLAGS::NONE >
void Sort (ITERATOR start, ITERATOR end) const
 
void Sort (ITERATOR start, Int count) const
 
void Sort (ARRAY &arr) const
 
Int FindIndex (const SEARCHTYPE &key, ITERATOR arr, Int count) const
 
ITERATOR Find (const SEARCHTYPE &key, ITERATOR arr, Int count) const
 
ARRAY::ValueType * Find (const SEARCHTYPE &key, const ARRAY &arr) const
 
ITERATOR FindInsertionIndex (const SEARCHTYPE &key, ITERATOR arr, Int count, Int &insertionIndex) const
 
ARRAY::ValueType * FindInsertionIndex (const SEARCHTYPE &key, const ARRAY &arr, Int &insertionIndex) const
 

Private Member Functions

template<typename ITERATOR , typename CONTENT >
void ISort (ITERATOR start, Int count, const CONTENT &valType, JobQueueInterface *queue) const
 
template<typename CONTENT >
void ISort (CONTENT *start, Int count, const CONTENT &valType, JobQueueInterface *queue) const
 
template<typename ITERATOR , typename CONTENT , typename MOVEHELPERFORWARD , typename MOVEHELPERBACKWARD >
void ParallelSortAlgorithm (ITERATOR start, Int count, const CONTENT &valType, JobQueueInterface *queue, const MOVEHELPERFORWARD &moveHelperForward, const MOVEHELPERBACKWARD &moveHelperBackward) const
 
template<typename ITERATOR >
void ReduceRedundantBlocks (Int chunksize, Int &cnt, ITERATOR &arr) const
 
Int PowerOfTwo (Int count) const
 

Member Typedef Documentation

◆ Super

using Super = BaseSort<SORTCLASS, FLAGS>

Member Function Documentation

◆ Sort() [1/3]

void Sort ( ITERATOR  start,
ITERATOR  end,
JobQueueInterface queue = JOBQUEUE_CURRENT 
) const

Sort elements of an array, so that the smallest element comes first. Note that the sorting is not guaranteed to be stable (elements with the same sort value may change their order). The time for sorting is O(n * log(n)). Depending on the available number of threads and initial element distribution you can get speedups of 1 to 8 times compared to BaseSort. If the number of elements is too small less threads will be used or ultimately non-parallel sorting will be used (<1024 elements). Parallel sorting temporarily needs the same amount of memory as the sorted elements take up. If memory isn't available the algorithm will still succeed, but be slightly slower than the non-Threaded version.

Parameters
[in]startThe start iterator of an array.
[in]endThe end iterator of an array. Note that this is not the last element! It needs to be the boundary (which is last element + 1). See in the BaseSort class description for examples.
[in]queueOptional queue on which the parallel sort will run.

◆ Sort() [2/3]

void Sort ( ITERATOR  start,
Int  count,
JobQueueInterface queue = JOBQUEUE_CURRENT 
) const

Sort elements of an array, so that the smallest element comes first. Note that the sorting is not guaranteed to be stable (elements with the same sort value may change their order). The time for sorting is O(n * log(n)) Depending on the available number of threads and initial element distribution you can get speedups of 1 to 8 times compared to BaseSort. If the number of elements is too small less threads will be used or ultimately non-parallel sorting will be used (<1024 elements). Parallel sorting temporarily needs the same amount of memory as the sorted elements take up. If memory isn't available the algorithm will still succeed, but be slightly slower than the non-Threaded version.

Parameters
[in]startThe start iterator of an array.
[in]countThe number of elements to be sorted.
[in]queueOptional queue on which the parallel sort will run.

◆ Sort() [3/3]

void Sort ( ARRAY &  arr,
JobQueueInterface queue = JOBQUEUE_CURRENT 
) const

Sort elements of an array, so that the smallest element comes first. Note that the sorting is not guaranteed to be stable (elements with the same sort value may change their order). The time for sorting is O(n * log(n)) Depending on the available number of threads and initial element distribution you can get speedups of 1 to 8 times compared to BaseSort. If the number of elements is too small less threads will be used or ultimately non-parallel sorting will be used (<1024 elements). Parallel sorting temporarily needs the same amount of memory as the sorted elements take up. If memory isn't available the algorithm will still succeed, but be slightly slower than the non-Threaded version.

Parameters
[in]arrThe array to be sorted.
[in]queueOptional queue on which the parallel sort will run.

◆ ISort() [1/2]

void ISort ( ITERATOR  start,
Int  count,
const CONTENT &  valType,
JobQueueInterface queue 
) const
private

◆ ISort() [2/2]

void ISort ( CONTENT *  start,
Int  count,
const CONTENT &  valType,
JobQueueInterface queue 
) const
private

◆ ParallelSortAlgorithm()

void ParallelSortAlgorithm ( ITERATOR  start,
Int  count,
const CONTENT &  valType,
JobQueueInterface queue,
const MOVEHELPERFORWARD &  moveHelperForward,
const MOVEHELPERBACKWARD &  moveHelperBackward 
) const
private

◆ ReduceRedundantBlocks()

void ReduceRedundantBlocks ( Int  chunksize,
Int cnt,
ITERATOR &  arr 
) const
private

◆ PowerOfTwo()

Int PowerOfTwo ( Int  count) const
private