Großer Unterschied (x9) in der Ausführungszeit zwischen fast identischem Code in C und C++

Lesezeit: 11 Minuten

Benutzeravatar von Alex Lop
Alex Lopp.

Ich habe versucht, diese Übung von www.spoj.com zu lösen: FCTRL – Fakultät

Du musst es nicht wirklich lesen, tu es einfach, wenn du neugierig bist 🙂

Zuerst habe ich es implementiert C++ (hier meine Lösung):

#include <iostream>
using namespace std;

int main() {
    unsigned int num_of_inputs;
    unsigned int fact_num;
    unsigned int num_of_trailing_zeros;

    std::ios_base::sync_with_stdio(false); // turn off synchronization with the C library’s stdio buffers (from https://stackoverflow.com/a/22225421/5218277)

    cin >> num_of_inputs;

    while (num_of_inputs--)
    {
        cin >> fact_num;

        num_of_trailing_zeros = 0;

        for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
            num_of_trailing_zeros += fact_num/fives;

        cout << num_of_trailing_zeros << "\n";
    }

    return 0;
}

Ich habe es als Lösung für hochgeladen g++ 5.1

Das Ergebnis war: Zeit 0,18 Speicher 3,3 Mio
Ergebnisse der C++-Ausführung

Aber dann sah ich einige Kommentare, die behaupteten, ihre Zeitausführung sei weniger als 0,1. Da ich nicht an einen schnelleren Algorithmus denken konnte, habe ich versucht, den gleichen Code in zu implementieren C:

#include <stdio.h>

int main() {
    unsigned int num_of_inputs;
    unsigned int fact_num;
    unsigned int num_of_trailing_zeros;

    scanf("%d", &num_of_inputs);

    while (num_of_inputs--)
    {
        scanf("%d", &fact_num);

        num_of_trailing_zeros = 0;

        for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
            num_of_trailing_zeros += fact_num/fives;

        printf("%d", num_of_trailing_zeros);
        printf("%s","\n");
    }

    return 0;
}

Ich habe es als Lösung für hochgeladen gcc 5.1

Das Ergebnis war diesmal: Zeit 0,02 Speicher 2,1 Mio
Ergebnisse der C-Ausführung

Jetzt ist der Code fast das gleicheIch fügte hinzu std::ios_base::sync_with_stdio(false); in den C++-Code, wie hier vorgeschlagen wurde, um die Synchronisation mit den stdio-Puffern der C-Bibliothek zu deaktivieren. Ich spalte die auch printf("%d\n", num_of_trailing_zeros); zu printf("%d", num_of_trailing_zeros); printf("%s","\n"); Doppelanruf von zu kompensieren operator<< in cout << num_of_trailing_zeros << "\n";.

Aber ich habe es trotzdem gesehen x9 bessere Leistung und geringerer Speicherverbrauch in C- vs. C++-Code.

Warum ist das so?

BEARBEITEN

Ich habe es repariert unsigned long zu unsigned int im C-Code. Es hätte sein sollen unsigned int und die oben gezeigten Ergebnisse beziehen sich auf die neuen (unsigned int) Ausführung.

  • C++-Streams sind konstruktionsbedingt extrem langsam. Denn langsam und stetig gewinnt das Rennen. 😛 (läuft, bevor ich geflammt werde)

    – Mystisch

    6. Dezember 2015 um 20:19 Uhr


  • Die Langsamkeit kommt nicht von Sicherheit oder Anpassungsfähigkeit. Es ist viel zu überdesignt mit all den Stream-Flags.

    – Karoly Horvath

    6. Dezember 2015 um 20:23 Uhr


  • @AlexLop. Verwendung einer std::ostringstream um die Ausgabe zu akkumulieren und zu senden std::cout alles auf einmal am Ende bringt die Zeit auf 0,02 herunter. Verwenden std::cout in a loop ist in ihrer Umgebung einfach langsamer und ich glaube nicht, dass es eine einfache Möglichkeit gibt, dies zu verbessern.

    – Hochofen

    6. Dezember 2015 um 21:10 Uhr

  • Ist sonst niemand besorgt darüber, dass diese Timings mit ideone ermittelt wurden?

    – Ildjarn

    6. Dezember 2015 um 21:21 Uhr


  • @Olaf: Ich fürchte, ich bin anderer Meinung, diese Art von Frage ist für alle ausgewählten Tags sehr relevant. C und C++ sind im Allgemeinen so nah beieinander, dass solch ein Leistungsunterschied nach einer Erklärung verlangt. Ich bin froh, dass wir es gefunden haben. Vielleicht sollte die GNU libc++ als Konsequenz verbessert werden.

    – chqrlie

    6. Dezember 2015 um 21:49 Uhr

Benutzeravatar von chqrlie
chqrlie

Beide Programme machen genau dasselbe. Sie verwenden genau denselben Algorithmus, und aufgrund seiner geringen Komplexität hängt ihre Leistung hauptsächlich von der Effizienz der Eingabe- und Ausgabeverarbeitung ab.

Scannen Sie die Eingabe mit scanf("%d", &fact_num); auf einer Seite u cin >> fact_num; auf der anderen Seite scheint beides nicht sehr kostspielig zu sein. Tatsächlich sollte es in C++ weniger kostspielig sein, da der Konvertierungstyp zur Kompilierzeit bekannt ist und der richtige Parser direkt vom C++-Compiler aufgerufen werden kann. Gleiches gilt für die Ausgabe. Sie legen sogar Wert darauf, einen separaten Aufruf zu schreiben printf("%s","\n");aber der C-Compiler ist gut genug, um dies als Aufruf zu kompilieren putchar('\n');.

Betrachtet man also die Komplexität sowohl der E/A als auch der Berechnung, sollte die C++-Version schneller sein als die C-Version.

Vollständiges Deaktivieren der Pufferung von stdout verlangsamt die C-Implementierung sogar noch langsamer als die C++-Version. Ein weiterer Test von AlexLop mit an fflush(stdout); nach dem letzten printf liefert eine ähnliche Leistung wie die C++-Version. Es ist nicht so langsam wie das vollständige Deaktivieren der Pufferung, da die Ausgabe in kleinen Blöcken statt jeweils einem Byte auf das System geschrieben wird.

Dies scheint auf ein bestimmtes Verhalten in Ihrer C++-Bibliothek hinzudeuten: Ich vermute die Implementierung Ihres Systems von cin und cout spült die Ausgabe auf cout wenn eine Eingabe angefordert wird von cin. Einige C-Bibliotheken tun dies auch, aber normalerweise nur beim Lesen/Schreiben zum und vom Terminal. Das von der Website www.spoj.com durchgeführte Benchmarking leitet wahrscheinlich Ein- und Ausgabe zu und von Dateien um.

AlexLop hat einen weiteren Test durchgeführt: Das gleichzeitige Lesen aller Eingaben in einem Vektor und das anschließende Berechnen und Schreiben aller Ausgaben hilft zu verstehen, warum die C++-Version so viel langsamer ist. Es erhöht die Leistung auf die der C-Version, dies beweist meinen Standpunkt und beseitigt den Verdacht auf den C++-Formatierungscode.

Ein weiterer Test von Blastfurnace, bei dem alle Ausgaben in einem gespeichert werden std::ostringstream und das am Ende auf einen Schlag zu leeren, verbessert die Leistung von C++ auf die der grundlegenden C-Version. QED.

Interlacing-Eingang aus cin und Ausgabe an cout scheint eine sehr ineffiziente E/A-Behandlung zu verursachen, wodurch das Stream-Pufferungsschema zunichte gemacht wird. Leistungsminderung um den Faktor 10.

PS: Ihr Algorithmus ist falsch für fact_num >= UINT_MAX / 5 Weil fives *= 5 wird überlaufen und sich umwickeln, bevor es wird > fact_num. Sie können dies korrigieren, indem Sie fives ein unsigned long oder ein unsigned long long wenn einer dieser Typen größer ist als unsigned int. Auch verwenden %u als die scanf Format. Sie haben Glück, dass die Jungs von www.spoj.com in ihren Benchmarks nicht zu streng sind.

BEARBEITEN: Wie später von vitaux erklärt, wird dieses Verhalten tatsächlich vom C++-Standard vorgeschrieben. cin gebunden ist cout standardmäßig. Eine Eingabeoperation von cin für die der Eingangspuffer nachgefüllt werden muss cout um die anstehende Ausgabe zu löschen. In der OP-Implementierung cin scheint zu spülen cout systematisch, was etwas übertrieben und sichtbar ineffizient ist.

Ilya Popov hat dafür eine einfache Lösung bereitgestellt: cin abgebunden werden kann cout indem Sie zusätzlich einen weiteren Zauberspruch wirken std::ios_base::sync_with_stdio(false);:

cin.tie(nullptr);

Beachten Sie auch, dass eine solche erzwungene Spülung auch bei der Verwendung auftritt std::endl Anstatt von '\n' um ein Zeilenende zu erzeugen cout. Ändern der Ausgabezeile in die C++-idiomatischere und unschuldigere Erscheinung cout << num_of_trailing_zeros << endl; würde die Leistung auf die gleiche Weise beeinträchtigen.

  • Mit der Stromspülung hast du wahrscheinlich recht. Sammeln der Ausgabe in a std::ostringstream und am Ende alles einmal auszugeben, bringt die Zeit auf die Parität mit der C-Version.

    – Hochofen

    6. Dezember 2015 um 21:18 Uhr

  • @ DavidC.Rankin: Ich habe eine Vermutung gewagt (cout wird beim Lesen von cin gespült), einen Weg gefunden, es zu beweisen, AlexLop hat es implementiert und es liefert überzeugende Beweise, aber Blastfurnace hat einen anderen Weg gefunden, um meinen Standpunkt und seine Tests zu beweisen ebenso überzeugende Beweise liefern. Ich nehme es als Beweis, aber natürlich ist es kein vollständig formaler Beweis, wenn man sich den C++-Quellcode ansieht.

    – chqrlie

    6. Dezember 2015 um 21:28 Uhr

  • Ich habe versucht, mit ostringstream für die Ausgabe und es gab Zeit 0,02 QED :). Bezüglich der fact_num >= UINT_MAX / 5Guter Punkt!

    – Alex Lopp.

    6. Dezember 2015 um 21:43 Uhr

  • Sammeln aller Eingaben in a vector und dann die Berechnungen verarbeiten (ohne ostringstream) liefert das gleiche Ergebnis! Zeit 0,02. Beides kombinieren vector und ostringstream verbessert es nicht weiter. Dasselbe Zeit 0,02

    – Alex Lopp.

    6. Dezember 2015 um 21:52 Uhr


  • Eine einfachere Lösung, die auch dann funktioniert, wenn sizeof(int) == sizeof(long long) ist dies: fügen Sie einen Test in den Körper der Schleife danach ein num_of_trailing_zeros += fact_num/fives; um zu prüfen ob fives hat sein Maximum erreicht: if (fives > UINT_MAX / 5) break;

    – chqrlie

    6. Dezember 2015 um 21:53 Uhr

Benutzeravatar von Ilya Popov
Ilja Popow

Ein weiterer Trick zu machen iostreams schneller, wenn Sie beide verwenden cin und cout ist anzurufen

cin.tie(nullptr);

Standardmäßig, wenn Sie etwas eingeben von cines spült cout. Es kann die Leistung erheblich beeinträchtigen, wenn Sie eine verschachtelte Eingabe und Ausgabe durchführen. Dies geschieht für die Verwendung der Befehlszeilenschnittstelle, bei der Sie eine Eingabeaufforderung anzeigen und dann auf Daten warten:

std::string name;
cout << "Enter your name:";
cin >> name;

In diesem Fall sollten Sie sicherstellen, dass die Eingabeaufforderung tatsächlich angezeigt wird, bevor Sie auf die Eingabe warten. Mit der Linie oben brechen Sie diese Krawatte, cin und cout selbstständig werden.

Seit C++11 ist eine weitere Möglichkeit, mit iostreams eine bessere Leistung zu erzielen, die Verwendung von std::getline zusammen mit std::stoiso was:

std::string line;
for (int i = 0; i < n && std::getline(std::cin, line); ++i)
{
    int x = std::stoi(line);
}

Auf diese Weise kann C-Style in der Leistung nahe kommen oder sogar übertroffen werden scanf. Verwenden getchar und speziell getchar_unlocked zusammen mit der handschriftlichen Analyse bietet immer noch eine bessere Leistung.

PS. ich habe geschrieben Ein Eintrag Vergleich mehrerer Möglichkeiten zur Eingabe von Zahlen in C++, nützlich für Online-Richter, aber leider nur auf Russisch. Die Codebeispiele und die abschließende Tabelle sollten jedoch verständlich sein.

  • Vielen Dank für die Erklärung und +1 für die Lösung, aber Ihre vorgeschlagene Alternative mit std::readline und std::stoi ist funktionell nicht äquivalent zum OPs-Code. Beide cin >> x; und scanf("%f", &x); Akzeptieren Sie ein Leerzeichen als Trennzeichen, es können mehrere Zahlen in derselben Zeile stehen.

    – chqrlie

    7. Dezember 2015 um 7:14 Uhr


Benutzeravatar von vitaut
vitaut

Das Problem ist das Zitat cpReferenz:

Jede Eingabe von std::cin, Ausgabe an std::cerr oder Programmbeendigung erzwingt einen Aufruf von std::cout.flush()

Das ist einfach zu testen: Wenn Sie ersetzen

cin >> fact_num;

mit

scanf("%d", &fact_num);

und dasselbe für cin >> num_of_inputs aber behalte cout Sie erhalten in Ihrer C++-Version (oder eher IOStream-Version) so ziemlich die gleiche Leistung wie in C:

Geben Sie hier die Bildbeschreibung ein

Dasselbe passiert, wenn Sie es behalten cin aber ersetzen

cout << num_of_trailing_zeros << "\n";

mit

printf("%d", num_of_trailing_zeros);
printf("%s","\n");

Eine einfache Lösung ist das Lösen cout und cin wie von Ilya Popov erwähnt:

cin.tie(nullptr);

Implementierungen von Standardbibliotheken dürfen den Aufruf von flush in bestimmten Fällen weglassen, aber nicht immer. Hier ist ein Zitat aus C++14 27.7.2.1.3 (danke an chqrlie):

Klasse basic_istream::sentry : Erstens, wenn is.tie() kein Nullzeiger ist, ruft die Funktion is.tie()->flush() auf, um die Ausgabesequenz mit jedem zugehörigen externen C-Stream zu synchronisieren. Nur dass dieser Aufruf unterdrückt werden kann, wenn der Put-Bereich von is.tie() leer ist. Weiterhin ist es einer Implementierung erlaubt, den Aufruf von Flush aufzuschieben, bis ein Aufruf von is.rdbuf()->underflow() auftritt. Wenn kein solcher Aufruf auftritt, bevor das Wachobjekt zerstört wird, kann der Aufruf zum Spülen vollständig eliminiert werden.

  • Danke für die Erklärung. Noch C ++ 14 27.7.2.1.3 zitieren: Klasse basic_istream::sentry : Erstens, wenn is.tie() kein Nullzeiger ist, ruft die Funktion auf is.tie()->flush() um die Ausgangssequenz mit einem beliebigen zugehörigen externen C-Stream zu synchronisieren. Außer, dass dieser Aufruf unterdrückt werden kann, wenn der Put-Bereich von is.tie() ist leer. Ferner ist es einer Implementierung erlaubt, den Aufruf zum Spülen bis zu einem Aufruf von aufzuschieben is.rdbuf()->underflow() tritt ein. Wenn kein solcher Aufruf auftritt, bevor das Wachobjekt zerstört wird, kann der Aufruf zum Spülen vollständig eliminiert werden.

    – chqrlie

    7. Dezember 2015 um 6:40 Uhr

  • Wie bei C++ üblich, sind die Dinge komplexer, als sie aussehen. Die C++-Bibliothek des OP ist nicht so effizient, wie es der Standard zulässt.

    – chqrlie

    7. Dezember 2015 um 6:40 Uhr


  • Danke für den cpreference Link. Allerdings mag ich die “falsche Antwort” im Druckbildschirm nicht ☺

    – Alex Lopp.

    7. Dezember 2015 um 6:46 Uhr

  • @AlexLop. Hoppla, das Problem mit der „falschen Antwort“ wurde behoben =). Ich habe vergessen, das andere Cin zu aktualisieren (dies hat jedoch keinen Einfluss auf das Timing).

    – vitaut

    7. Dezember 2015 um 14:38 Uhr

  • @chqrlie Richtig, aber selbst im Unterlauffall ist die Leistung im Vergleich zur stdio-Lösung wahrscheinlich schlechter. Danke für die Standardref.

    – vitaut

    7. Dezember 2015 um 14:41 Uhr

1419280cookie-checkGroßer Unterschied (x9) in der Ausführungszeit zwischen fast identischem Code in C und C++

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy