Welche Funktion ist schneller: strcmp oder strlen?

SeppJ

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.

Ethon

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.

SeppJ

Ethon schrieb:

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.

Nee, die Zeiten sind lange vorbei. Besonders der Assembler, außer du hast richtig viel Manpower zur Verfügung oder kennst ganz spezielle Nebenbedingungen über das Anwendungsgebiet oder den Prozessor, die der Compiler nicht kennen kann.

Ich kann dir das tolle Primzahlenbeispiel in idiomatischem C++ schreiben, sogar mit vector<bool>, da kannst du in absehbarer Zeit mit C höchstens gleichziehen und in Assembler wirst du höchstwahrscheinlich auch nicht dran vorbeikommen (oder wenn doch, wirst du ziemlich lange dafür brauchen).

Mit der GPU oder OpenMP wirst du natürlich auf einfache Weise schneller, da das Sieb halbwegs gut parallelisierbar ist. Aber diese Techniken sind unabhängig von der Sprache.

SeppJ schrieb:

Ich kann dir das tolle Primzahlenbeispiel in idiomatischem C++ schreiben, sogar mit vector<bool>, da kannst du in absehbarer Zeit mit C höchstens gleichziehen und in Assembler wirst du höchstwahrscheinlich auch nicht dran vorbeikommen (oder wenn doch, wirst du ziemlich lange dafür brauchen).

Mach doch mal...

volkard

SeppJ schrieb:

Ich kann dir das tolle Primzahlenbeispiel in idiomatischem C++ schreiben,

idiomatisch? meinste kanonisch?
Daß Du beim Programmieren irgendwelche Idiome verwenden wirst, ist eh klar.
Was ist nicht-idiomatisches C++?

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.