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

Question

所以我正在研究这个问题,普遍的共识是uint cast版本比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检查执行得更快,比如将比较变量移动到类的字段中,生成随机索引访问等等但是在每种情况下结果似乎都是相同的两个版本.那么这种变化是否适用于现代x86处理器,有人能以某种方式展示它吗？

请注意,我不是要求某人修复我的样本或解释它有什么问题.我只是想看看优化确实有效的情况.

Answer 1

       if (x < 0 || x > MaxSize)

比较由CMP处理器指令(比较)执行.您将要查看Agner Fog的指令表文档(PDF),它列出了指令的成本.在列表中找回您的处理器,然后找到CMP指令.

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

像这样的小数成本可以使用解释,Haswell有4个整数执行单元,可以同时执行指令.当程序包含足够的整数运算(如CMP)而没有相互依赖性时,它们都可以同时执行.实际上使程序加快了4倍.你并不总是设法让所有4个人同时忙于你的代码,这实际上是非常罕见的.但在这种情况下,你确实让其中2人忙碌.换句话说,两次比较只需要一次,一次循环.

还有其他因素可以使执行时间相同.一个有用的是处理器可以很好地预测分支,它可以推测性地执行x > MaxSize,尽管短路评估.事实上它最终会使用结果,因为从不采用分支.

这段代码的真正瓶颈是数组索引,访问内存是处理器可以做的最慢的事情之一.所以代码的"快速"版本并不快,即使它提供了更多机会允许处理器同时执行指令.无论如何,今天的机会并不多,处理器有太多的执行单元来保持忙碌.否则,使HyperThreading工作的功能.在这两种情况下,处理器都以相同的速率陷入困境.

在我的机器,我必须编写代码占据更多比4升的发动机,使其更慢.愚蠢的代码是这样的:

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

使用5比较,现在我可以有所不同,61对47毫秒.或者换句话说,这是一种计算处理器中整数引擎数量的方法.呵呵 :)

所以这是一个微观优化,可能用于十年前的回报.它不再了.从你担心的事情列表中删除它:)

Answer 2

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