79

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

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

显然这比（？）更有效if (index < 0 || index >= _size)

我很好奇这个把戏背后的原理。单个分支指令真的比两次转换更昂贵uint吗？或者是否有其他一些优化可以使这段代码比额外的数字比较更快？

为了解决房间里的大象问题：是的，这是微优化，不，我不打算在我的代码中到处使用它——我只是好奇；）

4

7 回答 7

58

从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）。

也就是说，从 an到 a的转换只是记账的问题——从现在开始，堆栈上/寄存器中的值现在被称为 unsigned int 而不是 int。intuint

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

于 2015-03-30T10:42:15.463 回答
29

假设我们有：

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分支将它们视为有符号值，同时弹出堆栈的两个值并在将它们视为无符号值时如果第一个小于第二个则分支）。bltblt.unbltblt.un

这完全是一个微型选择，但有时微型选择是值得的。进一步考虑，对于方法主体中的其余代码，这可能意味着是否在内联的抖动限制内的东西之间的差异，如果他们不想有一个帮助器来抛出超出范围的异常，他们是如果可能的话，可能会尝试确保内联发生，而额外的 4 个字节可能会产生重大影响。

实际上，这种内联差异很可能比减少一个分支更大。没有多少次会竭尽全力确保内联发生是值得的，但是一个如此大量使用的类的核心方法List<T>肯定是其中之一。

于 2015-03-30T14:09:08.760 回答
8

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

进一步假设_size始终> = 0。

那么原始测试将是：

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

优化版_

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

有一个比较（与前一个示例中的两个相比）。因为强制转换只是重新解释这些位并使>实际上是无符号比较，所以没有使用额外的 CPU 周期。

为什么它有效？

只要索引> = 0，结果就很简单/微不足道。

如果 index < 0(uint)index将把它变成一个非常大的数字：

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

(uint)-1 > (uint)x

如果x为正，则始终为真。

于 2015-03-30T10:44:00.853 回答
8

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

如果您想“正确”地编写它并且以更“肯定会工作”的方式，您应该放一个

unchecked
{
    // test
}

到处都是测试。

于 2015-03-30T11:31:47.633 回答
5

是的，这样更有效率。JIT 在范围检查数组访问时执行相同的技巧。

变换和推理如下：

i >= 0 && i < array.Length变为(uint)i < (uint)array.Length因为array.Length <= int.MaxValueso 与array.Length具有相同的值(uint)array.Length。如果i恰好为负(uint)i > int.MaxValue，则检查失败。

于 2015-03-30T20:08:22.427 回答
4

显然在现实生活中它并没有更快。检查这个：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" );

    }
}
于 2015-03-31T18:51:22.480 回答
1

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

但是，当在既没有分支预测也没有整数执行单元的 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];
}
于 2015-05-30T06:19:18.450 回答