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

小开

最佳答案

来自 MS 分区 I第12.1节(支持的数据类型) :

有符号整数类型(int8、 int16、 int32、 int64和本机 int)及其对应的无符号整数整数类型(无符号 int8、无符号 int16、无符号 int32、无符号 int64和本机无符号整数的位的解释方式不同。对于那些无符号整数与有符号整数的处理方法不同(例如，在比较或溢出算法中) 将整数视为无符号的说明(例如，cgt.un 和 add.ovf.un)。

也就是说，从 int到 uint的转变仅仅是一个簿记的问题——从现在开始，堆栈/寄存器中的值现在已经知道是一个无符号整型数而不是一个整型数。

因此，一旦代码被 JITted，这两个转换应该是“自由的”，然后可以执行无符号比较操作。

小开

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

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

那么最初的测试应该是:

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

优化版本

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

有一个比较(与前面的例子中的两个整型相比)因为强制转换只是重新解释位，并使 >实际上成为一个无符号比较，所以不使用额外的 CPU 周期。

为什么会有用？

只要索引 > = 0，结果就是简单/平凡的。

如果指数小于0，(uint)index会变成一个非常大的数字:

例如: 0xFFFF 是 -1作为 int，而65535作为 uint，因此

(uint)-1 > (uint)x

如果 x为阳性，那么它总是正确的。

小开

注意，如果您的项目是 checked而不是 unchecked，那么这个技巧将不起作用。最好的情况下它会更慢(因为每个强制转换都需要检查溢出)(或者至少不会更快) ，最坏的情况下，如果你试图传递 -1作为 index(而不是你的异常) ，你会得到一个 OverflowException。

如果您希望以“正确”和“肯定会奏效”的方式编写它，则应该将

unchecked
{
// test
}

在考试的时候。

小开

假设我们有:

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>这样使用频繁的类的核心方法肯定是其中之一。

小开

是的，这样更有效。当 范围检查数组访问。

转换和推理如下:

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" );


}
}

小开

在英特尔处理器上研究这个问题时，我发现执行时间没有什么不同，可能是由于多个整数执行单元的缘故。

但是在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];
}