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;)
int
bis enthältuint
): codeproject.com/Articles/8052/…_size
niemals negativ sein kann.Antworten:
Aus MS Partition I , Abschnitt 12.1 (Unterstützte Datentypen):
Das heißt, die Konvertierung von a
int
nach auint
ist 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.
quelle
_size
dies nicht negativ sein kann, sodass er die Optimierung nicht sicher anwenden kann (da sie nur gültig ist, wenn(int)_size >= 0
).blt
oderblt.s
undblt.un
oderblt.un.s
, und es ist nicht erforderlich, dass die aus der C # erzeugte CIL überhaupt eine tatsächliche Konvertierung beinhaltet._size > int.MaxValue
. Der Compiler könnte die Optimierung durchführen, wenn_size
es sich um eine nicht negative Konstante handelt, oder wenn er aus früherem Code schließen könnte, dass der Wert von_size
immer zwischen 0 undint.MaxValue
einschließ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).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.s
undbge.s
oder verwendet werden sollblt.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.s
undblt.s.un
sind die „kurzen“ Versionenbge
,blt
undblt.un
jeweils.blt
Pop zwei Werte aus dem Stapel und Zweigen , wenn die ersten weniger ist als die zweite , wenn Betrachten Sie sie als vorzeichenbehaftete Werte, währendblt.un
zwei 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.quelle
_size
dann 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 .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.Beachten Sie, dass dieser Trick nicht funktioniert, wenn Ihr Projekt
checked
anstelle von istunchecked
. 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,OverflowException
wenn Sie versuchen, -1 alsindex
(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.
quelle
checked
Kontext und nicht im normalen getan wirdunchecked
. Dies beantwortet die Frage jedoch nicht wirklich.cmp dword ptr [rsp+64h],0 / jl 00000000000000A2
, also führt ein Cast explizit einen Vergleich durch, wenn der int <0 ist, dann springenint
aufuint
und Speichern wird keine Ausnahmen auf dieser Ebene verursacht so ein Test hat explizit sein, aber hier ist der Unterschied könnte nur sein , zwischenjl
undjb
.Angenommen, es
_size
handelt sich um eine Ganzzahl, die für die Liste privat ist, undindex
ist das Argument für diese Funktion, deren Gültigkeit geprüft werden muss.Angenommen, das
_size
ist 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)index
wird daraus eine sehr große Zahl:Beispiel: 0xFFFF ist -1 als int, aber 65535 als uint
(uint)-1 > (uint)x
ist immer wahr, wenn
x
positiv war.quelle
checked
Kontext erhalten Sie eineOverflowException
. In einemunchecked
Kontext können Sie sich nicht auf das Ergebnis verlassen: "Das Ergebnis der Konvertierung ist ein nicht angegebener Wert des Zieltyps." stackoverflow.com/questions/22757239/…OverflowException
mit aktiviertem Kontext und T-MaxValue im nicht aktivierten Kontext. Das gibt also zurückuint.Maxvalue
:unchecked { uint ui = (uint)-1; };
. Es ist jedoch nicht garantiert. Wenn Sie das mit versuchen, erhaltenchecked
Sie einen Compilerfehler mit der -1-Konstante und wenn SieOverflowException
zur Laufzeit eine Variable verwenden . Übrigens bezog ich mich(uint)-1
gleich istuint.MaxValue
, nicht markiert(uint)-2
nicht - esuint.MaxValue-1
ist stattdessen gleich. Beide sind "sehr groß" - in der Tat streng größer alsint.MaxValue
- obwohl.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.Length
wird(uint)i < (uint)array.Length
weilarray.Length <= int.MaxValue
so dasarray.Length
den gleichen Wert hat wie(uint)array.Length
. Wenni
dies dann negativ ist(uint)i > int.MaxValue
und die Prüfung fehlschlägt.quelle
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" ); } }
quelle
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]; }
quelle