79

.NET のリスト ソース コードでこのコードを見つけました。

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

どうやらこれはより効率的 (?) です。if (index < 0 || index >= _size)

トリックの背後にある理論的根拠に興味があります。単一の分岐命令は、 への 2 回の変換よりも本当にコストがかかるのuintでしょうか? または、このコードを追加の数値比較よりも高速にする他の最適化が行われていますか?

部屋の中の象に対処するには: はい、これはマイクロ最適化です。いいえ、コードのどこでもこれを使用するつもりはありません。ただ興味があるだけです ;)

4

7 に答える 7

58

MS Partition I、セクション 12.1 (サポートされているデータ型)から:

符号付き整数型 (int8、int16、int32、int64、およびネイティブ int) とそれに対応する符号なし整数型 (unsigned int8、unsigned int16、unsigned int32、unsigned int64、およびネイティブ unsigned int) は、整数のビットがどのように異なるかのみが異なります。解釈されます。符号なし整数が符号付き整数とは異なる方法で処理される演算 (例: オーバーフローを伴う比較または演算) については、整数を符号なしとして処理する別の命令 (例: cgt.un および add.ovf.un) があります。

つまり、anから aへの変換は単なる簿記の問題です。今後、スタック/レジスタ内の値は int ではなく unsigned int であることがわかります。intuint

したがって、コードが JITted されると、2 つの変換は「フリー」になり、符号なしの比較操作を実行できるようになります。

于 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
}

2 番目の方がコードが少なく、分岐が 1 つ少ないことが簡単にわかります。

実際には、キャストはまったくありません。andまたはを使用blt.sするかどうかの選択があり、後者は渡された整数を符号なしとして扱い、前者はそれらを符号付きとして扱います。bge.sblt.s.un

(これは CIL の回答を含む C# の質問であるため、CIL に慣れていない方への注意、、、および はそれぞれ、およびbge.sの「短い」バージョンです。スタックから 2 つの値をポップし、最初の値が 2 番目の値より小さい場合に分岐します。それらを符号付きの値と見なし、スタックの 2 つの値をポップし、それらを符号なしの値と見なしたときに最初の値が 2 番目の値より小さい場合は分岐します)。blt.sblt.s.unbgebltblt.unbltblt.un

それは完全にマイクロオプトですが、マイクロオプトを実行する価値がある場合もあります。さらに、メソッド本体の残りのコードでは、インライン化のジッター制限内に収まるかどうかの違いを意味する可能性があることを考慮してください。範囲外の例外をスローするためのヘルパーが必要な場合は、おそらく、可能な限りインライン化が確実に行われるようにしようとしており、余分な 4 バイトがすべての違いを生む可能性があります。

実際、そのインライン化の違いは、1 つのブランチの削減よりもはるかに大きな問題になる可能性が非常に高くなります。インライン化が確実に行われるようにするためにわざわざ行く価値がある場合はあまりありませんが、そのような頻繁に使用されるクラスのコア メソッドは、List<T>確かにその 1 つです。

于 2015-03-30T14:09:08.760 に答える
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.MaxValue、になります。たまたま負の場合、チェックは失敗します。array.Length(uint)array.Lengthi(uint)i > int.MaxValue

于 2015-03-30T20:08:22.427 に答える
4

どうやら実生活ではそれは速くありません。これを確認してください：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" );

    }
}
于 2015-03-31T18:51:22.480 に答える