并行mergesort C++中的性能问题

Question

并行mergesort C++中的性能问题

erk*_*kan 4 c++ recursion performance mergesort multithreading

我试图使用线程和模板编写mergesort的并行实现.相关代码如下所示.

我已经将性能与C++ STL中的排序进行了比较.当没有线程产生时,我的代码比std :: sort慢6倍.使用变量maxthreads(和/或FACTOR)我只能将性能提高一倍,因此在最好的情况下,我比std :: sort慢3倍.我已经在16核多处理器机器上尝试了代码.

htop显示核心是按预期使用的,但为什么缺乏性能而我感觉不到整体运行时的并行性？

有错误吗？

谢谢你的回复.

#define FACTOR 1
static unsigned int maxthreads = FACTOR * std::thread::hardware_concurrency();

unsigned int workers=0;
std::mutex g_mutex;

template <typename T>
std::vector<T>* mergesort_inplace_multithreading(
    typename std::vector<T>::iterator* listbegin,
    typename std::vector<T>::iterator *listend,
    std::vector<T>* listarg)
{
    if (*listbegin == *listend)
    {
        return listarg;
    }
    else if (*listend == *listbegin + 1)
    {
        return listarg;
    }
    else
    {
        size_t offset = std::distance(*listbegin, *listend)/2;
        typename std::vector<T>::iterator listhalf = *listbegin + offset;
        g_mutex.lock();
        if (::workers <= maxthreads-2 and maxthreads >=2)
        {
            workers += 2;

            g_mutex.unlock();

            std::thread first_thread(mergesort_inplace_multithreading<T>, listbegin, &listhalf, listarg);
            std::thread second_thread(mergesort_inplace_multithreading<T>, &listhalf, listend, listarg);
            first_thread.join();
            second_thread.join();
            g_mutex.lock();
            workers -= 2;
            g_mutex.unlock();
        }
        else
        {
            g_mutex.unlock();
            mergesort_inplace_multithreading<T>(listbegin, &listhalf, listarg);
            mergesort_inplace_multithreading<T>(&listhalf, listend, listarg);
        }

        typename std::vector<T> result;
        typename std::vector<T>::iterator lo_sorted_it = *listbegin;
        typename std::vector<T>::iterator hi_sorted_it = listhalf;
        typename std::vector<T>::iterator lo_sortedend = listhalf;
        typename std::vector<T>::iterator hi_sortedend = *listend;
        while (lo_sorted_it != lo_sortedend and hi_sorted_it != hi_sortedend)
        {
            if (*lo_sorted_it <= *hi_sorted_it)
            {
                result.push_back(*lo_sorted_it);
                ++lo_sorted_it;
            }
            else
            {
                result.push_back(*hi_sorted_it);
                ++hi_sorted_it;
            }

        }//end while

        if (lo_sorted_it != lo_sortedend)
        {
            //assert(hi_sorted_it == hi_sortedend);
            result.insert(result.end(), lo_sorted_it, lo_sortedend);
        }
        else
        {
            //assert(lo_sorted_it == lo_sortedend);
            result.insert(result.end(), hi_sorted_it, hi_sortedend);
        }
        std::copy(result.begin(), result.end(), *listbegin);
        return listarg;
    }
}

int main()
{
    //some tests
}

Run Code Online (Sandbox Code Playgroud)

Answer 1

Who*_*aig 16

并行mergesort不需要互斥锁.而且你肯定不需要为每个分区分区启动两个线程.你启动一个线程; 第二个分区在当前线程上处理; 线程资源的使用要好于一个线程,除了等待其他两个完成之外什么都不做.

首先,简单的测试程序,排序2000万个无符号整数.注意:使用Apple LLVM版本5.1(clang-503.0.40)(基于LLVM 3.4svn)编译的所有程序,64位,posix线程和设置为O2的优化

测试程序

int main()
{
    using namespace std::chrono;

    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<unsigned int> dist(0, std::numeric_limits<unsigned int>::max());

    std::vector<unsigned int> v, back(20*1000000);

    for (int i=0; i<5; ++i)
    {
        std::cout << "Generating...\n";
        std::generate_n(back.begin(), back.size(), [&](){return dist(rng);});

        time_point<system_clock> t0, t1;

        v = back;
        std::cout << "std::sort: ";
        t0 = system_clock::now();
        std::sort(v.begin(), v.end());
        t1 = system_clock::now();
        std::cout << duration_cast<milliseconds>(t1-t0).count() << "ms\n";

        v = back;
        std::cout << "mergesort_mt1: ";
        t0 = system_clock::now();
        mergesort_mt1(v.begin(), v.end());
        t1 = system_clock::now();
        std::cout << duration_cast<milliseconds>(t1-t0).count() << "ms\n";
    }

    return 0;
}

Run Code Online (Sandbox Code Playgroud)

并行Mergesort

我们从超基本的东西开始.我们将并发线程数量限制为标准库中报告的硬件并发性.一旦我们达到这个限制,我们就会停止发布新线程并简单地对现有线程进行递归.一旦分布在硬件支持的线程上,这种简单的算法就具有令人惊讶的良好行为.

template<typename Iter>
void mergesort_mt1(Iter begin, Iter end,
                  unsigned int N = std::thread::hardware_concurrency()/2)
{
    auto len = std::distance(begin, end);
    if (len < 2)
        return;

    Iter mid = std::next(begin, len/2);
    if (N > 1)
    {
        auto fn = std::async(mergesort_mt1<Iter>, begin, mid, N-2);
        mergesort_mt1(mid, end, N-2);
        fn.wait();
    }
    else
    {
        mergesort_mt1(begin, mid, 0);
        mergesort_mt1(mid, end, 0);
    }

    std::inplace_merge(begin, mid, end);
}

Run Code Online (Sandbox Code Playgroud)

产量

Generating...
std::sort: 1902ms
mergesort_mt1: 1609ms
Generating...
std::sort: 1894ms
mergesort_mt1: 1584ms
Generating...
std::sort: 1881ms
mergesort_mt1: 1589ms
Generating...
std::sort: 1840ms
mergesort_mt1: 1580ms
Generating...
std::sort: 1841ms
mergesort_mt1: 1631ms

Run Code Online (Sandbox Code Playgroud)

这看起来很有希望,但肯定可以改进.

并行合并+标准库排序

该std::sort算法在实现中因供应商而异.标准的主要限制是它必须具有平均复杂度O(NlogN).为了在性能方面实现这一点,许多std::sort算法都是标准库中可以找到的最复杂,最精简的代码.我仔细研究了一些具有多种内部排序特征的实现.一种这样的实现我看到使用内省排序(快速排序,直到递归深度是有限的,则堆排序)为更大分区,并且一旦小分区被达到,屈从于一个庞大的手展开16槽插入排序.

关键是,标准库作者理解一种通用排序算法根本不适合所有.有几个人经常被用来完成这项任务,经常和谐共处.不要天真地认为你可以打败他们; 相反,通过利用他们的辛勤工作加入他们.

修改我们的代码非常简单.我们使用std::sort小于1025的所有分区.其余分区相同:

template<typename Iter>
void mergesort_mt2(Iter begin, Iter end,
                   unsigned int N = std::thread::hardware_concurrency())
{
    auto len = std::distance(begin, end);
    if (len <= 1024)
    {
        std::sort(begin,end);
        return;
    }

    Iter mid = std::next(begin, len/2);
    if (N > 1)
    {
        auto fn = std::async(mergesort_mt2<Iter>, begin, mid, N-2);
        mergesort_mt2(mid, end, N-2);
        fn.wait();
    }
    else
    {
        mergesort_mt2(begin, mid, 0);
        mergesort_mt2(mid, end, 0);
    }

    std::inplace_merge(begin, mid, end);
}

Run Code Online (Sandbox Code Playgroud)

将新的测试用例添加到测试程序后,我们得到:

产量

Generating...
std::sort: 1930ms
mergesort_mt1: 1695ms
mergesort_mt2: 998ms
Generating...
std::sort: 1854ms
mergesort_mt1: 1573ms
mergesort_mt2: 1030ms
Generating...
std::sort: 1867ms
mergesort_mt1: 1584ms
mergesort_mt2: 1005ms
Generating...
std::sort: 1862ms
mergesort_mt1: 1589ms
mergesort_mt2: 1001ms
Generating...
std::sort: 1847ms
mergesort_mt1: 1578ms
mergesort_mt2: 1009ms

Run Code Online (Sandbox Code Playgroud)

好.现在我们看到一些令人印象深刻的东西.但是我们可以挤得更远吗？

并行合并+标准排序w /有限递归

如果你考虑一下,为了充分利用所有的努力工作std::sort,我们可以在达到完整的线程数后立即停止递归.如果发生这种情况,只需对我们所拥有的std::sort内容进很难相信,这实际上会降低代码的复杂性.我们的算法变成了在核心之间简单地扩展分区的算法,每个分区在std::sort时机到来时处理:

template<typename Iter>
void mergesort_mt3(Iter begin, Iter end,
                   unsigned int N = std::thread::hardware_concurrency()/2)
{
    auto len = std::distance(begin, end);
    if (len <= 1024 || N < 2)
    {
        std::sort(begin,end);
        return;
    }

    Iter mid = std::next(begin, len/2);
    auto fn = std::async(mergesort_mt3<Iter>, begin, mid, N-2);
    mergesort_mt3(mid, end, N-2);
    fn.wait();
    std::inplace_merge(begin, mid, end);
}

Run Code Online (Sandbox Code Playgroud)

将此添加到我们的测试循环之后再次...

产量

Generating...
std::sort: 1911ms
mergesort_mt1: 1656ms
mergesort_mt2: 1006ms
mergesort_mt3: 802ms
Generating...
std::sort: 1854ms
mergesort_mt1: 1588ms
mergesort_mt2: 1008ms
mergesort_mt3: 806ms
Generating...
std::sort: 1836ms
mergesort_mt1: 1580ms
mergesort_mt2: 1017ms
mergesort_mt3: 806ms
Generating...
std::sort: 1843ms
mergesort_mt1: 1583ms
mergesort_mt2: 1006ms
mergesort_mt3: 853ms
Generating...
std::sort: 1855ms
mergesort_mt1: 1589ms
mergesort_mt2: 1012ms
mergesort_mt3: 798ms

Run Code Online (Sandbox Code Playgroud)

如上所述,对于任何1024个或更小的分区,我们只需委托给std::sort.如果分区较大,我们引入一个新线程来处理拆分分区的一侧,使用当前线程来处理另一个.一旦我们使线程限制N饱和,我们就会停止拆分并简单地将所有内容委托给std::sort无论如何.简而言之,我们是一个多线程分发前端std::sort.

摘要

在我们可以解雇的房间里还有更多的子弹(使用一些元编程并假设一个固定的并发池号),但我留给你.

如果您只关注分区,分配到线程直到分区,使用高度优化的分区算法进行分区,然后将各种东西拼接在一起以完成工作,则可以显着提高分类性能.还有改进的余地吗？当然.但是在上面提到的最简单的形式中没有锁定,没有互斥,等等.最终样本和裸露之间的差异std::sort是相同的数据集在2011年中期的一个微不足道的小型MacBook Air上有惊人的58%改进,4gB RAM和一个二人组-core i7处理器.这是令人印象深刻的,考虑到它花了很少的代码,只是简单的f'ing 真棒.

归档时间：	12 年，1 月前
查看次数：	2240 次
最近记录：	9 年，8 月前