Пример кода, который показывает приведение к uint, более эффективен, чем проверка диапазона

Question

Поэтому я смотрю на этот вопрос, и общее согласие заключается в том, что версия Uint Cast более эффективна, чем проверка диапазона с 0. Поскольку код также находится в реализации List для MS, я предполагаю, что это реальная оптимизация. Однако мне не удалось создать пример кода, который приведет к лучшей производительности для версии 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

Я бы предложил попробовать код, который не выдает исключение, когда index вне диапазона. Исключения невероятно дороги и могут полностью отбросить ваши результаты.

Приведенный ниже код выполняет среднесрочную оценку для 1000 итераций с 1 000 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 (PDF), в котором перечислены стоимость инструкций. Найдите свой процессор в списке, затем найдите инструкцию CMP.

Для моего, Haswell, CMP принимает 1 цикл задержки и 0,25 цикла пропускной способности.

Подобная дробная стоимость могла бы использовать объяснение: у Haswell есть 4 целочисленных исполнительных блока, которые могут выполнять инструкции одновременно. Когда программа содержит достаточно целочисленных операций, таких как CMP, без взаимозависимости, все они могут выполняться одновременно. По сути делает программу в 4 раза быстрее. Не всегда удается сохранить все 4 одновременно занятыми вашим кодом, на самом деле это довольно редко. Но вы держите 2 из них заняты в этом случае. Или, другими словами, два сравнения занимают столько же времени, сколько один, 1 цикл.

Существуют и другие факторы, которые делают время выполнения идентичным. Помогает то, что процессор может очень хорошо прогнозировать ветвь, он может спекулятивно выполнять x > MaxSize несмотря на оценку короткого замыкания. И на самом деле это в конечном итоге будет использовать результат, так как ветвь никогда не берется.

И настоящим узким местом в этом коде является индексация массива, доступ к памяти - одна из самых медленных возможностей процессора. Таким образом, "быстрая" версия кода не является быстрой, даже если она предоставляет больше возможностей, чтобы процессор мог одновременно выполнять инструкции. В любом случае, сегодня такая возможность невелика, у процессора слишком много исполнительных блоков, чтобы занять его. В противном случае функция, которая делает HyperThreading работать. В обоих случаях процессор останавливается с одинаковой скоростью.

На моей машине я должен написать код, который занимает более 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.

(И нет, это не значит, что я думаю, что все методы должны быть написаны таким образом, но, безусловно, могут быть различия в производительности, когда это происходит).