c# - 对类实例而不是 float 进行排序时 Array.Sort() 性能下降

Question

如果对 float 进行排序，C# 中的 Array.Sort 非常快，我需要一些额外的数据来处理这些 float ，所以我创建了一个简单的类并扩展了 IComparable 接口(interface)。现在 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.

---

编辑:我更新了代码以使用结构和委托(delegate)进行排序，如下所示，没有区别。

新的演示输出:

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 的重载方法。请注意，我在 Stopwatch 外部创建并填充了 test[] ，因为在我的例子中我已经有了该数组。 arraySortOverload 在 Debug模式下速度更快，在 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 的区别很有趣!

• 对于 normalFloatAverage，x64 比 x86 更快
• 对于 floatWithIDAverage，x86 比 x64 更快

结论

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