Welche Funktion ist schneller: strcmp oder strlen?

er hat sich vertippt und meint: idiotisch

It0101

Mach doch mal. Es gibt sicher den einen oder anderen C-Experten, der die Herausforderung gern annimmt

volkard schrieb:

fairy story schrieb:

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

Das ruft nach einem Vergleich.
Sagen wir mal, einen um 1G großen Eingabestrom wortweise lesen (whitspace als trenner). Stoppuhr starten. Sortieren. Stoppuhr stoppen. Doppeleinträge löschen. Anzahl der ubrigen Einträge anzeigen. Sortierzeit anzeigen.

Ja, ohne Vergleich geht es nicht.
Wer hindert einen daran, einen solchen Algorithmus in C zu implementieren? Einen Algo der mindestens so effizient/schnell arbeitet wie der in C++?
Oder sogar einen schnelleren?

knivil

Wer hindert einen daran, einen solchen Algorithmus in C zu implementieren?

Niemand hindert einen, gleiches gilt fuer Assembler oder gleich Binary. But what 's the point?

SeppJ

Eigentlich ist nicht viel zu machen, außer objdumps Code zu nehmen und sich nicht wie ein Idiot anzustellen:

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <array>
#include <sys/time.h> 

using namespace std;

long unsigned get_num_primes_bool(size_t upper_limit)
{
  vector<bool> nonprime(upper_limit);
  for(size_t i = 2; i < upper_limit; ++i)
    if (!nonprime[i])
      for (size_t j = i + i; j < upper_limit; j += i)
        if (!nonprime[j])
          nonprime[j] = true;
  long unsigned count = 0;
  for(size_t i = 2; i < upper_limit; ++i)
    count += !nonprime[i];
  return count;
}

long unsigned get_num_primes_char(size_t upper_limit)
{
  vector<char> nonprime(upper_limit);
  for(size_t i = 2; i < upper_limit; ++i)
    if (!nonprime[i])
      for (size_t j = i + i; j < upper_limit; j += i)
        if (!nonprime[j])
          nonprime[j] = true;
  long unsigned count = 0;
  for(size_t i = 2; i < upper_limit; ++i)
    count += !nonprime[i];
  return count;
}

long unsigned get_num_primes_VLA(size_t upper_limit)
{
  char nonprime[upper_limit];
  memset(nonprime, 0, upper_limit);
  for(size_t i = 2; i < upper_limit; ++i)
    if (!nonprime[i])
      for (size_t j = i + i; j < upper_limit; j += i)
        if (!nonprime[j])
          nonprime[j] = true;
  long unsigned count = 0;
  for(size_t i = 2; i < upper_limit; ++i)
    count += !nonprime[i];
  return count;
}

long unsigned get_num_primes_malloc(size_t upper_limit)
{
  char *nonprime = static_cast<char*>(malloc(upper_limit));
  memset(nonprime, 0, upper_limit);
  for(size_t i = 2; i < upper_limit; ++i)
    if (!nonprime[i])
      for (size_t j = i + i; j < upper_limit; j += i)
        if (!nonprime[j])
          nonprime[j] = true;
  long unsigned count = 0;
  for(size_t i = 2; i < upper_limit; ++i)
    count += !nonprime[i];
  free(nonprime);
  return count;
}

long unsigned get_num_primes_array(size_t upper_limit)
{
  array<char, 1000000> nonprime;  // :p
  for(size_t i = 2; i < upper_limit; ++i)
    if (!nonprime[i])
      for (size_t j = i + i; j < upper_limit; j += i)
        if (!nonprime[j])
          nonprime[j] = true;
  long unsigned count = 0;
  for(size_t i = 2; i < upper_limit; ++i)
    count += !nonprime[i];
  return count;
}

int main()
{
  size_t limits[] = {1000, 1000000, 1000000000};
  for (auto upper_limit : limits)
    {
      cout << "Number of primes up to " << upper_limit << '\n';
      timespec start, end;
      clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
      //      long unsigned count = get_num_primes_bool(upper_limit);
      //      long unsigned count = get_num_primes_char(upper_limit);
      //      long unsigned count = get_num_primes_VLA(upper_limit);
      //      long unsigned count = get_num_primes_malloc(upper_limit);
      long unsigned count = get_num_primes_array(upper_limit);
      clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
      long unsigned nanoseconds = (end.tv_sec - start.tv_sec) * 1000000000
        + (end.tv_nsec - start.tv_nsec);
      cout << count << '\n' << "Time: " << nanoseconds << " ns\n";
    }
}

Typischer Lauf für vector<bool>:

Number of primes up to 1000
168
Time: 66688 ns
Number of primes up to 1000000
78498
Time: 17084588 ns
Number of primes up to 1000000000
50847534
Time: 30425390933 ns

Typischer Lauf für vector<char>

Number of primes up to 1000
168
Time: 64221 ns
Number of primes up to 1000000
78498
Time: 12095071 ns
Number of primes up to 1000000000
50847534
Time: 32024051561 ns

Typischer Lauf für VLA:

Number of primes up to 1000
168
Time: 12364 ns
Number of primes up to 1000000
78498
Time: 12127712 ns
Number of primes up to 1000000000
Segmentation fault

Fail.
Typischer Lauf für malloc:

Number of primes up to 1000
168
Time: 65080 ns
Number of primes up to 1000000
78498
Time: 12186941 ns
Number of primes up to 1000000000
50847534
Time: 31873605252 ns

Typischer Lauf für Array:

Number of primes up to 1000
168
Time: 13859 ns
Number of primes up to 1000000
78361
Time: 11911901 ns
Number of primes up to 1000000000
Segmentation fault

Fail by design .

Merke: vector<bool> ist nicht so scheiße, wie man denkt. Datenmenge kann wichtig sein. Ansonsten eben das, was man erwartet: Gleiche Ergebnisse für vector<char> und malloc. VLAs spielen ihre Stärke aus, zeigen aber auch ihre größte Schwäche.

Was könnte man lernen? Natürlich gar nichts, denn in diesem Thread geht es darum gar nicht :p . Falls es doch irgendwelche verrückte Lernwilligen gibt, die eine differenzierte Meinung zu schätzen wissen, dann mögen sie eine Fallunterscheidung machen:

< 1 MB: VLA (oder in C++ statisches Array)
< 100 MB: malloc/vector<char>
größer: vector<bool>

(Größenangaben geschätzt)

Ich warte auf die Assemblerantwort! Bitte keine Parallelisierung. Parallel kann ich in C und C++ auch. Außerdem könnte ich natürlich noch die obige Lehre umsetzen, falls mir diese Erkenntnis geklaut wird.

P.S.: Für alle die sich über das malloc&memset wurdern: calloc war erstaunlicherweise messbar langsamer. Muss man da irgendwie noch rumtricksen und mit möglichst großen Elementen arbeiten?

The point ...
dass es Leute gibt, die einem weismachen wollen, mit C++ käme ein performanteres Endprodukt als mit C heraus.

dot schrieb:

denn C++ hat gegenüber C wesentliche Vorteile, insbesondere auch was Performance betrifft...

SeppJ

fairy story schrieb:

The point ...
dass es Leute gibt, die einem weismachen wollen, mit C++ käme ein performanteres Endprodukt als mit C heraus.

Ich warte immer noch auf ein performantes qsort oder getline. Natürlich geht das. Aber kein Mensch macht das, da es viel zu viel Aufwand ist. Selbst wenn man in einem Internetforum recht behalten möchte ist das anscheinend zu viel Aufwand. Welchen motivierenderen Anlass gäbe es denn, wenn nicht Klugscheißerei?

It0101

SeppJ schrieb:

fairy story schrieb:

The point ...
dass es Leute gibt, die einem weismachen wollen, mit C++ käme ein performanteres Endprodukt als mit C heraus.

Ich warte immer noch auf ein performantes qsort oder getline. Natürlich geht das. Aber kein Mensch macht das, da es viel zu viel Aufwand ist. Selbst wenn man in einem Internetforum recht behalten möchte ist das anscheinend zu viel Aufwand. Welchen motivierenderen Anlass gäbe es denn, wenn nicht Klugscheißerei?

Der Punkt ist, dass es gar nicht darum geht, an jeder Stelle die wesentlich bequemere C++-Variante durch eine aufwendig zu entwickelnde C-Lösung zu ersetzen. Da sind wir uns sicherlich einig, dass std::getline sicherlich kein gutes Beispiel für Perfomanceverbesserung ist. Warum? Weil solche Stellen selten Performancerelevant sind.

Wenn es aber an irgendeiner extrem kritischen Stelle an der Performance krankt, dann macht es auf jeden Fall Sinn, über eine C-Variante nachzudenken.

volkard

It0101 schrieb:

SeppJ schrieb:

fairy story schrieb:

The point ...
dass es Leute gibt, die einem weismachen wollen, mit C++ käme ein performanteres Endprodukt als mit C heraus.

Ich warte immer noch auf ein performantes qsort oder getline. Natürlich geht das. Aber kein Mensch macht das, da es viel zu viel Aufwand ist. Selbst wenn man in einem Internetforum recht behalten möchte ist das anscheinend zu viel Aufwand. Welchen motivierenderen Anlass gäbe es denn, wenn nicht Klugscheißerei?

Der Punkt ist, dass es gar nicht darum geht, an jeder Stelle die wesentlich bequemere C++-Variante durch eine aufwendig zu entwickelnde C-Lösung zu ersetzen. Da sind wir uns sicherlich einig, dass std::getline sicherlich kein gutes Beispiel für Perfomanceverbesserung ist. Warum? Weil solche Stellen selten Performancerelevant sind.

Wenn es aber an irgendeiner extrem kritischen Stelle an der Performance krankt, dann macht es auf jeden Fall Sinn, über eine C-Variante nachzudenken.

Der Punkt ist, daß C++ nicht nur wesentlich bequemer ist, sondern tendenziell schneller. C++-Programme, wenn sie nicht mini-klein sind, werden inzwischen ganz von alleine schneller als vergleichbare C-Programme.

SeppJ

It0101 schrieb:

Wenn es aber an irgendeiner extrem kritischen Stelle an der Performance krankt, dann macht es auf jeden Fall Sinn, über eine C-Variante nachzudenken.

Nachdenken allgemein: Klar! Aber wieso über C? Ist das inhärent schneller? Eher im Gegenteil, man müsste sehr viel Aufwand betreiben, um gleich schnell zu sein. Mehr Arbeit für das gleiche Ergebnis.

Mich wundert auch, was an dem getline-Beispiel so schwer zu verstehen ist? Mir geht es natürlich nicht um Performancevergleiche bei der Eingabeverarbeitung. Es geht darum, dass C extrem aufwändig wird, sobald es irgendwie dynamisch wird. Eine Lösung die das gleiche macht wie die drei Zeilen C++ und dabei noch gleich schnell ist, hätte gewiss deutlich über 100 Zeilen und stundenlange Entwicklungsarbeit. Das ist die Stärke von C++. Gleiche Performance wie die bestmögliche C-Lösung bei einem Bruchteil des Entwicklungsaufwandes.

Es ist kein Zufall, dass diese theoretisch möglichen besten C-Lösungen in diesem Thread von niemandem vorgeführt werden. Der große C-Verteidiger objdump muss auf billige Tricks zurückgreifen (Miniprogramme unter Nutzung von Anomalien im C++-Standard wie vector<bool>; Optimierung des Problems auf unportable und gefährliche Features wie VLAs). Der Grund ist, dass niemand diese Lösungen programmieren will, da es viel zu viel Arbeit ist.

It0101

SeppJ schrieb:

Der Grund ist, dass niemand diese Lösungen programmieren will, da es viel zu viel Arbeit ist.

Wir haben einen Server, der in Spitzenzeiten pro Sekunde bis zu 100.000 Messages verarbeiten muss, ohne größere Latenzen reinzuzaubern. Das System ist überlebenswichtig und da kannst du sicher sein, dass uns kein Aufwand zu hoch ist, um da noch das eine oder andere Prozent Performance rauszuholen. Auch aufwändige C-Lösungen sind da relevant.

volkard

SeppJ schrieb:

Falls es doch irgendwelche verrückte Lernwilligen gibt, die eine differenzierte Meinung zu schätzen wissen, dann mögen sie eine Fallunterscheidung machen:

< 1 MB: VLA (oder in C++ statisches Array)

< 100 MB: malloc/vector<char>

größer: vector<bool>

(Größenangaben geschätzt)
[/list]

Ich nehme eher

< 4k: array (VLA würde auch gehen)
sonst: malloc/vector<char>

Wenns klein und schnell sein soll, manchmal auch einen selbergebauten vector, der drunter ein array hat, also nicht über die zur Compilezeit fest vorgegebene Größe wachsen kann.

SeppJ schrieb:

Das ist gar kein C, auch kein C11.

was soll das sonst sein? das ist valide c-syntax.
es wird eine funktion aufgerufen, also das, was auch dein code macht.

SeppJ

kenner der schummler schrieb:

es wird eine funktion aufgerufen, also das, was auch dein code macht.

Diese Funktion gibt es aber in ANSI-C nicht.

SeppJ schrieb:

Mich wundert auch, was an dem getline-Beispiel so schwer zu verstehen ist?

Ersetze printf durch fwrite, dann funktioniert mein Code auch in deinem konstruierten Szenario. Und er ist echt schneller, weil in C++ standardmässig cin mit cout getied ist und mit stdio gesynct wird. Das kann man ausstellen, aber kein mir bekannter C++-Programmierer macht sowas.

Es ist ein ungeschriebenes Gesetz, dass:
Nutzereingabe <=> Eingabe UTF-8, ohne Kontrollzeichen und zeilenweise, entweder Länge überschaubar oder Geschwindigkeit irrelevant
Binärstream <=> Länge wird angegeben

Für die Interaktion mit dem Nutzer sollte auf GNU Readline zurückgegriffen werden (d.h. C++ nutzt hier auch C), für das Parsen von Config-Files kann auch mal 32'000 Zeichen als maximale Länge angenommen werden. Ansonsten ist etwas mit der Datei falsch (Zeilenenden der Datei vom Mac nicht erkannt); C++ würde da der Speicher ausgehen.

Schnelles Parsen und C passt perfekt zusammen. An Bison/Flex kommt kein Stream ran.

Es ist kein Zufall, dass diese theoretisch möglichen besten C-Lösungen in diesem Thread von niemandem vorgeführt werden.

Mit anderen Worten lautet deine Argumentation: C++ ist besser als C weil die Standardbibliothek hat viel mehr fertige Algorithmen.
Beweise für die Richtigkeit meiner Behauptung: getline ist für dich kein C.

Nehmen wir einmal Hashtables. Alle scheinen sie zu brauchen, weder C noch C++98 haben welche vorzuweisen. Es gibt schöne C-Bibliotheken, die sie anbieten: https://developer.gnome.org/glib/stable/glib-Hash-Tables.html. Wenn ich mich recht erinnere, war die schneller als boost::unordered_map.
Mit C++11 hat sich da nicht viel geändert, std::unordered_map ist weder sonderlich schneller noch langsamer, und wenn dann liegt der Unterschied im Algorithmus und nicht an der Sprache.

SeppJ schrieb:

Diese Funktion gibt es aber in ANSI-C nicht.[/quote]
invalid Argument :p

natürlich ist das keine standard bibliotheksfunktion.
aber, das eine nicht-standard funktion programmiert werden müsste, war doch von vornherein klar.

SeppJ

kenner der schummler schrieb:

aber, das eine nicht-standard funktion programmiert werden müsste, war doch von vornherein klar.

Klar. Aber mach doch mal! Außerdem gibt das Programm immer noch was anderes aus als das C++-Programm.

Ethon

objdump schrieb:

Nehmen wir einmal Hashtables. Alle scheinen sie zu brauchen, weder C noch C++98 haben welche vorzuweisen. Es gibt schöne C-Bibliotheken, die sie anbieten: https://developer.gnome.org/glib/stable/glib-Hash-Tables.html. Wenn ich mich recht erinnere, war die schneller als boost::unordered_map.
Mit C++11 hat sich da nicht viel geändert, std::unordered_map ist weder sonderlich schneller noch langsamer, und wenn dann liegt der Unterschied im Algorithmus und nicht an der Sprache.

Es gibt hunderte Opensource C++ Hashtables in allen Variationen und für jeden Spezialfall - das hat C nicht für sich gepachtet. Aber alle C-Hashtables teilen sich die Eigenschaft dass sie nicht typsicher sind und von daher Fehlerquellen sind.

Fakt ist ebenfalls dass es bei C++ wenigstens eine in der Stdlib gibt und bei C nicht.

Schnelles Parsen und C passt perfekt zusammen. An Bison/Flex kommt kein Stream ran.

Kennste Boost.Spirit? Ich behaupte es geht nicht schneller. Und Spirit läuft sogar auf Sprachebene und ist kein extra Tool.

Ethon schrieb:

Kennste Boost.Spirit?

Ja

Ethon schrieb:

Kennste Boost.Spirit? Ich behaupte es geht nicht schneller.

Nein.

Boost.Spirit ist ziemlich schnell, hat aber die Einschränkung nur die Sprachebene von C++ nutzen zu können. Es würde mich überraschen, wenn er aus den Strings "abc", "abd", "ac" den Code if (c[0]==a){if(c[1]==b){if(c[2]==d])else if (c[2]==d)}else if(c[1]==c)} generiert.
Und selbst wenn, spätestens bei etwas grösseren Grammatiken ist dann Schluss aus Compilezeitgründen.

Boost.Spirit wäre in C unmöglich; ich meine aber, dass hier der richtige Weg externe Code-Generatoren sind. Die Alternative ist eine echte Compilezeitsprache, aber dafür sind Templates ungeeignet. Und constexpr wird wohl nie mächtig genug.

Ich finde diese Diskussion ziemlich langweilig. Beide Seiten haben Recht und Unrecht zugleich.

In C++ lässt sich ein Programm schnell und einfach entwickeln. Es ist bei Beachtung einfacher Regeln sehr sicher und flexibel. Trotz allem lässt es sich noch immer gut warten.

In C lässt sich mit entsprechender Erfahrung ebenso recht schnell ein Programm schreiben. Trotzdem ist man hier auf sich alleine gestellt und muss genau wissen, was man tut. Da man noch mehr selber machen muss, spart man hier und da etwas Rechenzeit. Es lässt sich möglicherweise weniger gut warten, da man schnell etwas vergessen kann, was Fehler hervorruft.

Da heutige C++ Compiler sehr gut optimieren, ist der Unterschied jedoch nicht mehr sonderlich groß. Es muss schon eine sehr performancekritische Software sein, dass man auf die Idee kommt alles in C zu schreiben. In dem konkretem Fall kann C wirklich im Vorteil sein. Aber dann muss auch der Programmierer ein absoluter Profi sein.

Denn nur weil man in C programmiert, ist das Programm nicht automatisch schneller. Das zeigt ja schon die Eingangsfrage, wo erst strlen und dann strcmp aufgerufen werden sollte, was aus Performancesicht das absolute Gegenteil bewirkt.