多线程合并排序比迭代方法C++慢[关闭]

b5buobof 于 9个月前发布在其他

关注(0)|答案(2)|浏览(118)

已关闭。此问题需要details or clarity。目前不接受回答。
**要改进此问题吗？**通过editing this post添加详细信息并阐明问题。

#include <iostream>
#include <vector>
#include <thread>

void mergeSort(std::vector<int>& v, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        std::thread t1(mergeSort, std::ref(v), left, mid);
        std::thread t2(mergeSort, std::ref(v), mid + 1, right);

        t1.join();
        t2.join();

        merge(v, left, mid, right);
    }
}

我尝试了多线程方法来实现归并排序算法，但是当测试多线程和迭代之间的差异时，即使输入高达1M，迭代方法也要快得多。我的算法有什么问题，我如何才能让它按预期工作？

c++

来源：https://stackoverflow.com/questions/77755082/multi-threaded-merge-sort-slower-than-the-iterative-approach-c

2条答案

按热度按时间

ut6juiuv1#

使用线程时，重要的是要考虑以下几点：

一次可以运行的最大线程数是多少（给定硬件？）。通常是系统上的逻辑核心数。
如何降低线程启动/加入的频率？启动线程是一个开销很大的操作，线程所做的工作要超过启动它的开销。
如何（尽管这对于您的特定用例不太重要）尽可能减少线程访问相同数据的数量？

在你的例子中，我认为你最终会产生比你的系统实际上可以处理的多得多的线程。让我们举一个最简单的例子，假设你在一个双核机器上;你想把你的工作分成两个线程来实现最大的吞吐量。
你可能想要这样的东西：

void mergeSort(std::vector<int>& v, int left, int right, bool shouldThread) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        if (shouldThread) {
            std::thread t1(mergeSort, std::ref(v), left, mid, false);
            std::thread t2(mergeSort, std::ref(v), mid + 1, right, false);

            t1.join();
            t2.join();
        }
        else
        {
            mergeSort(std::ref(v), left, mid, false);
            mergeSort(std::ref(v), mid + 1, right, false);
        }

        merge(v, left, mid, right);
    }
}

字符串
这将跨两个线程启动第一级，每个线程将向下递归树的一半。
假设这是可行的（未经测试），下一步就是让它启动线程，只要你有有用的硬件来执行它们。

赞(0）回复(0）举报 9个月前

tmb3ates2#

将线程数限制为核心数或核心数的2倍。链接到示例4线程合并排序，它比单线程合并排序快3倍。
https://codereview.stackexchange.com/q/148025/59065

赞(0）回复(0）举报 9个月前