c# - 不同优化的无法解释的时间

Question

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

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

初始化 Func<>委托(delegate)引用所需的算法。从主循环中调用此委托(delegate)。

循环数据并从主循环中调用适当的算法。

为每个算法调用实现主循环本身的单独方法。

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

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

在这个测试代码中， DataReductionAlgorithm只是一个定义各种算法的枚举。除了模拟真实代码中会发生的事情之外，它并没有真正被使用。

这是我对方法(1)的测试实现。非常简单:分配 Func<> a到要调用的算法，然后从循环中调用它:

private static void test1(int[] data, DataReductionAlgorithm algorithm)
{
    Func<int[], int, int, int> 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() 相同的新测试。除了在 switch case 中循环，我调用一个方法来执行完全相同的循环。

因此，我预计这将花费几乎与 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<int[], int, int, int> 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() 比我想象的要快(可能表明调用委托(delegate)是高度优化的)。

这是 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 < data.Length; ++i)
                if (data[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、没有调试器上重现该问题。

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

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

不必如此。 Hotspot JVM performs dynamic range check elimination . .NET JIT 并不复杂，无法做到这一点。
test3内联:


test2计算未内联:



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

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