[c++] Warum liest man Zeilen von stdin in C ++ viel langsamer als in Python?


Answers

Aus dtruss/strace Neugier habe ich mir mal angesehen, was unter der Haube passiert, und ich habe bei jedem Test dtruss/strace .

C ++

./a.out < in
Saw 6512403 lines in 8 seconds.  Crunch speed: 814050

syscalls sudo dtruss -c ./a.out < in

CALL                                        COUNT
__mac_syscall                                   1
<snip>
open                                            6
pread                                           8
mprotect                                       17
mmap                                           22
stat64                                         30
read_nocancel                               25958

Python

./a.py < in
Read 6512402 lines in 1 seconds. LPS: 6512402

syscalls sudo dtruss -c ./a.py < in

CALL                                        COUNT
__mac_syscall                                   1
<snip>
open                                            5
pread                                           8
mprotect                                       17
mmap                                           21
stat64                                         29
Question

Ich wollte Lesezeilen der Stringeingabe von stdin mit Python und C ++ vergleichen und war schockiert, dass mein C ++ - Code eine Größenordnung langsamer lief als der entsprechende Python-Code. Da mein C ++ rostig ist und ich noch kein Experte für Pythonista bin, sag mir bitte, ob ich etwas falsch mache oder ob ich etwas falsch verstehe.

(TLDR-Antwort: Fügen Sie die Anweisung ein: cin.sync_with_stdio(false) oder verwenden fgets stattdessen fgets .

TLDR-Ergebnisse: blättern Sie bis zum Ende meiner Frage und schauen Sie sich den Tisch an.)

C ++ - Code:

#include <iostream>
#include <time.h>

using namespace std;

int main() {
    string input_line;
    long line_count = 0;
    time_t start = time(NULL);
    int sec;
    int lps;

    while (cin) {
        getline(cin, input_line);
        if (!cin.eof())
            line_count++;
    };

    sec = (int) time(NULL) - start;
    cerr << "Read " << line_count << " lines in " << sec << " seconds.";
    if (sec > 0) {
        lps = line_count / sec;
        cerr << " LPS: " << lps << endl;
    } else
        cerr << endl;
    return 0;
}

// Compiled with:
// g++ -O3 -o readline_test_cpp foo.cpp

Python-Äquivalent:

#!/usr/bin/env python
import time
import sys

count = 0
start = time.time()

for line in  sys.stdin:
    count += 1

delta_sec = int(time.time() - start_time)
if delta_sec >= 0:
    lines_per_sec = int(round(count/delta_sec))
    print("Read {0} lines in {1} seconds. LPS: {2}".format(count, delta_sec,
       lines_per_sec))

Hier sind meine Ergebnisse:

$ cat test_lines | ./readline_test_cpp
Read 5570000 lines in 9 seconds. LPS: 618889

$cat test_lines | ./readline_test.py
Read 5570000 lines in 1 seconds. LPS: 5570000

Edit: Ich sollte beachten, dass ich dies sowohl unter Mac OS X 10.6.8 (Snow Leopard) und Linux 2.6.32 (Red Hat Linux 6.2) ausprobiert habe. Das erste ist ein MacBook Pro, und das letztere ist ein sehr bulliger Server, nicht dass dies zu sachdienlich ist.

Edit 2: (Diese Bearbeitung wurde entfernt, da sie nicht mehr anwendbar ist)

$ for i in {1..5}; do echo "Test run $i at `date`"; echo -n "CPP:"; cat test_lines | ./readline_test_cpp ; echo -n "Python:"; cat test_lines | ./readline_test.py ; done
Test run 1 at Mon Feb 20 21:29:28 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 2 at Mon Feb 20 21:29:39 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 3 at Mon Feb 20 21:29:50 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 4 at Mon Feb 20 21:30:01 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 5 at Mon Feb 20 21:30:11 EST 2012
CPP:   Read 5570001 lines in 10 seconds. LPS: 557000
Python:Read 5570000 lines in  1 seconds. LPS: 5570000

Bearbeiten 3:

Okay, ich habe JN's Vorschlag ausprobiert, Python die Zeile lesen zu lassen, aber es machte keinen Unterschied zu Pythons Geschwindigkeit.

Ich habe auch den Vorschlag von JN ausprobiert, scanf in ein char Array zu verwenden, anstatt getline in eine std::string . Bingo! Dies führte zu einer gleichwertigen Leistung für Python und C ++. (3.333.333 LPS mit meinen Eingabedaten, die übrigens nur kurze Zeilen von je drei Feldern sind, meist etwa 20 Zeichen breit, wenn auch manchmal mehr).

Code:

char input_a[512];
char input_b[32];
char input_c[512];
while(scanf("%s %s %s\n", input_a, input_b, input_c) != EOF) {
    line_count++;
};

Geschwindigkeit:

$ cat test_lines | ./readline_test_cpp2
Read 10000000 lines in 3 seconds. LPS: 3333333
$ cat test_lines | ./readline_test2.py
Read 10000000 lines in 3 seconds. LPS: 3333333

(Ja, ich habe es mehrmals ausgeführt.) Also, ich schätze, ich werde jetzt scanf anstelle von getline . Aber ich bin immer noch neugierig, ob Leute denken, dass diese Leistung von std::string / getline ist typisch und vernünftig.

Edit 4 (war: Final Edit / Lösung):

Hinzufügen:

cin.sync_with_stdio(false);

Unmittelbar über meiner ursprünglichen while-Schleife ergibt sich Code, der schneller als Python läuft.

Neuer Leistungsvergleich (auf meinem 2011 MacBook Pro), bei dem der Originalcode, das Original mit deaktivierter Synchronisierung und der ursprüngliche Python-Code in einer Datei mit 20 Millionen Textzeilen verwendet werden. Ja, ich habe es mehrere Male ausgeführt, um das Festplatten-Caching zu vermeiden.

$ /usr/bin/time cat test_lines_double | ./readline_test_cpp
       33.30 real         0.04 user         0.74 sys
Read 20000001 lines in 33 seconds. LPS: 606060
$ /usr/bin/time cat test_lines_double | ./readline_test_cpp1b
        3.79 real         0.01 user         0.50 sys
Read 20000000 lines in 4 seconds. LPS: 5000000
$ /usr/bin/time cat test_lines_double | ./readline_test.py
        6.88 real         0.01 user         0.38 sys
Read 20000000 lines in 6 seconds. LPS: 3333333

Danke an @Vaughn Cato für seine Antwort! Jede Ausarbeitung, die Leute machen können, oder gute Referenzen, auf die die Leute hinweisen können, warum diese Synchronisierung geschieht, was es bedeutet, wann es nützlich ist und wann es in Ordnung ist, es zu deaktivieren, würde von der Nachwelt sehr geschätzt werden. :-)

Edit 5 / Bessere Lösung:

Wie von Gandalf The Gray unten vorgeschlagen, ist scanf sogar schneller als scanf oder der unsynchronisierte cin Ansatz. Ich habe auch gelernt, dass scanf und gets sind beide UNSAFE und sollte nicht verwendet werden, wegen möglicher Pufferüberlauf. Also schrieb ich diese Iteration mit fgets , der sichereren Alternative zu fgets . Hier sind die entsprechenden Zeilen für meine Kollegen noobs:

char input_line[MAX_LINE];
char *result;

//<snip>

while((result = fgets(input_line, MAX_LINE, stdin )) != NULL)
    line_count++;
if (ferror(stdin))
    perror("Error reading stdin.");

Nun, hier sind die Ergebnisse mit einer noch größeren Datei (100M Zeilen; ~ 3,4 GB) auf einem schnellen Server mit sehr schneller Festplatte, Vergleichen der Python-Code, der unsynchronisierten cin , und die fgets Ansätze, sowie mit dem wc-Dienstprogramm verglichen . [Die scanf Versions-Segmentierung ist fehlerhaft und ich habe keine Lust, sie zu scanf .]:

$ /usr/bin/time cat temp_big_file | readline_test.py
0.03user 2.04system 0:28.06elapsed 7%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
Read 100000000 lines in 28 seconds. LPS: 3571428

$ /usr/bin/time cat temp_big_file | readline_test_unsync_cin
0.03user 1.64system 0:08.10elapsed 20%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
Read 100000000 lines in 8 seconds. LPS: 12500000

$ /usr/bin/time cat temp_big_file | readline_test_fgets
0.00user 0.93system 0:07.01elapsed 13%CPU (0avgtext+0avgdata 2448maxresident)k
0inputs+0outputs (0major+181minor)pagefaults 0swaps
Read 100000000 lines in 7 seconds. LPS: 14285714

$ /usr/bin/time cat temp_big_file | wc -l
0.01user 1.34system 0:01.83elapsed 74%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
100000000


Recap (lines per second):
python:         3,571,428
cin (no sync): 12,500,000
fgets:         14,285,714
wc:            54,644,808

Wie Sie sehen können, ist fgets besser, aber immer noch ziemlich weit von WC-Leistung; Ich bin mir ziemlich sicher, dass dies auf die Tatsache zurückzuführen ist, dass wc jedes Zeichen überprüft, ohne dass ein Speicher kopiert wird. Ich vermute, dass an dieser Stelle andere Teile des Codes zum Engpass werden, daher glaube ich nicht, dass sich eine Optimierung auf dieses Niveau auch nur lohnen würde, wenn es möglich wäre (schließlich muss ich eigentlich die Leselinien speichern) in Erinnerung).

Beachten Sie auch, dass ein kleiner Kompromiss bei der Verwendung von char * buffer und fgets vs. unsynchronized cin to string darin besteht, dass die Letzteren Zeilen beliebiger Länge lesen können, während Ersteres die Begrenzung der Eingabe auf eine endliche Zahl erfordert. In der Praxis ist dies wahrscheinlich kein Problem für das Lesen der meisten zeilenbasierten Eingabedateien, da der Puffer auf einen sehr großen Wert gesetzt werden kann, der von einer gültigen Eingabe nicht überschritten wird.

Das war lehrreich. Danke an alle für Ihre Kommentare und Vorschläge.

Edit 6:

Wie von JF Sebastian in den Kommentaren vorgeschlagen, verwendet das Dienstprogramm GNU wc das reelle C read() (innerhalb des safe-read.c-Wrappers), um Blöcke (von 16k Bytes) gleichzeitig zu lesen und neue Zeilen zu zählen. Hier ist ein Python-Äquivalent, das auf dem JF-Code basiert (es wird nur das relevante Snippet gezeigt, das die Python- for Schleife ersetzt:

BUFFER_SIZE = 16384
count = sum(chunk.count('\n') for chunk in iter(partial(sys.stdin.read, BUFFER_SIZE), ''))

Die Leistung dieser Version ist ziemlich schnell (obwohl sie immer noch etwas langsamer als das rohe C wc-Dienstprogramm ist):

$ /usr/bin/time cat temp_big_file | readline_test3.py
0.01user 1.16system 0:04.74elapsed 24%CPU (0avgtext+0avgdata 2448maxresident)k
0inputs+0outputs (0major+181minor)pagefaults 0swaps
Read 100000000 lines in 4.7275 seconds. LPS: 21152829

Auch hier ist es ein wenig albern, C ++ fgets / cin und den ersten Python-Code einerseits mit wc -l und andererseits mit dem letzten Python-Snippet zu vergleichen, da die letzten beiden die gelesenen Zeilen nicht speichern, sondern zählt nur Zeilenumbrüche. Dennoch ist es interessant, all die verschiedenen Implementierungen zu untersuchen und über die Auswirkungen auf die Performance nachzudenken. Danke noch einmal!

Edit 7: Kleiner Benchmark-Nachtrag und Zusammenfassung

Der Vollständigkeit halber dachte ich, ich würde die Lesegeschwindigkeit für die gleiche Datei in derselben Box mit dem ursprünglichen (synchronisierten) C ++ - Code aktualisieren. Dies gilt wiederum für eine 100M-Zeilendatei auf einer schnellen Festplatte. Hier ist die komplette Tabelle jetzt:

Implementation      Lines per second
python (default)           3,571,428
cin (default/naive)          819,672
cin (no sync)             12,500,000
fgets                     14,285,714
wc (not fair comparison)  54,644,808



Ich bin ein paar Jahre hier hinten, aber:

In 'Edit 4/5/6' des ursprünglichen Posts verwenden Sie die Konstruktion:

$ /usr/bin/time cat big_file | program_to_benchmark

Das ist auf verschiedene Arten falsch:

  1. Sie planen tatsächlich die Ausführung von "Katze", nicht Ihre Benchmark. Die 'user' und 'sys' CPU-Auslastung, die durch `time` angezeigt werden, sind diejenigen von` cat`, nicht Ihr Benchmark-Programm. Schlimmer noch, die "echte" Zeit ist auch nicht unbedingt genau. Abhängig von der Implementierung von `cat` und von Pipelines in Ihrem lokalen Betriebssystem ist es möglich, dass` cat` einen letzten gigantischen Puffer schreibt und lange bevor der Reader seine Arbeit beendet, beendet wird.

  2. Die Verwendung von "Katze" ist unnötig und in der Tat kontraproduktiv; Sie fügen bewegliche Teile hinzu. Wenn Sie auf einem ausreichend alten System (dh mit einer einzigen CPU und - in bestimmten Generationen von Computern - I / O schneller als CPU) waren - konnte die bloße Tatsache, dass "cat" lief, die Ergebnisse wesentlich färben. Sie unterliegen auch, was auch immer Input und Output-Pufferung und andere Verarbeitung "Katze" tun können. (Dies würde Ihnen wahrscheinlich einen 'Useless Use Of Cat' Preis einbringen, wenn ich Randal Schwartz wäre: https://en.wikipedia.org/wiki/Cat_(Unix)#UUOC_(Useless_Use_Of_Cat) )

Eine bessere Konstruktion wäre:

$ /usr/bin/time program_to_benchmark < big_file

In dieser Anweisung ist es die Shell, die big_file öffnet und sie an Ihr Programm (also tatsächlich an "time", das dann Ihr Programm als Subprozess ausführt) als einen bereits geöffneten Dateideskriptor übergibt. 100% des Lesens von Dateien liegt ausschließlich in der Verantwortung des Programms, das Sie benchmarken möchten. Dies ermöglicht es Ihnen, seine Leistung ohne falsche Komplikationen zu lesen.

Ich werde zwei mögliche, aber eigentlich falsche "Fixes" erwähnen, die ebenfalls berücksichtigt werden könnten (aber ich nummeriere sie anders, da es sich nicht um Dinge handelt, die im ursprünglichen Post falsch waren):

A. Sie können dies beheben, indem Sie nur Ihr Programm zeitlich festlegen:

$ cat big_file | /usr/bin/time program_to_benchmark

B. oder durch Timing der gesamten Pipeline:

$ /usr/bin/time sh -c 'cat big_file | program_to_benchmark'

Diese sind aus den gleichen Gründen wie Nr. 2 falsch: Sie verwenden immer noch "Katze" unnötig. Ich erwähne sie aus ein paar Gründen:

  • Sie sind "natürlicher" für Leute, die mit den I / O-Umleitungsmöglichkeiten der POSIX-Shell nicht ganz vertraut sind

  • Es kann Fälle geben, in denen `cat` benötigt wird (zB: Die zu lesende Datei benötigt eine Art von Zugriffsberechtigung, und Sie möchten diese Berechtigung nicht dem zu prüfenden Programm erteilen:` sudo cat / dev / sda | / usr / bin / time mein_kompressionstest --no-output`)

  • In der Praxis , auf modernen Maschinen, ist die hinzugefügte "Katze" in der Pipeline wahrscheinlich keine wirkliche Konsequenz

Aber ich sage das letzte mit etwas Zögern. Wenn wir das letzte Ergebnis in "Edit 5" untersuchen -

$ /usr/bin/time cat temp_big_file | wc -l
0.01user 1.34system 0:01.83elapsed 74%CPU ...

- Das behauptet, dass "cat" während des Tests 74% der CPU verbraucht hat; und tatsächlich ist 1,34 / 1,83 ungefähr 74%. Vielleicht eine Folge von:

$ /usr/bin/time wc -l < temp_big_file

hätte nur die restlichen .49 Sekunden genommen! Wahrscheinlich nicht: "cat" musste hier für die read () - Systemaufrufe (oder Äquivalente) bezahlen, die die Datei von "disk" (eigentlich Puffer-Cache) transferierten, sowie die Pipe-Schreibvorgänge, um sie an "wc" zu liefern. Der richtige Test hätte immer noch diese read () -Aufrufe machen müssen; nur die Write-to-Pipe- und Read-from-Pipe-Aufrufe wären gespeichert worden, und diese sollten ziemlich billig sein.

Trotzdem sage ich voraus, dass Sie den Unterschied zwischen `cat file | wc -l` und `wc -l <file` und finden einen merklichen (zweistelligen) Unterschied. Jeder der langsameren Tests hat eine ähnliche Strafe in absoluter Zeit bezahlt; was jedoch einen kleineren Teil seiner größeren Gesamtzeit bedeuten würde.

In der Tat habe ich ein paar schnelle Tests mit einer 1,5 Gigabyte großen Datei von Müll auf einem Linux 3.13 (Ubuntu 14.04) System durchgeführt und diese Ergebnisse erhalten (das sind tatsächlich "Best of 3" Ergebnisse; natürlich nach dem Vorbereiten des Caches):

$ time wc -l < /tmp/junk
real 0.280s user 0.156s sys 0.124s (total cpu 0.280s)
$ time cat /tmp/junk | wc -l
real 0.407s user 0.157s sys 0.618s (total cpu 0.775s)
$ time sh -c 'cat /tmp/junk | wc -l'
real 0.411s user 0.118s sys 0.660s (total cpu 0.778s)

Beachten Sie, dass die beiden Pipelineergebnisse mehr CPU-Zeit (Benutzer + System) als Echtzeit beanspruchen. Dies liegt daran, dass ich den eingebauten "time" -Befehl der Shell (Bash) verwende, der sich der Pipeline bewusst ist; und ich bin auf einer Multi-Core-Maschine, wo separate Prozesse in einer Pipeline separate Kerne verwenden können, wodurch CPU-Zeit schneller als in Echtzeit entsteht. Unter Verwendung von / usr / bin / time sehe ich eine geringere CPU-Zeit als in Echtzeit - was zeigt, dass es nur das einzelne Pipelineelement zeitlich steuern kann, das an seiner Befehlszeile übergeben wird. Außerdem liefert die Ausgabe der Shell Millisekunden, während / usr / bin / time nur Hundertstel Sekunden angibt.

Auf der Effizienzstufe von 'wc -l' macht die 'Katze' einen großen Unterschied: 409/283 = 1.453 oder 45.3% mehr Echtzeit und 775/280 = 2.768, oder satte 177% mehr CPU-Auslastung! Auf meiner zufälligen Test-Box.

Ich sollte hinzufügen, dass zwischen diesen Prüfungsarten mindestens ein weiterer signifikanter Unterschied besteht, und ich kann nicht sagen, ob es sich um einen Nutzen oder einen Fehler handelt. Sie müssen das selbst entscheiden:

Wenn Sie `cat big_file | / usr / bin / time my_program`, Ihr Programm empfängt eine Eingabe von einer Pipe, genau in dem Tempo, das von `cat` gesendet wird, und in Chunks, die nicht größer sind als von` cat` geschrieben.

Wenn Sie "/ usr / bin / time my_program <big_file" ausführen, erhält Ihr Programm einen offenen Dateideskriptor für die eigentliche Datei. Ihr Programm - oder in vielen Fällen die E / A-Bibliotheken der Sprache, in der es geschrieben wurde - kann verschiedene Aktionen ausführen, wenn es mit einem Dateideskriptor konfrontiert wird, der auf eine reguläre Datei verweist. Es kann mmap (2) verwenden, um die Eingabedatei in seinen Adressraum abzubilden, anstatt explizite (2) Systemaufrufe zu verwenden. Diese Unterschiede können einen weitaus größeren Effekt auf Ihre Benchmark-Ergebnisse haben als die geringen Kosten für die Ausführung der `cat`-Binärdatei.

Natürlich ist es ein interessantes Benchmark-Ergebnis, wenn das gleiche Programm zwischen den beiden Fällen signifikant unterschiedlich ist. Es zeigt, dass das Programm oder seine E / A-Bibliotheken tatsächlich etwas Interessantes tun, wie die Verwendung von mmap (). In der Praxis könnte es also gut sein, die Benchmarks in beide Richtungen zu setzen. vielleicht das "Katzen" -Ergebnis um einen kleinen Faktor herabsetzen, um die Kosten für das Ausführen von "Katze" selbst zu "verzeihen".




Ein erstes Element einer Antwort: <iostream> ist langsam. Verdammt langsam. Ich bekomme einen enormen Leistungsschub mit scanf wie im Folgenden, aber es ist immer noch zweimal langsamer als Python.

#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;

int main() {
    char buffer[10000];
    long line_count = 0;
    time_t start = time(NULL);
    int sec;
    int lps;

    int read = 1;
    while(read > 0) {
        read = scanf("%s", buffer);
        line_count++;
    };
    sec = (int) time(NULL) - start;
    line_count--;
    cerr << "Saw " << line_count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = line_count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } 
    else
        cerr << endl;
    return 0;
}



Der folgende Code war für mich schneller als der bisher hier veröffentlichte Code: (Visual Studio 2013, 64-Bit, 500 MB Datei mit Zeilenlänge einheitlich in [0, 1000)).

const int buffer_size = 500 * 1024;  // Too large/small buffer is not good.
std::vector<char> buffer(buffer_size);
int size;
while ((size = fread(buffer.data(), sizeof(char), buffer_size, stdin)) > 0) {
    line_count += count_if(buffer.begin(), buffer.begin() + size, [](char ch) { return ch == '\n'; });
}

Es schlägt alle meine Python-Versuche um mehr als einen Faktor 2.




Der Grund dafür, dass die Zeilenanzahl für die C ++ - Version um eins höher ist als die Anzahl für die Python-Version, ist, dass das eof-Flag nur gesetzt wird, wenn versucht wird, über eof hinaus zu lesen. Also wäre die richtige Schleife:

while (cin) {
    getline(cin, input_line);

    if (!cin.eof())
        line_count++;
};





Related