c# - 为什么C#中的多线程快速排序比单线程慢

Question

我知道以前曾问过这个问题，而我找到的答案都是关于抢先和同步开销等的。但是，我还是很想知道自己情况的答案。所以这是交易。

我在Intel Core i7-2670QM CPU(4个内核，8个线程)上运行，并编写了以下代码:

using System;
using System.Diagnostics;
using System.Threading;

namespace _T
{
    class Program
    {
        private static void stquicksort(object parameter)
        {
            object[] parameters = (object[])parameter;

            int[] array = (int[])parameters[0];
            int left = (int)parameters[1];
            int right = (int)parameters[2];

            if (left >= right) return;

            int temp = (left + right) / 2;
            int pivot = array[temp];

            array[temp] = array[right];

            int j = left;
            for (int i = left; i < right; i++)
            {
                if (array[i] < pivot)
                {
                    if (i != j)
                    {
                        temp = array[i];
                        array[i] = array[j];
                        array[j++] = temp;
                    }
                    else j++;
                }
            }

            array[right] = array[j];
            array[j] = pivot;

            stquicksort(new object[] { array, left, j - 1 });
            stquicksort(new object[] { array, j + 1, right });
        }
        private static void mtquicksort(object parameter)
        {
            object[] parameters = (object[])parameter;

            int[] array = (int[])parameters[0];
            int left = (int)parameters[1];
            int right = (int)parameters[2];

            if (left >= right) return;

            int temp = (left + right) / 2;
            int pivot = array[temp];

            array[temp] = array[right];

            int j = left;
            for (int i = left; i < right; i++)
            {
                if (array[i] < pivot)
                {
                    if (i != j)
                    {
                        temp = array[i];
                        array[i] = array[j];
                        array[j++] = temp;
                    }
                    else j++;
                }
            }

            array[right] = array[j];
            array[j] = pivot;

            Thread t = new Thread(mtquicksort);
            t.Start(new object[] { array, left, j - 1 });
            mtquicksort(new object[] { array, j + 1, right });
            t.Join();
        }

        private static void dump(int[] array)
        {
            Console.Write("Array:");
            foreach (int el in array) Console.Write(" " + el);
            Console.WriteLine();
        }

        private static void Main(string[] args)
        {
            while (true)
            {
                Console.Write("Enter the number of elements: ");
                int count = Convert.ToInt32(Console.ReadLine());
                if (count < 0) break;

                Random rnd = new Random();

                int[] array1 = new int[count];
                for (int i = 0; i < array1.Length; i++)
                    array1[i] = rnd.Next(1, 100);
                int[] array2 = (int[])array1.Clone();

                Stopwatch sw = new Stopwatch();

                sw.Reset(); sw.Start();
                stquicksort(new object[] { array1, 0, array1.Length - 1 });
                sw.Stop();

                Console.WriteLine("[ST] Time needed: " + sw.ElapsedMilliseconds + "ms");

                sw.Reset(); sw.Start();
                mtquicksort(new object[] { array2, 0, array2.Length - 1 });
                sw.Stop();

                Console.WriteLine("[MT] Time needed: " + sw.ElapsedMilliseconds + "ms");
            }

            Console.WriteLine("Press any key to exit . . .");
            Console.ReadKey(true);
        }
    }
}

stquicksort是单线程的，mtquicksort是多线程的，是的，我故意保留了st参数，因此装箱/拆箱的开销在两个版本上都是相同的(如果有的话)。我已将解决方案发布(禁用了所有调试功能)，输出有些令人遗憾:

Enter the number of elements: 100  
[ST] Time needed: 0ms  
[MT] Time needed: 323ms  

Enter the number of elements: 1000  
[ST] Time needed: 0ms  
[MT] Time needed: 7476ms  

Enter the number of elements: 1000  
[ST] Time needed: 0ms  
[MT] Time needed: 7804ms  

Enter the number of elements: 1000  
[ST] Time needed: 0ms  
[MT] Time needed: 7474ms  

Enter the number of elements: 10  
[ST] Time needed: 0ms  
[MT] Time needed: 32ms  

Enter the number of elements: 100  
[ST] Time needed: 0ms  
[MT] Time needed: 339ms  

再说一遍，这个问题是否先发制人，这可能是代码中的缺陷吗？更重要的是，什么是解决此问题的合适方法。

Answer 1

生成线程是一个相当昂贵的操作。它不是瞬时的，因此您所看到的大量时间不是执行排序所需的额外时间，而是生成胎面所需的时间。当您生成一个新线程以使其值得使用时，该线程必须运行一段时间。

.NET和C#确实具有任务系统，任务类似于线程，不同的是它们在线程池上运行，而不是每次都生成新线程。这使您可以执行多线程任务，而无需为每个任务创建一个新线程。

尝试以此替换线程代码。

Task t = Task.Run(()=>mtquicksort(new object[] { array, left, j - 1 }));
t.Wait();

注意，您将必须使用System.Threading.Tasks命名空间