并行快速排序优于单线程快速排序

Question

我一直在读C++ concurrency in action这本书，下面是书中使用未来实现并行快速排序的示例。

但是我发现这个函数比不使用c++标准库中任何异步工具的单线程快速排序函数慢两倍以上。使用g++ 4.8和visual c++ 2012进行了测试。

我使用了10M个随机整数进行测试，在visual c++ 2012中，这个函数总共产生了6个线程来在我的四核PC上执行该操作。

我对表演真的很困惑。任何人都能告诉我为什么？

template<typename T>
std::list<T> parallel_quick_sort(std::list<T> input)
{
    if(input.empty())
    {
        return input;
    }
    std::list<T> result;
    result.splice(result.begin(),input,input.begin());
    T const& pivot=*result.begin();
    auto divide_point=std::partition(input.begin(),input.end(),
        [&](T const& t){return t<pivot;});
    std::list<T> lower_part;
    lower_part.splice(lower_part.end(),input,input.begin(),
        divide_point);
    std::future<std::list<T> > new_lower(
        std::async(&parallel_quick_sort<T>,std::move(lower_part)));
    auto new_higher(
        parallel_quick_sort(std::move(input)));
    result.splice(result.end(),new_higher);
    result.splice(result.begin(),new_lower.get());
    return result;
}

Answer 1

代码是可怕的次优的。例如，为什么不使用std::list<T> result(input)？为什么不是parallel_quick_sort(const std::list<T>& input呢？描述一下，我打赌你会发现各种各样可怕的东西。在你理解代码的性能之前，你必须确保它把时间花在你认为它正在做的事情上！