Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?



  • Hi(gh)!

    Abgesehen davon, dass es dafür eigene Funktionen in string.h gibt... Goll/Grüner/Wiese vergleichen in "C als erste Programmiersprache" (1999er Auflage) auf den Seiten 209 bis 211 das Kopieren eines Strings mittels Arrayelementen:

    #include <stdio.h>
    
    int main(void)
    {
      char alpha[30]="zu kopierender String";
      char beta[30]="";
      
      int lv=0;
      while (alpha[lv] != '\0')
      {
        beta[lv] = alpha[lv];
        lv++;
      }
      
      // printf("String beta: %s\n", beta);
      
      return 0;
    }
    

    und mittels Zeigerarithmetik:

    #include <stdio.h>
    
    
    int main(void)
    {
      char alpha[30]="zu kopierender String";
      char beta[30]="";
      char* ptralpha = alpha;
      char* ptrbeta = beta;
      
      while (*ptralpha != '\0') 
      {
        *ptrbeta = *ptralpha;
        ptralpha++;
        ptrbeta++;
      }
      *ptrbeta = '\0';
      
      // printf("String beta: %s\n", beta);
      
      return 0;
    }
    
    

    Da wollte ich doch mal überprüfen, ob die Zeiger-Version irgendeinen Geschwindigkeitsvorteil gegenüber der Arrayelemente-Version bietet und baute mir ein primitives Benchmark-Programm für die bash-Shell (die Zeitmessungs-Routine hatte ich aus einem älteren Skript übernommen, sie ist für die kurzen Rechenzeiten, wie sie hier vorkommen, definitiv Overkill):

    timesum=0
    loop=100
    
    for a in $(seq 1 $loop)
    do
      start=$(date +%s.%N)
    
      for i in $(seq 1 10000)
      do
        ./stringcopy5
      done
    
      end=$(date +%s.%N)
      time_elapsed=`echo "scale=9 ; $end-$start" | bc`
      timesum=`echo "scale=9 ; $timesum+$time_elapsed" | bc`
    done
      
      average=`echo "scale=9 ; $timesum/$loop" | bc`
    
      fract=`echo "scale=9 ; $average/86400.000" | bc`
      days=`echo "scale=0 ; $fract/1" | bc`
      rest=`echo "scale=9 ; $fract-$days" | bc`
      fract=`echo "scale=9 ; $rest*24.000" | bc`
      hours=`echo "scale=0 ; $fract/1" | bc`
      rest=`echo "scale=9 ; $fract-$hours" | bc`
      fract=`echo "scale=9 ; $rest*60.000" | bc`
      minutes=`echo "scale=0 ; $fract/1" | bc`
      rest=`echo "scale=9 ; $fract-$minutes" | bc`
      seconds=`echo "scale=9 ; $rest*60.000" | bc`
    
    
      echo -n "Benötigte Zeit: "
      if [ $days -gt 0 ]
      then
        echo -n $days
        if [ $days -gt 1 ]
        then
          echo -n " Tage, "
        else
          echo -n " Tag, "
        fi
      fi
      if [ $hours -gt 0 ]
      then
        echo -n $hours
        if [ $hours -gt 1 ]
        then
          echo -n " Stunden, "
        else
          echo -n " Stunde, "
        fi
      fi
      if [ $minutes -gt 0 ]
      then
        echo -n $minutes
        if [ $minutes -gt 1 ]
        then
          echo -n " Minuten, "
        else
          echo -n " Minute, "
        fi
      fi
      echo $seconds" Sekunden."
    
    

    Aber was stellte ich fest: die Durchschnitts-Laufzeit aus 100 Programmläufen zu je 10000 String-Kopien beträgt mit Arrayelementen 21,051, mit Zeigern 21,286 Sekunden (auf Millisekunden gerundet)! Kommt der Vor- oder Nachteil von Zeigerarithmetik (beim Kopieren von Strings) erst bei wesentlich komplexeren Operationen zum Tragen - oder gibt es gar keinen nennenswerten Vor- oder Nachteil? Falls letzteres, wieso dann überhaupt Zeigerarithmetik? Nur als stilistisches Erkennungszeichen für professionelle Programmierkunst?

    Bis bald im Khyberspace!

    Yadgar


  • Mod

    Die Zeigerarithmetik ist halt pro Durchlauf eine Addition weniger (denn ptr[i] ist kurz für *(ptr + i)). Zumindest in der Theorie. In der Praxis wird dir jeder Compiler diese simplen Schleifen zu etwas optimieren, das nicht mehr viel mit dem zu tun hat, was du im Code stehen hast.

    Ich muss jedoch zugeben, dass ich etwas überrascht bin, dass die verschiedenen Schreibweisen nicht beim exakt gleichen Maschinencode enden. Vermutlich wegen irgendwelcher obskuren Sonderfälle vonwegen Überläufen, etc.

    Clang macht deine beiden Versionen zu fast identischen Anweisungen, aber in unterschiedlicher Reihenfolge. Aber für die "übliche" Kompaktschreibweise (while((*ptrbeta++ = *ptralpha++));) erzeugt er nochmals deutlich anderen (und besseren) Code.

    GCC macht aus allen Versionen komplett unterschiedliche Maschinenprogramme.

    Es ist zwar ein schlechtes Maß für Codeeffizienz, aber zumindest eine ungefähre Orientierung: Bei Clang ist der innere Loop deiner Versionen 5 Anweisungen, der innere Loop der Kompaktschreibweise aber nur 4 Anweisungen. Bei GCC ist deine Indexversion 4 Anweisungen, ebenso die Kompaktversion, aber deine Zeigerarithmetikversion ist 5 Anweisungen.

    Zum Herumspielen:
    https://godbolt.org/g/mLPFDc



  • Wer misst misst Mist.

    1. einen Prozess zu starten dauert um Größenordnungen länger, als 20 Zeichen im Speicher zu kopieren
    2. wenn du den Optimizer nicht eingeschaltet hast, sind die Ergebnisse witzlos
    3. wenn du den Optimizer eingeschaltet hast, wird der gesamte Kopiervorgang wegoptimiert
    4. ich vermute, dass ein Optimizer in einem echten Programm für beide Varianten den gleichen Code erzeugt


  • @yadgar sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Kommt der Vor- oder Nachteil von Zeigerarithmetik (beim Kopieren von Strings) erst bei wesentlich komplexeren Operationen zum Tragen - oder gibt es gar keinen nennenswerten Vor- oder Nachteil?

    ptr[N] ist dasselbe wie *(ptr + N). Da gibt es keine Magie, die irgendwas schneller macht.

    @yadgar sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Falls letzteres, wieso dann überhaupt Zeigerarithmetik?

    Man benutzt Zeiger, wenn man Zeiger benutzen muss.



  • @swordfish sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Man benutzt Zeiger, wenn man Zeiger benutzen muss.

    Genau, ein Mann muss tun, was ein Mann tun muss (John Wayne)... ratsch ratsch klick PLAMM! PLAMM! PLAMM!

    Nee, ernsthaft - das hört sich so an, als sollte man Zeigerarithmetik nach Möglichkeit vermeiden und nur verwenden, wenn es gar nicht anders geht...



  • @yadgar sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Nee, ernsthaft - das hört sich so an, als sollte man Zeigerarithmetik nach Möglichkeit vermeiden und nur verwenden, wenn es gar nicht anders geht...

    👌


  • Mod

    @yadgar sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Nee, ernsthaft - das hört sich so an, als sollte man Zeigerarithmetik nach Möglichkeit vermeiden und nur verwenden, wenn es gar nicht anders geht...

    Das ist aber nicht richtig. Mit der Zeigerarithmetik kann man weniger machen als mit der Indexschreibweise. Die Mächtigkeit der Indexschreibweise kommt aber mit Kosten. Wie ich schon erklärt habe, hat es versteckte Additionen. Wenn man diese Mächtigkeit also nicht braucht (Paradebeispiel: Schritt für Schritt durch ein Array gehen), dann drückt man mit der Zeigervariante viel besser die eigenen Absichten aus und macht dem Compiler Optimierungen leichter. Entsprechend war die kompakt geschriebene Variante des Codes (aka: Wie man das normalerweise schreibt) sicherlich die schnellste aller gezeigten Varianten, wie man am Maschinencode sehen konnte.



  • @seppj sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Mit der Zeigerarithmetik kann man weniger machen als mit der Indexschreibweise.

    ??



  • Hi(gh)!

    @manni66 sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Wer misst misst Mist.

    1. einen Prozess zu starten dauert um Größenordnungen länger, als 20 Zeichen im Speicher zu kopieren
    2. wenn du den Optimizer nicht eingeschaltet hast, sind die Ergebnisse witzlos
    3. wenn du den Optimizer eingeschaltet hast, wird der gesamte Kopiervorgang wegoptimiert
    4. ich vermute, dass ein Optimizer in einem echten Programm für beide Varianten den gleichen Code erzeugt

    O.k., ich habe die Version mit Arrayindizes und die mit Zeigerarithmetik jeweils mit oder ohne Optimizer (-O3) laufen lassen, hier die gemittelten Werte aus jeweils 100 Läufen à 10000 Stringkopien:

    g++:

    stringcopy: 21.0514464 s
    stringcopy2: 21.076848 s
    stringcopy3: 21.0497174 s
    stringcopy4: 21.285504 s
    stringcopy5: 22.0465152 s

    gcc:

    stringcopy: 16.1379648 s
    stringcopy4: 15.7963392 s

    gcc -O3:

    stringcopy: 15.8974272 s
    stringcopy4: 14.45256 s

    Beim einfachen Kopieren von Strings scheint der Optimizer nicht viel zu bringen, sehr wohl aber das Kompilieren als nativen C-Code im Gegensatz zu C++!

    Bis bald im Khyberspace!

    Yadgar



  • @manni66 sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Wer misst misst Mist.

    1. einen Prozess zu starten dauert um Größenordnungen länger, als 20 Zeichen im Speicher zu kopieren

    Du misst, wie lange es dauert, einen Prozess z starten. Ein C++ Programm lädt halt noch eine weitere Bibliothek.


  • Mod

    Ich habe es mal mit einem richtigen Benchmark gemessen. Leider habe ich nur einen uralten GCC 5.4 auf diesem Rechner. Getestet habe ich:

    void indexbasiert(const char* alpha, char *beta)  // index
    {
      int lv=0;
      while (alpha[lv] != '\0')
        {
          beta[lv] = alpha[lv];
          lv++;
        }
      beta[lv] = '\0';
    }
    
    void zeigerarithmetik(const char* ptralpha, char *ptrbeta)  // pointer
    {
      while (*ptralpha != '\0')
        {
          *ptrbeta = *ptralpha;
          ptralpha++;
          ptrbeta++;
        }
      *ptrbeta = '\0';
    }
    
    void uebliche_schreibweise(const char* ptralpha, char *ptrbeta)  // kompakt
    {
      while((*ptrbeta++ = *ptralpha++));
    }
    

    und das normale strcpy aus string.h

    Gemacht hat mein GCC 5.4 bei O3 daraus:

    index:
            movzbl  (%rdi), %edx
            xorl    %eax, %eax
            testb   %dl, %dl
            je      .L3
    .L4:
            movb    %dl, (%rsi,%rax)
            addq    $1, %rax
            movzbl  (%rdi,%rax), %edx
            testb   %dl, %dl
            jne     .L4
    .L3:
            movb    $0, (%rsi,%rax)
            ret
    
    pointer:
           jmp     .L15
    .L10:
            movb    %al, (%rsi)
            addq    $1, %rdi
            addq    $1, %rsi
    .L15:
            movzbl  (%rdi), %eax
            testb   %al, %al
            jne     .L10
            movb    $0, (%rsi)
            ret
    
    kompakt:
    .L17:
            addq    $1, %rdi
            movzbl  -1(%rdi), %eax
            addq    $1, %rsi
            testb   %al, %al
            movb    %al, -1(%rsi)
            jne     .L17
            rep ret
    

    Hier hat der GCC tatsächlich für die Indexfunktion den kürzesten (und vermeintlich schnellsten) inneren Loop erzeugt. Siehe oben im Thread, dass neuere GCC das anders machen. Mal sehen, was rausgekommen ist:

    VARIANTE STRINGLÄNGE REPEATS: ZEIT
    strcpy 1 10000000000: ca. 50
    strcpy 10 1000000000: 5.03
    strcpy 100 100000000: 0.74
    strcpy 1000 10000000: 0.30
    strcpy 10000 1000000: 0.25
    strcpy 100000 100000: 0.41 (> memory  page?)
    
    index 1 10000000000: ca. 20
    index 10 1000000000: 7.40
    index 100 100000000: 6.71
    index 1000 10000000: 6.00
    index 10000 1000000: 5.94
    index 100000 100000: 5.92
    
    pointer 1 10000000000: ca. 33
    pointer 10 1000000000: 11.23
    pointer 100 100000000: 7.81
    pointer 1000 10000000: 6.11
    pointer 10000 1000000: 5.94
    pointer 100000 100000: 5.93
    
    kompakt 1 10000000000: ca. 30
    kompakt 10 1000000000: 10.98
    kompakt 100 100000000: 7.81
    kompakt 1000 10000000: 6.12
    kompakt 10000 1000000: 5.93
    kompakt 100000 100000: 5.92
    

    Also ungefähr das, was wir vom Assembler Code her erwartet hätten: Der Index ist hier ein kleines bisschen schneller als die Pointervarianten. Die ganzen selbstgeschriebenen Varianten sind linear mit der Anzahl der kopierten Zeichen, außer wenn es ganz wenige Zeichen sind und der Function Call zu viel Overhead hat. Ist auch zu erwarten, denn es wird ja jedes Zeichen einzeln kopiert. strcpy hängt natürlich alles gnadenlos ab, da es intern wer weiß was für verbotene Sachen machen darf. auch das ist zu erwarten gewesen.

    Was lehrt uns das?

    • Nicht annehmen, dass ein Stück Code unbedingt schneller ist, als ein anderes, ohne es zu prüfen!
    • Man muss natürlich schon korrekte Benchmarks schreiben, sonst misst man Unsinn!
    • Die genaue Compilerversion und Optimierungen sind dabei höchst wichtig
    • Die eingebauten Funktionen sind sowieso immer VIEL besser, als alles, was man selber schreiben kann


  • @SeppJ
    @swordfish sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    @seppj sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Mit der Zeigerarithmetik kann man weniger machen als mit der Indexschreibweise.

    ??

    Wie meinst Du das?


  • Mod

    @swordfish sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    @SeppJ
    @swordfish sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    @seppj sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Mit der Zeigerarithmetik kann man weniger machen als mit der Indexschreibweise.

    ??

    Wie meinst Du das?

    So wie es da steht. Die Zeigerarithmetik (so wie der Begriff in diesem Thread verwendet wurde, aka die Algorithmen bei denen man Indexberechnungen spart) erlaubt immer nur relative Sprünge (in der Regel um 1 nach vorne), Indexzugriff ist Random Access.

    Und sag jetzt bitte nicht, dass *(ptr + i) Zeigerarithmetik wäre. So wie der Begriff hier im Thread benutzt wird, ist das eine verkappte Indexschreibweise.



  • @seppj sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    So wie es da steht.

    Ja, ist halt bloß Quatsch. Außer man definiert, daß Zeigerarithmetik außschließlich inkrementieren und dektrementieren erlaubt.


  • Mod

    @swordfish sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    @seppj sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    So wie es da steht.

    Ja, ist halt bloß Quatsch. Außer man definiert, daß Zeigerarithmetik außschließlich inkrementieren und dektrementieren erlaubt.

    Wenn du ein ungeschickter Fragesteller bist und den Begriff zur Abgrenzung von Indexzugriffen verwendest, dann ist es aber genau das. Also kein Quatsch, sondern ungeschickte Wortwahl durch den TE. Nenn es Iterator, wenn du willst, aber damit verwirrst du am Ende nur unnötig den TE. Oder besteh auf contiguous, bidirectional, mutable Iterator, wenn du willst, dass man deine Beiträge gar nicht lesen braucht.

    Bitte Mitdenken und Mitlesen. Sonst sind wir zurück bei der schlimmsten Zeit im alten Forum, als man jeden noch so kleinen Beitrag mit 20 Disclaimern versehen musste, wegen der ganzen nervigen Klugscheißer. Und dabei habe ich meinen Beitrag sogar mit zwei fetten Disclaimern versehen!



  • @seppj sagte in [Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?]

    Und sag jetzt bitte nicht, dass *(ptr + i) Zeigerarithmetik wäre.

    Was soll das denn sonst sein?



  • @tyrdal Man muss neuerdings zum Verständnis von eigentlich klar definierten Begriffen zuerst mutmaßen, was ein Fragesteller darunter vielleicht verstehen *könnte* um folgende Antworten dann im richtigentm Kontext verstehen zu können.

    @SeppJ Ja ne, ist klar.

    Ich für meinen Teil werde von nun an jedem Neuling sagen, daß man mit Zeigerarithmetik weniger machen kann als mit Indexschreibweise und auf @SeppJ und diesen Thread verweisen. 👍🏻


  • Mod

    @tyrdal sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    @seppj sagte in [Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?]

    Und sag jetzt bitte nicht, dass *(ptr + i) Zeigerarithmetik wäre.

    Was soll das denn sonst sein?

    Dankeschön Tyrdal, für diese exzellente Demonstration eines doofen Klugscheißers, der nicht einmal bis zum Ende eines Satzes lesen kann, in einem Beitrag darüber, wie man in diesem Forum nicht einmal mehr einfachste Anfängerfragen beantworten kann, weil sonst Leute wie du hervorgekrochen kommen, die ohne Beiträge vollständig zu lesen, ihre dummen, unnötigen Kommentare dazu geben müssen. Bravo!



  • @seppj Ich schätze Dich wirklich dafür, daß Du Dir meistens viel Mühe gibst, Fragen ausführlich und mit viel Text zu beantworten, aber in diesem Fall wäre es vielleicht eine Überlegung wert, "zurück zu Rudern". Deine Aussage

    @seppj sagte in Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?:

    Mit der Zeigerarithmetik kann man weniger machen als mit der Indexschreibweise.

    ist halt (egal in welchem Kontext) einfach Quatsch & Deine Antwort würde nicht leiden, wenn er nicht da stünde. Worauf Du hinaus willst ist ja schließlich, daß ein inc weniger kostet, als ein load und ein add. Dann sag das doch auch so, ohne Begriffe umzudeuten.



  • @seppj sagte in [Stringkopie mittels Zeigern statt Arrayelementen - wo liegt der Vorteil?]

    Dankeschön Tyrdal, für diese exzellente Demonstration eines doofen Klugscheißers, der nicht einmal bis zum Ende eines Satzes lesen kann

    Ich habe deinen gesamten Satz zitiert. Es gibt keinen Grund mir hier irgendwas vorzuwerfen nur weil du sozial herausgefordert bist!


Log in to reply