不同优化的不可解释的时间安排

我正在编写一些代码，必须根据设置将不同的算法应用于大型数据集。 数据集很大，现实世界的时间表明我们需要尽可能地优化它。

所选算法必须在来自大型arrays的许多数据子集上运行。 因此，我决定尝试几种不同的方法：

1. 初始化Func委托以引用所需的算法。 从主循环中调用此委托。
2. 循环数据并从主循环内调用适当的算法。
3. 调用一个单独的方法，为每个算法实现主循环。

在我的测试中，我让每种方法都调用相同的底层方法calculate() 。 （当然，真实代码为每个算法调用不同的方法，但在这里我测试调用算法的最快方法，而不是算法本身。）

每个测试都在ITERS循环中调用所需的算法。

在此测试代码中， DataReductionAlgorithm只是一个定义各种算法的枚举。 除了模拟实际代码中会发生什么之外，它并不是真正使用的。

这是我的方法（1）的测试实现。 它非常简单：将Func a分配给要调用的算法，然后从循环中调用它：

 private static void test1(int[] data, DataReductionAlgorithm algorithm) { Func a; switch (algorithm) { case DataReductionAlgorithm.Max: a = calculate; break; case DataReductionAlgorithm.Mean: a = calculate; break; default: a = calculate; break; } for (int i = 0; i < ITERS; ++i) a(data, 0, data.Length); } 

这是方法（2）的测试实现。 它在循环外移动if算法选择算法。 我期待这是最快的方法：

 private static void test2(int[] data, DataReductionAlgorithm algorithm) { switch (algorithm) { case DataReductionAlgorithm.Max: for (int i = 0; i < ITERS; ++i) calculate(data, 0, data.Length); break; case DataReductionAlgorithm.Mean: for (int i = 0; i < ITERS; ++i) calculate(data, 0, data.Length); break; default: for (int i = 0; i < ITERS; ++i) calculate(data, 0, data.Length); break; } } 

这是测试方法的代码（3）。 如果在循环内移动if算法选择算法。 我希望这个方法比较慢（2），因为if测试将在ITERS时间执行，而不是仅执行一次：

 private static void test3(int[] data, DataReductionAlgorithm algorithm) { for (int i = 0; i < ITERS; ++i) { switch (algorithm) { case DataReductionAlgorithm.Max: calculate(data, 0, data.Length); break; case DataReductionAlgorithm.Mean: calculate(data, 0, data.Length); break; default: calculate(data, 0, data.Length); break; } } } 

由于我得到了奇怪的计时结果，我添加了一个新的测试，它与test2()几乎完全相同，只是在切换情况下不是循环，而是调用一个方法来完成相同的循环。

因此，我希望这与test2()几乎相同：

 private static void test4(int[] data, DataReductionAlgorithm algorithm) { switch (algorithm) { case DataReductionAlgorithm.Max: iterate(ITERS, data); break; case DataReductionAlgorithm.Mean: iterate(ITERS, data); break; default: iterate(ITERS, data); break; } } private static void iterate(int n, int[] data) { for (int i = 0; i < n; ++i) calculate(data, 0, data.Length); } 

这是整个程序，以防有人想自己尝试：

 using System; using System.Diagnostics; using System.Linq; namespace Demo { public enum DataReductionAlgorithm { Single, Max, Mean } internal class Program { private const int ITERS = 100000; private void run() { int[] data = Enumerable.Range(0, 10000).ToArray(); Stopwatch sw = new Stopwatch(); for (int trial = 0; trial < 4; ++trial) { sw.Restart(); test1(data, DataReductionAlgorithm.Mean); Console.WriteLine("test1: " + sw.Elapsed); sw.Restart(); test2(data, DataReductionAlgorithm.Mean); Console.WriteLine("test2: " + sw.Elapsed); sw.Restart(); test3(data, DataReductionAlgorithm.Mean); Console.WriteLine("test3: " + sw.Elapsed); sw.Restart(); test4(data, DataReductionAlgorithm.Mean); Console.WriteLine("test4: " + sw.Elapsed); Console.WriteLine(); } } private static void test1(int[] data, DataReductionAlgorithm algorithm) { Func a; switch (algorithm) { case DataReductionAlgorithm.Max: a = calculate; break; case DataReductionAlgorithm.Mean: a = calculate; break; default: a = calculate; break; } for (int i = 0; i < ITERS; ++i) a(data, 0, data.Length); } private static void test2(int[] data, DataReductionAlgorithm algorithm) { switch (algorithm) { case DataReductionAlgorithm.Max: for (int i = 0; i < ITERS; ++i) calculate(data, 0, data.Length); break; case DataReductionAlgorithm.Mean: for (int i = 0; i < ITERS; ++i) calculate(data, 0, data.Length); break; default: for (int i = 0; i < ITERS; ++i) calculate(data, 0, data.Length); break; } } private static void test3(int[] data, DataReductionAlgorithm algorithm) { for (int i = 0; i < ITERS; ++i) { switch (algorithm) { case DataReductionAlgorithm.Max: calculate(data, 0, data.Length); break; case DataReductionAlgorithm.Mean: calculate(data, 0, data.Length); break; default: calculate(data, 0, data.Length); break; } } } private static void test4(int[] data, DataReductionAlgorithm algorithm) { switch (algorithm) { case DataReductionAlgorithm.Max: iterate(ITERS, data); break; case DataReductionAlgorithm.Mean: iterate(ITERS, data); break; default: iterate(ITERS, data); break; } } private static void iterate(int n, int[] data) { for (int i = 0; i < n; ++i) calculate(data, 0, data.Length); } private static int calculate(int[] data, int i1, int i2) { // Just a dummy implementation. // Using the same algorithm for each approach to avoid differences in timings. int result = 0; for (int i = i1; i < i2; ++i) result += data[i]; return result; } private static void Main() { new Program().run(); } } } 

---

结果

首先，请注意这些结果来自调试器外部的RELEASE BUILD运行。 运行调试版本 – 或从调试器运行版本构建 – 将产生误导性结果。

我正在使用四核英特尔处理器在Windows 8.1上测试带有.Net 4.51的版本。 （但是，我在.Net 4.5和.Net 4中获得了类似的结果。）

我得到了不同的结果，取决于它是x64 / AnyCPU还是x86。

回顾一下：我期望test1（）和test3（）是最慢的，test2（）是最快的，test4（）与test2（）的速度几乎相同。

这是x86的结果：

 test1: 00:00:00.5892166 test2: 00:00:00.5848795 test3: 00:00:00.5866006 test4: 00:00:00.5867143 

这是我所期望的，除了test1（）比我认为的更快（可能表明调用委托是高度优化的）。

这是x64的结果：

 test1: 00:00:00.8769743 test2: 00:00:00.8750667 test3: 00:00:00.5839475 test4: 00:00:00.5853400 

哇！

test1()和test2()发生了什么？ 我无法解释。 test2()如何比test3()慢得多？

为什么test4()与test2()几乎没有相同的速度？

为什么x86和x64之间存在巨大差异？

任何人都可以对此有所了解吗？ 速度的差异并不是微不足道的 – 它可能会使得需要花费10秒钟和花费15秒的东西之间的差异。

---

附录

我接受了下面的答案。

但是，为了说明下面@usr提到的JIT优化的脆弱性，请考虑以下代码：

 using System; using System.Diagnostics; namespace Demo { internal class Program { private const int ITERS = 10000; private void run() { Stopwatch sw = new Stopwatch(); int[] data = new int[10000]; for (int trial = 0; trial < 4; ++trial) { sw.Restart(); test1(data, 0); var elapsed1 = sw.Elapsed; sw.Restart(); test2(data, 0); var elapsed2 = sw.Elapsed; Console.WriteLine("Ratio = " + elapsed1.TotalMilliseconds / elapsed2.TotalMilliseconds); } Console.ReadLine(); } private static void test1(int[] data, int x) { switch (x) { case 0: { for (int i = 0; i < ITERS; ++i) dummy(data); break; } } } private static void test2(int[] data, int x) { switch (x) { case 0: { loop(data); break; } } } private static int dummy(int[] data) { int max = 0; // Also try with "int i = 1" in the loop below. for (int i = 0; i  max) max = data[i]; return max; } private static void loop(int[] data) { for (int i = 0; i < ITERS; ++i) dummy(data); } private static void Main() { new Program().run(); } } } 

注意注释下面的代码行// Also try with "int i = 1" in the loop below. 。

在i = 0 ，我获得了x64版本的以下结果：

 Ratio = 1.52235829774506 Ratio = 1.50636405328076 Ratio = 1.52291602053827 Ratio = 1.52803278744701 

仅将其更改为i = 1 ，我得到以下结果：

 Ratio = 1.16920209593233 Ratio = 0.990370350435142 Ratio = 0.991150637472754 Ratio = 0.999941245001628 

有趣！ 🙂

Answer 1

我可以在x64，.NET 4.5，Release，no Debugger上重现这个问题。

我已经查看了为test2和test3生成的x64。 热内循环消耗99％的时间。 只有这个循环很重要。

对于test3 ， calculate是内联的，循环边界等于数组边界。 这允许JIT消除范围检查。 在test2 ，无法消除范围检查，因为循环边界是动态的。 它们由int i1, int i2给出int i1, int i2它们在静态上不是有效的数组边界。 只有内联才能在当前的JIT中提供该信息。 内联将这些值替换为0, data.Length 。

这不一定是这样。 Hotspot JVM执行动态范围检查消除 。 .NET JIT并不复杂。

带有内联的test3 ：

test2 with calculate not inlined：

两个分支而不是一个。 一个是循环测试，一个是范围检查。

我不知道为什么JIT在这里有所不同。 内联是由启发式驱动的。