Является ли более эффективным выполнение проверки диапазона путем приведения к uint вместо проверки на отрицательные значения?
Я наткнулся на этот кусок кода в исходном коде списка.NET:
// Following trick can reduce the range check by one
if ((uint) index >= (uint)_size) {
ThrowHelper.ThrowArgumentOutOfRangeException();
}
Видимо, это более эффективно (?), Чем if (index < 0 || index >= _size)
Мне любопытно обоснование уловки. Является ли инструкция с одной ветвью действительно более дорогой, чем два преобразования в uint? Или происходит какая-то другая оптимизация, которая сделает этот код быстрее, чем дополнительное числовое сравнение?
Чтобы обратиться к слону в комнате: да, это микрооптимизация, нет, я не собираюсь использовать это везде в своем коде - мне просто любопытно;)
7 ответов
Из MS Partition I, раздел 12.1 (Поддерживаемые типы данных):
Целочисленные типы со знаком (int8, int16, int32, int64 и native int) и соответствующие им целочисленные типы без знака (unsigned int8, unsigned int16, unsigned int32, unsigned int64 и native unsigned int) отличаются только тем, как биты целого числа интерпретируются. Для тех операций, в которых целое число без знака обрабатывается иначе, чем целое число со знаком (например, в сравнениях или арифметике с переполнением), существуют отдельные инструкции для обработки целого числа как без знака (например, cgt.un и add.ovf.un).
То есть преобразование из int к uint это просто вопрос бухгалтерского учета - теперь известно, что значение в стеке / в регистре - это целое число без знака, а не целое число.
Таким образом, оба преобразования должны быть "свободными" после того, как код будет JITted, и тогда может быть выполнена операция сравнения без знака.
Допустим, у нас есть:
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где последний обрабатывает целые числа, переданные как беззнаковые, тогда как первый обрабатывает их как подписанные.
(Примечание для тех, кто не знаком с CIL, так как это вопрос C# с ответом CIL, bge.s, blt.s а также blt.s.un являются "короткими" версиями bge, blt а также blt.un соответственно. blt выталкивает два значения из стека и разветвляет, если первое меньше второго, рассматривая их как знаковые значения, в то время как blt.un выскакивает два значения стека и ветвей, если первое меньше второго, рассматривая их как значения без знака).
Это совершенно микроопция, но бывают моменты, когда микроопция стоит делать. Далее рассмотрим, что с остальной частью кода в теле метода это может означать разницу между чем-то, попадающим в пределы дрожания для встраивания или нет, и если им надоело иметь помощника для выброса исключений из диапазона, они вероятно, попытка гарантировать, что встраивание произойдет, если это вообще возможно, и дополнительные 4 байта могут иметь все значение.
Действительно, вполне вероятно, что эта внутренняя разница будет гораздо более значимой, чем сокращение одной ветви. Не так уж много раз, когда стоит попытаться добиться того, чтобы встраивание произошло, стоит того, но основной метод класса такого интенсивного использования, как List<T> конечно был бы одним из них.
Обратите внимание, что этот трюк не сработает, если ваш проект checked вместо unchecked, В лучшем случае это будет медленнее (потому что каждый бросок должен быть проверен на переполнение) (или, по крайней мере, не быстрее), в худшем случае вы получите OverflowException если вы попытаетесь передать -1 в качестве index (вместо вашего исключения).
Если вы хотите написать это "правильно" и более "наверняка будет работать", вы должны поставить
unchecked
{
// test
}
все вокруг теста.
Если предположить, _sizeявляется целым числом, приватным для списка и index является аргументом этой функции, правильность которой нужно проверить.
Предполагая далее, что _size всегда>= 0.
Тогда оригинальный тест был бы:
if(index < 0 || index > size) throw exception
Оптимизированная версия
if((uint)index > (uint)_size) throw exception
имеет одно сравнение (как в двух предыдущих примерах). Потому что приведение просто интерпретирует биты и делает >фактически сравнение без знака, дополнительные циклы ЦП для него не используются.
Почему это работает?
Результаты просты / тривиальны, пока индекс>= 0.
Если индекс < 0, (uint)index превратит это в очень большое число:
Пример: 0xFFFF равно -1 как int, но 65535 как uint, таким образом
(uint)-1 > (uint)x
всегда верно, если x был положительным.
Да, это более эффективно. 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 и проверка не проходит.
Видимо в реальной жизни это не быстрее. Проверьте это: 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" );
}
}
Исследуя это на процессоре Intel, я не обнаружил различий во времени выполнения, возможно, из-за нескольких целочисленных исполнительных блоков.
Но при этом на микропроцессоре реального времени 16 МГц без предсказания ветвлений и целочисленных исполнительных блоков были заметные различия.
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];
}