Was sich gut in Hardware giessen lässt ist noch lange nicht gut für C.
Eine herrliches Schaustück, wie man durch Kontextwechsel und inkorrekte Abstraktion den reinen Blödsinn verzapfen kann und sich auch noch grandios dabei vorkommt.
Zwei Werte vertauschen. Gut und schön, braucht man immer wieder. Die Zwischenvariable ist unästethisch. Naja, Ansichtssache[1].
| Frage: | Wie vertauscht man in C den Inhalt zweier Variablen ohne Verwendung einer temporären Variablen. |
|---|---|
| Antwort: | Nicht rot werden! Unter irgend einem Vorwand das Gebäude verlassen und bitterlich weinend nach einem neuen Arbeitgeber suchen. Sollte das wegen Kind und Kegel nicht möglich sein, unbedingt darauf achten, dass es dafür keine lebenden Zeugen gibt. |
| Frage: | Glaubt denn wirklich irgendjemand, dass das einen Sinn hat? |
| Antwort: | Eine Suche auf google.com mit dem Suchausdruck “swap variables with xor” ist da recht aufschlussreich :). Glücklicherweise sind die informierten Stimmen in der Überzahl, aber die uninformierten sind auf der ersten Seite. |
Und in der Hardware schaut das auf Signalebene sooo toll aus:
X ---+----XOR--> Q1 (==Y)
\ /
XOR
/ \
Y ---+----XOR--> Q2 (==X)
| X | Y | X^Y | Q1 = X^(X^Y) | Q2 = Y^(X^Y) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
Yep. Und das ist es auch – in Hardware – Leitung rein / Leitung raus – kein Trick – kein doppelter Boden – Punkt.
Und das war auch schon die eine von zwei echten Lösungen, die tatsächlich keine weitere Hilfestellung benötigt und die in sich geschlossen ist.
Man kann sich auch noch vorstellen, dass sowas Sinn machen kann, um eine Drahtbrücke zu vermeiden (Induktive/Kapazitäre Effekte und Signallaufzeiten in der HF-Magie :)).
Ansonsten würde ja wohl jeder die einfache Lösung vorziehen :)
X ---+ +---> Y
\ /
/
/ \
Y ---+ +--> X
Diese hübsche Vermischung von analogen Signalträgern (die sich beliebig aufspalten lassen) und digitaler Verschaltung führt im Softwarebereich zu einem wahrlich grotesken Schauspiel von “Ich auch! Ich auch!”
Das blödeste Argument, das im Softwarebereich angeführt wird ist die angebliche Schnelligkeit.
Die einzig gültige Softwareproblemstellung die mit XOR zu lösen ist, ist gleichzeitig ein API Designfehler, den man aber vielleicht nicht unbedingt vermeiden kann. (Siehe auch lokales Exzerpt von http://www.piclist.com/techref/microchip/math/bit/swap.htm).
Eine Assemblerroutine bekommt zwei Werte in zwei Registern. Dummerweise hat eines der Register Spezialeigenschaften, die benötigt werden, um den zweiten Wert zu behandeln.
Das Szenario sieht so aus:
Register Inhalt Initialisierung
R1 WERT Kann als indirekter Zeiger dienen
R2 STAPELZEIGER Kann NICHT als indirekter Zeiger dienen
Hier gibt es nur eine einzige Lösung:
xor R2 |-> R1
xor R1 |-> R2
xor R2 |-> R1
mov R2 |-> (R1)
Wenn die Bedingungen gelockert werden, ergibt sich eine Reihe weiterer Varianten.
Wenn ein temporäres Register verwendet werden darf, dann ist die Lösung:
mov R1 |-> R3
mov R2 |-> R1
mov R3 |-> R2
mov R2 |-> (R1)
mit Sicherheit genauso schnell, je nach Prozessor sogar schneller.
Lediglich PUSH/POP Varianten, die Speicherzugriffe benötigen, hätten noch eine Chance, als langsamer abgestempelt zu werden:
push R1
mov R2 |-> R1
pop R2
mov R2 |-> (R1)
Aber das gilt nur für CPUs ohne Primary Cache :).
Aber am schnellsten ist mit Sicherheit die Lösung, das API anzupassen, sodass die Register richtig belegt sind:
mov R2 |-> (R1)
Wenn es darum geht, zwei SPEICHERSTELLEN zu vertauschen, dann wird es so richtig grandios schwachsinnig, selbst wenn der Prozessor Memory-Memory-Operationen kann. Denn Speicherzugriffe sind teuer, wenn kein Cache da ist
XOR-FASSSSSSST (aber praktisch unmöglich, da die meisten CPU’s sowas nicht haben :))
xor MEM2 |-> MEM1 ; 2 SP.Zugriffe
xor MEM1 |-> MEM2 ; 2 SP.Zugriffe
xor MEM2 |-> MEM1 ; 2 SP.Zugriffe
XOR-OPTIMIZED
push R1 ; 1 SP.Zugriff
push R2 ; 1 SP.Zugriff
mov MEM1 |-> R1 ; 1 SP.Zugriff
mov MEM2 |-> R2 ; 1 SP.Zugriff
xor R2 |-> R1
xor R1 |-> R2
xor R2 |-> R1
mov R1 |-> MEM1 ; 1 SP.Zugriff
mov R2 |-> MEM2 ; 1 SP.Zugriff
pop R2 ; 1 SP.Zugriff
pop R1 ; 1 SP.Zugriff
PLAIN-SWAP
push R1 ; 1 SP.Zugriff
push R2 ; 1 SP.Zugriff
mov MEM1 |-> R1 ; 1 SP.Zugriff
mov MEM2 |-> R2 ; 1 SP.Zugriff
mov R1 |-> MEM2 ; 1 SP.Zugriff
mov R2 |-> MEM1 ; 1 SP.Zugriff
pop R2 ; 1 SP.Zugriff
pop R1 ; 1 SP.Zugriff
Selbst Intel-CPU’s haben zwei Register, die vom Compiler als Scratch behandelt werden, d.h. sie werden üblicherweise nicht gesichert ax, dx).
Damit ergibt sich als optimalste Lösung
PLAIN-SWAP
mov MEM1 |-> R1 ; 1 SP.Zugriff
mov MEM2 |-> R2 ; 1 SP.Zugriff
mov R1 |-> MEM2 ; 1 SP.Zugriff
mov R2 |-> MEM1 ; 1 SP.Zugriff
Und die Visual Basic Dumpfbacken müssen natürlich auch plärren (siehe lokale Kopie von dead link http://www.pinnaclepublishing.com/VB/VBmag.nsf/0/15D2712EB6378291852568D8006AFFEE):
“Here’s a quick tip. I think the following code provides a good alternative that’s both faster and uses less memory than the usual method of declaring a temporary variable and using that to swap the variables.
Public Sub SwapLong(ByRef lngFirst As Long, ByRef lngSecond As Long) lngFirst = lngFirst Xor lngSecond lngSecond= lngFirst Xor lngSecond lngFirst = lngFirst Xor lngSecond End Sub"
Die Alternative:
Public Sub SwapLong(ByRef lngFirst As Long, ByRef lngSecond As Long)
Temp = lngFirst
lngFirst = lngSecond
lngSecond = Temp
End Sub
Also, wie macht’s denn der Interpreter so im allgemeinen?
- Zuweisung::
- Variable suchen Expression auswerten Wert zuweisen
- Expression == Variable::
- Variable suchen Wert auslesen
- Expression == ( E1 Xor E2 )::
- E1 auswerten E2 auswerten Werte verknüpfen (das temporär angelegte) Ergebnis liefern
Variable lngFirst suchen
Variable lngFirst suchen
Wert auslesen
Variable lngSecond suchen
Wert auslesen
Werte verknüpfen (und hier haben wir doch eine temporäre Variable :))
Wert zuweisen
Variable lngSecond suchen
Variable lngFirst suchen
Wert auslesen
Variable lngSecond suchen
Wert auslesen
Werte verknüpfen (und hier haben wir doch eine temporäre Variable :))
Wert zuweisen
Variable lngFirst suchen
Variable lngFirst suchen
Wert auslesen
Variable lngSecond suchen
Wert auslesen
Werte verknüpfen (und hier haben wir doch eine temporäre Variable :))
Wert zuweisen
Temp anlegen (Und das soll jetzt sooo lange brauchen und sooo viel
Speicher fressen ?:))
Variable lngFirst suchen
Wert auslesen
Wert zuweisen
Variable lngFirst suchen
Variable lngSecond suchen
Wert auslesen
Wert zuweisen
Variable lngSecond suchen
Variable Temp suchen
Wert auslesen
Wert zuweisen
Das ist jetzt schon lächerlich, oder nicht? :)
Tja, und in C :)))
Bei Speicherzugriffen gilt das gleiche wie für Assembler.
Also tauschen wir mal nur zwei Variablen aus, die weder aus dem Speicher kommen, noch in den Speicher gehen …
{
int erste = 55aa;
int zweite = ff00;
result = erste * zweite;
/* Und jetzt der grosse Austausch! */
result = zweite * erste;
}
Ja, ja das allseits beliebte XOR …
| a | b | a’ == ( a xor b ) | b’ == a’ xor b | a’ xor b’ |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 |
Fein.
a' = a xor b // a enthält nun a'
b' = a' xor b
a = a' xor b'
Oder:
a ^= b;
b ^= a;
a ^= b;
Na, wenn wir schon dabei sind …
a ^= ( b ^= ( a ^= b ));
So. Jetzt kann’s mit Sicherheit keiner mehr lesen, aber wenn’s in einer Zeile steht, dann muss es wohl schneller sein als der Standard-Dreizeiler ….
c = a;
a = b;
b = c;
Also, für so einen hochoptimierten Algrithmus lohnt sich mit Sicherheit ein wenig Inline-Assembler. Portabilität muss ja nicht immer gleich die höchste Priorität haben …
Intel: PPC:
movl a,%eax lwz 0,a@l(29)
movl b,%edx lwz 9,b@l(28)
xorl %edx,%eax xor 0,0,9
xorl %eax,%edx xor 9,9,0
xorl %edx,%eax xor 0,0,9
movl %eax,a stw 0,a@l(29)
movl %edx,b stw 9,b@l(28)
Da können wir aber noch ein wenig feilen …
Intel: PPC:
movl a,%eax lwz 0,a@l(29)
movl b,%edx lwz 9,b@l(28)
movl %edx,a stw 9,a@l(29)
movl %eax,b stw 0,b@l(28)
Oder bekommt’s der Kompiler besser hin? (Siehe vswap.c).
Also schau ‘mer mal (mit volatile und verschiedenen Optimierungen):
XOR1 -O0: XOR2 -O0: SWAP -O0:
movl a,%eax movl a,%eax movl a,%eax
movl b,%edx movl b,%edx movl %eax,-4(%ebp)
xorl %edx,%eax xorl %edx,%eax movl b,%eax
movl %eax,a movl %eax,a movl %eax,a
movl a,%eax movl b,%eax movl -4(%ebp),%eax
movl b,%edx movl a,%edx movl %eax,b
xorl %edx,%eax xorl %edx,%eax
movl %eax,b movl %eax,b
movl b,%eax movl a,%eax
movl a,%edx movl b,%edx
xorl %edx,%eax xorl %edx,%eax
movl %eax,a movl %eax,a
XOR1 -Ox: XOR2 -Ox: SWAP -Ox:
movl a,%eax movl a,%eax movl a,%edx
movl b,%edx movl b,%edx movl b,%eax
xorl %edx,%eax xorl %edx,%eax movl %eax,a
movl %eax,a movl %eax,a movl %edx,b
movl a,%edx movl b,%eax
movl b,%eax movl a,%edx
xorl %edx,%eax xorl %edx,%eax
movl %eax,b movl %eax,b
movl b,%edx movl a,%eax
movl a,%eax movl b,%edx
xorl %edx,%eax xorl %edx,%eax
movl %eax,a movl %eax,a
Na so ein Mist :(. Wenn das Pointer wären und sich wirklich eins der Dinger zwischendrin ändert, dann geht das mit dem XOR voll daneben. Der Compiler ist ja wirklich doof.
Hmm, dann halt ohne volatile … (Kann man ja auch weg-casten! Dann weiss auch gleich jeder, dass wir eigentlich nur tauschen wollen. Und dass wir jetzt ZWEI temporäre Variablen brauchen soll uns auch nicht weiter stören, weil der Algorithmus ja sooo schööön ist :))
XOR1 -O0: XOR2 -O0: SWAP -O0:
movl a,%eax movl b,%eax movl a,%eax
xorl b,%eax xorl %eax,a movl %eax,-4(%ebp)
movl %eax,%edx movl a,%eax movl b,%eax
movl %edx,a xorl %eax,b movl %eax,a
movl %edx,%eax movl b,%eax movl -4(%ebp),%eax
xorl b,%eax xorl %eax,a movl %eax,b
movl %eax,%edx
movl %edx,b
xorl %edx,a
Schön! mit -O0 haben wir aber jetzt einen gewaltigen Vorteil! ( Na gut, man muss auch noch wissen, dass es der Compiler schön einfach notiert haben will. )
XOR1 -Ox: XOR2 -Ox: SWAP -Ox:
movl a,%edx movl a,%edx movl a,%eax
xorl b,%edx xorl b,%edx movl b,%edx
movl a,%eax movl a,%eax movl %edx,a
movl %eax,b movl %eax,b movl %eax,b
xorl %eax,%edx xorl %eax,%edx
movl %edx,a movl %edx,a
Und mit Optimierung schon wieder nicht, weil der blöde Compiler nicht kapiert, dass wir nur zwei Variablen tauschen wollen :(. Wenn er doch schon merkt, dass das eine XOR unnötig ist – warum merkt er denn das zweite nicht?
Herr im Himmel! Das kann doch nur an dem blöden Intel-Prozessor liegen, weil der keine Memory-Memory-Operationen kann.
Wie sieht’s denn da mit dem PPC aus? (Die volatile-Version wollen wir glaub’ ich nicht sehen …)
XOR1 -Ox: XOR2 -Ox: SWAP -Ox:
lis 9,a@ha lis 9,a@ha lis 9,a@ha
lis 11,a@ha lis 11,a@ha lwz 0,a@l(9)
lis 10,b@ha lis 10,b@ha stw 0,16(31)
lis 8,b@ha lwz 0,a@l(11) lis 9,a@ha
lis 7,a@ha lwz 11,b@l(10) lis 11,b@ha
lis 6,a@ha xor 0,0,11 lwz 0,b@l(11)
lis 5,b@ha stw 0,a@l(9) stw 0,a@l(9)
lwz 0,a@l(6) lis 9,b@ha lis 9,b@ha
lwz 5,b@l(5) lis 11,b@ha lwz 0,16(31)
xor 6,0,5 lis 10,a@ha stw 0,b@l(9)
mr 0,6 lwz 0,b@l(11)
stw 0,a@l(7) lwz 11,a@l(10)
lwz 7,b@l(8) xor 0,0,11
xor 8,0,7 stw 0,b@l(9)
mr 0,8 lis 9,a@ha
stw 0,b@l(10) lis 11,a@ha
lwz 11,a@l(11) lis 10,b@ha
xor 0,11,0 lwz 0,a@l(11)
stw 0,a@l(9) lwz 11,b@l(10)
xor 0,0,11
stw 0,a@l(9)
Ach verdammt. Jetzt ist der -O0 Vorteil vom Intel-Prozessor hin :(. Na macht nix, wir benutzen halt einen #define auf den Prozessor, um die jeweils optimalere Variante zu verwenden :).
XOR1 -Ox: XOR2 -Ox: SWAP -Ox:
lwz 9,b@l(28) lwz 9,b@l(28) lwz 6,a@l(29)
lwz 0,a@l(29) lwz 0,a@l(29) lwz 5,b@l(28)
xor 0,0,9 xor 0,0,9 stw 5,a@l(29)
xor 9,9,0 xor 9,9,0 stw 6,b@l(28)
xor 0,0,9 xor 0,0,9
stw 9,b@l(28) stw 9,b@l(28)
stw 0,a@l(29) stw 0,a@l(29)
Hmm. Der PPC hat offensichtlich auch keine Memory-Memory-Operationen :(. (Einen HPPA hätt ich noch anzubieten. Aber der ist auch ein RISC :)).
Also wenn ich mir das so anschaue, glaube ich, dass die Compiler- Schreiber noch ordentlich ran müssen, bevor sie behaupten können, sie wären in der Lage C-Code fast wie mit der Hand optimieren zu können :).
PS: So geht’s übrigens auch …
b = ( a ^ b ) ^ ( a = b );… jedenfalls meistens
:)[2].Nur der saudumme ANSI-Standard sagt, dass der Compiler-Hersteller bei kommutativen Operationen die Reihenfolge der Auswertung ändern darf. Und wenn er das wirklich mal macht (SGI Compiler mit -n32!), dann wird’s im Speicher wenigstens schön einheitlich:
b = ( a = b ) ^ ( a ^ b );
PPS: Die Ausgabe des Progrämmchens …
--init-- a: 0x55aa55aa b: 0xff00ff00
x: a ^= ( b^= ( a ^= b )); res: a: 0xff00ff00 b: 0x55aa55aa
x: ((int) a ) ^= (((int) b )^= (((int) a ) ^= ((int) b ))); res: a: 0x55aa55aa b: 0xff00ff00
x: c ^= ( d^= ( c ^= d )); res: a: 0xff00ff00 b: 0x55aa55aa
x: a ^= b; b ^= a; a ^= b; res: a: 0x55aa55aa b: 0xff00ff00
x: c = a; a = b; b = c; res: a: 0xff00ff00 b: 0x55aa55aa
x: b = ( a ^ b ) ^ ( a = b ); res: a: 0x55aa55aa b: 0xff00ff00
x: b = ( a = b ) ^ ( a ^ b ); res: a: 0xff00ff00 b: 0xff00ff00
PPPS:
Und den Schwachsinn kann man auch noch des Langen und des Breiten im Internet nachlesen :))))))))))))) (Siehe lokale Kopie von dead link http://www.con.wesleyan.edu/~eric/cpp-tips/xor-swap.html).
Vor allen Dingen:
“Using this as an inline function, where A and B are references to integers, increased my quicksort implementation by a lot (several tenths)”
| [1] | Mit Macro gehts auch schöner … Siehe vswap-macro.c |
| [2] | Zumindest kommt der beste XOR Assembler dabei raus (4 Speicherzugriffe). Und beim PPC merkt der Compiler sogar endlich, was gespielt wird! Intel: PPC:
movl b,%edx lwz 6,a@l(26)
movl %edx,%eax lwz 5,b@l(27)
xorl a,%eax stw 6,b@l(27)
movl %edx,a stw 5,a@l(26)
xorl %edx,%eax
movl %eax,b
|