[c++] Perché leggere le righe da stdin è molto più lento in C ++ rispetto a Python?



4 Answers

Solo per curiosità ho dato un'occhiata a quello che succede sotto il cofano, e ho usato dtruss/strace su ogni test.

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

Pitone

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

Volevo confrontare le righe di lettura di input di stringa da stdin usando Python e C ++ ed ero scioccato nel vedere il mio codice C ++ eseguire un ordine di grandezza più lento del codice Python equivalente. Dato che il mio C ++ è arrugginito e non sono ancora un esperto Pythonista, ti prego di dirmi se sto facendo qualcosa di sbagliato o se sto fraintendendo qualcosa.

(Risposta TLDR: includi la frase: cin.sync_with_stdio(false) o usa invece fgets .

Risultati TLDR: scorri fino in fondo alla mia domanda e guarda la tabella.)

Codice 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

Equivalente Python:

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

Ecco i miei risultati:

$ 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: Devo notare che ho provato questo sia con Mac OS X v10.6.8 (Snow Leopard) e Linux 2.6.32 (Red Hat Linux 6.2). Il primo è un MacBook Pro, e quest'ultimo è un server molto robusto, non che questo sia troppo pertinente.

Modifica 2: (rimossa questa modifica, non più applicabile)

$ 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

Modifica 3:

Okay, ho provato il suggerimento di JN di provare a fare in modo che Python memorizzasse la riga, ma non ha fatto alcuna differenza con la velocità di Python.

Ho anche provato il suggerimento di JN di usare scanf in un array di char anziché in una std::string . Bingo! Ciò ha comportato prestazioni equivalenti sia per Python che per C ++. (3.333.333 LPS con i miei dati di input, che tra l'altro sono solo linee brevi di tre campi ciascuno, solitamente di circa 20 caratteri, anche se a volte di più).

Codice:

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

Velocità:

$ 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

(Sì, l'ho eseguito più volte.) Quindi, suppongo che ora utilizzerò scanf invece di getline . Ma, sono ancora curioso di getline se le persone pensano che questo successo nelle prestazioni di std::string / getline sia tipico e ragionevole.

Modifica 4 (era: Modifica finale / Soluzione):

Aggiunta:

cin.sync_with_stdio(false);

Immediatamente sopra il mio ciclo while originale sopra risulta un codice che gira più velocemente di Python.

Nuovo confronto delle prestazioni (questo è sul mio MacBook Pro 2011), utilizzando il codice originale, l'originale con la sincronizzazione disattivata e il codice Python originale, rispettivamente, su un file con 20M di righe di testo. Sì, l'ho eseguito più volte per eliminare la confusione nella cache del disco.

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

Grazie a @Vaughn Cato per la sua risposta! Qualsiasi tipo di elaborazione può fare o buone referenze le persone possono indicare perché questa sincronizzazione si verifica, che cosa significa, quando è utile, e quando va bene disabilitare sarà molto apprezzata dai posteri. :-)

Modifica 5 / Soluzione migliore:

Come suggerito da Gandalf The Gray in basso, gets è ancora più veloce di scanf o dell'approccio cin non sincronizzato. Ho anche appreso che scanf e gets sono entrambi UNSAFE e NON DEVONO ESSERE UTILIZZATI a causa del potenziale di overflow del buffer. Quindi, ho scritto questa iterazione usando fgets , l'alternativa più sicura per ottenere. Ecco le linee pertinenti per i miei amici noob:

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

Ora, ecco i risultati usando un file ancora più grande (linee da 100 M; ~ 3,4 GB) su un server veloce con disco molto veloce, confrontando il codice Python, l'approccio non sincronizzato e gli approcci di fgets , oltre a confrontare con l'utilità wc . [La segmentazione della versione scanf è in errore e non mi sembra di risolverlo.]:

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

Come potete vedere, i fgets sono migliori, ma ancora piuttosto lontani dalle prestazioni del wc; Sono abbastanza sicuro che questo è dovuto al fatto che wc esamina ogni personaggio senza alcuna copia di memoria. Sospetto che, a questo punto, altre parti del codice diventeranno il collo di bottiglia, quindi non penso che l'ottimizzazione per quel livello sarebbe anche utile, anche se possibile (poiché, dopo tutto, ho effettivamente bisogno di memorizzare le righe di lettura in memoria).

Si noti inoltre che un piccolo compromesso con l'utilizzo di un buffer char * e di fgets rispetto a cin -string non sincronizzati è che quest'ultimo può leggere linee di qualsiasi lunghezza, mentre il primo richiede un input di limitazione per un numero finito. In pratica, questo è probabilmente un non-problema per leggere la maggior parte dei file di input basati sulla linea, poiché il buffer può essere impostato su un valore molto grande che non verrebbe superato da un input valido.

Questo è stato educativo. Grazie a tutti per i vostri commenti e suggerimenti.

Modifica 6:

Come suggerito da JF Sebastian nei commenti qui sotto, l'utility wc GNU utilizza plain C read() (all'interno del wrapper safe-read.c) per leggere blocchi (di 16k byte) alla volta e contare nuove linee. Ecco un equivalente Python basato sul codice di JF (basta mostrare lo snippet pertinente che sostituisce il loop di Python for :

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

Le prestazioni di questa versione sono abbastanza veloci (anche se ancora un po 'più lente rispetto all'utilità Cc grezza C, ovviamente):

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

Ancora una volta, è un po 'sciocco per me confrontare C ++ fgets / cin e il primo codice Python da un lato con wc -l e quest'ultimo snippet Python dall'altro, poiché gli ultimi due non memorizzano effettivamente le righe di lettura, ma si limitano a contare le newline. Tuttavia, è interessante esplorare tutte le diverse implementazioni e pensare alle implicazioni di rendimento. Grazie ancora!

Modifica 7: Aggiunta e riepilogo di benchmark minuscolo

Per completezza, ho pensato di aggiornare la velocità di lettura per lo stesso file sulla stessa scatola con il codice C ++ originale (sincronizzato). Ancora una volta, questo è per un file di linea 100M su un disco veloce. Ecco la tabella completa ora:

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



Sono qualche anno indietro qui, ma:

In "Modifica 4/5/6" del post originale, stai utilizzando la costruzione:

$ /usr/bin/time cat big_file | program_to_benchmark

Questo è sbagliato in un paio di modi diversi:

  1. In realtà stai cronometrando l'esecuzione di `cat`, non il tuo punto di riferimento. L'utilizzo della CPU 'user' e 'sys' visualizzato da `time` sono quelli di` cat`, non il tuo programma benchmark. Ancora peggio, il tempo "reale" non è necessariamente preciso. A seconda dell'implementazione di `cat` e delle pipeline nel sistema operativo locale, è possibile che` cat` scriva un buffer gigante finale ed esce molto prima che il processo del lettore finisca il suo lavoro.

  2. L'uso di `cat` è inutile e in effetti controproducente; stai aggiungendo parti mobili. Se si fosse su un sistema sufficientemente vecchio (cioè con una singola CPU e - in alcune generazioni di computer - I / O più veloce della CPU) - il semplice fatto che `cat` fosse in esecuzione poteva sostanzialmente colorare i risultati. Sei anche soggetto a qualunque buffering di input e output e ad altre operazioni di `cat`. (Questo probabilmente ti farà guadagnare un premio "Uso inutile del gatto" se fossi Randal Schwartz: https://en.wikipedia.org/wiki/Cat_(Unix)#UUOC_(Useless_Use_Of_Cat) )

Una costruzione migliore sarebbe:

$ /usr/bin/time program_to_benchmark < big_file

In questa istruzione è la shell che apre big_file, passandola al tuo programma (beh, in realtà a `time` che poi esegue il tuo programma come sottoprocesso) come un descrittore di file già aperto. Il 100% della lettura del file è strettamente responsabilità del programma che stai cercando di confrontare. Questo ti dà una lettura reale delle sue prestazioni senza complicazioni spurie.

Citerò due possibili, ma in realtà sbagliati, "correzioni" che potrebbero anche essere considerate (ma le ho "numerate" diversamente dal momento che queste non sono cose che erano sbagliate nel post originale):

R. Potresti "sistemare" questo temporizzando solo il tuo programma:

$ cat big_file | /usr/bin/time program_to_benchmark

B. o cronometrando l'intera pipeline:

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

Questi sono sbagliati per gli stessi motivi del # 2: stanno ancora usando `cat` inutilmente. Li ho citati per alcuni motivi:

  • sono più "naturali" per le persone che non sono del tutto a proprio agio con le funzioni di reindirizzamento I / O della shell POSIX

  • ci possono essere casi in cui `cat` è necessario (ad esempio: il file da leggere richiede una sorta di privilegio per accedere, e non si vuole concedere tale privilegio al programma da sottoporre a benchmark:` sudo cat / dev / sda | / usr / bin / time my_compression_test --no-output`)

  • in pratica , su macchine moderne, il `gatto` aggiunto nella pipeline non ha probabilmente alcuna conseguenza reale

Ma io dico quell'ultima cosa con un po 'di esitazione. Se esaminiamo l'ultimo risultato in "Modifica 5" -

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

- questo afferma che `cat` ha consumato il 74% della CPU durante il test; e infatti 1.34 / 1.83 è circa il 74%. Forse una corsa di:

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

avrei preso solo i restanti 49 secondi! Probabilmente no: `cat` qui ha dovuto pagare per le chiamate di sistema read () (o equivalenti) che hanno trasferito il file da 'disk' (in effetti buffer cache), così come le pipe pipe per consegnarle a` wc`. Il test corretto avrebbe comunque dovuto fare quelle chiamate read (); solo le chiamate write-to-pipe e read-from-pipe sarebbero state salvate e quelle dovrebbero essere piuttosto economiche.

Tuttavia, prevedo che saresti in grado di misurare la differenza tra `cat file | wc -l` e `wc -l <file` e troviamo una differenza notevole (percentuale a due cifre). Ciascuno dei test più lenti avrà pagato una penalità simile in tempo assoluto; che tuttavia equivarrebbe ad una frazione più piccola del suo tempo totale più ampio.

In effetti ho eseguito alcuni test rapidi con un file di 1,5 gigabyte di garbage, su un sistema Linux 3.13 (Ubuntu 14.04), ottenendo questi risultati (questi sono in realtà i risultati "migliori di 3", dopo aver utilizzato la cache, ovviamente):

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

Si noti che i due risultati della pipeline dichiarano di aver impiegato più tempo CPU (utente + sys) rispetto al tempo reale. Questo perché sto usando il comando "time" incorporato della shell (Bash), che è a conoscenza della pipeline; e sono su una macchina multi-core in cui processi separati in una pipeline possono utilizzare core separati, accumulando tempo di CPU più veloce del tempo reale. Usando / usr / bin / time, vedo un tempo di CPU più piccolo del tempo reale, a dimostrazione del fatto che può passare solo il tempo in cui il singolo elemento della pipeline viene passato alla sua riga di comando. Inoltre, l'output della shell fornisce i millisecondi mentre / usr / bin / time dà solo un secondo di hundreth.

Quindi, a livello di efficienza di `wc -l`,` cat` fa una grande differenza: 409/283 = 1.453 o 45.3% in più in tempo reale, e 775/280 = 2.768, o un enorme 177% in più di CPU utilizzata! Sulla mia casella di prova casualmente era-lì-al-tempo.

Dovrei aggiungere che c'è almeno un'altra differenza significativa tra questi stili di test, e non posso dire se sia un vantaggio o un difetto; devi decidere da solo:

Quando esegui `cat big_file | / usr / bin / time my_program`, il tuo programma riceve input da una pipe, precisamente al ritmo inviato da `cat`, e in blocchi non più grandi di quelli scritti da` cat`.

Quando esegui `/ usr / bin / time my_program <big_file`, il tuo programma riceve un descrittore di file aperto nel file vero e proprio. Il tuo programma - o in molti casi le librerie di I / O della lingua in cui è stato scritto - può prendere diverse azioni quando viene presentato con un descrittore di file che fa riferimento a un file normale. Può utilizzare mmap (2) per mappare il file di input nel suo spazio indirizzo, invece di utilizzare chiamate di sistema esplicite di lettura (2). Queste differenze potrebbero avere un effetto molto più grande sui risultati del benchmark rispetto al piccolo costo dell'esecuzione del file binario cat.

Ovviamente è un interessante risultato di benchmark se lo stesso programma si comporta in modo significativamente diverso tra i due casi. Dimostra che, in effetti, il programma o le sue librerie di I / O stanno facendo qualcosa di interessante, come usare mmap (). Quindi, in pratica, potrebbe essere utile eseguire i benchmark in entrambe le direzioni; forse scontando il risultato `cat` di qualche piccolo fattore per" perdonare "il costo di eseguire` cat` stesso.




Il seguente codice è stato più veloce per me rispetto all'altro codice pubblicato finora: (Visual Studio 2013, file a 64 bit, 500 MB con lunghezza della linea uniformemente 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'; });
}

Batte tutti i miei tentativi Python di più di un fattore 2.




A proposito, il motivo per cui il conteggio delle righe per la versione C ++ è maggiore del conteggio per la versione di Python è che il flag di eof viene impostato solo quando si tenta di leggere oltre eof. Quindi il ciclo corretto sarebbe:

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

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



Un primo elemento di una risposta: <iostream> è lento. Accidenti, lento. Ottengo un enorme incremento delle prestazioni con scanf come nel seguito, ma è ancora due volte più lento di 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;
}



Related