Эффективнее ли выполнять проверку диапазона путем литья в uint вместо проверки отрицательных значений?

Question

я наткнулся на этот кусок кода в List source code .NET в:

// Following trick can reduce the range check by one 
if ((uint) index >= (uint)_size) { 
    ThrowHelper.ThrowArgumentOutOfRangeException(); 
} 

Видимо, это более эффективно, чем if (index < 0 || index >= _size)

Я любопытный об основаниях трюка (?). Является ли одна инструкция филиала действительно более дорогой, чем две конверсии, до uint? Или существует какая-то другая оптимизация, которая сделает этот код быстрее, чем дополнительное числовое сравнение?

Для решения слона в комнате: да, это микро оптимизация, нет, я не собираюсь использовать это везде в моем коде - я просто любопытно;)

Answer 1

С MS Partition I, раздел 12.1 (Поддерживаемые типы данных):

подписанные целые типы (int8, int16, int32, int64, и родной INT) и их соответствующие неподписанные целочисленных типов (без знака iNT8 без знака Int16, без знака Int32, без знака Int64, и native unsigned int) отличаются только тем, как биты в teger интерпретируются. Для тех операций, в которых целое число без знака обрабатывается иначе, чем целое число со знаком (например, в сравнении или арифметика с переполнением), существуют отдельные инструкции для обработки целого числа без знака (например, cgt.un и add.ovf.un) ,

То есть, преобразование из int в uint является лишь вопросом бухгалтерского учета - с этого момента, значение в стеке/в регистре теперь известен как беззнаковое целочисленное значение, а чем int.

Таким образом, два преобразования должны быть «свободными» после того, как код JITted, а затем можно выполнить операцию сравнения без знака.

Answer 2

Предполагая, что _size является целым числом, закрытым для списка, и index является аргументом в пользу этой функции, срок действия которой должен быть проверен.

Предполагая далее, что _size всегда> = 0.

Тогда оригинальный тест был бы:

if(index < 0 || index > size) throw exception 

версия оптимизировано

if((uint)index > (uint)_size) throw exception 

имеет одно сравнение (как opsed to two int he бывший пример.) Поскольку приведение просто переинтерпретирует бит и делает > на самом деле беззнаковое сравнение, для него не используются дополнительные циклы ЦП.

Почему это работает?

Результаты просты/тривиальны до тех пор, пока индекс> = 0.

Если индекс будет превратить его в очень большом числе:

Пример: 0xFFFF равно -1, как Int, но 65535, как UINT, таким образом,

(uint)-1 > (uint)x 

всегда верно, если x была положительной.

Answer 3

Обратите внимание, что этот трюк не будет работать, если ваш проект checked вместо unchecked. В лучшем случае он будет медленнее (потому что каждый бросок должен быть проверен против переполнения) (или, по крайней мере, не быстрее), в худшем случае вы получите OverflowException, если попытаетесь передать -1 как index (вместо вашего исключения) ,

Если вы хотите, чтобы написать это «правильно» и более «безусловно, работать» путь, вы должны поставить

unchecked 
{ 
    // test 
} 

все вокруг теста.

Answer 4

Допустим, мы имеем:

public void TestIndex1(int index) 
{ 
    if(index < 0 || index >= _size) 
    ThrowHelper.ThrowArgumentOutOfRangeException(); 
} 
public void TestIndex2(int index) 
{ 
    if((uint)index >= (uint)_size) 
    ThrowHelper.ThrowArgumentOutOfRangeException(); 
} 

Давайте компилировать их и посмотреть на ILSpy:

.method public hidebysig 
    instance void TestIndex1 (
     int32 index 
    ) cil managed 
{ 
    IL_0000: ldarg.1 
    IL_0001: ldc.i4.0 
    IL_0002: blt.s IL_000d 
    IL_0004: ldarg.1 
    IL_0005: ldarg.0 
    IL_0006: ldfld int32 TempTest.TestClass::_size 
    IL_000b: bge.s IL_0012 
    IL_000d: call void TempTest.ThrowHelper::ThrowArgumentOutOfRangeException() 
    IL_0012: ret 
} 

.method public hidebysig 
    instance void TestIndex2 (
     int32 index 
    ) cil managed 
{ 
    IL_0000: ldarg.1 
    IL_0001: ldarg.0 
    IL_0002: ldfld int32 TempTest.TestClass::_size 
    IL_0007: blt.un.s IL_000e 
    IL_0009: call void TempTest.ThrowHelper::ThrowArgumentOutOfRangeException() 
    IL_000e: ret 
} 

Легко видеть, что второй имеет меньше кода, с одной меньше отрасли.

Действительно, нет броска на все, что есть выбор, следует ли использовать blt.s и bge.s или использовать blt.s.un, где последний обрабатывает целые числа, переданные в качестве знака в то время как бывшие трактует их как знаковые.

(Примечание для тех, кто не знаком с КСС, так как это C# вопрос с КСС ответ, bge.s, blt.s и blt.s.un являются «короткие» версии bge, blt и blt.un соответственно. blt выскакивает два значения из стека и ветви, если первая меньше второй, рассматривая их как подписанные значения, тогда как blt.un извлекает два значения стека и ветвей, если первое меньше второго, рассматривая их как значения без знака).

Это совершенно микроопт, но есть моменты, когда стоит делать микроопт. Рассмотрим далее, что с остальной частью кода в теле метода это может означать разницу между тем, что попадает внутрь пределов колебаний для вложения или нет, и если они беспокоятся о том, чтобы иметь помощника для исключения исключений из диапазона, они вероятно, попытка обеспечить inlining происходит, если это вообще возможно, и дополнительные 4 байта могут иметь значение.

Действительно, вполне вероятно, что разница в разветвлении будет гораздо более сложной, чем сокращение одной ветви. Не так много раз, когда вы идете на своем пути, чтобы обеспечить, что инлайнкация происходит, стоит того, но основным методом такого интенсивного использования, как List<T>, несомненно, будет один из них.

Answer 5

Да, это более эффективно. JIT делает тот же трюк, когда контролирует диапазон доступа к массиву.

Преобразование и рассуждение следующим образом:

i >= 0 && i < array.Length становится (uint)i < (uint)array.Length, потому что array.Length <= int.MaxValue так, что array.Length имеет такое же значение, как (uint)array.Length. Если i оказывается отрицательным, тогда (uint)i > int.MaxValue и проверка не выполняется.

Answer 6

Видимо, в реальной жизни это происходит не быстрее. Проверьте это: https://dotnetfiddle.net/lZKHmn

Оказывается, что благодаря предсказания ветвлений Intel и параллельного выполнения более очевидным и читаемый код на самом деле работает быстрее ...

Вот код:

using System; 
using System.Diagnostics; 

public class Program 
{ 


    const int MAX_ITERATIONS = 10000000; 
    const int MAX_SIZE = 1000; 


    public static void Main() 
    { 

      var timer = new Stopwatch(); 


      Random rand = new Random(); 
      long InRange = 0; 
      long OutOfRange = 0; 

      timer.Start(); 
      for (int i = 0; i < MAX_ITERATIONS; i++) { 
       var x = rand.Next(MAX_SIZE * 2) - MAX_SIZE; 
       if (x < 0 || x > MAX_SIZE) { 
        OutOfRange++; 
       } else { 
        InRange++; 
       } 
      } 
      timer.Stop(); 

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


      rand = new Random(); 
      InRange = 0; 
      OutOfRange = 0; 

      timer.Reset(); 
      timer.Start(); 
      for (int i = 0; i < MAX_ITERATIONS; i++) { 
       var x = rand.Next(MAX_SIZE * 2) - MAX_SIZE; 
       if ((uint) x > (uint) MAX_SIZE) { 
        OutOfRange++; 
       } else { 
        InRange++; 
       } 
      } 
      timer.Stop(); 

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

    } 
} 

Answer 7

Изучая это на процессоре Intel, я не обнаружил различий во времени выполнения, возможно, из-за множества целых исполнительных блоков.

Но при выполнении этого на микропроцессоре 16MHZ в реальном времени с отсутствием предсказания ветвления и целых блоков исполнения были заметные различия.

1 миллион итераций медленному кода взял 1761 мс

int slower(char *a, long i) 
{ 
    if (i < 0 || i >= 10) 
    return 0; 

    return a[i]; 
} 

1 миллион итераций быстрее код взял 1635 мс

int faster(char *a, long i) 
{ 
    if ((unsigned int)i >= 10) 
    return 0; 
    return a[i]; 
}