Dlaczego czytanie linii ze standardowego wejścia w C ++ jest znacznie wolniejsze niż w Pythonie?

Chciałem porównać odczytane wiersze wejściowych ciągów ze standardowego wejścia przy użyciu Pythona i C ++ i byłem zszokowany, gdy mój kod C ++ działał o rząd wielkości wolniej niż równoważny kod Pythona. Ponieważ mój C ++ jest zardzewiały i nie jestem jeszcze ekspertem Pythonista, proszę powiedz mi, czy robię coś źle lub coś źle rozumiem.

(Odpowiedź TLDR: dołącz instrukcję: cin.sync_with_stdio(false)lub po prostu użyj fgetszamiast tego.

Wyniki TLDR: przewiń do samego końca pytania i spójrz na tabelę).

Kod C ++:

#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

Odpowiednik Pythona:

#!/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))

Oto moje wyniki:

$ 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

Powinienem zauważyć, że próbowałem tego zarówno w systemie Mac OS X 10.6.8 (Snow Leopard), jak i Linux 2.6.32 (Red Hat Linux 6.2). Ten pierwszy to MacBook Pro, a ten drugi to bardzo mocny serwer, ale nie jest to zbyt istotne.

$ 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

Małe uzupełnienie i podsumowanie testu porównawczego

Dla kompletności pomyślałem, że zaktualizuję prędkość odczytu tego samego pliku w tym samym pudełku z oryginalnym (zsynchronizowanym) kodem C ++. Ponownie, dotyczy to pliku liniowego 100M na szybkim dysku. Oto porównanie z kilkoma rozwiązaniami / podejściami:

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

Domyślnie cinjest synchronizowany ze stdio, co powoduje, że unika buforowania danych wejściowych. Jeśli dodasz to do górnej części głównej, powinieneś zobaczyć znacznie lepszą wydajność:

std::ios_base::sync_with_stdio(false);

Zwykle, gdy strumień wejściowy jest buforowany, zamiast odczytywania jednego znaku na raz, strumień będzie odczytywany w większych fragmentach. Zmniejsza to liczbę wywołań systemowych, które zwykle są stosunkowo drogie. Ponieważ jednak FILE*bazowe stdioi iostreamsczęsto mają osobne implementacje, a zatem osobne bufory, może to prowadzić do problemu, jeśli oba zostaną użyte razem. Na przykład:

int myvalue1;
cin >> myvalue1;
int myvalue2;
scanf("%d",&myvalue2);

Jeśli odczytano więcej danych wejściowych, cinniż było to potrzebne, wówczas druga wartość całkowita nie byłaby dostępna dla scanffunkcji, która ma swój własny niezależny bufor. Doprowadziłoby to do nieoczekiwanych rezultatów.

Aby tego uniknąć, domyślnie strumienie są synchronizowane stdio. Jednym z powszechnych sposobów osiągnięcia tego celu jest cinodczytywanie każdego znaku po kolei za pomocą stdiofunkcji. Niestety wprowadza to wiele kosztów ogólnych. W przypadku niewielkiej ilości danych wejściowych nie jest to duży problem, ale gdy czytasz miliony wierszy, znaczna jest utrata wydajności.

Na szczęście projektanci bibliotek zdecydowali, że powinieneś być w stanie wyłączyć tę funkcję, aby uzyskać lepszą wydajność, jeśli wiesz, co robisz, więc podali tę sync_with_stdiometodę.

Właśnie z ciekawości przyjrzałem się, co dzieje się pod maską, i użyłem dtruss / strace na każdym teście.

C ++

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

wywołania systemowe 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

Pyton

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

wywołania systemowe sudo dtruss -c ./a.py < in

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

Jestem tu kilka lat wstecz, ale:

W „Edycji 4/5/6” oryginalnego postu używasz konstrukcji:

$ /usr/bin/time cat big_file | program_to_benchmark

Jest to złe na kilka różnych sposobów:

1. Rzeczywiście mierzysz czas wykonania cat, a nie testu. Wyświetlane przez użytkownika użycie procesora przez „użytkownika” i „sys” oznacza użycie timeprogramu cat, a nie programu testowego. Co gorsza, „czas rzeczywisty” niekoniecznie jest dokładny. W zależności od implementacji cati potoków w lokalnym systemie operacyjnym możliwe jest, że catzapisze ostateczny gigantyczny bufor i zostanie zamknięty na długo przed zakończeniem pracy czytnika.

2. Używanie catjest niepotrzebne i faktycznie przynosi efekt przeciwny do zamierzonego; dodajesz ruchome części. Jeśli korzystasz z wystarczająco starego systemu (tj. Z jednym procesorem i - w niektórych generacjach komputerów - I / O szybszym niż procesor) - sam fakt, który catdziałał, może znacznie pokolorować wyniki. Podlegasz również wszelkiemu buforowaniu danych wejściowych i wyjściowych oraz innego przetwarzania cat. (Prawdopodobnie dałbym ci nagrodę „Bezużyteczne użytkowanie kota”, gdybym był Randalem Schwartzem.

Lepszą konstrukcją byłoby:

$ /usr/bin/time program_to_benchmark < big_file

W tej instrukcji jest to powłoka, która otwiera duży_plik, przekazując go do twojego programu (cóż, właściwie do timektórego następnie wykonuje twój program jako podproces) jako już otwarty deskryptor pliku. 100% odczytu pliku jest ściśle obowiązkiem programu, który próbujesz przetestować. Dzięki temu możesz naprawdę odczytać jego wydajność bez fałszywych komplikacji.

Wspomnę o dwóch możliwych, ale w rzeczywistości błędnych „poprawkach”, które można również wziąć pod uwagę (ale „numeruję” je inaczej, ponieważ nie są to rzeczy, które były złe w oryginalnym poście):

A. Możesz to naprawić, mierząc czas tylko swojego programu:

$ cat big_file | /usr/bin/time program_to_benchmark

B. lub mierząc czas całego rurociągu:

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

Są one błędne z tych samych powodów, co # 2: nadal używają catniepotrzebnie. Wspominam o nich z kilku powodów:

• są bardziej „naturalne” dla osób, które nie do końca czują się dobrze z funkcjami przekierowywania we / wy powłoki POSIX

• mogą być przypadki, gdzie cat jest potrzebne (np: plik do odczytu wymaga pewnego rodzaju przywilej dostępu, i nie chcą przyznać, że uprawnienie do programu należy odwzorować: sudo cat /dev/sda | /usr/bin/time my_compression_test --no-output)

• w praktyce na nowoczesnych maszynach dodanie catdo rurociągu prawdopodobnie nie ma rzeczywistych konsekwencji.

Ale mówię to z wahaniem. Jeśli sprawdzimy ostatni wynik w „Edycji 5” -

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

- twierdzi, że catzużywa 74% procesora podczas testu; i faktycznie 1,34 / 1,83 wynosi około 74%. Być może seria:

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

zajęłoby tylko pozostałe 0,49 sekundy! Prawdopodobnie nie: cattutaj trzeba było zapłacić za read()wywołania systemowe (lub równoważne), które przeniosły plik z „dysku” (faktycznie bufor pamięci podręcznej), a także zapisy potoku, aby je dostarczyć wc. Właściwy test nadal musiałby wykonywać te read()połączenia; zapisywane byłyby tylko wywołania zapisu do potoku i odczytu z potoku, a te powinny być dość tanie.

Mimo to przewidywania będzie można zmierzyć różnicę między cat file | wc -la wc -l < filei znaleźć zauważalny (2-cyfrowy) procentową różnicę. Każdy wolniejszy test zapłaci podobną karę w czasie bezwzględnym; co jednak stanowiłoby mniejszy ułamek jego większego całkowitego czasu.

W rzeczywistości zrobiłem kilka szybkich testów z plikiem śmieci 1,5 gigabajta, na systemie Linux 3.13 (Ubuntu 14.04), uzyskując te wyniki (w rzeczywistości są to wyniki „najlepsze z 3”; oczywiście po zainicjowaniu pamięci podręcznej):

$ 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)

Zauważ, że wyniki dwóch potoków twierdzą, że zajęły więcej czasu procesora (użytkownik + sys) niż rzeczywisty czas zegara ściennego. Jest tak, ponieważ używam wbudowanego polecenia powłoki (bash) „time”, które rozpoznaje potok; i jestem na wielordzeniowym komputerze, na którym osobne procesy w potoku mogą korzystać z oddzielnych rdzeni, akumulując czas procesora szybciej niż w czasie rzeczywistym. Używając /usr/bin/timewidzę mniejszy czas procesora niż w czasie rzeczywistym - pokazując, że może on tylko zmierzyć czas pojedynczego elementu potoku przekazanego do niego w wierszu poleceń. Ponadto, wynik powłoki daje milisekundy, a /usr/bin/timejedynie setne sekundy.

Tak na poziomie sprawności wc -lThe catrobi ogromną różnicę: 409/283 = 1,453 lub 45,3% więcej w czasie rzeczywistym, a 775/280 = 2.768, czyli aż o 177% więcej CPU używane! Na moim losowym pudełku testowym „był tam, kiedy był”.

Powinienem dodać, że istnieje co najmniej jedna znacząca różnica między tymi stylami testowania i nie mogę powiedzieć, czy jest to korzyść, czy wina; musisz sam to zdecydować:

Kiedy uruchamiasz cat big_file | /usr/bin/time my_program, twój program odbiera dane wejściowe z potoku, dokładnie w tempie wysyłanym przez cati w kawałkach nie większych niż napisane przez cat.

Po uruchomieniu /usr/bin/time my_program < big_fileprogram otrzymuje otwarty deskryptor pliku do rzeczywistego pliku. Twój program - lub w wielu przypadkach biblioteki I / O języka, w którym został napisany - może podejmować różne działania, gdy zostanie przedstawiony deskryptor pliku odnoszący się do zwykłego pliku. Może użyć mmap(2)do mapowania pliku wejściowego do jego przestrzeni adresowej, zamiast używania jawnych read(2)wywołań systemowych. Różnice te mogą mieć znacznie większy wpływ na wyniki testu porównawczego niż niewielki koszt uruchomienia pliku catbinarnego.

Oczywiście jest to interesujący wynik testu porównawczego, jeśli ten sam program działa znacząco różnie w obu przypadkach. To pokazuje, że rzeczywiście, program lub jego biblioteki I / O są robi coś ciekawego, jak przy użyciu mmap(). Tak więc w praktyce może być dobrze przeprowadzić testy porównawcze w obie strony; być może pomniejszając catwynik o jakiś drobny czynnik, aby „wybaczyć” catsamemu sobie koszty .

Odtworzyłem oryginalny wynik na moim komputerze, używając g ++ na komputerze Mac.

Dodanie następujących instrukcji do wersji C ++ tuż przed tym, jak whilepętla dostosuje ją do wersji Python :

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

sync_with_stdio poprawił prędkość do 2 sekund, a ustawienie większego bufora sprowadziło ją do 1 sekundy.

getline, operatorzy strumieniowi scanf, może być wygodny, jeśli nie obchodzi Cię czas ładowania pliku lub jeśli ładujesz małe pliki tekstowe. Ale jeśli zależy Ci na wydajności, powinieneś po prostu buforować cały plik do pamięci (zakładając, że będzie pasował).

Oto przykład:

//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();

Jeśli chcesz, możesz owinąć strumień wokół tego bufora, aby uzyskać bardziej wygodny dostęp:

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

Ponadto, jeśli masz kontrolę nad plikiem, rozważ użycie płaskiego binarnego formatu danych zamiast tekstu. Czytanie i pisanie jest bardziej niezawodne, ponieważ nie musisz radzić sobie z wszystkimi dwuznacznościami białych znaków. Jest także mniejszy i znacznie szybszy do analizy.

Poniższy kod był dla mnie szybszy niż inny kod opublikowany tutaj tutaj: (Visual Studio 2013, 64-bitowy, 500 MB plik o długości linii równomiernie w [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'; });
}

Pokonuje wszystkie moje próby w Pythonie ponad dwa razy.

Nawiasem mówiąc, powodem, dla którego liczba wierszy dla wersji C ++ jest większa niż liczba dla wersji Pythona, jest to, że flaga eof jest ustawiana tylko wtedy, gdy próba odczytu odbywa się poza eof. Tak więc poprawna pętla to:

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

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

W twoim drugim przykładzie (z scanf ()) powodem, dla którego wciąż jest wolniejszy, może być to, że scanf ("% s") analizuje ciąg znaków i szuka dowolnego znaku spacji (spacja, tabulator, nowa linia).

Ponadto tak, CPython wykonuje pewne buforowanie, aby uniknąć odczytów z dysku twardego.

Pierwszy element odpowiedzi: <iostream>jest powolny. Cholera powolna. Mam ogromny wzrost wydajności, jak pokazano scanfponiżej, ale wciąż jest dwa razy wolniejszy niż 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;
}

Cóż, widzę, że w twoim drugim rozwiązaniu przełączyłeś się cinna scanf, co było pierwszą sugestią, którą chciałem cię zmusić (cin to sloooooooooooow). Teraz, jeśli przełączysz się z scanfna fgets, zobaczysz kolejny wzrost wydajności: fgetsjest to najszybsza funkcja C ++ do wprowadzania ciągów znaków.

BTW, nie wiedziałem o tej synchronizacji, miło. Ale nadal powinieneś spróbować fgets.