执行范围检查通过投射到uint而不是检查负值是否更有效?

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

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

显然这比if (index < 0 || index >= _size)更有效率(? if (index < 0 || index >= _size)

我很好奇背后的理由。 单个分支指令是否比两个转换为uint更昂贵? 还是有一些其他的优化,会使这个代码比另一个数字比较更快?

为了解决房间里的大象:是的,这是微型优化,不,我不打算在我的代码中到处使用它 – 我只是好奇;)

从MS分区I ,第12.1节(支持的数据types):

有符号整数types(int8,int16,int32,int64和本地int)及其对应的无符号整数types(无符号整数8,无符号整数16,无符号整数32,无符号整数64和本机无符号整数)仅在整数被解释。 对于无符号整数与有符号整数处理不同的操作(例如,比较或算术溢出),有单独的指令将整数视为无符号(例如,cgt.un和add.ovf.un)。

也就是说,从一个int到一个uint转换仅仅是一个簿记问题 – 从现在开始,栈中的值现在被认为是一个无符号整数,而不是整数。

所以一旦代码被打乱,两次转换应该是“空闲的”,然后可以执行无符号的比较操作。

假设我们有:

 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 } 

很容易看到第二个代码less了一个分支。

真的,根本没有演员,可以select是使用blt.sbge.s还是使用blt.s.un ,后者将整数作为无符号进行处理,而前者将其视为有符号。

(注意那些不熟悉CIL的人,因为这是一个带有CIL答案的C#问题, bge.sblt.sblt.s.un分别是bgebltblt.un的“short”版本。从堆栈中popup两个值,如果第一个值小于第二个值, blt.un其作为有符号值;如果第一个值小于第二个值, blt.unpopup堆栈和分支的两个值。

这完全是一个微select,但有时微select是值得的。 进一步考虑一下,对于方法体中的其余代码,这可能意味着在内部不稳定的内部区域之间的区别,如果他们有困难的帮助者抛出范围exception,他们可能试图确保内联发生,如果可能的话,额外的4个字节可以使所有的差异。

实际上,内联差异很可能比减less一个分支大得多。 为了确保内联发生是值得的,没有多less时间,但像List<T>这样的一类重用的核心方法当然就是其中之一。

请注意,如果您的项目被checked而不是unchecked ,这个技巧将不起作用。 最好的情况下,它会变慢(因为每个强制转换将被检查溢出)(或至less不是更快),最坏的情况下,如果您尝试传递-1作为index (而不是您的例外) 。

如果你想把它写得“正确”,并以更“肯定的工作”的方式,你应该把一个

 unchecked { // test } 

所有的testing。

假设_size是一个整数,私有的列表和index是这个函数的有效性需要testing的参数。

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

那么原来的testing会是:

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

优化的版本

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

有一个比较(因为前面的例子中select了两个int)。因为cast只是重新解释了这些位,并且使得其中一个无符号的比较,所以没有使用额外的CPU周期。

为什么它工作?

只要index> = 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处理器上探索这个时,我发现执行时间没有差异,可能是由于多个整数执行单元。

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