음수 값을 확인하는 대신 uint로 캐스팅하여 범위 확인을 수행하는 것이 더 효율적입니까?

음수 값을 확인하는 대신 uint로 캐스팅하여 범위 확인을 수행하는 것이 더 효율적입니까?

---

.NET의 List 소스 코드 에서이 코드를 발견했습니다 .

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

분명히 이것은 더 효율적입니다 (?) if (index < 0 || index >= _size)

나는 트릭의 근거가 궁금합니다. 단일 분기 명령어가 두 번의 변환보다 실제로 비용이 많이 듭 uint니까? 아니면이 코드를 추가 숫자 비교보다 빠르게 만드는 다른 최적화가 진행되고 있습니까?

방에있는 코끼리를 다루기 위해 : 예, 이것은 마이크로 최적화입니다. 아니오 저는 이것을 코드의 모든 곳에서 사용할 생각이 없습니다 – 저는 단지 궁금합니다;)

---

에서 MS 파티션 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 로의 변환 은 단지 부기의 문제입니다. 이제부터 스택 / 레지스터의 값은 이제 int가 아닌 unsigned int로 알려져 있습니다.intuint

따라서 코드가 JIT 처리되면 두 개의 변환이 "무료"여야하며 서명되지 않은 비교 작업이 수행 될 수 있습니다.

---

다음이 있다고 가정 해 보겠습니다.

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부호없는 값으로 간주 할 때 첫 번째 값이 두 번째 값보다 작 으면 스택 및 분기의 두 값을 팝 하는 동안 부호있는 값으로 간주).

It's utterly a micro-opt, but there are times when micro-opt's are worth doing. Consider further, that with the rest of the code in the method body this could mean the difference between something falling inside the jitters limits for inlining or not, and if they're bothering to have a helper for throwing out of range exceptions they're probably attempting to ensure inlining happens if at all possible, and the extra 4 bytes could make all the difference.

Indeed, it's quite likely for that inlining difference to be a much bigger deal than the reduction of one branch. There aren't a lot of times when going out of your way to ensure inlining happens is worth it, but a core method of a class of such heavy use as List<T> would certainly be one of them.

---

프로젝트의 경우이 트릭이 작동하지 않습니다 checked대신 unchecked. 가장 좋은 경우에는 더 느릴 것입니다 (각 캐스트가 오버플로에 대해 확인되어야하기 때문에) (또는 적어도 빠르지 않음) 최악의 경우 (예외 대신) OverflowException-1을 전달하려고 하면 얻을 수 있습니다 index.

"올바르게"작성하고보다 "확실히 작동 할 것"방식으로 작성하려면

unchecked
{
    // test
}

모든 테스트.

---

_size정수 라고 가정 하고 목록에 비공개이며 index유효성을 테스트해야하는이 함수에 대한 인수입니다.

더 나아가 _size항상> = 0 이라고 가정합니다 .

그렇다면 원래 테스트는 다음과 같습니다.

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

최적화 된 버전

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

하나의 비교를가집니다 (이전 예제에서 두 가지를 선택합니다.) 캐스트가 비트를 재 해석하고 >실제로는 서명되지 않은 비교를 만들기 때문에 추가 CPU 사이클이 사용되지 않습니다.

왜 작동합니까?

결과는 인덱스가 0보다 크면 간단하고 사소합니다.

인덱스 <0이면 (uint)index매우 큰 숫자로 바뀝니다.

예 : 0xFFFF는 int로 -1이지만 uint로 65535이므로

(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하고 검사가 실패합니다.

---

Apparently in real life it isn't faster. Check this: https://dotnetfiddle.net/lZKHmn

Turns out, that thanks to Intel's branch prediction and parallel execution the more obvious and readable code actually works faster...

Here's the code:

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

    }
}

---

While exploring this on an intel processor I found no differene in execution times, possibly due to multiple integer execution units.

But when doing this on 16MHZ real-time microprocessor with neither branch prediction nor integer execution units there were notable differences.

1 million iterations of the slower code took 1761 ms

int slower(char *a, long i)
{
  if (i < 0 || i >= 10)
    return 0;

  return a[i];
}

1 million iterations faster code took 1635 ms

int faster(char *a, long i)
{
  if ((unsigned int)i >= 10)
    return 0;
  return a[i];
}

참고URL : https://stackoverflow.com/questions/29343533/is-it-more-efficient-to-perform-a-range-check-by-casting-to-uint-instead-of-chec