Ist es effizienter, eine Bereichsprüfung durch Casting auf uint durchzuführen, anstatt nach negativen Werten zu suchen?

77

Ich bin auf diesen Code im Quellcode der .NET- Liste gestoßen :

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

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

Ich bin neugierig auf die Gründe für den Trick. Ist ein einzelner Zweigbefehl wirklich teurer als zwei Konvertierungen in uint? Oder gibt es eine andere Optimierung, die diesen Code schneller macht 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;)

enzi
quelle
4
Die Neugier wird in diesem Fall leicht mit ein paar Codezeilen befriedigt. Probier es aus.
Sam Axe
3
@SamAxe Ein Test würde nur bestätigen, dass Casts schneller sind (wenn ja), nicht erklären, warum.
Enzi
7
Die zwei "Konvertierungen" zu uint sind kostenlos - dieselben Bitmuster existieren im selben Register (oder im Speicher, aber wenn Sie Glück haben, in einem Register)
Damien_The_Unbeliever
2
In Verbindung stehender Artikel (der auch eine Besetzung von intbis enthält uint): codeproject.com/Articles/8052/…
Tim Schmelter
5
Das Codieren in diesem Stil kann leicht zu Sicherheitslücken führen. Tatsächlich passiert dies in C ++ die ganze Zeit und ist ein großer Teil des Grundes, warum dieser Codierungsstil in C # dringend empfohlen wird. Der obige Code funktioniert nur korrekt, da die Entwickler wissen, dass er _size niemals negativ sein kann.
BlueRaja - Danny Pflughoeft

Antworten:

56

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

Die vorzeichenbehafteten Ganzzahltypen (int8, int16, int32, int64 und native int) und ihre entsprechenden vorzeichenlosen Ganzzahltypen (vorzeichenlose int8, vorzeichenlose int16, vorzeichenlose int32, vorzeichenlose int64 und native vorzeichenlose int) unterscheiden sich nur darin, wie die Bits der Ganzzahl interpretiert werden. Für Operationen, bei denen eine vorzeichenlose Ganzzahl anders behandelt wird als eine vorzeichenbehaftete Ganzzahl (z. B. bei Vergleichen oder Arithmetik mit Überlauf), gibt es separate Anweisungen zum Behandeln einer Ganzzahl als vorzeichenlos (z. B. cgt.un und add.ovf.un).

Das heißt, die Konvertierung von a intnach a uintist lediglich eine Frage der Buchhaltung - von nun an ist bekannt, dass der Wert auf dem Stapel / in einem Register eher ein vorzeichenloses int als ein int ist.

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

Damien_The_Unbeliever
quelle
4
Ich bin etwas überrascht, dass der Compiler diese Optimierung nicht automatisch implementiert. (Oder doch?)
Ilmari Karonen
3
@IlmariKaronen Wie könnte es? Es kennt die Bedeutung der Werte nicht. C # und .NET sind beide sehr spezifisch definiert (im Gegensatz zu beispielsweise C ++), und dies ist genau die Art von "Optimierung", die im Allgemeinen ziemlich unsicher wäre. Ganz zu schweigen davon, dass der JIT-Compiler nicht wirklich genug Zeit hat, um nach solchen "Optimierungen" zu suchen, und der C # -Compiler selbst nicht wirklich viele Optimierungen vornimmt. Schreiben Sie einfach klaren Code, es sei denn, Sie können die Leistungsvorteile nachweisen (an einem Ort, an dem Ihnen die Leistung wirklich am Herzen liegt).
Luaan
2
@Luaan: Ah, ja, ich verstehe ... das Problem ist vermutlich, dass der Compiler nicht klug genug ist, um zu wissen, dass _sizedies nicht negativ sein kann, sodass er die Optimierung nicht sicher anwenden kann (da sie nur gültig ist, wenn (int)_size >= 0).
Ilmari Karonen
1
Die beiden Konvertierungen sind kostenlos, bevor der Code gesendet wird. Da sie immer nur als Einheimische verwendet werden, besteht der Unterschied zwischen bltoder blt.sund blt.unoder blt.un.s, und es ist nicht erforderlich, dass die aus der C # erzeugte CIL überhaupt eine tatsächliche Konvertierung beinhaltet.
Jon Hanna
2
@Luaan: Auch in diesem Fall konnte es nicht sicher gehen, da die Optimierung auch wenn bricht _size > int.MaxValue. Der Compiler könnte die Optimierung durchführen, wenn _sizees sich um eine nicht negative Konstante handelt, oder wenn er aus früherem Code schließen könnte, dass der Wert von _sizeimmer zwischen 0 und int.MaxValueeinschließlich liegt. Und ja, moderne Compiler führen normalerweise diese Art der Datenflussanalyse durch, obwohl es offensichtlich Grenzen gibt, wie viel davon sie tun können (da das vollständige Problem Turing-complete ist).
Ilmari Karonen
29

Nehmen wir an, 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 ILSpy betrachten:

.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 erkennen, dass der zweite weniger Code mit einem Zweig weniger enthält.

Wirklich, es gibt überhaupt keine Besetzung, es gibt die Wahl, ob blt.sund bge.soder verwendet werden soll blt.s.un, wobei letztere die übergebenen Ganzzahlen als nicht signiert behandelt, während erstere sie als signiert behandelt.

(Hinweis für diejenigen , die nicht mit CIL, da dies eine C # Frage mit einer CIL Antwort bge.s, blt.sund blt.s.unsind die „kurzen“ Versionen bge, bltund blt.unjeweils. bltPop zwei Werte aus dem Stapel und Zweigen , wenn die ersten weniger ist als die zweite , wenn Betrachten Sie sie als vorzeichenbehaftete Werte, während blt.unzwei Werte des Stapels und der Verzweigungen angezeigt werden, wenn der erste kleiner als der zweite ist, wenn Sie sie als vorzeichenlose Werte betrachten.

Es ist absolut ein Micro-Opt, aber es gibt Zeiten, in denen es sich lohnt, Micro-Opt zu machen. Bedenken Sie außerdem, dass dies mit dem Rest des Codes im Methodenkörper den Unterschied zwischen etwas bedeuten kann, das innerhalb der Jitter-Grenzen für Inlining liegt oder nicht, und ob sie sich die Mühe machen, einen Helfer für das Auslösen von Ausnahmen außerhalb des Bereichs zu haben Wahrscheinlich wird versucht, das Inlining sicherzustellen, wenn dies überhaupt möglich ist, und die zusätzlichen 4 Bytes könnten den Unterschied ausmachen.

In der Tat ist es sehr wahrscheinlich, dass dieser Inlining-Unterschied viel größer ist als die Reduzierung eines Zweigs. Es gibt nicht viele Fälle, in denen es sich lohnt, sich die Mühe zu machen, um sicherzustellen, dass Inlining stattfindet, aber eine Kernmethode für eine Klasse von so starker Beanspruchung, wie List<T>sie sicherlich eine davon wäre.

Jon Hanna
quelle
2
Ich wünschte, Sprachen würden ein Konstrukt enthalten, um zu testen, ob eine Variable innerhalb eines bestimmten Bereichs liegt, sodass man nicht raten muss, was Optimierer tun oder nicht tun. Wenn eine solche Mikrooptimierung auf einigen Systemen die Geschwindigkeit einer engen Schleife verdoppeln könnte (durchaus möglich, wenn sie eine "In-Lining" -Entscheidungsschwelle anstößt), kann es sich sehr lohnen, dies zu tun. Wenn es jedoch auf keinem System eine echte Beschleunigung bietet, sollte man das besser lesbare Formular verwenden. Ich finde es ärgerlich , wenn die lesbare Form eines Ausdruck könnte auf die schnellste Form vergleichbar sein, aber vielleicht nicht.
Supercat
@supercat Ich stimme im Allgemeinen zu, obwohl hier ein breiteres Wissen erforderlich ist, um zu wissen, dass _sizedann schon garantiert größer als 0 ist (index < 0 || index < _size) == ((uint)index >= (uint)_size). Natürlich könnte ein Compiler, der Code-Verträge als Teil seiner Optimierungsentscheidung verwenden könnte, sicherlich so etwas tun, aber selbst die Optimierung, um das (sich bewegende Ziel der) Inlining-Grenze zu überschreiten, ist in gewisser Weise ein eigenartiger Fall .
Jon Hanna
@supercat in der Tat, jetzt denke ich darüber nach, wenn C # ein Konstrukt wie z. B. hätte 0 < index < _size(wie bei Python und sogar für C # durchaus plausibel, da es nicht implizit zwischen booleschen und ganzzahligen Typen konvertiert), wäre die Optimierung hier immer noch um es nicht zu benutzen.
Jon Hanna
Eine Sache, die ich mir für Sprachen wünschte, wäre ein Variablen- / Parametertyp "(n-1) -bit 'natürliche Zahl'", der sich in arithmetischen Ausdrücken wie normal signierte Typen verhält, jedoch mit einer vom Compiler erzwungenen Behauptung, dass dies nicht möglich ist negativ sein. Oft ist die einzige Möglichkeit, vernünftige Berechnungen für Werte vorzeichenloser Typen durchzuführen, die Verwendung des nächstgrößeren vorzeichenbehafteten Ganzzahltyps, der unangenehm und ineffizient sein kann. Es wäre jedoch hilfreich, die Idee auszudrücken, dass eine Variable / ein Parameter nur natürliche Zahlen enthält.
Supercat
8

Beachten Sie, dass dieser Trick nicht funktioniert, wenn Ihr Projekt checkedanstelle von ist unchecked. Im besten Fall ist es langsamer (da jeder Wurf auf Überlauf geprüft werden muss) (oder zumindest nicht schneller), im schlimmsten Fall erhalten Sie eine, OverflowExceptionwenn Sie versuchen, -1 als index(anstelle Ihrer Ausnahme) zu übergeben.

Wenn Sie es "richtig" und auf eine "sicher funktionierende" Weise schreiben möchten, sollten Sie eine setzen

unchecked
{
    // test
}

rund um den Test.

Xanatos
quelle
Die Überprüfung auf Überlauf verlangsamt im Allgemeinen nichts, wenn man bedenkt, wie die Überlaufprüfung auf dem Chip erfolgt. Es wird natürlich in der Tat werfen, wenn es in einem checkedKontext und nicht im normalen getan wird unchecked. Dies beantwortet die Frage jedoch nicht wirklich.
Jon Hanna
@ JonHanna Yep ... Aber es war zu lang für einen Kommentar und eine gute Antwort war bereits verfügbar. Und zur Geschwindigkeit: Wenn Sie sich die Demontage eines Casts ansehen (Release-Modus, also optimierter Code), sehe ich ein cmp dword ptr [rsp+64h],0 / jl 00000000000000A2, also führt ein Cast explizit einen Vergleich durch, wenn der int <0 ist, dann springen
xanatos
Wenn es eine gegossen wird, weil Gießen intauf uintund Speichern wird keine Ausnahmen auf dieser Ebene verursacht so ein Test hat explizit sein, aber hier ist der Unterschied könnte nur sein , zwischen jlund jb.
Jon Hanna
8

Angenommen, es _sizehandelt sich um eine Ganzzahl, die für die Liste privat ist, und indexist das Argument für diese Funktion, deren Gültigkeit geprüft werden muss.

Angenommen, das _sizeist immer> = 0.

Dann wäre der ursprüngliche Test gewesen:

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

Die optimierte Version

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

hat einen Vergleich (wie im vorherigen Beispiel mit zwei verglichen). Da der Cast nur die Bits neu interpretiert und den >Vergleich tatsächlich ohne Vorzeichen macht, werden keine zusätzlichen CPU-Zyklen dafür verwendet.

Warum funktioniert es?

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

Wenn der Index <0 ist, (uint)indexwird daraus eine sehr große Zahl:

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

(uint)-1 > (uint)x 

ist immer wahr, wenn xpositiv war.

DrKoch
quelle
2
In einem checkedKontext erhalten Sie eine OverflowException. In einem uncheckedKontext können Sie sich nicht auf das Ergebnis verlassen: "Das Ergebnis der Konvertierung ist ein nicht angegebener Wert des Zieltyps." stackoverflow.com/questions/22757239/…
Tim Schmelter
@Tim scheint das Zitat für zu sein Für eine Konvertierung von float oder double zu einem integralen Typ hängt die Verarbeitung vom Kontext der Überlaufprüfung ab , also nicht int-> uint
xanatos
@xanatos: aber die Regeln sind die gleichen, wenn die Umwandlung fehlschlägt, erhalten Sie einen OverflowExceptionmit aktiviertem Kontext und T-MaxValue im nicht aktivierten Kontext. Das gibt also zurück uint.Maxvalue: unchecked { uint ui = (uint)-1; };. Es ist jedoch nicht garantiert. Wenn Sie das mit versuchen, erhalten checkedSie einen Compilerfehler mit der -1-Konstante und wenn Sie OverflowExceptionzur Laufzeit eine Variable verwenden . Übrigens bezog ich mich
Tim Schmelter
@ TimSchmelter: Nur um zu verdeutlichen, während nicht markiert (uint)-1gleich ist uint.MaxValue, nicht markiert (uint)-2nicht - es uint.MaxValue-1ist stattdessen gleich. Beide sind "sehr groß" - in der Tat streng größer als int.MaxValue- obwohl.
Ilmari Karonen
1
@ TimSchmelter Die Bedeutung dieser Besetzung ist in der Tat definiert und genau das, was hier benötigt wird. Sie zitieren eine Antwort, die den falschen Teil von §6.2.1 zitiert. Der relevante Fall wird hier einige Absätze vor Beginn dieses Zitats erwähnt und ergibt das Ergebnis "dann wird der Quellwert als Wert des Zieltyps behandelt".
Jon Hanna
5

Ja, das ist effizienter. Die JIT führt den gleichen Trick aus, wenn Array-Zugriffe zur Bereichsprüfung durchgeführt werden .

Die Transformation und Argumentation ist wie folgt:

i >= 0 && i < array.Lengthwird (uint)i < (uint)array.Lengthweil array.Length <= int.MaxValueso das array.Lengthden gleichen Wert hat wie (uint)array.Length. Wenn idies dann negativ ist (uint)i > int.MaxValueund die Prüfung fehlschlägt.

usr
quelle
Können Sie Beispielcode bereitstellen, in dem dies geschieht, weil ich kein Beispiel erstellen kann, in dem einer schneller als der andere ist?
Stilgar
Ich bin mir nicht sicher, wo das Problem liegt. Vergleichen Sie einfach die beiden Versionen miteinander. Freigabemodus, Strg-F5 (kein Debugger). Der Benchmark sollte ungefähr 1 Sekunde pro Test dauern, damit alle einmaligen Kosten und Abweichungen im Rauschen verschwinden.
usr
Nun, ich habe keinen Unterschied festgestellt, als ich verschiedene Ansätze ausprobiert habe, einschließlich des von @nsimeonov in einer Antwort bereitgestellten.
Stilgar
Geben Sie Ihren Code als Frage an Stack Overflow ein und hinterlassen Sie hier einen Link. Ich werde schauen.
usr
4

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

Es stellt sich heraus, dass dank Intels Verzweigungsvorhersage und paralleler Ausführung 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" );

    }
}
nsimeonov
quelle
Sie vergleichen nicht denselben Code wie die Frage. Siehe Jon Hannas Antwort - in vielen Fällen kommt es auf die Größe an , und das haben Sie völlig verloren.
Ben Voigt
Ich verstehe nicht. Wäre es wichtig, wenn ich die eigentliche Prüfung zu einer separaten Funktion machen würde? Mein Punkt war, dass aufgrund der Vorhersage der CPU-Verzweigung der erste Fall schneller ablief. Auch nachdem wir ein bisschen mehr damit gespielt haben, stellte sich heraus, dass je mehr "außerhalb des Bereichs" Werte wir überprüfen, desto besser funktioniert der erste Fall. Wenn jedoch 99% im Bereich liegen, scheint der zweite Fall etwas schneller zu sein. Und so haben wir mehr Spaß, wenn Sie im Release-Modus kompilieren - 2. Fall ist schneller :-)
nsimeonov
Warten Sie, Sie haben Timing-Ergebnisse gemeldet, ohne die Optimierung aktiviert zu haben?
Ben Voigt
Schuldig im Sinne der Anklage. Ich habe anfangs dotnetfiddle.com verwendet und es gibt keine Optionen für Optimierungen. Die Ergebnisse haben mich überrascht. Später habe ich es mit Mono versucht und die gleichen Ergebnisse erzielt. Nachdem ich ein bisschen mehr gespielt hatte, bekam ich wirklich interessante Statistiken. Jon Hanna machte tatsächlich einen guten Punkt. Der Unterschied könnte in der Größe und nicht in der Geschwindigkeit liegen, da ein paar weitere Anweisungen dazu führen können, dass die aufrufende Methode inline ist oder nicht, was wiederum einen großen Unterschied machen kann.
nsimeonov
1

Während ich dies auf einem Intel-Prozessor untersuchte, stellte ich keine Unterschiede in den Ausführungszeiten fest, möglicherweise aufgrund mehrerer ganzzahliger Ausführungseinheiten.

Bei einem 16-MHz-Echtzeit-Mikroprozessor ohne Verzweigungsvorhersage oder Ganzzahl-Ausführungseinheiten gab es jedoch bemerkenswerte Unterschiede.

1 Million Iterationen des langsameren Codes dauerten 1761 ms

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

  return a[i];
}

1 Million Iterationen schnellerer Code dauerte 1635 ms

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