Frage Ist es effizienter, eine Bereichsüberprüfung durchzuführen, indem Sie nach Uint gießen, anstatt nach negativen Werten zu suchen?


Ich bin über diesen Code in .NET gestolpert Quellcode auflisten:

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

Anscheinend ist das effizienter (?) Als if (index < 0 || index >= _size)

Ich bin neugierig auf die Gründe hinter dem Trick. Ist eine einzelne Verzweigungsinstruktion wirklich teurer als zwei Konvertierungen zu? uint? Oder gibt es andere Optimierungen, die diesen Code schneller machen als einen zusätzlichen numerischen Vergleich?

Um den Elefanten im Raum anzusprechen: ja, das ist Mikrooptimierung, nein, ich habe nicht vor, dies überall in meinem Code zu verwenden - ich bin nur neugierig;)


76
2018-03-30 10:10


Ursprung


Antworten:


Von MS-Partition I, Abschnitt 12.1 (Unterstützte Datentypen):

Die vorzeichenbehafteten Integer-Typen (int8, int16, int32, int64 und native int) und ihre entsprechenden unsigned   Integer-Typen (unsigned int8, unsigned int16, unsigniertes int32, unsigned int64 und systemeigenes unsigned   int) unterscheiden sich nur darin, wie die Bits der Ganzzahl interpretiert werden. Für solche Operationen, in denen eine vorzeichenlose Ganzzahl enthalten ist   wird anders behandelt als eine vorzeichenbehaftete Ganzzahl (z. B. in Vergleichen oder Arithmetik mit Überlauf), die getrennt sind   Anweisungen zum Behandeln einer ganzen Zahl als unsigniert (z. B. cgt.un und add.ovf.un).

Das heißt, die Umwandlung von einem int zu einem uint ist nur eine Frage der Buchführung - von nun an ist der Wert auf dem Stapel / in einem Register jetzt bekannt als ein nicht signierter int anstelle eines int.

Die beiden Konvertierungen sollten also "frei" sein, sobald der Code JITted ist, und dann kann die vorzeichenlose Vergleichsoperation ausgeführt werden.


54
2018-03-30 10:42



Sagen wir, wir haben:

public void TestIndex1(int index)
{
  if(index < 0 || index >= _size)
    ThrowHelper.ThrowArgumentOutOfRangeException();
}
public void TestIndex2(int index)
{
  if((uint)index >= (uint)_size)
    ThrowHelper.ThrowArgumentOutOfRangeException();
}

Lassen Sie uns diese kompilieren und schauen Sie sich ILSpy an:

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

Es ist leicht zu sehen, dass die Sekunde weniger Code hat, mit einem Zweig weniger.

Wirklich, es gibt überhaupt keine Besetzung, es gibt die Wahl, ob man sie benutzt blt.s und bge.s oder zu benutzen blt.s.un, wobei letztere die Ganzzahlen behandelt, die als nicht signiert übergeben wurden, während die ersteren sie als signiert behandeln.

(Hinweis für diejenigen, die nicht mit CIL vertraut sind, da dies eine C # -Frage mit einer CIL-Antwort ist, bge.s, blt.s und blt.s.un sind die "kurzen" Versionen von bge, blt und blt.un beziehungsweise. blt löscht zwei Werte aus dem Stapel und verzweigt, wenn der erste kleiner als der zweite ist, wenn sie als signierte Werte betrachtet werden blt.un gibt zwei Werte des Stapels aus und verzweigt, wenn der erste kleiner als der zweite ist, wenn sie als vorzeichenlose Werte betrachtet werden).

Es ist ein Mikro-opt, aber es gibt Zeiten, in denen Mikro-opt's es wert sind. Man bedenke weiter, dass mit dem Rest des Codes im Methodenkörper dies den Unterschied zwischen etwas bedeuten könnte, das in die Jittergrenzen für Inlining fällt oder nicht, und wenn sie sich Mühe geben, einen Helfer zu haben, der außer Reichweite Ausnahmen macht wahrscheinlich versucht, Inlining zu gewährleisten, wenn überhaupt möglich, und die zusätzlichen 4 Bytes könnten den Unterschied ausmachen.

In der Tat ist es sehr wahrscheinlich, dass dieser Unterschied viel größer ist als der Abbau einer Branche. Es gibt nicht viele Zeiten, in denen es sich lohnt, Inlining zu machen, ist es wert, aber eine Kernmethode von einer Klasse von so starkem Gebrauch wie List<T>wäre sicherlich einer von ihnen.


29
2018-03-30 14:09



Beachten Sie, dass dieser Trick nicht funktioniert, wenn Ihr Projekt ist checked Anstatt von unchecked. Im besten Fall wird es langsamer (weil jeder Cast gegen Überlauf überprüft werden muss) (oder zumindest nicht schneller), schlimmstenfalls erhalten Sie ein OverflowException wenn du versuchst, -1 als index (anstelle Ihrer Ausnahme).

Wenn Sie es "richtig" und auf eine mehr "wird sicherlich arbeiten" Weise schreiben möchten, sollten Sie ein setzen

unchecked
{
    // test
}

rund um den Test.


8
2018-03-30 11:31



Angenommen _sizeist eine Ganzzahl, privat für die Liste und index ist das Argument für diese Funktion, deren Gültigkeit getestet werden muss.

Davon ausgehend weiter _size ist immer> = 0.

Dann wäre der ursprüngliche Test gewesen:

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

Das optimiert Ausführung

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

hat einen Vergleich (wie im vorigen Beispiel zu zweien). Weil der Cast die Bits einfach neuinterpretiert und den >in der Tat ein vorzeichenloser Vergleich, keine zusätzlichen CPU-Zyklen werden dafür verwendet.

Warum funktioniert es?

Die Ergebnisse sind einfach / trivial, solange der Index> = 0 ist.

Wenn der Index <0 ist, (uint)index wird es in eine sehr große Zahl verwandeln:

Beispiel: 0xFFFF ist -1 als int, aber 65535 als uint, also

(uint)-1 > (uint)x 

ist immer wahr wenn x war positiv.


8
2018-03-30 10:44



Ja, das ist effizienter. Das JIT macht den gleichen Trick wenn Bereichsüberprüfung von Array-Zugriffen.

Die Transformation und Argumentation ist wie folgt:

i >= 0 && i < array.Length wird (uint)i < (uint)array.Length weil array.Length <= int.MaxValue damit array.Length hat den gleichen Wert wie (uint)array.Length. Ob i passiert dann negativ (uint)i > int.MaxValue und die Überprüfung schlägt fehl.


5
2018-03-30 20:08



Scheinbar im wirklichen Leben ist es nicht schneller. Überprüfen Sie dies: https://dotnetfiddle.net/lZKHmn

Es stellt sich heraus, dass dank der Verzweigungsvorhersage und parallelen Ausführung von Intel der offensichtlichere und lesbarere Code tatsächlich schneller funktioniert ...

Hier ist der 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" );

    }
}

4
2018-03-31 18:51



Während ich dies auf einem Intel-Prozessor erkundete, fand ich keine Unterschiede in den Ausführungszeiten, möglicherweise aufgrund von mehreren Integer-Ausführungseinheiten.

Aber als dies auf einem 16 MHz Echtzeit-Mikroprozessor mit weder Verzweigungsvorhersage- noch Integer-Ausführungseinheiten geschah, gab es bemerkenswerte Unterschiede.

1 Million Iterationen des langsameren Codes benötigten 1761 ms

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

  return a[i];
}

1 Million Iterationen schneller Code dauerte 1635 ms

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

1
2018-05-30 06:19