多线程合并排序 -> 如何优化？

Question

我尝试多线程合并排序算法。该算法的简单形式是：(Merge(( 是一个标准的合并算法(

static void MergeSort(this int[] array, int initial, int final) {
if (initial == final) return;
array.MergeSort(initial, (initial + final) / 2);
array.MergeSort((initial + final) / 2 + 1, final);
array.Merge(initial, final);
}

多线程版本是：

static void MergeSortMT(this int[] array, int initial, int final, int mtCount) {
if (initial == final) return;
if (mtCount > 0) {
Task t = Task.Run(() =>
{
array.MergeSortMT(initial, (initial + final) / 2, mtCount - 1);
});
array.MergeSortMT((initial + final) / 2 + 1, final, mtCount - 1);
t.Wait();
}
else
{
array.MergeSort(initial, (initial + final) / 2);
array.MergeSort((initial + final) / 2 + 1, final);
}
array.Merge(initial, final);
}

此处的 mtCount 指示线程分离将发生多少次。通常，整个排序由单个线程运行。如果 mtCount 为 1，则总线程数变为 2，如果 mtCount 为 2，则总线程数变为 4，依此类推。

以下是一些结果：

Method - Input Size - Times Run - Miliseconds
Merge 1000000 X 1000    606832
Merge 100000 X 1000     51061
Merge 10000 X 1000      4080
Merge 1000 X 1000       314
Merge 100 X 1000        22
Merge 10 X 1000         1
mtCount = 1
MergeMT 1000000 X 1000  258237
MergeMT 100000 X 1000   23498
MergeMT 10000 X 1000    2088
MergeMT 1000 X 1000     202
MergeMT 100 X 1000      57
MergeMT 10 X 1000       44
mtCount = 2
MergeMT 1000000 X 1000  188337
MergeMT 100000 X 1000   16836
MergeMT 10000 X 1000    1825
MergeMT 1000 X 1000     355
MergeMT 100 X 1000      162
MergeMT 10 X 1000       299
mtCount = 3
MergeMT 1000000 X 1000  175220
MergeMT 100000 X 1000   15276
MergeMT 10000 X 1000    1690
MergeMT 1000 X 1000     455
MergeMT 100 X 1000      296
MergeMT 10 X 1000       416
mtCount = 4
MergeMT 1000000 X 1000  197234
MergeMT 100000 X 1000   17046
MergeMT 10000 X 1000    2087
MergeMT 1000 X 1000     684
MergeMT 100 X 1000      657
MergeMT 10 X 1000       596

因此，使用 2 个线程将代码优化了 2 倍以上。使用 4 个线程的影响较小，8 个线程几乎没有任何好处。使用 16 个线程甚至会降低性能，这是可以理解的。(较小的输入大小并不重要。我知道启动一个新线程需要一些时间。

知道我的计算机有 4 个物理内核和 8 个线程，我的问题是为什么使用 4 或 8 个线程对性能的提高要少得多？

Answer 1

因为合并排序由 2 个主要部分组成：

1. 递归排序 2 半
2. 合并 2 个分选的半部分

合并排序中的多线程处理是有效的，因为两个线程可以在第一步中异步执行 2 个不同的调用。但是，第二步不能通过多线程来加快，因为它是一个必须在单个线程上运行的线性过程。第二步实际上需要相当长的时间。例如，最后一个(也是最大的(合并调用大约占用整个排序持续时间的三分之一。