Pregunta ¿Por qué las líneas de lectura de stdin son mucho más lentas en C ++ que en Python?


Quería comparar las líneas de lectura de entrada de cadena desde stdin usando Python y C ++ y me sorprendió ver que mi código C ++ corría un orden de magnitud más lento que el código Python equivalente. Como mi C ++ está oxidado y todavía no soy un Pythonista experto, dígame si estoy haciendo algo mal o si estoy malinterpretando algo.


(Respuesta TLDR: incluir la declaración: cin.sync_with_stdio(false) o simplemente usa fgets en lugar.

Resultados TLDR: desplácese hasta el final de mi pregunta y mire la tabla.)


Código 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 de 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))

Aquí están mis resultados:

$ 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

Editar:  Debo señalar que probé esto tanto con Mac OS X v10.6.8 (Snow Leopard) como con Linux 2.6.32 (Red Hat Linux 6.2). La primera es una MacBook Pro, y la última es un servidor muy robusto, no es que esto sea demasiado pertinente.

Editar 2:  (Se eliminó esta edición, como ya no es aplicable)

$ 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

Editar 3:

De acuerdo, probé la sugerencia de J.N. de tratar de que Python almacene la lectura de la línea, pero no cambió la velocidad de Python.

También probé la sugerencia de J.N. de usar scanf en un char matriz en lugar de getline en un std::string. ¡Bingo! Esto dio como resultado un rendimiento equivalente para Python y C ++. (3,333,333 LPS con mis datos de entrada, que por cierto son solo líneas cortas de tres campos cada uno, generalmente de unos 20 caracteres de ancho, aunque a veces más).

Código:

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

Velocidad:

$ 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í, lo ejecuté varias veces.) Entonces, supongo que ahora usaré scanf en lugar de getline. Pero, todavía tengo curiosidad de que la gente piense que este rendimiento se debe a std::string/getline es típico y razonable.

Editar 4 (fue: Final Edit / Solution):

Agregar:

cin.sync_with_stdio(false);

Inmediatamente por encima de mi ciclo while original, el resultado es un código que se ejecuta más rápido que Python.

Nueva comparación de rendimiento (esto está en mi MacBook Pro 2011), utilizando el código original, el original con la sincronización deshabilitada y el código de Python original, respectivamente, en un archivo con 20 millones de líneas de texto. Sí, lo ejecuté varias veces para eliminar la confusión del almacenamiento en caché de 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

¡Gracias a @Vaughn Cato por su respuesta! Cualquier elaboración que la gente pueda hacer o buenas referencias a las que la gente pueda hacer referencia en cuanto a por qué ocurre esta sincronización, qué significa, cuándo es útil y cuándo está bien desactivarla sería muy apreciada por la posteridad. :-)

Editar 5 / Mejor solución:

Como lo sugirió Gandalf The Gray a continuación, gets es incluso más rápido que scanf o el no sincronizado cin enfoque. También aprendí que scanf y gets no son SEGUROS y NO DEBEN UTILIZARSE debido al potencial de desbordamiento del búfer. Entonces, escribí esta iteración usando fgets, la alternativa más segura a get. Aquí están las líneas pertinentes para mis compañeros 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.");

Ahora, aquí están los resultados usando un archivo aún más grande (100M líneas; ~ 3.4 GB) en un servidor rápido con un disco muy rápido, comparando el código de Python, el no sincronizado cin, y el fgetsenfoques, así como la comparación con la utilidad wc. [Los scanf la segmentación de la versión falló y no tengo ganas de solucionarlo.]:

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

Como puedes ver, fgets es mejor, pero todavía bastante lejos del rendimiento del WC; Estoy bastante seguro de que esto se debe al hecho de que wc examina cada personaje sin ninguna copia de memoria. Sospecho que, en este punto, otras partes del código se convertirán en el cuello de botella, por lo que no creo que la optimización a ese nivel merezca la pena, incluso si es posible (ya que, después de todo, realmente necesito almacenar las líneas de lectura). en memoria).

También tenga en cuenta que una pequeña compensación con el uso de un char * buffer y fgets vs. Sin sincronizar cin to string es que este último puede leer líneas de cualquier longitud, mientras que el primero requiere limitar la entrada a algún número finito. En la práctica, esto probablemente no sea un problema para leer la mayoría de los archivos de entrada basados ​​en líneas, ya que el búfer se puede establecer en un valor muy grande que no se excedería con una entrada válida.

Esto ha sido educativo. Gracias a todos por sus comentarios y sugerencias.

Editar 6:

Según lo sugerido por J.F. Sebastian en los comentarios a continuación, la utilidad de wc de GNU utiliza C simple read() (dentro del contenedor safe-read.c) para leer fragmentos (de 16k bytes) a la vez y contar nuevas líneas. Aquí hay un equivalente de Python basado en el código de J.F. (solo muestra el fragmento relevante que reemplaza al Python) for lazo:

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

El rendimiento de esta versión es bastante rápido (aunque aún un poco más lento que la utilidad de C wc sin procesar, por supuesto):

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

De nuevo, es un poco tonto para mí comparar C ++ fgets/cin y el primer código python por un lado para wc -l y este último fragmento de Python por el otro, ya que los dos últimos no almacenan las líneas de lectura, sino que simplemente cuentan las nuevas líneas. Aún así, es interesante explorar todas las diferentes implementaciones y pensar en las implicaciones de rendimiento. ¡Gracias de nuevo!

Edición 7: Adición y recapitulación del punto de referencia minúsculo

Para completar, pensé que actualizaría la velocidad de lectura para el mismo archivo en el mismo cuadro con el código C ++ original (sincronizado). De nuevo, esto es para un archivo de línea de 100M en un disco rápido. Aquí está la tabla completa ahora:

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

1456
2018-02-21 03:24


origen


Respuestas:


Por defecto, cin está sincronizado con stdio, lo que hace que evite cualquier búfer de entrada. Si agrega esto a la parte superior de su principal, debería ver un rendimiento mucho mejor:

std::ios_base::sync_with_stdio(false);

Normalmente, cuando una corriente de entrada se almacena en búfer, en lugar de leer un carácter a la vez, la secuencia se leerá en trozos más grandes. Esto reduce la cantidad de llamadas al sistema, que generalmente son relativamente costosas. Sin embargo, desde el FILE* basado stdio y iostreams a menudo tienen implementaciones separadas y, por lo tanto, separa los búferes, esto podría generar un problema si ambos se usaran juntos. Por ejemplo:

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

Si más entrada fue leída por cin de lo que realmente necesita, entonces el segundo valor entero no estaría disponible para el scanf función, que tiene su propio buffer independiente. Esto llevaría a resultados inesperados.

Para evitar esto, de manera predeterminada, las transmisiones se sincronizan con stdio. Una forma común de lograr esto es tener cin lea cada personaje uno a la vez según sea necesario usando stdio funciones. Desafortunadamente, esto introduce una gran cantidad de gastos generales. Para pequeñas cantidades de entrada, este no es un gran problema, pero cuando lee millones de líneas, la penalización de rendimiento es significativa.

Afortunadamente, los diseñadores de la biblioteca decidieron que también debería poder deshabilitar esta característica para obtener un mejor rendimiento si supiera lo que estaba haciendo, por lo que proporcionaron el sync_with_stdio método.


1279
2018-03-11 18:10



Solo por curiosidad he echado un vistazo a lo que ocurre debajo del capó, y he usado dtruss / strace en cada prueba.

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

Pitón

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

115
2018-02-21 03:33



Estoy unos años atrás, pero:

En 'Editar 4/5/6' de la publicación original, está utilizando la construcción:

$ /usr/bin/time cat big_file | program_to_benchmark

Esto está mal de dos maneras diferentes:

  1. En realidad estás sincronizando la ejecución de `cat`, no tu punto de referencia. El uso de CPU 'usuario' y 'sys' mostrado por `tiempo 'son los de' gato ', no su programa de referencia. Peor aún, el tiempo "real" tampoco es necesariamente exacto. Dependiendo de la implementación de `cat` y de las tuberías en su sistema operativo local, es posible que` cat` escriba un buffer final gigante y salga mucho antes de que el proceso de lectura finalice su trabajo.

  2. El uso de `cat` es innecesario y de hecho contraproducente; estás agregando partes móviles. Si tuviera un sistema lo suficientemente antiguo (es decir, con una sola CPU y, en ciertas generaciones de computadoras, E / S más rápido que la CPU), el mero hecho de que `cat` se ejecutara podría colorear sustancialmente los resultados. También está sujeto a lo que pueda hacer el almacenamiento en búfer de entrada y salida y otro procesamiento `cat`. (Esto probablemente le otorgaría un premio de 'Uso inútil del gato' si fuera Randal Schwartz: https://en.wikipedia.org/wiki/Cat_(Unix)#UUOC_(Useless_Use_Of_Cat))

Una mejor construcción sería:

$ /usr/bin/time program_to_benchmark < big_file

En esta declaración, es el cáscara que abre big_file, pasándolo a su programa (bueno, en realidad a `time` que luego ejecuta su programa como un subproceso) como un descriptor de archivo ya abierto. El 100% de la lectura del archivo es estrictamente responsabilidad del programa que está tratando de comparar. Esto te hace una lectura real de su rendimiento sin complicaciones espurias.

Mencionaré dos "soluciones" posibles, pero realmente incorrectas, que también podrían considerarse (pero las "numere" de forma diferente ya que no son cosas que estaban mal en la publicación original):

R. Podrías 'arreglar' esto al sincronizar solo tu programa:

$ cat big_file | /usr/bin/time program_to_benchmark

B. o cronometrando la tubería completa:

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

Estos son incorrectos por las mismas razones que el # 2: todavía están usando `cat` innecesariamente. Los menciono por algunas razones:

  • son más "naturales" para las personas que no están del todo cómodas con las funciones de redirección de E / S del shell POSIX

  • puede haber casos donde `gato ' es necesario (por ejemplo: el archivo que se va a leer requiere algún tipo de privilegio para acceder, y no desea otorgar ese privilegio al programa que se comparará: `sudo cat / dev / sda | / usr / bin / time my_compression_test - no-output`)

  • en la práctica, en las máquinas modernas, el 'gato' añadido en la tubería probablemente no tenga consecuencias reales

Pero digo eso último con cierta vacilación. Si examinamos el último resultado en 'Editar 5' -

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

- esto afirma que `cat` consumió el 74% de la CPU durante la prueba; y de hecho 1.34 / 1.83 es ​​aproximadamente 74%. Tal vez una corrida de:

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

¡habría tomado solo los restantes .49 segundos! Probablemente no: `cat` aquí tuvo que pagar las llamadas al sistema de lectura () (o equivalente) que transfirió el archivo de 'disco' (en realidad memoria caché del búfer), así como las escrituras de la tubería para entregarlas a` wc`. La prueba correcta todavía tendría que hacer esas llamadas de lectura (); solo las llamadas de escritura a tubería y lectura desde tubería se habrían guardado, y esas deberían ser bastante baratas.

Aún así, predigo que sería capaz de medir la diferencia entre `archivo cat | wc -l` y `wc -l <file` y encuentra una diferencia notable (porcentaje de 2 dígitos). Cada una de las pruebas más lentas habrá pagado una penalización similar en tiempo absoluto; que sin embargo equivaldría a una fracción más pequeña de su tiempo total más grande.

De hecho, hice algunas pruebas rápidas con un archivo de basura de 1.5 gigabytes, en un sistema Linux 3.13 (Ubuntu 14.04), obteniendo estos resultados (estos son en realidad los 'mejores de 3' resultados, después de cebar el caché, por supuesto):

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

Tenga en cuenta que los dos resultados de la interconexión afirman haber tenido más tiempo de CPU (usuario + sys) que en tiempo real. Esto se debe a que estoy usando el comando integrado 'time' de shell (Bash), que es consciente de la interconexión; y estoy en una máquina multi-core donde los procesos separados en una tubería pueden usar núcleos separados, acumulando tiempo de CPU más rápido que en tiempo real. Usando / usr / bin / time veo un tiempo de CPU menor que en tiempo real, lo que muestra que solo puede medir el tiempo que el único elemento de interconexión pasó a él en su línea de comando. Además, la salida del shell da milisegundos mientras que / usr / bin / time solo da cientos de segundo.

Entonces, en el nivel de eficiencia de `wc -l`, el` gato` hace una gran diferencia: 409/283 = 1.453 o 45.3% más en tiempo real, y 775/280 = 2.768, ¡o un enorme 177% más de CPU utilizada! En mi caja de prueba aleatoria, "estaba ahí en el momento".

Debo añadir que existe al menos otra diferencia significativa entre estos estilos de prueba, y no puedo decir si es un beneficio o una falla; tienes que decidir esto tú mismo:

Cuando ejecuta `cat big_file | / usr / bin / time my_program`, su programa recibe entrada de un conducto, exactamente al ritmo enviado por `cat`, y en fragmentos no mayores que los escritos por` cat`.

Cuando ejecuta `/ usr / bin / time my_program <big_file`, su programa recibe un descriptor de archivo abierto en el archivo real. Tu programa - o en muchos casos, las bibliotecas de E / S del idioma en el que se escribieron pueden tomar diferentes acciones cuando se presentan con un descriptor de archivo que hace referencia a un archivo normal. Puede usar mmap (2) para asignar el archivo de entrada a su espacio de direcciones, en lugar de usar llamadas de sistema explícitas de lectura (2). Estas diferencias podrían tener un efecto mucho mayor en sus resultados de referencia que el pequeño costo de ejecutar el binario `cat`.

Por supuesto, es un resultado de punto de referencia interesante si el mismo programa tiene un rendimiento significativamente diferente entre los dos casos. Muestra que, de hecho, el programa o sus bibliotecas de E / S son haciendo algo interesante, como usar mmap (). Entonces, en la práctica, podría ser bueno ejecutar los puntos de referencia en ambos sentidos; quizás descontando el resultado del 'gato' por algún pequeño factor para "perdonar" el costo de ejecutar `cat` en sí mismo.


77
2018-03-13 23:04



Reproduje el resultado original en mi computadora usando g ++ en una Mac.

Agregando las siguientes declaraciones a la versión C ++ justo antes del while loop lo trae en línea con el Pitón versión:

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

sync_with_stdio mejoró la velocidad a 2 segundos, y establecer un buffer más grande lo redujo a 1 segundo.


75
2018-03-11 16:37



getlineoperadores de flujo scanf, puede ser conveniente si no te importa el tiempo de carga del archivo o si estás cargando archivos de texto pequeños. Pero, si el rendimiento es algo que te importa, en realidad deberías almacenar el archivo completo en la memoria (suponiendo que encaje).

Aquí hay un ejemplo:

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

Si lo desea, puede envolver una secuencia alrededor de ese búfer para un acceso más conveniente como este:

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

Además, si tiene el control del archivo, considere usar un formato plano de datos binarios en lugar de texto. Es más confiable leer y escribir porque no tiene que lidiar con todas las ambigüedades de los espacios en blanco. También es más pequeño y mucho más rápido de analizar.


23
2018-02-21 03:32



Por cierto, la razón por la que el conteo de líneas para la versión de C ++ es uno mayor que el recuento para la versión de Python es que el indicador de eof solo se establece cuando se intenta leer más allá de eof. Entonces, el ciclo correcto sería:

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

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

11
2018-02-21 03:17



El siguiente código fue más rápido para mí que el otro código publicado hasta ahora: (Visual Studio 2013, 64 bits, archivo de 500 MB con longitud de línea uniformemente en [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'; });
}

Soporta todos mis intentos de Python por más de un factor 2.


8
2018-02-22 02:33