Pointer Swap

Laik · 2. August 2021

Hallo an alle nochmal,

ich habe eine Frage zu folgendem Code, der zwei Pointer vertauscht.

C:

void tausche_intPtr(int **zeiger1, int **zeiger2){
    int *temp = *zeiger1;
    *zeiger2 = *zeiger1;
    *zeiger1 = temp;
}

Wieso muss es *temp sein?
Und in der letzte Zeile jedoch nur temp?

Irgendwie verwirren mich Zeiger auf Zeiger.

LG
Laik

Laik · 3. August 2021

Wobei wenn ich das richtig verstehe, ist temp ja einfach eine Kopie des Zeigers *zeiger1?

LG
Laik

Technipion · 3. August 2021

Laik hat gesagt.:
Wobei wenn ich das richtig verstehe, ist temp ja einfach eine Kopie des Zeigers *zeiger1?

Genau.

Im Grunde lautet der Pseudocode für eine Swap-Operation ja so:

Code:

funktion tausche(A, B):
    temp = A // sichere A in temp
    A = B    // überschreibe A mit B
    B = temp // überschreibe B mit der gesicherten Kopie von A

Genau den Code hast du vor dir, nur, dass er wegen der vielen Pointer etwas unübersichtlich wird. Aber es wird direkt viel klarer, wenn wir (testweise) einen Typ intp einführen, der einfach ein Zeiger auf int ist:

C:

typedef int *intp; // Typ intp ist Zeiger auf int

void tausche_intPtr(intp *zeiger1, intp *zeiger2){
    intp temp = *zeiger2; // intp = dereferenziere Zeiger auf intp
    *zeiger2 = *zeiger1;  // deref *intp = deref *intp
    *zeiger1 = temp;      // deref *intp = intp
}

Ich glaube das macht es verständlich.
Gruß Technipion

vfl_freak · 3. August 2021

Technipion hat gesagt.:
Ich glaube das macht es verständlich.

Nicht wirklich, da in der Signatur des ersten Beitrags jeweils 'Zeiger auf einen Zeiger' steht !!

EDIT: bearbeitet, da teilsweise Blödsin!!

Technipion · 3. August 2021

vfl_freak hat gesagt.:
Nicht wirklich, da in der Signatur des ersten Beitrags jeweils 'Zeiger auf einen Zeiger' steht !!

Genau. Und da @Laik wohl genau davon verwirrt war, habe ich aus den multidimensionalen Zeigern wieder eindimensionale gemacht, in der Hoffnung, dass dies den Code etwas leichter verdaubar macht.

Allerdings ist mir gerade aufgefallen, dass die Funktion tausche_intPtr noch einen Logikfehler enthält. In temp muss nämlich zeiger2 gepuffert werden! Habe das oben mal angepasst.

Gruß Technipion

Laik · 5. August 2021

Danke für eure Antworten.
Wie so oft, hatte ich da einen Denkfehler, danke für die schnelle Aufklärung.

Genau den Logikfehler hatte ich auch erst hinterher bemerkt.

LG
Laik

Zvoni · 23. August 2021

Technipion hat gesagt.:

Genau.

C:

typedef int *intp; // Typ intp ist Zeiger auf int

void tausche_intPtr(intp *zeiger1, intp *zeiger2){
    intp temp = *zeiger2; // intp = dereferenziere Zeiger auf intp
    *zeiger2 = *zeiger1;  // deref *intp = deref *intp
    *zeiger1 = temp;      // deref *intp = intp
}

Oder ohne temp-variable.
Funktioniert für Zeiger natürlich nur wenn *zeiger1 != *zeiger2

Code:

void tausche_intPtr(intp *zeiger1, intp *zeiger2)
{
    *zeiger1= *zeiger1 ^ *zeiger2;
    *zeiger2= *zeiger1 ^ *zeiger2;
    *zeiger1= *zeiger1 ^ *zeiger2;
}

Hier gefunden:
How to swap two numbers without using a temporary variable? - GeeksforGeeks

Technipion · 25. August 2021

Zvoni hat gesagt.:
Oder ohne temp-variable.
Funktioniert für Zeiger natürlich nur wenn *zeiger1 != *zeiger2

Ich hatte mich gefragt warum jemand - gerade wo diese Lösung ja auch noch einige Fallstricke enthält - sich so eine Methode ausdenken, bzw. benutzen, würde. Die einzig plausible Antwort für mich war dann erst mal: Performance. Aber mir kam es eigentlich nicht so vor, als wären die XOR-Operationen schneller als einfach eine temporäre Variable zu benutzen. Also bin ich dem mal auf den Grund gegangen.

Zunächst habe ich folgendes Programm entworfen:

C:

// swaptest.c

#include <stdlib.h>
#include <stdio.h>

#ifndef SWAPXOR
void tausche_intPtr(int **zeiger1, int **zeiger2){
    int *temp = *zeiger2;
    *zeiger2 = *zeiger1;
    *zeiger1 = temp;
}
#else
void tausche_intPtr(int **zeiger1, int **zeiger2)
{
    **zeiger1 = **zeiger1 ^ **zeiger2;
    **zeiger2 = **zeiger1 ^ **zeiger2;
    **zeiger1 = **zeiger1 ^ **zeiger2;
}
#endif

int main()
{
    int **A = (int **)malloc(sizeof(int *));
    int **B = (int **)malloc(sizeof(int *));
    
    *A = (int *)malloc(sizeof(int));
    *B = (int *)malloc(sizeof(int));
    
    **A = 3;
    **B = 7;
    
    printf("%d %d\n", **A, **B);
    
    tausche_intPtr(A, B);
    
    printf("%d %d\n", **A, **B);
}

Ich habe das Programm mit und ohne das Compilerflag -D SWAPXOR compiliert und getestet. Beide Versionen liefern korrekte Ergebnisse.

Dann habe ich mir vom GCC lesbaren Assembler-Code erzeugen lassen (wie hier gezeigt):

Bash:

$ gcc -S -fverbose-asm -g -O2 swaptest.c -o swaptest_tempvar.s
$ gcc -S -fverbose-asm -g -O2 -D SWAPXOR swaptest.c -o swaptest_xor.s
$ as -alhnd swaptest_tempvar.s > swaptest_tempvar.lst
$ as -alhnd swaptest_xor.s > swaptest_xor.lst

Die Dateien sind natürlich wegen Einbindung der Standardbibliothek ziemlich aufgebläht. Aber hier sind die wichtigen Ausschnitte:

Code:

***************************************
*** Auszug aus swaptest_tempvar.lst ***
***************************************

   5:swaptest.c    **** void tausche_intPtr(int **zeiger1, int **zeiger2){
  67                      .loc 1 5 50 view -0
  68                      .cfi_startproc
  69                      .loc 1 5 50 is_stmt 0 view .LVU1
  70 0000 F30F1EFA         endbr64   
   6:swaptest.c    ****     int *temp = *zeiger2;
  71                      .loc 1 6 5 is_stmt 1 view .LVU2
  72                  # swaptest.c:6:     int *temp = *zeiger2;
  73                      .loc 1 6 10 is_stmt 0 view .LVU3
  74 0004 488B06           movq    (%rsi), %rax    # *zeiger2_3(D), temp
  75                  .LVL1:
   7:swaptest.c    ****     *zeiger2 = *zeiger1;
  76                      .loc 1 7 5 is_stmt 1 view .LVU4
  77                  # swaptest.c:7:     *zeiger2 = *zeiger1;
  78                      .loc 1 7 16 is_stmt 0 view .LVU5
  79 0007 488B17           movq    (%rdi), %rdx    # *zeiger1_5(D), _1
  80                  # swaptest.c:7:     *zeiger2 = *zeiger1;
  81                      .loc 1 7 14 view .LVU6
  82 000a 488916           movq    %rdx, (%rsi)    # _1, *zeiger2_3(D)
   8:swaptest.c    ****     *zeiger1 = temp;
  83                      .loc 1 8 5 is_stmt 1 view .LVU7
  84                  # swaptest.c:8:     *zeiger1 = temp;
  85                      .loc 1 8 14 is_stmt 0 view .LVU8
  86 000d 488907           movq    %rax, (%rdi)    # temp, *zeiger1_5(D)
  87                  # swaptest.c:9: }
 
 
  ***********************************
  *** Auszug aus swaptest_xor.lst ***
  ***********************************
 
    11:swaptest.c    **** void tausche_intPtr(int **zeiger1, int **zeiger2)
  12:swaptest.c    **** {
  67                      .loc 1 12 1 view -0
  68                      .cfi_startproc
  69                      .loc 1 12 1 is_stmt 0 view .LVU1
  70 0000 F30F1EFA         endbr64   
  13:swaptest.c    ****     **zeiger1 = **zeiger1 ^ **zeiger2;
  71                      .loc 1 13 5 is_stmt 1 view .LVU2
  72                  # swaptest.c:13:     **zeiger1 = **zeiger1 ^ **zeiger2;
  73                      .loc 1 13 30 is_stmt 0 view .LVU3
  74 0004 488B0E           movq    (%rsi), %rcx    # *zeiger2_12(D), _3
  75                  # swaptest.c:13:     **zeiger1 = **zeiger1 ^ **zeiger2;
  76                      .loc 1 13 18 view .LVU4
  77 0007 488B17           movq    (%rdi), %rdx    # *zeiger1_11(D), _1
  78                  # swaptest.c:13:     **zeiger1 = **zeiger1 ^ **zeiger2;
  79                      .loc 1 13 27 view .LVU5
  80 000a 8B02             movl    (%rdx), %eax    # *_1, *_1
  81 000c 3301             xorl    (%rcx), %eax    # *_3, _5
  82                  # swaptest.c:13:     **zeiger1 = **zeiger1 ^ **zeiger2;
  83                      .loc 1 13 15 view .LVU6
  84 000e 8902             movl    %eax, (%rdx)    # _5, *_1
  14:swaptest.c    ****     **zeiger2 = **zeiger1 ^ **zeiger2;
  85                      .loc 1 14 5 is_stmt 1 view .LVU7
  86                  # swaptest.c:14:     **zeiger2 = **zeiger1 ^ **zeiger2;
  87                      .loc 1 14 27 is_stmt 0 view .LVU8
  88 0010 3301             xorl    (%rcx), %eax    # *_3, _7
  89                  # swaptest.c:14:     **zeiger2 = **zeiger1 ^ **zeiger2;
  90                      .loc 1 14 15 view .LVU9
  91 0012 8901             movl    %eax, (%rcx)    # _7, *_3
  15:swaptest.c    ****     **zeiger1 = **zeiger1 ^ **zeiger2;
  92                      .loc 1 15 5 is_stmt 1 view .LVU10
  93                  # swaptest.c:15:     **zeiger1 = **zeiger1 ^ **zeiger2;
  94                      .loc 1 15 27 is_stmt 0 view .LVU11
  95 0014 3102             xorl    %eax, (%rdx)    # _7, *_1
  96                  # swaptest.c:16: }

Interessant wird es, wenn man das ganze rein auf die Instruktionen kürzt:

Code:

// Version mit temporärer Variable:

   5:swaptest.c    **** void tausche_intPtr(int **zeiger1, int **zeiger2){
  70 0000 F30F1EFA         endbr64   
  74 0004 488B06           movq    (%rsi), %rax    # *zeiger2_3(D), temp
  79 0007 488B17           movq    (%rdi), %rdx    # *zeiger1_5(D), _1
  82 000a 488916           movq    %rdx, (%rsi)    # _1, *zeiger2_3(D)
  86 000d 488907           movq    %rax, (%rdi)    # temp, *zeiger1_5(D)
  87                  # swaptest.c:9: }


// Version mit XOR-Jongliererei:

  11:swaptest.c    **** void tausche_intPtr(int **zeiger1, int **zeiger2)
  12:swaptest.c    **** {
  70 0000 F30F1EFA         endbr64   
  74 0004 488B0E           movq    (%rsi), %rcx    # *zeiger2_12(D), _3
  77 0007 488B17           movq    (%rdi), %rdx    # *zeiger1_11(D), _1
  80 000a 8B02             movl    (%rdx), %eax    # *_1, *_1
  81 000c 3301             xorl    (%rcx), %eax    # *_3, _5
  84 000e 8902             movl    %eax, (%rdx)    # _5, *_1
  88 0010 3301             xorl    (%rcx), %eax    # *_3, _7
  91 0012 8901             movl    %eax, (%rcx)    # _7, *_3
  95 0014 3102             xorl    %eax, (%rdx)    # _7, *_1
  96                  # swaptest.c:16: }

Wie man sehen kann erzeugt der GCC für die "klassische" Version mit Puffervariable im Wesentlichen 4 movq (move quadword = 64 Bit) Instruktionen. Die Version mit dem XOR-Rechenkniff benötigt hingegen 8 Instruktionen: Ebenfalls 2 movq und dann noch 3 Durchläufe mit movl und xorl. Inwiefern hier die Branch-Prediction oder das Autovectoring der CPU greifen, bleibt bei dieser einfachen Analyse natürlich außen vor. Trotzdem würde ich mal vermuten, dass die klassische Version mit temporärer Variable spürbar schneller läuft.

Gruß Technipion

Zvoni · 31. August 2021

Technipion hat gesagt.:
Trotzdem würde ich mal vermuten, dass die klassische Version mit temporärer Variable spürbar schneller läuft.

Gruß Technipion

Könnte man ja einfach testen, indem man ein Array mit 100K oder 1M Elementen durch nen Sortier-Algo laufen lässt.
Der XOR-Swap funktioniert auch mit reinen Integers (Siehe auch den GfG-Link, beschreibt auch für Integers)

Technipion · 1. September 2021

Zvoni hat gesagt.:
Könnte man ja einfach testen, indem man ein Array mit 100K oder 1M Elementen durch nen Sortier-Algo laufen lässt.

Stimmt. Das wäre doch eine klasse Fingerübung für @Laik ...?

Pointer Swap

Laik

Grünschnabel

Laik

Grünschnabel

Technipion

Erfahrenes Mitglied

vfl_freak

Technipion

Erfahrenes Mitglied

Laik

Grünschnabel

Zvoni

Erfahrenes Mitglied

Technipion

Erfahrenes Mitglied

Zvoni

Erfahrenes Mitglied

Technipion

Erfahrenes Mitglied

Neue Beiträge