多线程归并排序比迭代方法 C++ 慢

Question

#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，迭代方法也要快得多。 我的算法有什么问题以及如何使其按预期工作？

Answer 1

对于线程，考虑以下因素很重要：

• 我实际可以同时运行的最大线程数是多少（考虑到我的硬件？）。通常是系统上逻辑核心的数量。
• 如何减少线程启动/加入的频率？启动线程是一项昂贵的操作，线程所做的工作需要超过启动它的成本。
• 如何（尽管这对于您的特定用例不太重要）如何尽可能减少线程访问相同数据的数量？

就您而言，我认为您最终产生的线程数量远多于系统实际可以处理的数量。举个最简单的例子，假设你在一台双核机器上；您可能希望将工作分成两个线程以获得最大吞吐量。

您可能想要类似的东西：

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);
            mergeSort(std::ref(v), mid + 1, right);
        }

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

这将跨两个线程启动第一级，每个线程都会递归到树的一半。

假设这有效（未经测试），您的下一步将是让它启动线程，只要您有有用的硬件来执行它们。但我会先检查你是否理解这个级别。