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

Question

我在.NET的List源代码中偶然发现了这段代码:

// 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和native int)及其对应的无符号整数类型(unsigned int8,unsigned int16,unsigned int32,unsigned int64和native unsigned int)的区别仅在于整数的位数被解释.对于无符号整数与有符号整数不同处理的那些操作(例如,在比较或算术中具有溢出),存在用于将整数视为无符号的单独指令(例如,cgt.un和add.ovf.un).

也就是说,从a 到a 的转换仅仅是记账的问题 - 从现在开始,堆栈上的值/寄存器中的值现在已知为无符号整数而不是整数.intuint

因此,一旦代码被JIT打开,两次转换应该是"空闲的",然后可以执行无符号比较操作.

Answer 2

假设我们有:

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分别是"短"版本bge,blt并且blt.un分别blt从堆栈和分支中弹出两个值,如果第一个小于第二个,则将它们视为有符号值,同时blt.un弹出堆栈和分支的两个值,如果第一个小于第二个,则将它们视为无符号值).

这完全是微观选择,但有时微观选择值得做.进一步考虑一下,对于方法体中的其余代码,这可能意味着内联的抖动限制内的某些内容之间的差异,以及如果他们需要帮助抛出超出范围的异常,他们就是可能试图确保内联发生,如果可能的话,额外的4个字节可以产生重大影响.

实际上,与一个分支的减少相比,内联差异很可能是一个更大的交易.为了确保内联发生是值得的,并不是很多时候,但是一个如此大量使用的核心方法List<T>肯定会是其中之一.

Answer 3

假设_size是一个整数,列表index是私有的,并且是该函数的参数,需要测试其有效性.

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

然后原始测试将是:

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

该优化的版本

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

有一个比较(因为前一个例子选择了两个int.)因为演员只是重新解释这些位并使其>实际上是无符号比较,所以没有使用额外的CPU周期.

它为什么有效？

只要index> = 0,结果就是简单/平凡.

如果index <0 (uint)index则会将其变为非常大的数字:

示例:0xFFFF为-1,为int,但为65535为uint,因此

(uint)-1 > (uint)x 

如果x是积极的,那么总是如此.

Answer 4

请注意,如果您的项目checked不是,那么这个技巧将不起作用unchecked.最好的情况是它会更慢(因为每个演员都需要检查溢出)(或者至少不是更快),最坏的情况是你会得到一个OverflowException如果你试图传递-1作为index(而不是你的例外).

如果你想"正确地"写它并以更"肯定会工作"的方式,你应该放一个

unchecked
{
    // test
}

在测试周围.

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检查失败.