2

在列表被分成左右两半（小于和大于枢轴）之后，我正在使用 Pthreads 为每个分区创建一个新的线程。我递归地执行此操作，直到达到允许的最大线程数。

当我使用 printfs 跟踪程序中发生的事情时，我清楚地看到每个线程都在并行执行其委派的工作。但是，使用单个进程始终是最快的。一旦我尝试使用更多线程，完成所需的时间几乎翻了一番，并且随着线程数的增加而不断增加。

我被允许在运行它的服务器上使用多达 16 个处理器。

算法是这样的：通过将元素与枢轴进行比较，将数组拆分为左右。为左右开始一个新线程，并等待线程重新加入。如果有更多可用线程，它们可以更递归地创建。每个线程都等待其子节点加入。

一切对我来说都很有意义，并且排序工作得很好，但是更多的线程使它变得非常慢。

我尝试为要启动的线程设置每个分区的最小元素数（例如 50000）。

我尝试了一种方法，当一个线程完成后，它允许启动另一个线程，这会导致数百个线程在整个过程中启动和完成。我认为开销太大了。所以我摆脱了它，如果一个线程执行完毕，就不会创建新线程。我得到了更多的加速，但仍然比单个进程慢很多。

我使用的代码如下。

http://pastebin.com/UaGsjcq2

有人知道我做错了什么吗？

4

4 回答 4

6

启动一个线程有相当多的开销。您可能最好创建一个具有一些固定数量的线程的线程池，以及一个线程安全队列来排队等待线程执行的作业。线程等待队列中的一个项目，处理该项目，然后等待另一个项目。如果您想真正正确地做事，这应该是一个优先级队列，其排序基于分区的大小（因此您总是首先对最小的分区进行排序，以帮助防止队列大小过大）。

这至少大大减少了启动线程的开销——但这仍然不能保证您将获得比单线程版本更好的性能。特别是，快速排序在 CPU 本身上涉及的工作量很少，以至于它可能几乎完全受内存带宽的限制。一次处理多个分区可能会损害缓存局部性，以至于在任何情况下都会失去速度。

于 2010-06-07T13:57:03.467 回答
1

第一个猜测是创建、销毁，尤其是同步你的线程会消耗掉你可能获得的收益，这取决于你正在排序的元素数量。我实际上猜想弥补开销需要相当长的时间，而且可能永远不会弥补。

因为你有你的排序方式，你有一个线程在等待另一个等待另一个......你并没有真正得到那么多的并行性。您最好使用更线性的排序，也许像 Radix 之类的东西，它将线程与更多的数据分开。那仍然有一个线程等待其他线程很多，但至少线程同时可以做更多的工作。但是，即使这样，我仍然认为线程不会有太大帮助。

于 2010-06-07T13:57:12.950 回答
1

我只是快速浏览一下您的代码。我得到了一个评论。你为什么用锁。如果我明白你在做什么是这样的：

quickSort(array)
{
    left, right = partition(array);
    newThread(quickSort(left));
    newThread(quickSort(right));
}

你不应该需要锁。通常每个快速排序调用都不会访问数组的其他部分。所以不涉及共享。

于 2010-06-07T14:08:28.557 回答
0

除非每个线程都在单独的处理器或内核上运行，否则它们不会真正同时运行，并且上下文切换时间会很长。线程数应限制为可用执行单元的数量，即使那样，您也必须相信操作系统会将它们分发到单独的处理器/内核，如果它们也用于其他进程，它可能不会这样做。

此外，您应该使用静态线程池，而不是动态创建和销毁线程。创建/销毁线程包括从堆中分配/释放堆栈，这是不确定的并且可能很耗时。

最后，服务器上的 16 个处理器是真实的还是虚拟机？它们是否专门分配给您的流程？

于 2010-06-07T21:43:10.730 回答