c - OpenMP 通用 qsort 加速效果不佳

Question

因此，我的实现似乎在大约 10 亿个元素时与基本串行 qsort 保持平衡。大多数在线并行 qsort 算法用于对整数数组和其他内容进行排序，但我希望能够使用自定义比较器(如内置 qsort)对任何内容进行排序，因为我想对我拥有的一些结构进行排序。我正在使用 12 个线程，并且可以通过查看顶部来验证它们是否正确生成。也许我生成了太多线程，应该根据递归深度停止生成新线程？我知道我的 qsort 实现相当基本，显然内置 qsort 已经投入了大量的工作和优化，但我不明白为什么我没有通过并行化获得良好的加速。任何输入将不胜感激，因为如果我可以保持它的通用性，我可以在很多领域使用此代码。谢谢!

void test ( void* data, uint64_t startIdx, uint64_t endIdx, size_t dataSize, int (*cmp)(const void *, const void *) )
{
    #pragma omp parallel
    {
        #pragma omp single nowait
        {
            p_qsort( data, 0, MAX_INTS - 1, sizeof (testint), cmp );
        }
    }
}

void p_qsort ( void* data, uint64_t startIdx, uint64_t endIdx, size_t dataSize, int (*cmp)(const void *, const void *) )
{
    uint64_t idx = p_qsort_partition( data, startIdx, endIdx, dataSize, cmp );

    //Left array
    if ( startIdx < idx - 1 )
    {
        #pragma omp task
        p_qsort( data, startIdx, idx - 1, dataSize, cmp );
    }
    //Right array
    if ( endIdx > idx )
    {
        #pragma omp task
        p_qsort( data, idx, endIdx, dataSize, cmp );
    }
}

void swapVoidElements ( void* el1, void* el2, size_t size )
{
    if ( el1 == el2 )
        return;

    void* temp = malloc( size );

    //temp = el1
    memcpy( temp, el1, size );
    //el1 = el2
    memcpy( el1, el2, size );
    //el2 = temp
    memcpy( el2, temp, size );

    free( temp );
}

uint64_t p_qsort_partition ( void* data, uint64_t left, uint64_t right, size_t dataSize, int (*cmp)(const void *, const void *) )
{
    void* pivotP = getVoidPtr( data, left, dataSize );
    void* pivotCmp = malloc( dataSize );
    memcpy( pivotCmp, pivotP, dataSize );

    while ( left <= right )
    {
        while ( cmp( getVoidPtr( data, left, dataSize ), pivotCmp ) < 0 )
            left++;
        //while ( array[right] > pivot )
        while ( cmp( getVoidPtr( data, right, dataSize ), pivotCmp ) > 0 )
            right--;
        //Swap
        if ( left <= right )
        {
            void* leftP = getVoidPtr( data, left, dataSize );
            void* rightP = getVoidPtr( data, right, dataSize );

            swapVoidElements( leftP, rightP, dataSize );

            left++;
            right--;
        }
    }
    free( pivotCmp );

    return left;
}

void* getVoidPtr ( void* data, uint64_t idx, size_t dataSize )
{
    uint64_t idxNum = idx * dataSize;
    char* test = ((char*) data) + idxNum;

    return (void *) test;
}

Answer 1

您创建的每个 OMP 任务都会产生一些开销，并且您的特定任务会变得越来越小。随着每个任务的工作量变小，开销也会相应地变得更加昂贵。串行快速排序的一些常见优化技术不仅可能有助于基本算法，而且还有助于解决开销问题。

通过切换小子数组的策略，您可以大大减少所涉及的任务总数，从而减少相关的开销。这与针对小子数组切换到插入排序的常见快速排序优化非常吻合。 “小”的定义是一个可调参数，其最佳值在某种程度上取决于您要排序的内容，但可能 5 - 30 范围内的值对您来说是一个很好的截止值。当您进行此类切换时，请在一项任务中执行整个子数组插入排序。

您还可能受益于仅对每对子数组中较小的子数组进行递归，而不是循环处理较大的子数组。这将最大递归深度限制为 O(log n)，否则最坏情况下为 O(n)。由于每个递归都涉及其自己的任务，因此这也会将所需的任务总数减少至少两倍。

选择好的主元是快速排序性能的核心问题之一，但主元选择算法的相对效果高度依赖于数据。我建议至少比总是选择最左边的元素更复杂一点——在平均情况下，三中位数或随机主元选择可能会产生更好的性能。由于主元的选择会影响子数组大小，而子数组大小与创建的任务数量及其大小有关，因此这可能是并行版本的额外优势。