Wie sieht ein Zweig ohne Zweig in C ++ aus?

Abgesehen von all dem Twiddling-basierten Branchless-Code (der nicht alles abdeckt, wie zB FP), erhalten Sie Anweisungen, die speziell für die Erstellung von Branchless-Code gedacht sind. Diese wären SETcc , FCMOVcc und CMOVcc unter x86, die Operationen basierend auf den Bedingungsflags eines Vergleichs ausführen.

ein wirklich einfaches Beispiel wäre (ja, das Beispiel ist so einfach, dass man wahrscheinlich nie so etwas schreiben würde, es ist nur ein Punkt deutlich zu demonstrieren):

Nun könnte ein einfacher x86-Compiler das nach unten kompilieren:

Ein optimierender x86-Compiler würde es in den folgenden verzweigungslosen Code (oder ähnlich) ablegen:

Ein etwas komplexeres Beispiel finden Sie hier .

Dies wird jedoch von einem Compiler ausgeführt, und einige sollten sich nicht um Sie kümmern (zumindest nicht ohne die Ausgabe Ihres Compilers zu analysieren). Wenn der Code jedoch unbedingt fehlerfrei sein muss, bietet C ++ nicht genügend Steuerelemente, sodass Sie (inline) Assembly verwenden müssen.

Ссылка

Ich denke (obwohl ich nicht mehr weiß, als was ich auf der Seite lese), ist es eine Möglichkeit, wenn Funktionalität ohne die Verzweigung (die Sinn macht basierend auf den Worten verzweigt, wenn;)). Ich weiß nicht mehr.

Danke Herr Google.

Ich hatte vor nicht allzu langer Zeit einen ternären Logiksimulator geschrieben, und diese Frage war für mich lebensfähig, da sie sich unmittelbar auf die Ausführungsgeschwindigkeit meines Interpreters auswirkt; Ich wurde aufgefordert, Tonnen und Tonnen von ternären Logikgattern so schnell wie möglich zu simulieren.

In einem binärcodierten ternären System ist ein Trit in zwei Bits gepackt. Das höchstwertige Bit bedeutet negativ und das niedrigstwertige Bit bedeutet positiv. Fall "11" sollte nicht auftreten, aber es muss richtig gehandhabt werden und als 0 bedroht werden.

Betrachte inline int bct_decoder( unsigned bctData ) function, die unser formatiertes Trit als reguläre Ganzzahl -1, 0 oder 1 zurückgeben soll; Wie ich gesehen habe, gibt es 4 Ansätze: Ich nannte sie "cond", "mod", "math" und "lut"; Lassen Sie uns sie untersuchen

First basiert auf jz | jnz und jl | jb bedingten Sprüngen, also cond. Seine Leistung ist überhaupt nicht gut, weil er sich auf einen Verzweigungsprädiktor stützt. Und noch schlimmer - es variiert, weil es unbekannt ist, ob es einen oder zwei Zweige a priori geben wird. Und hier ist ein Beispiel:

Dies ist die langsamste Version, es könnte im schlimmsten Fall 2 Verzweigungen enthalten, und dies ist etwas, bei dem die Binärlogik fehlschlägt. Auf meiner 3770k kostet es durchschnittlich 200MIPS auf Zufallsdaten. (Hier und danach - jeder Test ist Durchschnitt von 1000 Versuchen auf zufällig gefülltem 2mb-Datensatz)

Als nächstes verlässt man sich auf den Modulo-Operator und seine Geschwindigkeit liegt irgendwo zwischen dem ersten und dem dritten, ist aber definitiv schneller - 600 MIPS:

Der nächste ist der zweiglose Ansatz, der nur Mathematik, also Mathematik, beinhaltet; es wird überhaupt keine Sprunginstruktionen angenommen:

Das macht was soll und verhält sich wirklich toll. Zum Vergleich beträgt die Leistungsbewertung 1000 MIPS und ist 5-mal schneller als die verzweigte Version. Wahrscheinlich verzweigte Version wird aufgrund fehlender systemeigener 2-Bit-Int-Unterstützung verlangsamt. Aber in meiner Anwendung ist es eine ziemlich gute Version für sich.

Wenn das nicht genug ist, können wir weiter gehen und etwas Besonderes haben. Als nächstes wird der Ansatz der Lookup-Tabelle genannt:

In meinem Fall belegte ein Trit nur zwei Bits, also war die Tabelle nur 2b * 4 = 8 Bytes, und es war einen Versuch wert. Es passt in Cache und arbeitet blitzschnell bei 1400-1600 MIPS, hier ist meine Messgenauigkeit sinkt. Und das ist 1,5x Beschleunigung von schnellen mathematischen Ansatz. Das liegt daran, dass Sie nur ein vorberechnetes Ergebnis und eine einzelne AND Anweisung haben. Leider sind Caches klein und (wenn Ihre Indexlänge größer als einige Bits ist), können Sie sie einfach nicht verwenden.

Also ich glaube, ich habe deine Frage beantwortet, was könnte verzweigt / verzweigter Code sein. Die Antwort ist viel besser und mit detaillierten Beispielen, reale Anwendung und reale Leistungsmessungen Ergebnisse.