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

85

Ich habe versucht, diese Übung von www.spoj.com zu lösen: FCTRL - Factorial

Du musst es nicht wirklich lesen, mach es einfach, wenn du neugierig bist :)

Zuerst habe ich es in C ++ implementiert (hier ist 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 g ++ 5.1 hochgeladen

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

Aber dann sah ich einige Kommentare, die behaupteten, dass ihre Zeitausführung weniger als 0,1 war. Da ich mir keinen schnelleren Algorithmus vorstellen konnte, habe ich versucht, denselben Code in C zu implementieren :

#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 gcc 5.1 hochgeladen

Diesmal war das Ergebnis: Zeit 0,02 Mem 2,1M C Ausführungsergebnisse

Jetzt ist der Code fast der gleiche , den ich dem hierstd::ios_base::sync_with_stdio(false); vorgeschlagenen C ++ - Code hinzugefügt habe , um die Synchronisation mit den Standardpuffern der C-Bibliothek zu deaktivieren. Ich teile auch die printf("%d\n", num_of_trailing_zeros);zu printf("%d", num_of_trailing_zeros); printf("%s","\n");Doppel Aufruf zu kompensieren operator<<in cout << num_of_trailing_zeros << "\n";.

Aber ich sah immer noch eine bessere x9-Leistung und eine geringere Speichernutzung in C vs. C ++ - Code.

Warum ist das so?

BEARBEITEN

Ich unsigned longhabe unsigned intim C-Code behoben . Es sollte gewesen sein unsigned intund die oben gezeigten Ergebnisse beziehen sich auf die neue ( unsigned int) Version.

Alex Lop.
quelle
31
C ++ - Streams sind von Natur aus extrem langsam. Weil langsam und stetig das Rennen gewinnt. : P ( läuft, bevor ich geflammt werde )
Mysticial
7
Die Langsamkeit kommt nicht von Sicherheit oder Anpassungsfähigkeit. Es ist viel mit allen Stream-Flags überarbeitet.
Karoly Horvath
8
@AlexLop. Wenn Sie std::ostringstreamdie Ausgabe mit a akkumulieren und am Ende std::cout auf einmal an alle senden, verringert sich die Zeit auf 0,02. Die Verwendung std::coutin einer Schleife ist in ihrer Umgebung einfach langsamer und ich glaube nicht, dass es einen einfachen Weg gibt, sie zu verbessern.
Blastfurnace
6
Ist sonst niemand besorgt darüber, dass diese Timings mit Ideone erhalten wurden?
ildjarn
6
@Olaf: Ich fürchte, ich bin anderer Meinung, diese Art von Frage ist für alle ausgewählten Tags sehr thematisch. C und C ++ sind im Allgemeinen so nahe beieinander, dass ein solcher Leistungsunterschied eine Erklärung erfordert. Ich bin froh, dass wir es gefunden haben. Vielleicht sollte die GNU libc ++ in der Folge verbessert werden.
Chqrlie

Antworten:

56

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

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

Angesichts der Komplexität von E / A und Berechnung sollte die C ++ - Version schneller sein als die C-Version.

Das vollständige Deaktivieren der Pufferung stdoutverlangsamt die C-Implementierung auf etwas, das noch langsamer als die C ++ - Version ist. Ein weiterer Test von AlexLop mit einem fflush(stdout);nach dem letzten printfergibt 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 anstelle von jeweils einem Byte in das System geschrieben wird.

Dies scheint auf ein bestimmtes Verhalten in Ihrer C ++ - Bibliothek hinzuweisen: Ich vermute, dass Ihr System die Ausgabe implementiert cinund coutlöscht, coutwenn eine Eingabe von angefordert wird cin. Einige C-Bibliotheken tun dies ebenfalls, jedoch normalerweise nur beim Lesen / Schreiben zum und vom Terminal. Das von der Website www.spoj.com durchgeführte Benchmarking leitet die Eingabe und Ausgabe wahrscheinlich in und aus 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 das 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 std::ostringstreamund am Ende in einem Druck gelöscht werden, verbessert die C ++ - Leistung gegenüber der C-Basisversion. QED.

Das Interlacing von Eingabe cinund Ausgabe an coutscheint eine sehr ineffiziente E / A-Behandlung zu verursachen, wodurch das Stream-Pufferschema zunichte gemacht wird. Leistungsreduzierung um den Faktor 10.

PS: Ihr Algorithmus ist falsch, fact_num >= UINT_MAX / 5da er fives *= 5überläuft und sich umwickelt, bevor er wird > fact_num. Sie können dies korrigieren, indem Sie fivesein unsigned longoder ein machen, unsigned long longwenn einer dieser Typen größer als ist unsigned int. Auch %uals scanfFormat verwenden. Sie haben Glück, dass die Jungs von www.spoj.com in ihren Benchmarks nicht zu streng sind.

EDIT: Wie später von vitaux erklärt, wird dieses Verhalten tatsächlich vom C ++ - Standard vorgeschrieben. cinist coutstandardmäßig gebunden . Eine Eingabeoperation, cinfür die der Eingabepuffer nachgefüllt werden muss, führt dazu cout, dass die ausstehende Ausgabe geleert wird . In der Implementierung des OP cinscheint coutsystematisch zu spülen , was etwas übertrieben und sichtbar ineffizient ist.

Ilya Popov bot hierfür eine einfache Lösung: cinKann gelöst werden, coutindem zusätzlich zu std::ios_base::sync_with_stdio(false);:

cin.tie(nullptr);

Beachten Sie auch, dass eine solche erzwungene Spülung auch auftritt, wenn std::endlanstelle von '\n'ein Zeilenende verwendet wird cout. Das Ändern der Ausgabezeile auf das idiotischere und unschuldigere C ++ - Aussehen cout << num_of_trailing_zeros << endl;würde die Leistung auf die gleiche Weise beeinträchtigen.

chqrlie
quelle
2
Sie haben wahrscheinlich Recht mit dem Spülen von Streams. Wenn Sie die Ausgabe in a std::ostringstreamsammeln und am Ende alle einmal ausgeben, wird die Zeit auf die Parität mit der C-Version reduziert.
Blastfurnace
2
@ DavidC.Rankin: Ich habe eine Vermutung gewagt (Cout wird beim Lesen von Cin gespült), einen Weg gefunden, dies zu beweisen, AlexLop hat es implementiert und es gibt überzeugende Beweise, aber Blastfurnace hat einen anderen Weg gefunden, um meinen Standpunkt und seine Tests zu beweisen ebenso überzeugende Beweise geben. Ich nehme es als Beweis, aber natürlich ist es kein vollständig formaler Beweis, wenn man sich den C ++ - Quellcode ansieht.
Chqrlie
2
Ich habe versucht, ostringstreamfür die Ausgabe zu verwenden und es gab Zeit 0,02 QED :). In Bezug auf den fact_num >= UINT_MAX / 5, guten Punkt!
Alex Lop.
1
Das Sammeln aller Eingaben in a vectorund das anschließende Verarbeiten der Berechnungen (ohne ostringstream) ergibt das gleiche Ergebnis! Zeit 0.02. Beides kombinieren vectorund ostringstreamnicht weiter verbessern. Gleiche Zeit 0.02
Alex Lop.
2
Eine einfachere Lösung, die auch dann funktioniert, wenn sizeof(int) == sizeof(long long)dies der num_of_trailing_zeros += fact_num/fives;fivesif (fives > UINT_MAX / 5) break;
Fall ist
44

Ein weiterer Trick, um iostreams schneller zu machen , wenn Sie beide verwenden cinund coutanrufen

cin.tie(nullptr);

Wenn Sie etwas cineingeben, wird es standardmäßig gelöscht cout. Dies kann die Leistung erheblich beeinträchtigen, wenn Sie Eingaben und Ausgaben verschachteln. Dies erfolgt für die Befehlszeilenschnittstelle, bei der Sie eine Eingabeaufforderung anzeigen und dann auf Daten warten:

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

In diesem Fall möchten Sie sicherstellen, dass die Eingabeaufforderung tatsächlich angezeigt wird, bevor Sie auf die Eingabe warten. Mit der obigen Linie brechen Sie diese Krawatte cinund coutwerden unabhängig.

Da C ++ 11, eine weitere Möglichkeit , eine bessere Leistung mit iostreams zu erreichen , ist die Verwendung std::getlinezusammen mit std::stoi, wie folgt aus :

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

Auf diese Weise kann die Leistung dem C-Stil nahe kommen oder sogar übertroffen werden scanf. Die Verwendung getcharund insbesondere getchar_unlockedzusammen mit handschriftlichem Parsen bietet immer noch eine bessere Leistung.

PS. Ich habe einen Beitrag geschrieben , in dem verschiedene Möglichkeiten zur Eingabe von Zahlen in C ++ verglichen werden. Dies ist nützlich für Online-Richter, aber leider nur auf Russisch. Die Codebeispiele und die endgültige Tabelle sollten jedoch verständlich sein.

Ilya Popov
quelle
1
Vielen Dank für die Erklärung und +1 für die Lösung, aber Ihre vorgeschlagene Alternative mit std::readlineund std::stoientspricht nicht funktional dem OP-Code. Beide cin >> x;und scanf("%f", &x);Ameisen-Leerzeichen als Trennzeichen akzeptieren, können mehrere Zahlen in derselben Zeile stehen.
Chqrlie
27

Das Problem ist, dass unter Angabe von cppreference :

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

Dies ist leicht zu testen: wenn Sie ersetzen

cin >> fact_num;

mit

scanf("%d", &fact_num);

und das Gleiche für, cin >> num_of_inputsaber behalten coutSie , dass Sie in Ihrer C ++ - Version (oder besser gesagt in der IOStream-Version) fast die gleiche Leistung erhalten wie in C 1:

Geben Sie hier die Bildbeschreibung ein

Das gleiche passiert, wenn Sie behalten, cinaber ersetzen

cout << num_of_trailing_zeros << "\n";

mit

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

Eine einfache Lösung besteht darin, zu lösen coutund cinwie von Ilya Popov erwähnt:

cin.tie(nullptr);

Standardbibliotheksimplementierungen dürfen in bestimmten Fällen den Aufruf zum Löschen weglassen, jedoch nicht immer. Hier ist ein Zitat aus C ++ 14 27.7.2.1.3 (danke an chqrlie):

Klasse basic_istream :: sentry: Wenn is.tie () kein Nullzeiger ist, ruft die Funktion is.tie () -> flush () auf, um die Ausgabesequenz mit einem zugehörigen externen C-Stream zu synchronisieren. Nur dass dieser Aufruf unterdrückt werden kann, wenn der Put-Bereich von is.tie () leer ist. Ferner kann eine Implementierung den Aufruf zum Leeren verschieben, bis ein Aufruf von is.rdbuf () -> underflow () auftritt. Wenn ein solcher Aufruf nicht erfolgt, bevor das Wachobjekt zerstört wurde, kann der Aufruf zum Löschen vollständig beseitigt werden.

vitaut
quelle
Danke für die Erklärung. Noch unter Angabe C ++ 14 27.7.2.1.3: Klasse basic_istream :: Sentry : Erstens, wenn is.tie()nicht ein Nullzeiger ist, die Funktionsaufrufe is.tie()->flush()die Ausgangssequenz mit einem beliebigen zugeordneten externen C Strom zu synchronisieren. Außer dass dieser Aufruf unterdrückt werden kann, wenn der Put-Bereich von is.tie()leer ist. Ferner kann eine Implementierung den Aufruf zum Leeren verschieben, bis ein Aufruf von is.rdbuf()->underflow()auftritt. Wenn ein solcher Aufruf nicht erfolgt, bevor das Wachobjekt zerstört wurde, kann der Aufruf zum Löschen vollständig beseitigt werden.
Chqrlie
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
Danke für den cppreference Link. Die "falsche Antwort" auf dem Druckbildschirm gefällt mir allerdings nicht ☺
Alex Lop.
@AlexLop. Hoppla, das Problem mit der "falschen Antwort" wurde behoben =). Ich habe vergessen, das andere Kino zu aktualisieren (dies hat jedoch keinen Einfluss auf das Timing).
Vitaut
@chqrlie Richtig, aber selbst im Unterlauffall ist die Leistung im Vergleich zur Standardlösung wahrscheinlich schlechter. Danke für die Standardreferenz.
Vitaut