Betragsfunktion ohne branching

[starcow]

Weils jetzt wieder mal aktuell wurde und ich mir die Sache eigentlich schon länger anschauen wollte, habe ich mir jetzt die Zeit einfach genommen und die Quelle studiert, die Krishty damals vor Jahren verlinkt hatte (danke nochmals an der Stelle).

Dabei wurde das Thema ja eher durch Zufall gestreift - im Zusammenhang mit meinen Fragen zu Softwarepatenten.
Ursprünglicher Thread viewtopic.php?p=66488

Es geht darum, den Betrag einer Ganzzahl ohne branching zu ermitteln.
Krishty, du hattest in der Diskussion eine Technik dazu erwähnt:

Code: Alles auswählen

(x ^ 0x80000000) - 0x80000000

Ich vermute allerdings, dass du sie verwechselt hattest (ein anderer Trick vielleicht?).
Gemeint hattest du wohl Folgendes (laut deiner verlinkten Quelle https://graphics.stanford.edu/~seander/ ... IntegerAbs ):

Code: Alles auswählen

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

Patented variation:
(Der Patentversuch durch Sun Microsystems dürfte ungültig sein - siehe Link weiter oben)

Code: Alles auswählen

r = (v ^ mask) - mask;

Die ganze Idee setzt ja voraus, dass beim right shift auf signed ein arithmetischer und kein logischer Shift stattfindet - heisst, es müssen Bits entsprechend dem "Vorzeichenbit" nachgeschoben werden.
Ist v negativ, dann hat mask den Wert -1 (alle Bits sind 1).
Ist v positiv, dann hat mask den Wert 0.
Dieser Mechanismus ersetzt quasi das branching.

Doch ob bei right shift auf signed arithmetisch oder logisch geshiftet wird, ist ja bekanntlich Implementation-Defined Behavior - also abhängig vom Compiler (was die Quelle ja auch erwähnt).
In der Praxis dürfte dadurch die "Verwendbarkeit" der Technik ziemlich eingeschränkt sein (oder wie seht ihr das?).

Ich habe dann das Ganze anhand von 4-Bit Beispielen mal durchgerechnet, mit Augenmerk auf die Grenzfälle (4-Bit oder 32-Bit - das Konzept und die möglichen Probleme bleiben ja die selben).

1. Version

Code: Alles auswählen

r = (v + mask) ^ mask;

Im Falle von v = INT_MIN findet ein overflow bei der Addition mit mask statt. overflow, weil typ signed - und kein wrap-around wie bei unsigned. Folglich ist es ab hier UB.

4-Bit Beispiel
Erster Schritt: Addtion mit mask

Code: Alles auswählen

   1000  // 1000 ≙ -8
+  1111  // 1111 ≙ -1    overflow: (-8) + (-1) = -9
  -----
 1 0111  // overflow

Zweiter Schritt: XOR mit mask

Code: Alles auswählen

   0111  // 1000 ≙ 7
^  1111  // 1111 ≙ -1
  -----
   1000  // -8 ≙ 8 (unsigned)

Das Ergebnis wäre also "eigentlich" richtig, denn beim impliziten cast nach unsigned (r wurde als unsigned definiert), ist das Resultat 8.
Das Bitmuster bleibt (bei gleicher Bitbreite) von signed zu unsigned (und umgekehrt) ja stets das selbe.
Aus -8 wird also 8. Doch weil das Ganze durch die Addition bereits UB war, ist das Kind in den Brunnen gefallen.
In der Quelle wird das soweit auch erwähnt - doch weiter auch Folgendes:

Hai Jin complained that the result was signed, so when computing the abs of the most negative value, it was still negative.

Diese Aussage kann ich in dieser Form nicht nachvollziehen.

2. Version ("Patentversuch")

Code: Alles auswählen

r = (v ^ mask) - mask;

Tatsächlich hat diese Version genau die selbe Problematik. Es tritt ein overflow auf (weil signed), was UB ist.
Beide Versionen sind also gleichermassen UB.

4-Bit Beispiel
Erster Schritt: XOR mit mask

Code: Alles auswählen

   1000  // 1000 ≙ -8
^  1111  // 1111 ≙ -1
  -----
   0111  // 0111 ≙ 7

Zweiter Schritt: Subtraktion mit mask

Code: Alles auswählen

   0111  // 1000 ≙ 7
-  1111  // 1111 ≙ -1    overflow: 7 - (-1) = 7 + 1 = 8
  -----
   1000  // -8 ≙ 8 (unsigned)

Auch hier wäre allerdings das Ergebnis rein rechnerisch richtig. Aus -8 wird 8.

Ich glaube allerdings für beide Versionen eine Lösung gefunden zu haben, wodurch diese definiertes Verhalten aufweisen.

aus:

Code: Alles auswählen

int mask = v >> sizeof(int) * CHAR_BIT - 1;

wird:

Code: Alles auswählen

unsigned int mask = v >> sizeof(int) * CHAR_BIT - 1;

Das funktioniert, weil der implizite cast nach unsigned int erst nach dem bitshifting ausgeführt wird. Für den Ausdruck rechts ändert sich also nichts. Fand vorhin ein arithmetischer Shift statt, findet dieser noch immer statt.

Weiter passiert dann Folgendes:
Variante 1.

Code: Alles auswählen

r = (v + mask) ^ mask;

v ist signed, mask jetzt allerdings unsigned. Dadurch wird v garantiert zu unsigned promoted (Vgl. C Standard "übliche arithmetische Typumwandlungs-Hierarchie. unsigned int "dominiert" signed int).
Dadurch, das v nun zu unsigned int promoted wurde, tritt jetzt kein overflow, sondern ein wrap-around auf - was bekanntlich wohl definiert ist.

Variante 2.

Code: Alles auswählen

r = (v ^ mask) - mask;

Auch bei Bitwise Operations werden die üblichen arithmetischen Typumwandlungen vorgenommen. (signed int) ^ (unsigned int) - v wird zu unsigned int promoted.

Mit dieser Lösung müssten sich jetzt beide Varianten ebenbürtig sein.
Rechnerisch hat sich nichts geändert, doch das Ganze resultiert jetzt maximal in einem wrap-around und nicht in einem overflow.
Ein expliziter cast ist durch die Regeln der integer promotion nicht nötig.

Vielleicht ist sogar die Variante 1. einen kleinen Tick eleganter, da eine Addition und keine Subtraktion stattfindet.
Ausserdem käme Variante 1. aufgrund der operator precedence auch ohne Klammern aus.

Code: Alles auswählen

r = v + mask ^ mask;

Die Problematik, dass das Ganze aufgrund des right shifts auf signed Implemetation-Defined ist, wird man aber leider nicht los.

Ich hoffe meine Überlegungen stimmen und ich habe nichts übersehen!
Vielleicht sind euch ja noch weitere Details aufgefallen?

[Schrompf]

Ich habe es jetzt nicht im Detail nachvollzogen, aber soweit ich das beurteilen kann, sind Deine Ausführungen echt gut! Der Trick besteht darin, den Bitshift rechts auf signed anzuwenden, wodurch das Vorzeichenbit auf alle Bits der Maske repliziert wird. Right Shift auf signed ist aber UB bis C++23, wo sie das jetzt endlich mal zu IB geändert haben. Keine Ahnung, wie das bei ANSI-C aussieht. Der Overflow bei Addition ist für signed ebenso UB, ebenso bis C++23, hab ich irgendwo aufgeschnappt, aber das hast Du ja mit Addition als unsigned sauber umschifft.

Beides ist aber meiner Meinung nach nur als Lern-Beispiel geeignet, weil ein optimierender Compiler auch aus der plumpen v < 0 ? -v : v ein ConditionalMove kompiliert, und ohne die genauen Latenzen der Instructions geprüft zu haben, behaupte ich, dass das gleichwertig ist.

[Mirror]

Alle Achtung. ich wäre wegen dem Thema nicht auf die Idee gekommen das ganze so zu machen. Echt gut.

[Krishty]

Sorry, ich komme gerade nicht dazu, mich da durchzuarbeiten! Aber schonmal Respekt dafür, wie tief du dich einarbeitest!

[TomasRiker]

Eine andere Möglichkeit mit SSE: http://0x80.pl/notesen/2018-03-11-sse-abs-unsigned.html (hat den netten Nebeneffekt, dass man dann gleich 4 Beträge parallel berechnen kann)

[starcow]

Danke euch fürs Feedback! :-)
"Lernbeispiel" trifft es glaube ich ziemlich gut, da die Technik aus den von euch genannten Gründen wohl keine wirklichen Vorteile (mehr) bietet.

Right Shift auf signed ist aber UB bis C++23, wo sie das jetzt endlich mal zu IB geändert haben. Keine Ahnung, wie das bei ANSI-C aussieht..

Bist du sicher, dass du das nicht verwechselst?
cppreference.com ist der Meinung es sei (war immer) IB (https://en.cppreference.com/w/cpp/langu ... _operators)

In C war und ist es IB (laut Standard "ISO/IEC 9899 - Second edition - 1999-12-01"):

6.5.7 Bitwise shift operators, Abschnitt 5 (p. 84):
E1 >> E2
"If E1 has a signed type and a negative value, the resulting value is implementation-defined."

Fairerweise sollte man jetzt vielleicht noch ergänzen, dass bei den beiden Techniken UB nur dann eintritt, wenn v INT_MIN entspricht.
Jedoch ist:

Code: Alles auswählen

int v = INT_MIN;
unsigned a = -v; // UB

ohnehin bereits UB.
Deshalb hatte wohl auch der Author in der diskutierten Alternative den cast vor dem Vorzeichoperator "-" platziert.

Code: Alles auswählen

return v < 0 ? -(unsigned)v : v;

Interessant wäre noch die Frage, ob der Ausdruck

Code: Alles auswählen

-2147483648

Konsequent überall einer 8 Byte (long long) Konstante entspricht.
Tatsächlich scheint der Compiler nämlich zuerst die Zahlenkonstante ohne Vorzeichen zu interpretieren.
Da er dann erkennt, dass 2'147'483'648 nicht mehr mit 4 Byte (signed) dargestellt werden kann, promoted er sie anscheinend hoch zu long long.
Obwohl -2'147'483'648 eigentlich gerade noch in einem 4 Byte signed Platz gehabt hätte!

Code: Alles auswählen

printf("1) Die Konstante ist vom Typ: %s\n", _Generic(-2147483647, long long: "long long", int: "int", default: "unknown"));
printf("2) Die Konstante ist vom Typ: %s\n", _Generic(-2147483648, long long: "long long", int: "int", default: "unknown"));

Output (clang, gcc):
1) Die Konstante ist vom Typ: int
2) Die Konstante ist vom Typ: long long

[Krishty]

Schrompf verwechselt das sicher mit Left Shift ins Sign Bit – der ist/war UB weil er de facto einer Multiplikation entspricht, die das Ergebnis von positiv nach negativ überlaufen lassen würde.

[Schrompf]

Echt? Ich dachte immer, es wäre der Right Shift, weil da von der Architektur abhängig ist, was da oben reingeshifted kommt.

[Lord Delvin]

Echt? Ich dachte immer, es wäre der Right Shift, weil da von der Architektur abhängig ist, was da oben reingeshifted kommt.

Vom Typ; die Architektur sollte dafür zwei Instruktionen haben.

[Krishty]

Echt? Ich dachte immer, es wäre der Right Shift, weil da von der Architektur abhängig ist, was da oben reingeshifted kommt.

Vom Typ; die Architektur sollte dafür zwei Instruktionen haben.

Hat aber nicht jede. Es war ja nicht einmal Zweierkomplement garantiert! Deshalb hatten sie es halt der Implementierung überlassen. Der Typ tut nichts zur Sache weil wir über signed int sprechen.

————

Vllt tauglich als Referenz für die Diskussion (statt „ich dachte“): https://stackoverflow.com/questions/766 ... 1#76694991

Before C++20

Positive signed integer

Left shift: Shifted-out bits get discarded and the least significant bits are filled with zeros. If the shifted-out bits are not all zeros, the behavior is undefined.

Right shift: Shifted-out bits get discarded and the most significant bits are filled with zeros.

Negative signed integer

Left shift: Undefined behavior.

Right shift: Implementation defined. Usually for 2's complement systems, the shifted-out bits get discarded, and the most significant bits are filled with ones.

Unsigned integer

Left shift: Shifted-out bits get discarded and the least significant bits are filled with zeros.

Right shift: Shifted-out bits get discarded and the most significant bits are filled with zeros.

After C++20

Positive signed integer

Left shift: Shifted-out bits get discarded and the least significant bits are filled with zeros.

Right shift: Shifted-out bits get discarded and the most significant bits are filled with zeros.

Negative signed integer

Left shift: Shifted-out bits get discarded and the least significant bits are filled with zeros.

Right shift: Shifted-out bits get discarded, and the most significant bits are filled with ones.

Unsigned integer

Left shift: Shifted-out bits get discarded and the least significant bits are filled with zeros.

Right shift: Shifted-out bits get discarded and the most significant bits are filled with zeros.

In all cases, if the number of bits to shift(the right operand) is greater than or equal to the number of bits of the left operand after integer promotion, the behavior is undefined.

[dot]

Der Vollständigkeit halber:

C++17

The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is \(\mathrm{E1} \times 2^\mathrm{E2}\), reduced modulo one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and \(E1 \times 2^\mathrm{E2}\) is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of \(\mathrm{E1} / 2^\mathrm{E2}\). If E1 has a signed type and a negative value, the resulting value is implementation-defined.

(emphasis mine)

vs

C++aktuell

The value of E1 << E2 is the unique value congruent to \(\mathrm{E1} \times 2^\mathrm{E2}\) modulo \(2^N\), where \(N\) is the width of the type of the result.

The value of E1 >> E2 is \(\mathrm{E1} / 2^\mathrm{E2}\), rounded towards negative infinity.

Beachte: In C isses weiterhin wie früher…

[Schrompf]

Oh, Danke für die Klarstellung. Ich kann mich also inzwischen darauf verlassen, dass meine Maschine das tut, was ich von ihr erwarte, aber starcow muss weiter mit UB leben.

[dot]

Es sei auch darauf hingewiesen, dass gcc und clang für ein einfaches std::abs(x) das hier produzieren:

Code: Alles auswählen

blub(int):
        mov     eax, edi
        neg     eax
        cmovs   eax, edi
        ret

bzw. auf ARM

Code: Alles auswählen

blub(int):
        cmp     w0, #0
        cneg    w0, w0, mi
        ret

Ich bezweifle mal sehr stark, dass ein Vermeiden der Branch hier was bringt. Vermutlich ist eher sogar das Gegenteil der Fall…

In der Tat scheint es so zu sein, dass zumindest clang die ganze Hackerei durchschaut und in ein normales cmov rückführt, womit dann exakt der selbe Code rauskommt wie bei std::abs(x): https://godbolt.org/z/Wa6qhE81T

[Krishty]

Ähnliches Problem: Conditional Sign Extension without Branching.

[Schrompf]

He, schön. Irgendwie albern, auf diesem Niveau noch zu überlegen, aber irgendwie stellt mich sowas zufrieden.

[Krishty]

Da er an Oodle sitzt, gehe ich davon aus, dass es um die inneren Schleifen der Kompressionsalgorithmen geht, mit denen Spiele heutzutage ihre Archive packen. Das könnte also tatsächlich ausmachen, ob (aus der Luft gegriffen) das neue Call of Duty 10 Sekunden zu Laden braucht oder 9,5. Da kommt durchaus ein Bisschen Strom und Lebenszeit zusammen.

[Schrompf]

Ah, der Knilch. Ja, der darf sich darüber Gedanken machen. Bei mir isses nutzlos, seit ich Check24 verlassen habe.