Ich wollte das Lesen von Zeilen der Zeichenfolgeneingabe von stdin mit Python und C ++ vergleichen und war schockiert, als mein C ++ - Code eine Größenordnung langsamer als der entsprechende Python-Code ausgeführt wurde. Da mein C ++ rostig ist und ich noch kein Pythonista-Experte bin, sagen Sie mir bitte, ob ich etwas falsch mache oder ob ich etwas falsch verstehe.
(TLDR-Antwort: Fügen Sie die Anweisung hinzu: cin.sync_with_stdio(false)
oder verwenden Sie fgets
stattdessen einfach .
TLDR-Ergebnisse: Scrollen Sie bis zum Ende meiner Frage und sehen Sie sich die Tabelle 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
Ich sollte beachten, dass ich dies sowohl unter Mac OS X 10.6.8 (Snow Leopard) als auch unter Linux 2.6.32 (Red Hat Linux 6.2) versucht habe. Ersteres ist ein MacBook Pro, und letzteres ist ein sehr leistungsfähiger Server, nicht dass dies zu relevant wäre.
$ 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
Winziger Benchmark-Nachtrag und Zusammenfassung
Der Vollständigkeit halber dachte ich, ich würde die Lesegeschwindigkeit für dieselbe Datei auf derselben Box mit dem ursprünglichen (synchronisierten) C ++ - Code aktualisieren. Dies gilt wiederum für eine 100-MB-Zeilendatei auf einer schnellen Festplatte. Hier ist der Vergleich mit mehreren Lösungen / Ansätzen:
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
<iostream>
Leistung ist schlecht. Nicht das erste Mal, dass es passiert. 2) Python ist klug genug, um die Daten nicht in die for-Schleife zu kopieren, weil Sie sie nicht verwenden. Sie könnten erneut versuchen, zu verwendenscanf
und achar[]
. Alternativ können Sie versuchen, die Schleife neu zu schreiben, damit etwas mit der Zeichenfolge getan wird (z. B. den 5. Buchstaben behalten und in einem Ergebnis verketten).cin.eof()
!! Setzen Sie dengetline
Aufruf in die 'if'-Anweisung.wc -l
ist schnell, da der Stream mehr als eine Zeile gleichzeitig liest (dies kann einefread(stdin)/memchr('\n')
Kombination sein). Python-Ergebnisse sind in der gleichen Größenordnung, zBwc-l.py
Antworten:
Standardmäßig wird
cin
es mit stdio synchronisiert, wodurch jegliche Eingabepufferung vermieden wird. Wenn Sie dies oben in Ihrem Hauptfenster hinzufügen, sollten Sie eine viel bessere Leistung sehen:Wenn ein Eingabestream gepuffert wird, wird der Stream normalerweise in größeren Blöcken gelesen, anstatt jeweils ein Zeichen zu lesen. Dies reduziert die Anzahl der Systemaufrufe, die typischerweise relativ teuer sind. Da die
FILE*
basiertenstdio
undiostreams
häufig getrennten Implementierungen und daher getrennte Puffer haben, könnte dies zu einem Problem führen, wenn beide zusammen verwendet würden. Zum Beispiel:Wenn mehr Eingaben gelesen würden,
cin
als tatsächlich benötigt würden, wäre der zweite ganzzahlige Wert für diescanf
Funktion, die über einen eigenen unabhängigen Puffer verfügt, nicht verfügbar . Dies würde zu unerwarteten Ergebnissen führen.Um dies zu vermeiden, werden Streams standardmäßig mit synchronisiert
stdio
. Eine übliche Möglichkeit, dies zu erreichen, besteht darincin
, jedes Zeichen nach Bedarf mithilfe vonstdio
Funktionen einzeln zu lesen . Dies führt leider zu einem hohen Overhead. Bei kleinen Eingaben ist dies kein großes Problem, aber wenn Sie Millionen von Zeilen lesen, ist der Leistungsverlust erheblich.Glücklicherweise haben die Bibliotheksdesigner entschieden, dass Sie diese Funktion auch deaktivieren können sollten, um eine verbesserte Leistung zu erzielen, wenn Sie wissen, was Sie tun. Daher haben sie die
sync_with_stdio
Methode bereitgestellt .quelle
fscanf
Aufruf zu ersetzen , da dies ganz einfach nicht so viel Arbeit leistet wie Python. Python muss Speicher für die Zeichenfolge zuweisen, möglicherweise mehrmals, da die vorhandene Zuordnung als unzureichend angesehen wird - genau wie beim C ++ - Ansatz mitstd::string
. Diese Aufgabe ist mit ziemlicher Sicherheit an E / A gebunden, und es geht viel zu viel FUD um die Kosten für das Erstellen vonstd::string
Objekten in C ++ oder die Verwendung<iostream>
an und für sich.sync_with_stdio()
eine statische Elementfunktion ist und ein Aufruf dieser Funktion für ein beliebiges Stream-Objekt (z. B.cin
) die Synchronisierung für alle Standard-Iostream-Objekte ein- oder ausschaltet .Nur aus Neugier habe ich mir angesehen, was unter der Haube passiert, und ich habe Dtruss / Strace verwendet bei jedem Test verwendet.
C ++
Systemaufrufe
sudo dtruss -c ./a.out < in
Python
Systemaufrufe
sudo dtruss -c ./a.py < in
quelle
Ich bin ein paar Jahre hinterher, aber:
In 'Edit 4/5/6' des ursprünglichen Beitrags verwenden Sie die Konstruktion:
Dies ist in vielerlei Hinsicht falsch:
Sie planen tatsächlich die Ausführung
cat
, nicht Ihren Benchmark. Die ‚Benutzer‘ und ‚sys‘ CPU - Auslastung angezeigt durchtime
diejenigen sindcat
, nicht Ihre gebenchmarkt Programm. Schlimmer noch, die "Echtzeit" ist auch nicht unbedingt genau. Abhängig von der Implementierung voncat
und von Pipelines in Ihrem lokalen Betriebssystem ist es möglich, dasscat
ein endgültiger Riesenpuffer geschrieben und beendet wird, lange bevor der Lesevorgang seine Arbeit beendet.Die Verwendung von
cat
ist unnötig und in der Tat kontraproduktiv; Sie fügen bewegliche Teile hinzu. Wenn Sie sich auf einem ausreichend alten System befinden (dh mit einer einzelnen CPU und - bei bestimmten Computergenerationen - E / A schneller als die CPU), kann die bloße Tatsache, dass siecat
ausgeführt wird, die Ergebnisse erheblich beeinflussen. Sie unterliegen auch jeglicher Eingabe- und Ausgabepufferung und anderer Verarbeitungcat
. (Dies würde Ihnen wahrscheinlich die Auszeichnung "Nutzlose Verwendung von Katzen" einbringen, wenn ich Randal Schwartz wäre.Eine bessere Konstruktion wäre:
In dieser Anweisung ist es die Shell, die big_file öffnet und
time
als bereits geöffneter Dateideskriptor an Ihr Programm übergibt (also tatsächlich an das dann Ihr Programm als Unterprozess ausgeführt wird). 100% des Dateilesens liegt ausschließlich in der Verantwortung des Programms, das Sie bewerten möchten. Auf diese Weise erhalten Sie einen echten Überblick über die Leistung ohne störende Komplikationen.Ich werde zwei mögliche, aber tatsächlich falsche "Korrekturen" erwähnen, die ebenfalls in Betracht gezogen werden könnten (aber ich "nummeriere" sie unterschiedlich, da dies keine Dinge sind, die im ursprünglichen Beitrag falsch waren):
A. Sie können dies beheben, indem Sie nur Ihr Programm zeitlich festlegen:
B. oder durch Timing der gesamten Pipeline:
Diese sind aus den gleichen Gründen wie # 2 falsch: Sie werden immer noch
cat
unnötig verwendet. Ich erwähne sie aus mehreren Gründen:Sie sind „natürlicher“ für Personen, die mit den E / A-Umleitungsfunktionen der POSIX-Shell nicht ganz vertraut sind
kann es Fälle geben, wo
cat
ist erforderlich (zB: die Datei erfordert eine Art Privileg , den Zugang zu lesen, und Sie wollen nicht dieses Privileg , um das Programm zu gewähren , werden gebenchmarkt:sudo cat /dev/sda | /usr/bin/time my_compression_test --no-output
)In der Praxis hat das Hinzufügen moderner Maschinen auf modernen Maschinen
cat
wahrscheinlich keine wirkliche Konsequenz.Aber ich sage das letzte mit einigem Zögern. Wenn wir das letzte Ergebnis in 'Edit 5' untersuchen -
- dies behauptet, dass
cat
74% der CPU während des Tests verbraucht wurden; und tatsächlich ist 1,34 / 1,83 ungefähr 74%. Vielleicht eine Serie von:hätte nur die restlichen 0,49 Sekunden gedauert! Wahrscheinlich nicht:
cat
Hier mussten dieread()
Systemaufrufe (oder gleichwertige) bezahlt werden, die die Datei von 'disk' (eigentlich Puffer-Cache) übertragen haben, sowie die Pipe-Schreibvorgänge, um sie zu liefernwc
. Der richtige Test hätte diese noch durchführen müssenread()
Anrufe ; nur die Write-to-Pipe- und Read-from-Pipe-Aufrufe wären gespeichert worden, und diese sollten ziemlich billig sein.Trotzdem gehe ich davon aus, dass Sie den Unterschied zwischen messen können
cat file | wc -l
undwc -l < file
und einen spürbaren Unterschied (zweistelliger Prozentsatz) feststellen können. Jeder der langsameren Tests hat in absoluter Zeit eine ähnliche Strafe gezahlt; Dies würde jedoch einen kleineren Bruchteil seiner größeren Gesamtzeit ausmachen.Tatsächlich habe ich einige schnelle Tests mit einer 1,5-Gigabyte-Mülldatei auf einem Linux 3.13-System (Ubuntu 14.04) durchgeführt, um diese Ergebnisse zu erhalten (dies sind tatsächlich die besten 3-Ergebnisse; natürlich nach dem Priming des Caches):
Beachten Sie, dass die beiden Pipeline-Ergebnisse angeblich mehr CPU-Zeit (Benutzer + System) als die tatsächliche Wanduhrzeit in Anspruch genommen haben. Dies liegt daran, dass ich den in die Shell (bash) integrierten Befehl 'time' verwende, der die Pipeline kennt. und ich bin auf einem Multi-Core-Computer, auf dem separate Prozesse in einer Pipeline separate Kerne verwenden können, wodurch die CPU-Zeit schneller als in Echtzeit angesammelt wird. Verwenden von
/usr/bin/time
sehe ich eine geringere CPU-Zeit als in Echtzeit - dies zeigt, dass nur das einzelne Pipeline-Element, das an ihn übergeben wurde, in der Befehlszeile zeitlich festgelegt werden kann. Außerdem gibt die Ausgabe der Shell Millisekunden an, während/usr/bin/time
nur Hundertstelsekunden ausgegeben werden .Also auf dem Wirkungsgrad von
wc -l
, dercat
macht einen großen Unterschied: 409/283 = 1,453 oder 45,3% mehr in Echtzeit, und 775/280 = 2,768, oder ein sattes 177% mehr CPU verwendet! Auf meiner zufälligen Testbox war es zu der Zeit da.Ich sollte hinzufügen, dass es mindestens einen weiteren signifikanten Unterschied zwischen diesen Teststilen gibt, und ich kann nicht sagen, ob es sich um einen Vorteil oder einen Fehler handelt. das musst du selbst entscheiden:
Wenn Sie ausführen
cat big_file | /usr/bin/time my_program
, empfängt Ihr Programm Eingaben von einer Pipe, genau in dem Tempo, das von gesendet wirdcat
, und in Blöcken, die nicht größer als von geschrieben sindcat
.Wenn Sie ausführen
/usr/bin/time my_program < big_file
, 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 unterschiedliche Aktionen ausführen, wenn ein Dateideskriptor angezeigt wird, der auf eine reguläre Datei verweist. Es kann verwendet werdenmmap(2)
, um die Eingabedatei ihrem Adressraum zuzuordnen, anstatt expliziteread(2)
Systemaufrufe zu verwenden. Diese Unterschiede können sich weitaus stärker auf Ihre Benchmark-Ergebnisse auswirken als die geringen Kosten für die Ausführung dercat
Binärdatei.Natürlich ist es ein interessantes Benchmark-Ergebnis, wenn dasselbe Programm zwischen den beiden Fällen signifikant unterschiedlich abschneidet. Es zeigt , dass in der Tat, das Programm oder dessen I / O - Bibliotheken sind etwas Interessantes zu tun, wie mit
mmap()
. In der Praxis kann es daher sinnvoll sein, die Benchmarks in beide Richtungen auszuführen. Vielleicht wird dascat
Ergebnis um einen kleinen Faktor abgezinst , um die Kosten für den Betriebcat
selbst zu "verzeihen" .quelle
$ < big_file time my_program
$ time < big_file my_program
Dies sollte in jeder POSIX-Shell (dh nicht in `csh) funktionieren `und ich bin mir nicht sicher über exotica wie` rc` :)time
misst die gesamte Pipeline anstelle des ersten Programms.time seq 2 | while read; do sleep 1; done
druckt 2 Sek.,/usr/bin/time seq 2 | while read; do sleep 1; done
druckt 0 Sek.Ich habe das ursprüngliche Ergebnis auf meinem Computer mit g ++ auf einem Mac reproduziert.
Durch Hinzufügen der folgenden Anweisungen zur C ++ - Version unmittelbar vor der
while
Schleife wird sie mit der Python- Version in Einklang gebracht :sync_with_stdio verbesserte die Geschwindigkeit auf 2 Sekunden und durch Einstellen eines größeren Puffers auf 1 Sekunde.
quelle
getline
Stream-Operatorenscanf
können nützlich sein, wenn Sie sich nicht für die Ladezeit von Dateien interessieren oder wenn Sie kleine Textdateien laden. Wenn Sie sich jedoch für die Leistung interessieren, sollten Sie die gesamte Datei einfach in den Speicher puffern (vorausgesetzt, sie passt).Hier ist ein Beispiel:
Wenn Sie möchten, können Sie einen Stream um diesen Puffer wickeln, um einen bequemeren Zugriff wie folgt zu erhalten:
Wenn Sie die Kontrolle über die Datei haben, sollten Sie auch ein flaches Binärdatenformat anstelle von Text verwenden. Lesen und Schreiben ist zuverlässiger, da Sie sich nicht mit allen Mehrdeutigkeiten von Leerzeichen auseinandersetzen müssen. Es ist auch kleiner und viel schneller zu analysieren.
quelle
Der folgende Code war für mich schneller als der andere Code, der bisher hier veröffentlicht wurde: (Visual Studio 2013, 64-Bit-Datei mit 500 MB und einheitlicher Zeilenlänge in [0, 1000)).
Es übertrifft alle meine Python-Versuche um mehr als den Faktor 2.
quelle
read
Systemaufrufe in einen statischen Puffer der LängeBUFSIZE
oder über die entsprechenden entsprechendenmmap
Systemaufrufe iterativ umwandelt und dann durch diesen Puffer peitscht und die Zeilenumbrüche à la zählt, können Sie noch schneller werdenfor (char *cp = buf; *cp; cp++) count += *cp == "\n"
. Sie müssen sich jedochBUFSIZE
auf Ihr System einstellen, was stdio bereits für Sie getan hat. Aber dasfor
Schleife sollte awesomely kompiliert nach unten zu schreien schnellen Assemblersprache Anweisungen für die Hardware Ihrer Box.Der Grund, warum die Zeilenanzahl für die C ++ - Version um eins höher ist als die Anzahl für die Python-Version, ist übrigens, dass das eof-Flag nur gesetzt wird, wenn versucht wird, über eof hinaus zu lesen. Die richtige Schleife wäre also:
quelle
while (getline(cin, input_line)) line_count++;
++line_count;
und nichtline_count++;
.long
, und der Compiler kann durchaus erkennen, dass das Ergebnis des Inkrements nicht verwendet wird. Wenn kein identischer Code für Nach- und Vorinkrementierung generiert wird, ist er fehlerhaft.++line_count;
stattline_count++;
nicht schaden :)while
, oder? Wäre es wichtig, wenn es einen Fehler gäbe und Sie sicherstellen möchten, dass der Fehlerline_count
korrekt ist? Ich rate nur, aber ich verstehe nicht, warum es wichtig sein würde.In Ihrem zweiten Beispiel (mit scanf ()) liegt dies möglicherweise daran, dass scanf ("% s") die Zeichenfolge analysiert und nach Leerzeichen (Leerzeichen, Tabulator, Zeilenumbruch) sucht.
Ja, CPython führt auch ein Caching durch, um das Lesen von Festplatten zu vermeiden.
quelle
Ein erstes Element einer Antwort:
<iostream>
ist langsam. Verdammt langsam. Ich bekomme einen enormen Leistungsschub mitscanf
wie unten, aber es ist immer noch zweimal langsamer als Python.quelle
Nun, ich sehe, dass Sie in Ihrer zweiten Lösung von
cin
zu gewechselt habenscanf
, was der erste Vorschlag war, den ich Ihnen machen wollte (cin ist sloooooooooooow). Wenn Sie jetzt vonscanf
zu wechselnfgets
, sehen Sie einen weiteren Leistungsschub:fgets
ist die schnellste C ++ - Funktion für die Eingabe von Zeichenfolgen.Übrigens, wusste nichts über diese Synchronisierungssache, nett. Aber du solltest es trotzdem versuchen
fgets
.quelle
fgets
ist falsch (in Bezug auf die Anzahl der Zeilen und in Bezug auf die Aufteilung der Zeilen auf Schleifen, wenn Sie sie tatsächlich verwenden müssen) für ausreichend große Zeilen, ohne zusätzliche Überprüfungen auf unvollständige Zeilen (und der Versuch, dies zu kompensieren, erfordert die Zuweisung unnötig großer Puffer , wostd::getline
die Neuzuweisung nahtlos mit der tatsächlichen Eingabe übereinstimmt). Schnell und falsch ist einfach, aber es lohnt sich fast immer, "etwas langsamer, aber korrekt" zu verwenden, was Sie beim Ausschaltensync_with_stdio
bringt.