如何将线程与递归模板函数一起使用 [英] How to use threads with a recursive template function

问题描述

我一直在尝试使用线程优化排序算法(快速排序).我知道它在std :: sort()实现中已经相当不错了，但是我正在尝试通过计算机上的优化来击败它，并同时了解线程.

I've been trying to optimize a sorting algorithm (quicksort) with threads. I know it is already quite good in the std::sort() implementation, but I'm trying to beat it with optimizations on my computer, and learn about threads at the same time.

所以，我的问题是，如何将线程与递归quicksort函数一起使用?

So, my question is, how do I use threads with my recursive quicksort function?

这里是函数(删除了不重要的问题):

Here's the function (with the not-important-to-the-question stuff removed):

template <typename T>
void quicksort(T arr[], const int &size, const int &beginning, const int &end)
{
    // Algorithm here
    thread t1(quicksort, arr, size, beginning, slow - 1);
    thread t2(quicksort, arr, size, slow + 1, end);
}

如果我错了，并且您最终需要更多代码，请告诉我，我将对其进行更新.

If I was wrong and you do end up needing more of the code, let me know and I'll update it.

我正在使用Visual Studio 2012，截至目前，错误状态为:

I'm using Visual Studio 2012, and as of right now, the error states:

error C2661: 'std::thread::thread' : no overloaded function takes 5 arguments

我也尝试过对每个参数调用ref(arr)等，但是我遇到了相同的错误.

I've also tried calling ref(arr), etc. on each of the parameters, but I got the same error.

在尝试了@mfontanini的解决方案之后，我可以毫无错误地进行编译，但是在运行时，我得到了:

After trying the solution by @mfontanini I can compile with no errors, but on running, I get:

Debug Error!

Program: ...sktop\VisualStudio\Projects\SpeedTester\Debug\SpeedTester.exe

R6010
- abort() has been called


(Press Retry to debug the application)

重复一遍.最终，它退出并显示代码3.

Repeated over an over again. Eventually, it exits with code 3.

推荐答案

您的主要问题可能是您需要join()生成的thread.如果线程对象是在没有join()或detach()的情况下销毁的，则实现将调用std::terminate().

Your main problem probably is that you need to join() the thread(s) you spawn. If the thread objects are destructed without a prior join() or detach() the implementation calls std::terminate().

您不希望detach()，因为您需要知道所有部分排序都已完成才能使整体排序完整，所以join ing是正确的做法.

You don't want detach(), as you need to know that all partial sorts are finished for the overall sort to be complete, so joining is the right thing to do.

此外，您还有其他需要改进的地方:

Additionally there are a few more things you could improve:

• 您不应通过引用绕过int.对于简单的标量类型，按值传递更有效，并且从其他线程引用局部变量通常不是一个好主意(除非您有充分的理由和协议)
• 您启动的线程过多.分区后，两个子类别需要两个线程，但是您有三个:当前线程也继续运行，因此您应该只创建一个新线程，并在当前线程中执行另一个子类别. (完成后还有join()另一部分.)
• 当分区变小时，您不应该继续创建新线程.通常，最好为您的快速排序设置一个截断大小，然后为较小的大小使用非递归(例如插入排序)，因为递归开销变得比算法复杂性收益更高.对于并行并发排序，类似的中断更为重要:线程的开销比简单的递归调用高得多，并且在较小(和附近)的分区下，线程将开始频繁命中相同的缓存行，从而减慢了运行速度甚至更多.
• 创建不受限制的线程通常不是一个好主意.最终将遇到平台限制.您可能想要限制要使用的线程数(使用原子计数器)，或者在默认的启动策略中使用类似std::async的名称，以避免启动的线程数量超出平台的处理能力.

• You should not pass around ints by reference. Pass by value is more efficient for simple scalar types and referencing local variables from other threads is generally not a good idea (unless you have a good reason and protocol for it)
• You start far too many threads. After partitioning you need two threads for the two sub-sorts, but you have three: the current thread also continues to run, so you should create just one new thread and do the other sub-sort in the current thread. (And join() the other part when done.)
• You should not keep creating new threads when the partitions get small. It may generally be a good idea to have a cutoff size for your quicksort and use something non-recursive (like insertion sort) for smaller sizes, as the recursion overhead becomes higher than the algorithm complexity benefit. A similar cut-off is even more important for concurrent sorting: the overhead of a thread is much higher than a simple recursive call and with small (and nearby) partitions, the threads will start to hit the same cache lines frequently, slowing things down even more.
• It is generally not a good idea to create threads without limit. That will eventually run into platform limits. You might want to restrict the count of threads to use (using an atomic counter) or use something like std::async with default launch policy to avoid launching more threads than the platform can handle.

这篇关于如何将线程与递归模板函数一起使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！