Array.Sort() performance drop when sorting class instances instead of floats

Question

Array.Sort in C# is really fast if you sort floats, I need some extra data to go along with those floats so I made a simple class and extended the IComparable interface. Now all of a sudden Array.Sort is around 3-4 times slower, why is this and how can I improve the performance?

Demo code:

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;
        }
    }
}

Demo output:

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

---

Edit: I updated the code to also sort using a struct and a delegate, as suggested below, there is no difference.

New demo output:

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

---

Edit 2: I have updated my code with some of the suggestions below, making it a struct either has no effect on my pc or I am doing something horribly wrong. I also added some sanity checks.

New demo output (don't let the "atleast once" fool you, it is misphrased):

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.

---

Edit 3: I have updated the demo code once again with a fix to the overloaded method of Array.Sort. Note that I create and fill test[] outside the Stopwatch because in my case I already have that array available. arraySortOverload is faster in debug mode, and about as fast as the struct method in release mode.

New demo output (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

There are two minor ways to speed this up:

1. Use a struct instead of a class.
2. Hand-code the CompareTo() instead of using float.CompareTo().

There is also a major way to speed this up for floatWithIDAverage: Use x86 instead of x64. (But this does NOT speed up normalFloatAverage!)

Results before making any changes (for a RELEASE build, not a DEBUG build):

x64:

normalFloatAverage: 2469.86 ticks.
floatWithIDAverage: 6172.564 ticks.

x86:

normalFloatAverage: 3071.544 ticks.
floatWithIDAverage: 6036.546 ticks.

Results after changing SortTest to be a struct:

This change allows the compiler to make a number of optimizations.

x64:

normalFloatAverage: 2307.552 ticks.
floatWithIDAverage: 4214.414 ticks.

x86:

normalFloatAverage: 3054.814 ticks.
floatWithIDAverage: 4541.864 ticks.

Results after changing SortTest.CompareTo() as follows:

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

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

This change removes the overhead of calling float.CompareTo().

x64:

normalFloatAverage: 2323.834 ticks.
floatWithIDAverage: 3721.254 ticks.

x86:

normalFloatAverage: 3087.314 ticks.
floatWithIDAverage: 3074.364 ticks.

Finally, in this specific case, floatWithIDAverage is actually faster than normalFloatAverage.

The difference between x86 and x64 is interesting!

• x64 is faster than x86 for normalFloatAverage
• x86 is faster than x64 for floatWithIDAverage

Conclusion

Although I can't explain why the x86 version is so much faster than the x64 version for floatWithIDAverage, I have shown a way of speeding it up significantly.