Variablenwerte tauschen ohne Verwendung einer Zwischenvariablen

Author: Wolfgang Scherer

Contents

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].

Bewerbungsgespräch

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 :).

http://www.google.de/search?q=swap+variables+with+xor&hl=de&meta=

Glücklicherweise sind die informierten Stimmen in der Überzahl, aber die uninformierten sind auf der ersten Seite.

Hardware

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!"

Software

Das blödeste Argument, das im Softwarebereich angeführt wird ist die angebliche Schnelligkeit.

Assembler

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
  1. Der Wert in R1 muss an die Speicherstelle gelegt werden, auf die R2 zeigt.
  2. Einen XCHG-Befehl gibt es nicht.
  3. Es dürfen keine anderen Register überschrieben werden.
  4. Der Stapel darf nicht verwendet werden.

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

Interpreter

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

XOR Lösung

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

NORMALE LÖSUNG

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? :)

Compiler

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;
}

Details

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

Copyright

Copyright (C) 2017, Wolfgang Scherer, <Wolfgang.Scherer@gmx.de>. See the document source for conditions of use under the GNU Free Documentation License.