benchmarking - Warum liest man Zeilen von stdin in C++viel langsamer als in Python?




readline getline (9)

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++;
};

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

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.


getline , stream operators, scanf , kann praktisch sein, wenn Sie sich nicht um das Laden von Dateien kümmern oder wenn Sie kleine Textdateien laden. Aber wenn die Leistung etwas ist, das Ihnen wichtig ist, sollten Sie nur die gesamte Datei in den Speicher puffern (vorausgesetzt, es passt).

Hier ist ein Beispiel:

//open file in binary mode
std::fstream file( filename, std::ios::in|::std::ios::binary );
if( !file ) return NULL;

//read the size...
file.seekg(0, std::ios::end);
size_t length = (size_t)file.tellg();
file.seekg(0, std::ios::beg);

//read into memory buffer, then close it.
char *filebuf = new char[length+1];
file.read(filebuf, length);
filebuf[length] = '\0'; //make it null-terminated
file.close();

Wenn Sie möchten, können Sie einen Stream um diesen Puffer wickeln, um bequemeren Zugriff zu erhalten:

std::istrstream header(&buffer[0], length);

Wenn Sie die Datei steuern, sollten Sie auch ein flaches binäres Datenformat anstelle von Text verwenden. Es ist zuverlässiger zu lesen und zu schreiben, weil Sie nicht mit allen Unklarheiten von Leerzeichen fertig werden müssen. Es ist auch kleiner und viel schneller zu analysieren.


In Ihrem zweiten Beispiel (mit scanf ()) kann dies daran liegen, dass scanf ("% s") die Zeichenfolge analysiert und nach einem beliebigen Leerzeichen (Leerzeichen, Tabulator, Newline) sucht.

Auch, ja, CPython macht etwas Caching, um Festplattenlesevorgänge zu vermeiden.


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".


Ich reproduzierte das ursprüngliche Ergebnis auf meinem Computer mit g ++ auf einem Mac.

Das Hinzufügen der folgenden Anweisungen zur C ++ - Version unmittelbar vor der while Schleife bringt sie inline mit der Python Version:

std::ios_base::sync_with_stdio(false);
char buffer[1048576];
std::cin.rdbuf()->pubsetbuf(buffer, sizeof(buffer));

sync_with_stdio verbesserte die Geschwindigkeit auf 2 Sekunden, und die Einstellung eines größeren Puffers brachte es auf 1 Sekunde herunter.


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

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;
}

Ich denke, der folgende Code ist besser, mit einigen C ++ 17 und C ++ 14 Funktionen:

// These codes are un-tested when I write this post, but I'll test it
// When I'm free, and I sincerely welcome others to test and modify this
// code.

// C++17
#include <istream>     // For std::istream.
#include <string_view> // new feature in C++17, sizeof(std::string_view) == 16 in libc++ on my x86-64 debian 9.4 computer.
#include <string>
#include <utility>     // C++14 feature std::move.

template <template <class...> class Container, class Allocator>
void split1(Container<std::string_view, Allocator> &tokens, 
            std::string_view str,
            std::string_view delimiter = " ") 
{
    /* 
     * The model of the input string:
     *
     * (optional) delimiter | content | delimiter | content | delimiter| 
     * ... | delimiter | content 
     *
     * Using std::string::find_first_not_of or 
     * std::string_view::find_first_not_of is a bad idea, because it 
     * actually does the following thing:
     * 
     *     Finds the first character not equal to any of the characters 
     *     in the given character sequence.
     * 
     * Which means it does not treeat your delimiters as a whole, but as
     * a group of characters.
     * 
     * This has 2 effects:
     *
     *  1. When your delimiters is not a single character, this function
     *  won't behave as you predicted.
     *
     *  2. When your delimiters is just a single character, the function
     *  may have an additional overhead due to the fact that it has to 
     *  check every character with a range of characters, although 
     * there's only one, but in order to assure the correctness, it still 
     * has an inner loop, which adds to the overhead.
     *
     * So, as a solution, I wrote the following code.
     *
     * The code below will skip the first delimiter prefix.
     * However, if there's nothing between 2 delimiter, this code'll 
     * still treat as if there's sth. there.
     *
     * Note: 
     * Here I use C++ std version of substring search algorithm, but u
     * can change it to Boyer-Moore, KMP(takes additional memory), 
     * Rabin-Karp and other algorithm to speed your code.
     * 
     */

    // Establish the loop invariant 1.
    typename std::string_view::size_type 
        next, 
        delimiter_size = delimiter.size(),  
        pos = str.find(delimiter) ? 0 : delimiter_size;

    // The loop invariant:
    //  1. At pos, it is the content that should be saved.
    //  2. The next pos of delimiter is stored in next, which could be 0
    //  or std::string_view::npos.

    do {
        // Find the next delimiter, maintain loop invariant 2.
        next = str.find(delimiter, pos);

        // Found a token, add it to the vector
        tokens.push_back(str.substr(pos, next));

        // Skip delimiters, maintain the loop invariant 1.
        //
        // @ next is the size of the just pushed token.
        // Because when next == std::string_view::npos, the loop will
        // terminate, so it doesn't matter even if the following 
        // expression have undefined behavior due to the overflow of 
        // argument.
        pos = next + delimiter_size;
    } while(next != std::string_view::npos);
}   

template <template <class...> class Container, class traits, class Allocator2, class Allocator>
void split2(Container<std::basic_string<char, traits, Allocator2>, Allocator> &tokens, 
            std::istream &stream,
            char delimiter = ' ')
{
    std::string<char, traits, Allocator2> item;

    // Unfortunately, std::getline can only accept a single-character 
    // delimiter.
    while(std::getline(stream, item, delimiter))
        // Move item into token. I haven't checked whether item can be 
        // reused after being moved.
        tokens.push_back(std::move(item));
}

Die Wahl des Behälters:

  1. std::vector .

    Unter der Annahme, dass die anfängliche Größe des zugewiesenen internen Arrays 1 ist und die endgültige Größe N ist, werden Sie die Log2 (N) -Zeiten zuweisen und freigeben, und Sie kopieren die (2 ^ (log2 (N) + 1) - 1) = (2N - 1) mal. Wie bereits in Ist die schlechte Leistung von std :: Vektor aufgrund der nicht realloc eine logarithmische Anzahl von Zeiten aufrufen? Dies kann eine schlechte Leistung haben, wenn die Größe des Vektors unvorhersehbar ist und sehr groß sein kann. Aber wenn Sie die Größe davon schätzen können, wird dies weniger ein Problem sein.

  2. std::list .

    Für jeden push_back ist die Zeit, die es verbraucht, eine Konstante, aber es dauert wahrscheinlich länger als std :: vector auf der individuellen push_back. Die Verwendung eines Threadpools pro Thread und eines benutzerdefinierten Zuordners kann dieses Problem beheben.

  3. std::forward_list .

    Wie std :: list, belegt aber weniger Speicherplatz pro Element. Erfordert, dass eine Wrapper-Klasse aufgrund der fehlenden API push_back funktioniert.

  4. std::array .

    Wenn Sie die Wachstumsgrenze kennen, können Sie std :: array verwenden. Natürlich können Sie es nicht direkt verwenden, da es nicht über die API push_back verfügt. Aber Sie können einen Wrapper definieren, und ich denke, es ist der schnellste Weg hier und kann etwas Speicher sparen, wenn Ihre Schätzung ziemlich genau ist.

  5. std::deque .

    Mit dieser Option können Sie den Speicher für die Leistung tauschen. Es wird keine (2 ^ (N + 1) - 1) mal Kopie des Elements, nur N-mal-Zuweisung und keine Freigabe geben. Außerdem haben Sie eine konstante Zugriffszeit und die Möglichkeit, an beiden Enden neue Elemente hinzuzufügen.

Entsprechend std::deque-cppreference

Auf der anderen Seite haben Deques typischerweise große minimale Speicherkosten; Eine Deque, die nur ein Element enthält, muss ihr gesamtes internes Array zuweisen (z. B. das 8-fache der Objektgröße auf 64-bit libstdc ++; das 16-fache der Objektgröße oder 4096 Bytes, je nachdem was größer ist, auf 64-bit libc ++)

oder Sie können die Kombination dieser verwenden:

  1. std::vector< std::array<T, 2 ^ M> >

    Dies ist vergleichbar mit std :: deque, der Unterschied ist nur, dass dieser Container kein Element an der Front hinzufügen kann. Aber es ist immer noch schneller in der Leistung, aufgrund der Tatsache, dass es das zugrundeliegende std :: array nicht für (2 ^ (N + 1) - 1) mal kopiert, sondern nur das Zeigerarray für (2 ^ (N - M + 1) - 1) mal, und das Zuweisen eines neuen Arrays nur, wenn der aktuelle Wert voll ist und keine Zuweisung aufgehoben werden muss. Übrigens können Sie konstante Direktzugriffszeit erhalten.

  2. std::list< std::array<T, ...> >

    Erleichtern Sie den Druck der Erinnerungsfragmentierung erheblich. Es wird nur dann ein neues Array zuweisen, wenn der aktuelle Wert voll ist, und muss nichts kopieren. Sie müssen immer noch den Preis für einen zusätzlichen Zeiger im Vergleich zu Combo 1 zahlen.

  3. std::forward_list< std::array<T, ...> >

    Wie 2, aber kostet den gleichen Speicher wie Combo 1.





c++ python benchmarking readline getline