通过强制转换为 uint 而不是检查负值来执行范围检查是否更有效？

Question

中偶然发现了这段代码

// 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 节（支持的数据类型）：

The signed integer types (int8, int16, int32, int64, and native int) and their corresponding unsigned integer types (unsigned int8, unsigned int16, unsigned int32, unsigned int64, and native unsigned int) differ only in how the bits of the integer are interpreted. For those operations in which an unsigned integer is treated differently from a signed integer (e.g., in comparisons or arithmetic with overflow) there are separate instructions for treating an integer as unsigned (e.g., cgt.un and add.ovf.un).

也就是说，从 int 到 uint 的转换只是一个簿记问题 - 从现在开始，价值stack/in 一个寄存器现在被认为是一个 unsigned int 而不是一个 int。

所以这两个转换应该是"free"一旦代码JITted，就可以进行无符号比较操作了

Answer 2

假设 _size 是一个整数，对列表私有，index 是这个函数的参数，需要测试其有效性。

进一步假设 _size 总是 >= 0。

那么原来的测试应该是：

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

优化版本

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

有一个比较（与前一个例子中的两个整数一样。）因为转换只是重新解释位并使 > 实际上是一个无符号比较，所以没有使用额外的 CPU 循环为此。

为什么有效？

只要索引>=0，结果就是simple/trivial。

如果索引 < 0，(uint)index 会将其变成一个非常大的数字：

示例：0xFFFF 作为 int 是 -1，但作为 uint 是 65535，因此

(uint)-1 > (uint)x

如果 x 为正，

始终为真。

Answer 3

请注意，如果您的项目是 checked 而不是 unchecked，则此技巧将不起作用。最好的情况它会更慢（因为每个演员都需要检查溢出）（或者至少不会更快），最坏的情况你会得到一个 OverflowException 如果你尝试将 -1 作为 index（而不是你的例外）。

如果你想写成"correctly"并且更"will surely work"的方式，你应该放一个

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，后者将传递的整数视为无符号，而前者将它们视为已签名。

（不熟悉 CIL 的人请注意，因为这是一个带有 CIL 答案的 C# 问题，bge.s、blt.s 和 blt.s.un 是 "short" 版本分别为 bge、blt 和 blt.un。blt 将两个值从堆栈中弹出，如果第一个值小于第二个值，则在将它们视为有符号值时进行分支，而 blt.un 弹出堆栈的两个值并在将它们视为无符号值时如果第一个小于第二个则分支。

这完全是一个微观选择，但有时微观选择是值得做的。进一步考虑，对于方法主体中的其余代码，这可能意味着某些东西是否落入内联的抖动限制之间的区别，以及如果他们不愿意有一个帮助程序来抛出超出范围的异常，他们是可能会尝试确保尽可能进行内联，额外的 4 个字节可能会有所不同。

的确，内联差异很可能比减少一个分支更重要。很多时候，特意确保内联的发生是值得的，但是像 List<T> 这样大量使用的 class 的核心方法肯定是其中之一。

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

事实证明，由于英特尔的分支预测和并行执行，更明显和可读的代码实际上运行得更快...

代码如下：

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

在英特尔处理器上进行探索时，我发现执行时间没有差异，这可能是由于多个整数执行单元。

但是在既没有分支预测也没有整数执行单元的 16MHZ 实时微处理器上执行此操作时，存在显着差异。

较慢代码的 100 万次迭代花费了 1761 毫秒

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

  return a[i];
}

100 万次更快的代码迭代花费了 1635 毫秒

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

通过强制转换为 uint 而不是检查负值来执行范围检查是否更有效？

Is it more efficient to perform a range check by casting to uint instead of checking for negative values?

c#

performance

micro-optimization

numeric-conversion

range-checking