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

SORTCLASS	The class itself. This has to be a derived class of BaseSort.
FLAGS	See BASESORTFLAGS.
PARALLELIZATION_THRESHOLD	The 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

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);

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);

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]	start	The start iterator of an array.
[in]	end	The 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]	queue	Optional 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]	start	The start iterator of an array.
[in]	count	The number of elements to be sorted.
[in]	queue	Optional 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]	arr	The array to be sorted.
[in]	queue	Optional 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