c++ - 在 C++ 中使用多线程进行快速排序

Question

我使用多线程 方法实现了一个quicksort 程序，在C++ 中有一个Portfolio 任务。

The method of portfolio tasks is to maintain a queue of tasks. Each free thread picks a task from the portfolio, executes it, if necessary generating new subtasks and placing them in to the portfolio

但我不确定什么是对的!在我看来，在一个 thread 中，该算法比两个或四个 thread 运行得更快。我能以某种方式搞乱同步吗？

感谢任何人帮助我。

代码:

#include <thread>
#include <chrono>
#include <mutex>
#include <condition_variable>
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <ctime>
#include <algorithm>

using namespace std;

//print array
template <typename T>
void print(const vector<T> &arr)
{
    for (size_t i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";
    cout << endl;
}

//queue tasks
queue< pair<int, int> > tasks;
//mutexs for set and queue task
mutex q_mutex, s_mutex;
//condition variable
condition_variable cv;
//set
set<int> ss;

//partition algorithm
template <typename T>
int partition(vector<T> &arr, int l, int r)
{
    T tmp = arr[r]; //as pivot element
    int i = l - 1;

    for (int j = l; j <= r - 1; j++)
        if (arr[j] < tmp)
        {
            i++;
            swap(arr[i], arr[j]);       
        }

    swap(arr[i + 1], arr[r]);
    i++;
    return i;
}

//quick sort
template <typename T>
void quick_sort(vector<T> &arr)
{
    while (true)
    {
        unique_lock<mutex> u_lock(q_mutex); //lock mutex

        //sort is fineshed
        if ( ss.size() == arr.size() ) //u_lock.unlock()
            return;

        //if queue task is not empty 
        if ( tasks.size() > 0 )
        {
            //get task from queue
            pair<int, int> cur_task = tasks.front();            
            tasks.pop();

            int l = cur_task.first, r = cur_task.second;        

            if (l < r)
            {
                int q = partition(arr, l, r); //split array

                //Add indexes in set
                s_mutex.lock();
                ss.insert(q);
                ss.insert(l);
                ss.insert(r);
                s_mutex.unlock();

                //push new tasks for left and right part
                tasks.push( make_pair(l, q - 1) );
                tasks.push( make_pair(q + 1, r) );

                //wakeup some thread which waiting 
                cv.notify_one();
            }
        }
        else
            //if queue is empty
            cv.wait(u_lock);
    }
}

//Size array
const int ARR_SIZE = 100000;
//Count threads
const int THREAD_COUNT = 8;

thread thrs[THREAD_COUNT];

//generatin array
void generate_arr(vector<int> &arr)
{
    srand(time( NULL ));

    std::generate(arr.begin(), arr.end(), [](){return rand() % 10000; });
}

//check for sorting
bool is_sorted(const vector<int> &arr)
{
    for (size_t i = 0; i < arr.size() - 1; i++)
        if ( ! (arr[i] <= arr[i + 1]) ) 
            return false;
    return true;
}

int main()
{
    //time
    clock_t start, finish;

    vector<int> arr(ARR_SIZE);

    //generate array
    generate_arr(arr);

    cout << endl << "Generating finished!" << endl << endl;

    cout << "Array before sorting" << endl << endl;

    //Before sorting
    print(arr);

    cout << endl << endl;

    cout << "Checking is_sorted finished! The result is " << (is_sorted(arr) == 0? "false": "true") << "." << endl << endl;

    //add task
    tasks.push( make_pair(0, arr.size() - 1) );

    //==================================================
    start = clock();

    for (int i = 0; i < THREAD_COUNT; i++)
        thrs[i] = thread( quick_sort<int>, ref(arr) );

    finish = clock();
    //==================================================

    for (auto& th : thrs)
        th.join();

    cout << "Sorting finished!" << endl << endl;

    cout << "Array after sorting" << endl << endl;
    //After sorting
    print(arr);

    cout << endl << endl;

    cout << "Checking is_sorted finished! The result is " << (is_sorted(arr) == 0? "false": "true") << "." << endl << endl;

    cout << "Runtime: " << (double)(finish - start) / CLOCKS_PER_SEC << endl;

    return 0;
}

Answer 1

影响性能的因素远不止您在解决问题时使用了多少线程。其中，

• 您需要具有实际的并发性，而不仅仅是多线程。正如@Rakete1111 和@user1034749 都观察到的那样，你没有。

• 标准快速排序具有良好的引用局部性，尤其是当分区大小变小时，但您的技术会舍弃很多，因为给定数组元素的责任很可能在每次分区时被交换到不同的线程。

• 此外，互斥操作并不是特别便宜，当分区变小时，相对于实际排序的数量，您会开始做相当多的操作。

• 使用比物理内核更多的线程没有意义。四个线程可能不会太多，但这取决于您的硬件。

以下是一些可以提高多线程性能的方法:

1. 在方法 quick_sort() 中，不要在实际排序过程中保持互斥体 q_mutex 锁定，就像目前您所做的那样(unique_lock 您正在使用的构造函数锁定了互斥锁，并且您在 unique_lock 的生命周期内没有解锁它。

2. 对于小于某个阈值大小的分区，切换到普通递归技术。您必须进行测试才能找到一个好的特定阈值；也许它需要可调。

3. 在每个分区中，让每个线程只将一个子分区发布到投资组合中；让它递归地处理另一个——或者更好的是，迭代地处理另一个。事实上，让它成为您发布的较小子分区，因为这将更好地限制投资组合的大小。

您还可以考虑增加运行测试的元素数量。 100000 并没有那么多，对于更大的问题，您可能会看到不同的性能特征。 1000000 个元素对于现代硬件上的此类测试来说一点也不合理。