[C++][OpenMP] A shared memory Quick Sort using openmp tasks (example, source code)

This quicksort class is a copy of the one from ScalFMM.


#if _OPENMP < 200805
#error You openmp version does not support tasks
#endif

#include <omp.h>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <utility> // For move
#include <functional> // To have std::function



/** This class is parallel quick sort
  *
  *
  * In the previous version Intel Compiler was not using the QS with task
  * defined(__ICC) || defined(__INTEL_COMPILER) defined the FQS_TASKS_ARE_DISABLED
  *
  * If needed one can define FQS_FORCE_NO_TASKS to ensure that the no task version is used.
  */

template <class SortType, class IndexType = size_t>
class FQuickSort {
protected:
    /** swap to value */
    template <class NumType>
    static inline void Swap(NumType& value, NumType& other){
        const NumType temp = std::move(value);
        value = std::move(other);
        other = std::move(temp);
    }

    typedef bool (*infOrEqualPtr)(const SortType&, const SortType&);

    ////////////////////////////////////////////////////////////
    // Quick sort
    ////////////////////////////////////////////////////////////

    /* Use in the sequential qs */
    static IndexType QsPartition(SortType array[], IndexType left, IndexType right, const infOrEqualPtr infOrEqual){
        Swap(array[right],array[((right - left ) / 2) + left]);

        IndexType idx = left;
        while( idx < right && infOrEqual(array[idx],array[right])){
            idx += 1;
        }
        left = idx;

        for( ; idx < right ; ++idx){
            if( infOrEqual(array[idx],array[right]) ){
                Swap(array[idx],array[left]);
                left += 1;
            }
        }

        Swap(array[left],array[right]);

        return left;
    }


    /* The sequential qs */
    static void QsSequentialStep(SortType array[], const IndexType left, const IndexType right, const infOrEqualPtr infOrEqual){
        if(left < right){
            const IndexType part = QsPartition(array, left, right, infOrEqual);
            QsSequentialStep(array,part + 1,right, infOrEqual);
            QsSequentialStep(array,left,part - 1, infOrEqual);
        }
    }

    /** A task dispatcher */
    static void QsOmpTask(SortType array[], const IndexType left, const IndexType right, const int deep, const infOrEqualPtr infOrEqual){
        if(left < right){
            const IndexType part = QsPartition(array, left, right, infOrEqual);
            if( deep ){
                #pragma omp task default(none) firstprivate(array, part, right, deep, infOrEqual)
                QsOmpTask(array,part + 1,right, deep - 1, infOrEqual);
                // #pragma omp task default(none) firstprivate(array, part, right, deep, infOrEqual) // not needed
                QsOmpTask(array,left,part - 1, deep - 1, infOrEqual);
            }
            else {
                QsSequentialStep(array,part + 1,right, infOrEqual);
                QsSequentialStep(array,left,part - 1, infOrEqual);
            }
        }
    }

public:
    /* a sequential qs */
    static void QsSequential(SortType array[], const IndexType size, const infOrEqualPtr infOrEqual){
        QsSequentialStep(array, 0, size-1, infOrEqual);
    }

    static void QsSequential(SortType array[], const IndexType size){
        QsSequential(array, size, [&](const SortType& v1, const SortType& v2){
            return v1 <= v2;
        });
    }

    /** The openmp quick sort */
    static void QsOmp(SortType array[], const IndexType size, const infOrEqualPtr infOrEqual){
        const int nbTasksRequiere = (omp_get_max_threads() * 5);
        int deep = 0;
        while( (1 << deep) < nbTasksRequiere ) deep += 1;

        #pragma omp parallel
        {
            #pragma omp single nowait
            {
                QsOmpTask(array, 0, size - 1 , deep, infOrEqual);
            }
        }
    }

    static void QsOmp(SortType array[], const IndexType size){
        QsOmp(array, size, [&](const SortType& v1, const SortType& v2){
            return v1 <= v2;
        });
    }
};

#endif // FQUICKSORT_HPP

Here is a small test to sort (increasing order) and using a anonymous function:

// Compile with g++ -fopenmp -std=c++11 -O3 main.cpp -o test.exe -lgomp
int main(){
    const size_t Size = 1000;
    int* array = new int[Size];

    // Genere random values
    for(int idx = 0 ; idx < Size ; ++idx){
        array[idx] = rand();
    }

    // Sort
    FQuickSort<int>::QsOmp(array, Size);

    // Reverse sort with lambda function
    FQuickSort<int>::QsOmp(array, Size,[](const int& v1, const int& v2){
        return v2 <= v1;
    });

    return 0;
}