显示转换为 uint 的代码示例比范围检查更有效

Question

所以我正在查看，普遍的共识是 uint 转换版本比使用 0 进行范围检查更有效。由于代码也在 MS 的 List 实现中，我认为这是一个真正的优化.但是，我未能生成可以为 uint 版本带来更好性能的代码示例。我尝试了不同的测试，但缺少某些东西，或者我的代码的其他部分使检查时间相形见绌。我最后一次尝试是这样的：

class TestType
{
    public TestType(int size)
    {
        MaxSize = size;
        Random rand = new Random(100);
        for (int i = 0; i < MaxIterations; i++)
        {
            indexes[i] = rand.Next(0, MaxSize);
        }
    }

    public const int MaxIterations = 10000000;
    private int MaxSize;
    private int[] indexes = new int[MaxIterations];

    public void Test()
    {
        var timer = new Stopwatch();

        int inRange = 0;
        int outOfRange = 0;

        timer.Start();
        for (int i = 0; i < MaxIterations; i++)
        {
            int x = indexes[i];
            if (x < 0 || x > MaxSize)
            {
                throw new Exception();

            }

            inRange += indexes[x];
        }
        timer.Stop();

        Console.WriteLine("Comparision 1: " + inRange + "/" + outOfRange + ", elapsed: " + timer.ElapsedMilliseconds + "ms");

        inRange = 0;
        outOfRange = 0;

        timer.Reset();
        timer.Start();

        for (int i = 0; i < MaxIterations; i++)
        {
            int x = indexes[i];
            if ((uint)x > (uint)MaxSize)
            {
                throw new Exception();
            }

            inRange += indexes[x];
        }

        timer.Stop();

        Console.WriteLine("Comparision 2: " + inRange + "/" + outOfRange + ", elapsed: " + timer.ElapsedMilliseconds + "ms");

    }
}

class Program
{
    static void Main()
    {
        TestType t = new TestType(TestType.MaxIterations);
        t.Test();
        TestType t2 = new TestType(TestType.MaxIterations);
        t2.Test();
        TestType t3 = new TestType(TestType.MaxIterations);
        t3.Test();
    }
}

代码有点乱，因为我尝试了很多方法来使 uint 检查执行得更快，比如将比较变量移动到 class 的字段中，生成随机索引访问等等，但在每个如果两个版本的结果似乎相同。那么此更改是否适用于现代 x86 处理器并且有人可以以某种方式演示它吗？

请注意，我并不是要找人修理我的样品或解释它有什么问题。我只是想看看优化确实起作用的情况。

Answer 1

我建议尝试在 index 超出范围时不抛出异常的代码。例外情况非常昂贵，可能会完全影响您的替补结果。

下面的代码对 1,000,000 个结果的 1,000 次迭代执行时间平均基准。

using System;
using System.Diagnostics;

namespace BenchTest
{
    class Program
    {
        const int LoopCount = 1000000;
        const int AverageCount = 1000;

        static void Main(string[] args)
        {
            Console.WriteLine("Starting Benchmark");
            RunTest();
            Console.WriteLine("Finished Benchmark");

            Console.Write("Press any key to exit...");
            Console.ReadKey();
        }

        static void RunTest()
        {
            int cursorRow = Console.CursorTop; int cursorCol = Console.CursorLeft;

            long totalTime1 = 0; long totalTime2 = 0;
            long invalidOperationCount1 = 0; long invalidOperationCount2 = 0;

            for (int i = 0; i < AverageCount; i++)
            {
                Console.SetCursorPosition(cursorCol, cursorRow);
                Console.WriteLine("Running iteration: {0}/{1}", i + 1, AverageCount);

                int[] indexArgs = RandomFill(LoopCount, int.MinValue, int.MaxValue);
                int[] sizeArgs = RandomFill(LoopCount, 0, int.MaxValue);

                totalTime1 += RunLoop(TestMethod1, indexArgs, sizeArgs, ref invalidOperationCount1);
                totalTime2 += RunLoop(TestMethod2, indexArgs, sizeArgs, ref invalidOperationCount2);
            }

            PrintResult("Test 1", TimeSpan.FromTicks(totalTime1 / AverageCount), invalidOperationCount1);
            PrintResult("Test 2", TimeSpan.FromTicks(totalTime2 / AverageCount), invalidOperationCount2);
        }

        static void PrintResult(string testName, TimeSpan averageTime, long invalidOperationCount)
        {
            Console.WriteLine(testName);
            Console.WriteLine("    Average Time: {0}", averageTime);
            Console.WriteLine("    Invalid Operations: {0} ({1})", invalidOperationCount, (invalidOperationCount / (double)(AverageCount * LoopCount)).ToString("P3"));
        }

        static long RunLoop(Func<int, int, int> testMethod, int[] indexArgs, int[] sizeArgs, ref long invalidOperationCount)
        {
            Stopwatch sw = new Stopwatch();

            Console.Write("Running {0} sub-iterations", LoopCount);
            sw.Start();
            long startTickCount = sw.ElapsedTicks;

            for (int i = 0; i < LoopCount; i++)
            {
                invalidOperationCount += testMethod(indexArgs[i], sizeArgs[i]);
            }

            sw.Stop();
            long stopTickCount = sw.ElapsedTicks;

            long elapsedTickCount = stopTickCount - startTickCount;
            Console.WriteLine(" - Time Taken: {0}", new TimeSpan(elapsedTickCount));
            return elapsedTickCount;
        }

        static int[] RandomFill(int size, int minValue, int maxValue)
        {
            int[] randomArray = new int[size];

            Random rng = new Random();

            for (int i = 0; i < size; i++)
            {
                randomArray[i] = rng.Next(minValue, maxValue);
            }

            return randomArray;
        }

        static int TestMethod1(int index, int size)
        {
            return (index < 0 || index >= size) ? 1 : 0;
        }

        static int TestMethod2(int index, int size)
        {
            return ((uint)(index) >= (uint)(size)) ? 1 : 0;
        }
    }
}

Answer 2

       if (x < 0 || x > MaxSize)

比较是由CMP处理器指令（Compare）进行的。您需要查看 Agner Fog's instruction tables document (PDF)，其中列出了说明的费用。在列表中找到您的处理器，然后找到 CMP 指令。

对于我的 Haswell，CMP 需要 1 个延迟周期和 0.25 个吞吐量周期。

这样的分数成本可以用解释，Haswell有4个整数执行单元，可以同时执行指令。当一个程序包含足够多的整数操作时，如 CMP，没有相互依赖性，那么它们可以同时执行。实际上使程序快 4 倍。你并不总是设法让所有 4 个同时忙于你的代码，这实际上是非常罕见的。但是在这种情况下，您确实让其中的 2 个忙。或者换句话说，两次比较和一次比较一样长，1 个周期。

还有其他因素导致执行时间相同。有一点帮助是处理器可以很好地预测分支，尽管有短路评估，它仍可以推测性地执行 x > MaxSize。它实际上最终会使用结果，因为分支从未被采用。

这段代码的真正瓶颈是数组索引，访问内存是处理器可以做的最慢的事情之一。因此，"fast" 版本的代码并没有更快，尽管它提供了更多允许处理器并发执行指令的机会。无论如何，今天这不是什么好机会，处理器有太多的执行单元而无法保持忙碌。否则，使超线程工作的功能。在这两种情况下，处理器都以相同的速度停滞不前。

在我的机器上，我必须编写比 4 个引擎占用更多的代码以使其变慢。像这样的愚蠢代码：

     if (x < 0 || x > MaxSize || x > 10000000 || x > 20000000 || x > 3000000) {
         outOfRange++; 
     }
     else {
         inRange++;
     }

使用 5 次比较，现在我可以区分 61 与 47 毫秒。或者换句话说，这是一种计算处理器中整数引擎数量的方法。呵呵:)

因此，这是一个 微优化，十年前可能曾获得回报。现在没有了。把它从你要担心的事情清单上划掉:)

Answer 3

你不是在比较同类。

你说的代码不仅通过优化节省了一个分支，而且在一个小方法中还节省了4个字节的CIL。

在一个小方法中，4 个字节可能是内联和未内联的区别。

如果调用该方法的方法也被编写得很小，那么这可能意味着两个（或更多）方法调用被合并为一段内联代码。

然后可能其中一些是，因为它是内联的并且可用于抖动分析，再次进一步优化。

真正的区别不在index < 0 || index >= _size和(uint)index >= (uint)_size之间，而是反复努力最小化方法体大小的代码和没有这样做的代码之间。例如，查看如何使用另一种方法在必要时抛出异常，进一步削减 CIL 的几个字节。

（不，这并不是说我认为所有的方法都应该这样写，但是当一个人这样做时肯定会有性能差异）。

显示转换为 uint 的代码示例比范围检查更有效

Code sample that shows casting to uint is more efficient than range check

c#

clr

jit