Array.Sort() 对 class 个实例而不是浮点数进行排序时性能下降
Array.Sort() performance drop when sorting class instances instead of floats
如果对浮点数进行排序，C# 中的 Array.Sort 真的很快，我需要一些额外的数据来处理这些浮点数，所以我制作了一个简单的 class 并扩展了 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：我已经根据下面的一些建议更新了我的代码，使其成为一个结构，要么对我的电脑没有影响，要么我做错了一些可怕的事情。我还添加了一些完整性检查。
新的演示输出（不要让 "atleast once" 骗了你，它用词不当）：
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 在调试模式下更快，在发布模式下与 struct 方法差不多快。
新的演示输出（发布）：
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.
有两种小方法可以加快速度：
- 使用结构而不是 class。
- 手动编码 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 更快
结论
虽然我无法解释为什么 x86 版本比 floatWithIDAverage 的 x64 版本快得多，但我已经展示了一种显着加快速度的方法。
我将通过添加另一种优化方法来补充其他答案。使用结构当然是必不可少的。它删除了很多指针跟随，并使 JIT 只为此结构生成专门的泛型代码。
遗憾的是，JIT 有时无法完全消除所有泛型开销，即使您使用结构也是如此。出于这个原因，分叉 .NET Array.Sort 代码并对数组项类型进行硬编码可能是有益的。这是一件残酷的事情。只有当您的性能要求很高时才值得。我已经这样做了一次并且得到了回报。
Array.Sort 真的很快，我需要一些额外的数据来处理这些浮点数，所以我制作了一个简单的 class 并扩展了 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：我已经根据下面的一些建议更新了我的代码，使其成为一个结构，要么对我的电脑没有影响，要么我做错了一些可怕的事情。我还添加了一些完整性检查。
新的演示输出（不要让 "atleast once" 骗了你，它用词不当）：
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 在调试模式下更快，在发布模式下与 struct 方法差不多快。
新的演示输出（发布）：
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.
有两种小方法可以加快速度：
- 使用结构而不是 class。
- 手动编码 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 更快
结论
虽然我无法解释为什么 x86 版本比 floatWithIDAverage 的 x64 版本快得多，但我已经展示了一种显着加快速度的方法。
我将通过添加另一种优化方法来补充其他答案。使用结构当然是必不可少的。它删除了很多指针跟随，并使 JIT 只为此结构生成专门的泛型代码。
遗憾的是，JIT 有时无法完全消除所有泛型开销，即使您使用结构也是如此。出于这个原因，分叉 .NET Array.Sort 代码并对数组项类型进行硬编码可能是有益的。这是一件残酷的事情。只有当您的性能要求很高时才值得。我已经这样做了一次并且得到了回报。