并行快速排序通过单线程快速排序 [英] parallel quick sort outdone by single threaded quicksort

问题描述

我一直在读书C ++并发的行动，这里是使用futures实现并行快速排序的例子。

I've been reading the book C++ concurrency in action, here is the example in the book using futures to implement parallel quick sort.

但我发现这个函数比单线程快速排序函数慢两倍，而不使用任何异步设施在c ++标准库。
用g ++ 4.8和visual c ++ 2012测试。

But I found this function is more than twice slower than the single threaded quick sort function without using any asynchronous facilities in c++ standard library. Tested with g++ 4.8 and visual c++ 2012.

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

I used 10M random integers to test, and in visual c++ 2012,this function spawned 6 threads in total to perform the operation in my quad core PC.

我真的很困惑的性能。任何机构都可以告诉我为什么？

I am really confused about the performance. Any body can tell me why?

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

推荐答案

代码只是可怕的sub -最佳。例如，为什么不 std :: list< T> result（input）？为什么不 parallel_quick_sort（const std :: list< T>& input ？简介它，我敢打赌你会发现各种可怕的东西。代码的性能，你必须确保它花时间做你认为它在做什么！

The code is just horribly sub-optimal. For example, why not std::list<T> result(input)? Why not parallel_quick_sort(const std::list<T>& input? Profile it and I bet you'll find all kinds of horrible things. Before you make any sense of code's performance, you have to make sure it's spending its time doing what you think it's doing!

这篇关于并行快速排序通过单线程快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！