c++ - 与 Mergesort 相比，为什么 GNU 并行快速排序这么慢？

Question

我一直在 C++ 标准库中测试 OpenMP GNU 并行排序算法的实用性，发现并行 Quicksort 算法明显比 Mergesort 算法慢。在我的 PC 上，Mergesort 需要 52 秒才能对 80 亿个整数的 vector 进行排序，而 Quicksort 只需不到 8 分钟。对其 CPU 使用情况的不科学检查表明，快速排序在大约 20 秒内充分利用了并行性，然后其运行的其余部分仅使用了 2 个线程(或 %200 CPU)。

我检查了算法的源代码，虽然我不能完全理解它。如果这不是原因，有人可以向我解释为什么该算法与合并排序相比如此慢吗？我曾想联系算法的原作者，但认为先在这里尝试比较礼貌。

这里是一些代码，希望能够说明问题，如果您没有我的运行所需的疯狂数量的资源，您可以在命令行上指定要排序的元素数。我正在使用 GCC 4.9:

#include <vector>
#include <parallel/algorithm>
#include <boost/date_time.hpp>
#include <stdlib.h>
#include <iostream>
#include <omp.h>
#include <sstream>

const size_t DEFAULT_NUMBER = 8000000000;
int main(int argc, char **argv)
{
    size_t number_of_elements = DEFAULT_NUMBER;
    if(argc > 1 && argv[1] != 0)
    {   
        number_of_elements = atoi(argv[1]);
    }   
    std::vector<int> elements(number_of_elements);
    srandom(10);
    for(size_t i = 0; i < elements.size(); i++)
    {   
        elements[i] = random();
    }   

    boost::posix_time::ptime time = boost::posix_time::second_clock::local_time();
    __gnu_parallel::sort(elements.begin(), elements.end(), __gnu_parallel::multiway_mergesort_tag());
    std::cout << "Mergesort took: " << boost::posix_time::to_simple_string(boost::posix_time::second_clock::local_time() - time) <<  std::endl;

    //Repopulate vector with random elements
    srandom(10);
    for(size_t i = 0; i < elements.size(); i++)
    {   
        elements[i] = random();
    }   
    time = boost::posix_time::second_clock::local_time();
    __gnu_parallel::sort(elements.begin(), elements.end(), __gnu_parallel::quicksort_tag());
    std::cout << "Quicksort took: " << boost::posix_time::to_simple_string(boost::posix_time::second_clock::local_time() - time) <<  std::endl;
}

Answer 1

请阅读this .我使用了选项:

CFLAGS += -fopenmp -Ofast -march=native

它们可以加快您的测试速度，但很遗憾，我没有足够的内核来重现您的结果。无论如何，允许 native CPU 操作应该会影响数据访问序列化。