c# - 线程合并排序比串行实现慢

Question

在学校，我们接到了创建多线程应用程序的任务。我们选择进行合并排序的多线程实现。

然而，我们无法让它比串行实现更快地工作。

我已经尝试过以下方法:

• 无限线程的实现(代码示例 1)(非常慢)
• 使用有限线程实现(代码示例 2)(最多 4 个线程 - 仍然很慢)
• 使用 Parallel.Invoke 实现(代码示例 3)(仍然较慢)
• 复杂的实现还带有并行合并功能(慢得可耻)

当我在 Visual Studio(Instrumentation 部分)中使用分析工具时，我发现调用函数的时间安排和线程解决方案总是比串行实现慢得多。

我看不出有任何可能的原因。

(例如:有 5000000 个数字要排序；串行实现:16.717,17；并行:20.259,97；结果只有 1 个额外线程)

我在我拥有的两台机器上测试了它:

• 英特尔酷睿 2 四核 Q9450 @ 2.66Ghz
• 英特尔酷睿 i7 Q720 @1.60Ghz

我这辈子都想不通这是怎么可能的，难道这不应该只是加快这个过程吗？

如果有人能够帮助我，我将非常感激。

代码示例 1:

ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3);
Thread thread = new Thread(new ThreadStart(pMerge.parallel_merge));
thread.Start();

ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1);
pMerge2.parallel_merge();
thread.Join();

代码示例 2:

if(depthRemaining > 0)
{
   ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3);
   thread thread = new Thread(new ThreadStart(pMerge.parallel_merge));
   thread.Start();
   ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1);
   pMerge2.parallel_merge(); 
   thread.Join();
}
else
{
   ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3);
   pMerge.parallel_merge(); 
   ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1);
   pMerge.parallel_merge(); 
}

代码示例 3:

if (depthRemaining > 0)
{
   Parallel.Invoke(
      () => threaded_merge_sort(getallen, p, q, depthRemaining-1));

   threaded_merge_sort(getallen, q + 1, r, 0);
}
else
{
   threaded_merge_sort(getallen, p, q, 0);
   threaded_merge_sort(getallen, q+1, r, 0);
}

Answer 1

您报告的时间单位是什么？

启动一个新线程是一个“缓慢”的操作。使用多线程对非常短的列表进行排序/合并可能会慢一些。

如果您只是将数字列表的长度分成两半，程序会运行得更快吗？否则，您的代码根本无法扩展。

在没有实际代码实现的情况下回答这个问题有点困难。