3. Welche Funktion ist schneller: strcmp oder strlen?

Welche Funktion ist schneller: strcmp oder strlen?


  • reinfall schrieb:

    Beides scheisse. strlen ist sogar noch scheissiger, selbst wenn strlen(suchbegriff) nur einmal berechnet wird (ausser in speziellen Umständen). Besser wird das, wenn du für jeden String auch noch die Länge mitspeicherst, aber selbst das ist dann immer noch eine verkappte Hashfunktion.

    Wenn es dir wirklich um Geschwindigkeit geht bekommst du diese nicht durch Feintunen der Implementierung sondern durch Verbesserung des Algorithmus. qsort + bsearch wäre ein erster Schritt, der nächste wäre ein Upgrade auf C++11 und unordered_set.

    In dem Fall hat er Recht. Das Problem ist hier nicht, ob strcmp oder strlen schneller sind, sondern dass evtl. dein Container nicht optimal ist.

    Eine HashMap kannst du in C auch selber schreiben. Eben nicht als Template sondern spezialisert für C-Strings. Ist eigentlich keine große Sache. Auch wenn deine HashMap vielleicht anfangs noch nicht so perfekt ist ( Stichwort HashKey-Genenerierung ), so ist es auf jeden Fall schon mal besser als ein simples Array aus Strings, besonders dann wenn man suchen muss.

    Ersatzweise könntest du auch, wie schon erwähnt, die Strings erstmal nach Länge sortieren, oder gar alle Strings der gleichen Länge in einer Struktur / Liste sammeln.

    In jedem Fall muss ein besserer Container her.

    0

  • SeppJ schrieb:

    dot schrieb:

    fairy story schrieb:

    Btw. kann ich mir in C einen Sortieralgo auch selber schreiben, wenn mir qsort zu lahm sein sollte.

    Schwachsinn, das offensichtliche Gegenbeispiel qsort vs. std::sort wurde ja schon genannt...

    Recht hat er schon, aber er widerlegt sich damit auch selber. Ein selbst geschriebenes, spezialisiertes qsort kann so schnell sein wie std::sort. Das ist doch gerade das Problem, dass der C++-Programmierer bloß eine Zeile schnell hinkritzeln braucht, während in C an dieser Stelle eine nicht unwesentliche Entwicklungsarbeit nötig ist. Ein paar Stunden gehen da gewiss drauf. Mehr, wenn man nicht irgendwo abschreibt sondern noch selber recherchiert, welcher Algorithmus der beste wäre und wie er optimal implementiert wird.

    Wenn aber genau die Performance eines Sortieralgorithmus der Knackpunkt ist, lohnt sich die Arbeit schon. Der größte Fehler, den man machen kann, ist die STL standardmäßig als "das schnellste" hinzunehmen. Denn das ist nicht (immer) der Fall.

    Und ja: Die Aufwände für einen Performancevergleich kann man nicht immer akzeptieren.

    0
  • E

    objdump schrieb:

    volkard schrieb:

    Komisch.

    Verständlich, wenn dein System bool in long long speichert.

    #include <stdio.h> 
#include <string.h> 
  
int f(int n) { 
  register int i, j, cnt; 
  char nonprime[n];
  memset(nonprime, 0, n); 
  
  for (i=2; i<n; ++i) 
    if (!nonprime[i]) 
      for (j=2; i*j<n; ++j) 
        nonprime[i*j]=1; 

  cnt = 0; 
  for (i=2; i<n; ++i) 
    cnt += !nonprime[i]; 
  return cnt; 
} 
  
int main() { 
  register int i, sum=0; 
  for (i=0; i<LOOPS; ++i) 
    sum += f(i&0xFF); 
  printf("%d\n", sum); 
  return 0; 
}

    Auf einem anderen Rechner erhalte ich dann 0.821s für C gegen 0.870s C++.

    Was für ein dummes Beispiel - das einzige was du da an Unterschied misst sind die Kosten von malloc/free, die der Vektor unter der Haube durchführt.
    Entweder du lässt deinen Code auch speicher dynamisch anfordern oder du gestattest der C++ Variante auch Speicher zu recyclen und legst den Vektor außerhalb der Funktion an. (Oder du benutzt einfach alloca)

    Dass man Heapallokationen aus Hotspots entfernt versteht sich ja wohl von selbst.

    0
  • ?

    Ethon schrieb:

    Entweder du lässt deinen Code auch speicher dynamisch anfordern oder du gestattest der C++ Variante auch Speicher zu recyclen und legst den Vektor außerhalb der Funktion an. (Oder du benutzt einfach alloca)

    Du darfst alles machen, solange du die Signatur und das Verhalten der Funktion f nicht veränderst, also die Parameter nicht willkürlich begrenzt. Wenn du nett bist, änderst du auch nicht den Algorithmus.
    Aber bleibe bitte bei Standard-C++.

    Ich will ja gerade darauf hinaus, dass "schöner" C++-Code viel Vektor verwendet und deshalb viel malloc/free braucht und deshalb langsamer ist als "schönes" C. Nicht der Test ist dümmlich, sondern C++.

    0
  • K

    also die Parameter nicht willkürlich begrenzt

    Die Groesse des lokalen Arrays muss beschreankt sein, hier ist es auf 255 Eintraege beschraenkt. Nicht durch die Funktion selbst aber durch & 0xFF beim Parameter. D.h. ein lokales Array mit max 256 Eintraegen tut es auch.

    Nicht der Test ist dümmlich, sondern C++.

    Nein, der Programmierer. In diesem Fall bist das du!

    0
  • E

    objdump schrieb:

    Ethon schrieb:

    Entweder du lässt deinen Code auch speicher dynamisch anfordern oder du gestattest der C++ Variante auch Speicher zu recyclen und legst den Vektor außerhalb der Funktion an. (Oder du benutzt einfach alloca)

    Du darfst alles machen, solange du die Signatur und das Verhalten der Funktion f nicht veränderst, also die Parameter nicht willkürlich begrenzt. Wenn du nett bist, änderst du auch nicht den Algorithmus.
    Aber bleibe bitte bei Standard-C++.

    Du begrenzt doch die Parameter auch. 😕
    2^31 sind 2GB, so viel kann ich auf keinem mir bekannten OS auf dem Stack anlegen.

    objdump schrieb:

    Ich will ja gerade darauf hinaus, dass "schöner" C++-Code viel Vektor verwendet und deshalb viel malloc/free braucht und deshalb langsamer ist als "schönes" C. Nicht der Test ist dümmlich, sondern C++.

    Der meiste C-Code geht ineffizienter mit Heapspeicher um, da auch in C sehr viel auf dem Heap angelegt wird, aber der meiste code nicht an die hochoptimierten C++-Klassen wie std::string herankommt (mit SSO etc).

    Du hast bei deinem Code die Freiheit unsicheren Code zu schreiben. Wenn ein Code nicht knallen darf, dann benutzt man auch in C keine VLAs, sondern eher malloc.

    0

  • Ethon schrieb:

    objdump schrieb:

    Ethon schrieb:

    Entweder du lässt deinen Code auch speicher dynamisch anfordern oder du gestattest der C++ Variante auch Speicher zu recyclen und legst den Vektor außerhalb der Funktion an. (Oder du benutzt einfach alloca)

    Du darfst alles machen, solange du die Signatur und das Verhalten der Funktion f nicht veränderst, also die Parameter nicht willkürlich begrenzt. Wenn du nett bist, änderst du auch nicht den Algorithmus.
    Aber bleibe bitte bei Standard-C++.

    Du begrenzt doch die Parameter auch. 😕
    2^31 sind 2GB, so viel kann ich auf keinem mir bekannten OS auf dem Stack anlegen.

    objdump schrieb:

    Ich will ja gerade darauf hinaus, dass "schöner" C++-Code viel Vektor verwendet und deshalb viel malloc/free braucht und deshalb langsamer ist als "schönes" C. Nicht der Test ist dümmlich, sondern C++.

    Der meiste C-Code geht ineffizienter mit Heapspeicher um, da auch in C sehr viel auf dem Heap angelegt wird, aber der meiste code nicht an die hochoptimierten C++-Klassen wie std::string herankommt (mit SSO etc).

    Du hast bei deinem Code die Freiheit unsicheren Code zu schreiben. Wenn ein Code nicht knallen darf, dann benutzt man auch in C keine VLAs, sondern eher malloc.

    std::string ist hochoptimiert?

    Also ich hatte mal hier irgendwo einen Thread wo Konkatenation von std::string und char * ( dynamisches array quasi ) verglichen habe und die Unterschiede waren enorm zugunsten von ANSI-C ?

    Der Thread ist leider irgendwie verschwunden...
    Damals konnte mir auch keiner erklären, was ich evtl. bei C++ falsch gemacht habe.

    0
  • ?

    knivil schrieb:

    also die Parameter nicht willkürlich begrenzt

    Die Groesse des lokalen Arrays muss beschreankt sein, hier ist es auf 255 Eintraege beschraenkt. Nicht durch die Funktion selbst aber durch & 0xFF beim Parameter. D.h. ein lokales Array mit max 256 Eintraegen tut es auch.

    Ok.

    #include <stdio.h> 
#include <string.h> 

int f(int n) { 
  register int i, j, cnt; 
  char nonprime[n];
  memset(nonprime, 0, n); 

  for (i=2; i<n; ++i) 
    if (!nonprime[i]) 
      for (j=2; i*j<n; ++j) 
        nonprime[i*j]=1; 

  cnt = 0; 
  for (i=2; i<n; ++i) 
    cnt += !nonprime[i]; 
  return cnt; 
} 

int main() { 
  register int i, sum=0; 
  for (i=0; i<LOOPS; ++i) 
    sum += f(i&0xFF + ((i==0)<<16)); 
  printf("%d\n", sum); 
  return 0; 
}

    #include <vector> 
#include <iostream> 

int f(int n) { 
  char nonprime[1<<16]={};
  //std::vector<char> nonprime(n);
  for (int i=2; i<n; ++i) 
    if (!nonprime[i]) 
      for (int j=2; i*j<n; ++j) 
        nonprime[i*j]=true; 

  int cnt = 0; 
  for (int i=2; i<n; ++i) 
    cnt += !nonprime[i]; 
  return cnt; 
} 

int main() { 
  int sum=0; 
  for (int i=0; i<LOOPS; ++i) 
    sum += f(i&0xFF + ((i==0)<<16)); 
  std::cout << sum << '\n'; 
  return 0; 
}

    C 0m0.811s
    C++ 0m4.801s

    Ethon schrieb:

    Der meiste C-Code geht ineffizienter mit Heapspeicher um, da auch in C sehr viel auf dem Heap angelegt wird, aber der meiste code nicht an die hochoptimierten C++-Klassen wie std::string herankommt (mit SSO etc).

    Willst du es drauf ankommen lassen? VLA ist viel mächtiger als SSO und hat weniger Overhead.
    Zeig du mir C++-Code mit Strings und ich bau dir einen schnelleren C-Code.
    Nur nicht kompliziertere Sachen wie Sortieren und Hashen, darauf habe ich gerade keine Lust.

    0
  • E

    objdump schrieb:

    Ethon schrieb:

    Der meiste C-Code geht ineffizienter mit Heapspeicher um, da auch in C sehr viel auf dem Heap angelegt wird, aber der meiste code nicht an die hochoptimierten C++-Klassen wie std::string herankommt (mit SSO etc).

    Willst du es drauf ankommen lassen? VLA ist viel mächtiger als SSO und hat weniger Overhead.
    Zeig du mir C++-Code mit Strings und ich bau dir einen schnelleren C-Code.
    Nur nicht kompliziertere Sachen wie Sortieren und Hashen, darauf habe ich gerade keine Lust.

    VLAs haben ein sehr begrenztes Einsatzgebiet, nämlich nur für funktionslokale Arrays. Strings werden aber in der Regel herumgereicht und da werden sie in C selbstverständlich mit malloc angelegt.

    objdump schrieb:

    C 0m0.811s
    C++ 0m4.801s

    Süßer Versuch den C++ Code das ganze Array nullen zu lassen und nicht nur n Bytes.
    Ändere das ab und beide sind exakt gleichschnell.

    0
  • Mod

    objdump schrieb:

    Zeig du mir C++-Code mit Strings und ich bau dir einen schnelleren C-Code.

    int main()
{
 string str;
 getline(str, cin);
 cout << str << '\n';
}

    Wenn dein C-Programm durch die Benutzereingabe abstürzt* oder sonstwie undefiniertes Verhalten oder Speicherlöcher oder anderes Verhalten als die C++-Lösung (ich kann Nullzeichen und Umlaute eingeben!) zeigt, dann ist es nicht gleichwertig. Du darfst dich in ein paar Stunden melden, wenn du die gleichschnelle C-Alternative zu diesen in 5 Sekunden getippten Zeilen fertig gestellt hast.

    *: Ich bin mal so fair, eine maximale Eingabelänge von 8 GB vorzugeben.

    0
  • V

    objdump schrieb:

    char nonprime[1<<16]={};

    Das ist doch Unfug. Mit allerbilligsten Tricks versuchst Du C++ zu verunglimpfen.
    Hier soll der extrem dumme C++-Programmierer nicht memset oder sowas nehmen. Warum?

    0
  • ?

    SeppJ schrieb:

    Du darfst dich in ein paar Stunden melden, wenn du die gleichschnelle C-Alternative zu diesen in 5 Sekunden getippten Zeilen fertig gestellt hast.

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

int main()
{
  char *line = NULL;
  size_t len = 0;
  while (getline(&line, &len, stdin) != -1)
    printf("%s", line);
  free(line);
  return 0;
}

    C 0m0.457s
    C++ 1.675s

    Wenn ich die C++-Variante optimiere, komme ich auf ähnliche Ergebnisse wie für C.

    0
  • V

    0
  • ?

    Also der C++-Code dazu ist

    int main() 
{
  std::string str; 
  while (std::getline(std::cin, str)) {
    std::cout << str << '\n';
  }
}
    0

  • SeppJ schrieb:

    Wenn dein C-Programm durch die Benutzereingabe abstürzt* oder sonstwie undefiniertes Verhalten oder Speicherlöcher oder anderes Verhalten als die C++-Lösung (ich kann Nullzeichen und Umlaute eingeben!) zeigt, dann ist es nicht gleichwertig. Du darfst dich in ein paar Stunden melden, wenn du die gleichschnelle C-Alternative zu diesen in 5 Sekunden getippten Zeilen fertig gestellt hast.

    Stimmt... Benutzereingaben sind absolut performancerelevant... 🙄

    0
  • E

    -- Hier stand Unsinn --

    0
  • Z

    objdump schrieb:

    SeppJ schrieb:

    Du darfst dich in ein paar Stunden melden, wenn du die gleichschnelle C-Alternative zu diesen in 5 Sekunden getippten Zeilen fertig gestellt hast.

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

int main()
{
  char *line = NULL;
  size_t len = 0;
  while (getline(&line, &len, stdin) != -1)
    printf("%s", line);
  free(line);
  return 0;
}

    C 0m0.457s
    C++ 1.675s

    Wenn ich die C++-Variante optimiere, komme ich auf ähnliche Ergebnisse wie für C.

    Lass mich raten:
    Bei C hast du gleich auf Enter gedrückt
    Bei C++ hast du paar Buchstaben gedrückt

    🤡 🤡 🤡

    0

  • Mir ist absolut schleierhaft, wie man auf die Idee kommen kann, Performancemessungen mit Benutzereingaben zu machen....

    Die ganze Diskussion scheint mir mal wieder sehr stark auf Basis von Emotionen anstatt von Fakten zu laufen. Und es sind mal wieder auf beiden Seiten Fanatiker unterwegs, die den Gebrauch des jeweils anderen Werkzeugs verteufeln.
    Ziemlich armselig.

    0
  • Mod

    Das ist gar kein C, auch kein C11. Außerdem macht deine C-Version andere Ausgaben als die C++-Version*. Setzen, 6.

    Wenn du was portables und funktionierendes gefrickelt hast, melde dich noch einmal zur Nachprüfung.

    *: Ist schon toll, wie ich sogar in meiner Herausforderung explizit erwähne, worauf zu achten ist, und du trotzdem darauf rein fällst.

    0
  • E

    Jetzt mal ernsthaft: Die ganze Diskussion ist für den Arsch. Performance-Hotspots schreibt man natürlich nicht mit aufgestyltem Code, der x mal Speicher vom Heap holt. Da wird C++-Code natürlich mit einem C-ähnlichem Subset geschrieben. Oder in Assembler, sollte mit Skill schneller sein als C. Oder man schickt es gleich auf dem GPU und lässt da rechnen.

    Es geht schlicht darum dass einige Sprachmechanismen in C++ wie Templates optimalen Code erzeugen, den man in C auch schreiben könnte - aber häufig mit erheblichem Mehraufwand seitens des Programmierers.

    0
Anmelden zum Antworten