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




fin getline (8)

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

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

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

$ 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

Piccolo punto di riferimento e riepilogo

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 il confronto, con diverse soluzioni / approcci:

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

Answer #1

Bene, vedo che nella tua seconda soluzione sei passato da cin a scanf , che è stato il primo suggerimento che stavo per farti (cin è sloooooooooooow). Ora, se si passa da scanf a fgets , si noterà un ulteriore aumento delle prestazioni: fgets è la funzione C ++ più veloce per l'input di stringhe.

A proposito, non sapevo cosa fosse la sincronizzazione, bello. Ma dovresti comunque provare fgets .


Answer #2

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

Answer #3

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`. (Probabilmente questo ti guadagnerebbe un premio "Uso inutile del gatto" se fossi Randal Schwartz.

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 - mostrando che può solo passare il tempo in cui il singolo elemento della pipeline passa ad esso sulla sua linea 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 di `cat` con qualche piccolo fattore per" perdonare "il costo dell'esecuzione di` cat` stesso.


Answer #4

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

Answer #5

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.


Answer #6

Nel secondo esempio (con scanf ()) il motivo per cui questo è ancora più lento potrebbe essere perché scanf ("% s") analizza la stringa e cerca qualsiasi spazio char (spazio, tab, newline).

Inoltre, sì, CPython fa un po 'di cache per evitare letture di dischi rigidi.


Answer #7

Di default, cin è sincronizzato con stdio, il che fa sì che eviti qualsiasi buffer di input. Se lo aggiungi alla parte superiore del tuo main, dovresti vedere prestazioni molto migliori:

std::ios_base::sync_with_stdio(false);

Normalmente, quando viene bufferizzato un flusso di input, anziché leggere un carattere alla volta, lo stream verrà letto in blocchi più grandi. Ciò riduce il numero di chiamate di sistema, che sono in genere relativamente costose. Tuttavia, poiché lo stdio e gli iostreams basati su FILE* spesso hanno implementazioni separate e quindi buffer separati, ciò potrebbe causare un problema se entrambi fossero utilizzati insieme. Per esempio:

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

Se cin più input è stato letto da quello effettivamente necessario, allora il secondo valore intero non sarebbe disponibile per la funzione scanf , che ha il proprio buffer indipendente. Ciò porterebbe a risultati inaspettati.

Per evitare questo, per impostazione predefinita, i flussi sono sincronizzati con stdio . Un modo comune per raggiungere questo obiettivo è quello di far leggere a cin ogni personaggio uno alla volta secondo necessità utilizzando le funzioni stdio . Sfortunatamente, questo introduce un sacco di spese generali. Per piccole quantità di input, questo non è un grosso problema, ma quando si leggono milioni di righe, la penalizzazione delle prestazioni è significativa.

Fortunatamente, i progettisti della biblioteca hanno deciso che dovresti essere in grado di disabilitare questa funzione per ottenere prestazioni migliori se sapessi cosa stavi facendo, quindi hanno fornito il metodo sync_with_stdio .





getline