排序类实例而不是浮点数时,Array.Sort()性能下降

Question

如果你对浮点数进行排序,C#中的Array.Sort真的很快,我需要一些额外的数据来配合这些浮点数,所以我做了一个简单的类并扩展了IComparable接口.现在,Array.Sort突然慢了3-4倍,为什么会这样,我怎样才能提高性能呢？

演示代码:

using System;
using System.Diagnostics;
using System.Linq;

namespace SortTest
{
    class Program
    {
        static void Main(string[] args)
        {
            int arraySize = 10000;
            int loops = 500;

            double normalFloatTime = 0;
            double floatWithIDTime = 0;
            double structTime = 0;
            double arraySortOverloadTime = 0;

            bool floatWithIDCorrect = true;
            bool structCorrect = true;
            bool arraySortOverloadCorrect = true;

            //just so we know the program is busy
            Console.WriteLine("Sorting random arrays, this will take some time...");

            Random random = new Random();
            Stopwatch sw = new Stopwatch();
            for (int i = 0; i < loops; i++)
            {
                float[] normalFloatArray = new float[arraySize];
                SortTest[] floatWithIDArray = new SortTest[arraySize];
                SortStruct[] structArray = new SortStruct[arraySize];
                SortTest[] arraySortOverloadArray = new SortTest[arraySize];

                //fill the arrays
                for (int j = 0; j < arraySize; j++)
                {
                    normalFloatArray[j] = NextFloat(random);
                    floatWithIDArray[j] = new SortTest(normalFloatArray[j], j);
                    structArray[j] = new SortStruct(normalFloatArray[j], j);
                    arraySortOverloadArray[j] = new SortTest(normalFloatArray[j], j);
                }

                //Reset stopwatch from any previous state
                sw.Reset();
                sw.Start();
                Array.Sort(normalFloatArray);
                sw.Stop();
                normalFloatTime += sw.ElapsedTicks;

                //Reset stopwatch from any previous state
                sw.Reset();
                sw.Start();
                Array.Sort(floatWithIDArray);
                sw.Stop();
                floatWithIDTime += sw.ElapsedTicks;

                //Reset stopwatch from any previous state
                sw.Reset();
                sw.Start();
                Array.Sort(structArray);
                sw.Stop();
                structTime += sw.ElapsedTicks;

                //Reset stopwatch from any previous state
                sw.Reset();
                sw.Start();
                Array.Sort(arraySortOverloadArray.Select(k => k.ID).ToArray(), arraySortOverloadArray);
                sw.Stop();
                arraySortOverloadTime += sw.ElapsedTicks;

                for (int k = 0; k < normalFloatArray.Length; k++)
                {
                    if (normalFloatArray[k] != floatWithIDArray[k].SomeFloat)
                    {
                        floatWithIDCorrect = false;
                    }

                    if (normalFloatArray[k] != structArray[k].SomeFloat)
                    {
                        structCorrect = false;
                    }

                    if (normalFloatArray[k] != arraySortOverloadArray[k].SomeFloat)
                    {
                        arraySortOverloadCorrect = false;
                    }
                }
            }

            //calculate averages
            double normalFloatAverage = normalFloatTime / loops;
            double floatWithIDAverage = floatWithIDTime / loops;
            double structAverage = structTime / loops;
            double arraySortOverloadAverage = arraySortOverloadTime / loops;

            //print averages
            Console.WriteLine("normalFloatAverage: {0} ticks.\nfloatWithIDAverage: {1} ticks.\nstructAverage: {2} ticks.\narraySortOverloadAverage: {3} ticks.", normalFloatAverage, floatWithIDAverage, structAverage, arraySortOverloadAverage);

            Console.WriteLine("floatWithIDArray has " + (floatWithIDCorrect ? "" : "NOT ") + "been sorted correctly atleast once.");
            Console.WriteLine("structArray has " + (structCorrect ? "" : "NOT ") + "been sorted correctly atleast once.");
            Console.WriteLine("arraySortOverloadArray has " + (arraySortOverloadCorrect ? "" : "NOT ") + "been sorted correctly atleast once.");

            Console.WriteLine("Press enter to exit.");
            //pause so we can see the console
            Console.ReadLine();
        }

        static float NextFloat(Random random)
        {
            double mantissa = (random.NextDouble() * 2.0) - 1.0;
            double exponent = Math.Pow(2.0, random.Next(-126, 128));
            return (float)(mantissa * exponent);
        }
    }

    class SortTest : IComparable<SortTest>
    {
        public float SomeFloat;
        public int ID;

        public SortTest(float f, int id)
        {
            SomeFloat = f;
            ID = id;
        }

        public int CompareTo(SortTest other)
        {
            float f = other.SomeFloat;
            if (SomeFloat < f)
                return -1;
            else if (SomeFloat > f)
                return 1;
            else
                return 0;
        }
    }

    struct SortStruct : IComparable<SortStruct>
    {
        public float SomeFloat;
        public int ID;

        public SortStruct(float f, int id)
        {
            SomeFloat = f;
            ID = id;
        }

        public int CompareTo(SortStruct other)
        {
            float f = other.SomeFloat;
            if (SomeFloat < f)
                return -1;
            else if (SomeFloat > f)
                return 1;
            else
                return 0;
        }
    }
}

演示输出:

Sorting random arrays, this will take some time...
normalFloatAverage: 3840,998 ticks.
floatWithIDAverage: 12850.672 ticks.
Press enter to exit.

---

编辑:我更新了代码以使用结构和委托排序,如下所示,没有区别.

新的演示输出:

Sorting random arrays, this will take some time...
normalFloatAverage: 3629.092 ticks.
floatWithIDAverage: 12721.622 ticks.
structAverage: 12870.584 ticks.
Press enter to exit.

---

编辑2:我已经使用下面的一些建议更新了我的代码,使其成为一个结构或者对我的电脑没有影响或我正在做一些可怕的错误.我还加了一些健全检查.

新的演示输出(不要让"至少一次"愚弄你,它是错误的):

Sorting random arrays, this will take some time...
normalFloatAverage: 3679.928 ticks.
floatWithIDAverage: 14084.794 ticks.
structAverage: 11725.364 ticks.
arraySortOverloadAverage: 2186.3 ticks.
floatWithIDArray has been sorted correctly atleast once.
structArray has been sorted correctly atleast once.
arraySortOverloadArray has NOT been sorted correctly atleast once.
Press enter to exit.

---

编辑3:我已经通过修复Array.Sort的重载方法再次更新了演示代码.请注意,我在秒表之外创建并填写test []因为在我的情况下我已经有了该数组.arraySortOverload在调试模式下更快,并且与发布模式下的struct方法一样快.

新的演示输出(RELEASE):

Sorting random arrays, this will take some time...
normalFloatAverage: 2384.578 ticks.
floatWithIDAverage: 6405.866 ticks.
structAverage: 4583.992 ticks.
arraySortOverloadAverage: 4551.104 ticks.
floatWithIDArray has been sorted correctly all the time.
structArray has been sorted correctly all the time.
arraySortOverloadArray has been sorted correctly all the time.
Press enter to exit.

Answer 1

有两种小方法可以加快速度：

1. 使用结构而不是类。
2. 手动编写 CompareTo() 而不是使用 float.CompareTo()。

还有一个主要方法可以加快速度floatWithIDAverage：使用 x86 而不是 x64。（但这并没有加速normalFloatAverage！）

进行任何更改之前的结果（对于 RELEASE 构建，而不是 DEBUG 构建）：

x64：

normalFloatAverage: 2469.86 ticks.
floatWithIDAverage: 6172.564 ticks.

x86：

normalFloatAverage: 3071.544 ticks.
floatWithIDAverage: 6036.546 ticks.

将 SortTest 更改为结构后的结果：

此更改允许编译器进行许多优化。

x64：

normalFloatAverage: 2307.552 ticks.
floatWithIDAverage: 4214.414 ticks.

x86：

normalFloatAverage: 3054.814 ticks.
floatWithIDAverage: 4541.864 ticks.

更改SortTest.CompareTo()后的结果如下：

public int CompareTo(SortTest other)
{
    float f = other.SomeFloat;

    if (SomeFloat < f)
        return -1;
    else if (SomeFloat > f)
        return 1;
    else
        return 0;
}

此更改消除了调用 的开销float.CompareTo()。

x64：

normalFloatAverage: 2323.834 ticks.
floatWithIDAverage: 3721.254 ticks.

x86：

normalFloatAverage: 3087.314 ticks.
floatWithIDAverage: 3074.364 ticks.

最后，在这种特定情况下，floatWithIDAverage实际上比normalFloatAverage.

x86 和 x64 之间的区别很有趣！

• x64 比 x86 更快normalFloatAverage
• x86 比 x64 更快floatWithIDAverage

结论

虽然我无法解释为什么 x86 版本比 x64 版本快得多floatWithIDAverage，但我已经展示了一种显着加快速度的方法。