¿Por qué leer líneas de stdin es mucho más lento en C ++ que Python?

Quería comparar la lectura de líneas de entrada de cadena desde stdin usando Python y C ++ y me sorprendió ver que mi código C ++ se ejecutaba 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, por favor dígame si estoy haciendo algo mal o si estoy malinterpretando algo.

(Respuesta TLDR: incluya la declaración: cin.sync_with_stdio(false)o simplemente use fgetsen su lugar.

Resultados de 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 a 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

Debo señalar que probé esto tanto en Mac OS X v10.6.8 (Snow Leopard) como en Linux 2.6.32 (Red Hat Linux 6.2). El primero es un MacBook Pro, y el segundo es un servidor muy robusto, no es que esto sea demasiado 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

Pequeño anexo de referencia y resumen

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). Nuevamente, esto es para un archivo de línea de 100M en un disco rápido. Aquí está la comparación, con varias soluciones / enfoques:

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

De forma predeterminada, cinse sincroniza con stdio, lo que hace que evite cualquier almacenamiento en búfer de entrada. Si agrega esto a la parte superior de su página principal, debería ver un rendimiento mucho mejor:

std::ios_base::sync_with_stdio(false);

Normalmente, cuando una secuencia de entrada está almacenada, en lugar de leer un carácter a la vez, la secuencia se leerá en fragmentos más grandes. Esto reduce la cantidad de llamadas al sistema, que generalmente son relativamente caras. Sin embargo, dado que las implementaciones FILE*basadas stdioya iostreamsmenudo tienen implementaciones separadas y, por lo tanto, memorias intermedias separadas, esto podría generar un problema si ambas se usaran juntas. Por ejemplo:

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

Si se leyera más entrada cinde la que realmente necesitaba, entonces el segundo valor entero no estaría disponible para la scanffunción, que tiene su propio búfer independiente. Esto llevaría a resultados inesperados.

Para evitar esto, de forma predeterminada, las secuencias se sincronizan con stdio. Una forma común de lograr esto es haber cinleído cada carácter uno a la vez según sea necesario usando stdiofunciones. Desafortunadamente, esto introduce muchos gastos generales. Para pequeñas cantidades de entrada, este no es un gran problema, pero cuando está leyendo 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 desactivar esta función para obtener un mejor rendimiento si supiera lo que estaba haciendo, por lo que proporcionaron el sync_with_stdiométodo.

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

C ++

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

llamadas al sistema 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

llamadas al sistema sudo dtruss -c ./a.py < in

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

Estoy unos años atrás aquí, 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 en un par de formas diferentes:

1. En realidad, estás cronometrando la ejecución cat, no tu punto de referencia. El uso de la CPU 'usuario' y 'sys' que se muestran timeson aquellos de cat, no su programa de referencia. Peor aún, el tiempo "real" tampoco es necesariamente preciso. Dependiendo de la implementación de caty de las tuberías en su sistema operativo local, es posible que catescriba un búfer gigante final y salga mucho antes de que el proceso del lector termine su trabajo.

2. El uso de cates innecesario y de hecho contraproducente; Estás agregando partes móviles. Si estuvieras en un sistema suficientemente antiguo (es decir, con una sola CPU y, en ciertas generaciones de computadoras, E / S más rápido que la CPU), el solo hecho de que se catestuviera ejecutando podría colorear sustancialmente los resultados. También está sujeto a lo que catpueda hacer el almacenamiento en búfer de entrada y salida y otros procesos . (Esto probablemente le otorgaría un premio de 'Uso inútil del gato' si fuera Randal Schwartz.

Una mejor construcción sería:

$ /usr/bin/time program_to_benchmark < big_file

En esta declaración, es el shell el que abre big_file, pasándolo a su programa (bueno, en realidad al timeque 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á intentando comparar. Esto le brinda una lectura real de su rendimiento sin complicaciones espurias.

Mencionaré dos 'arreglos' posibles, pero realmente incorrectos, que también podrían considerarse (pero los 'numero' de manera diferente ya que no son cosas que estaban mal en la publicación original):

R. Puede "arreglar" esto cronometrando solo su programa:

$ cat big_file | /usr/bin/time program_to_benchmark

B. o cronometrando toda la tubería:

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

Estos son incorrectos por las mismas razones que el n. ° 2: todavía se usan catinnecesariamente. Los menciono por algunas razones:

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

• puede haber casos en los que cat se necesita (por ejemplo: el archivo para ser leído requiere algún tipo de privilegio de acceso, y usted no desea conceder ese privilegio al programa a partir de referencias: sudo cat /dev/sda | /usr/bin/time my_compression_test --no-output)

• en la práctica , en máquinas modernas, lo agregado caten la tubería probablemente no tenga consecuencias reales.

Pero digo lo último con algunas dudas. 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 catconsumió el 74% de la CPU durante la prueba; y de hecho 1.34 / 1.83 es ​​aproximadamente el 74%. Quizás una serie de:

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

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

Aún así, predigo que sería capaz de medir la diferencia entre cat file | wc -ly wc -l < filey encontrar 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 menor 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 'el mejor de 3' resultados; después de preparar 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)

Observe que los dos resultados de la canalización afirman haber tomado más tiempo de CPU (usuario + sys) que el tiempo real del reloj de pared. Esto se debe a que estoy usando el comando 'time' incorporado del shell (bash), que conoce la canalización; y estoy en una máquina de múltiples núcleos 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. Al usar /usr/bin/time, veo un tiempo de CPU menor que el tiempo real, lo que muestra que solo puede cronometrar el elemento de tubería único que se le pasó en su línea de comando. Además, la salida del shell da milisegundos, mientras que /usr/bin/timesolo da centésimas de segundo.

Entonces, en el nivel de eficiencia de wc -l, cathace una gran diferencia: 409/283 = 1.453 o 45.3% más en tiempo real, y 775/280 = 2.768, ¡o se usa un sorprendente 177% más de CPU! En mi cuadro de prueba aleatorio, estaba allí en el momento.

Debo agregar que hay 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 información de una tubería, exactamente al ritmo enviado por cat, y en fragmentos no más grandes que los escritos por cat.

Cuando ejecuta /usr/bin/time my_program < big_file, su programa recibe un descriptor de archivo abierto para el archivo real. Su programa, o en muchos casos las bibliotecas de E / S del idioma en el que se escribió, puede tomar diferentes medidas cuando se le presenta un descriptor de archivo que hace referencia a un archivo normal. Puede usarse mmap(2)para asignar el archivo de entrada a su espacio de direcciones, en lugar de usar read(2)llamadas explícitas del sistema. Estas diferencias podrían tener un efecto mucho mayor en sus resultados de referencia que el pequeño costo de ejecutar el catbinario.

Por supuesto, es un resultado de referencia interesante si el mismo programa se desempeña de manera significativamente diferente entre los dos casos. Muestra que, de hecho, el programa o sus bibliotecas de E / S están 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 catresultado por algún pequeño factor para "perdonar" el costo de ejecutarse cat.

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

Agregar las siguientes declaraciones a la versión de C ++ justo antes de que el whilebucle lo alinee con la versión de Python :

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 búfer más grande lo redujo a 1 segundo.

getline, operadores de transmisión scanf, puede ser conveniente si no le importa el tiempo de carga de archivos o si está cargando archivos de texto pequeños. Pero, si el rendimiento es algo que le interesa, realmente debería almacenar todo el archivo en la memoria (suponiendo que se ajuste).

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 ajustar 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 de datos binarios planos en lugar de texto. Es más confiable leer y escribir porque no tiene que lidiar con todas las ambigüedades del espacio en blanco. También es más pequeño y mucho más rápido de analizar.

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

Supera todos mis intentos de Python en más de un factor 2.

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

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

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

En su segundo ejemplo (con scanf ()), la razón por la que esto es aún más lento podría deberse a que scanf ("% s") analiza la cadena y busca cualquier carácter de espacio (espacio, tabulación, nueva línea).

Además, sí, CPython almacena en caché para evitar lecturas de disco duro.

Un primer elemento de una respuesta: <iostream>es lento. Maldita sea lento. Obtuve un gran aumento de rendimiento scanfcomo en el siguiente, pero aún es dos veces más lento que 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;
}

Bueno, veo que en tu segunda solución cambiaste cina scanf, que fue la primera sugerencia que te haría (cin es sloooooooooooow). Ahora, si cambia de scanfa fgets, vería otro aumento en el rendimiento: fgetses la función C ++ más rápida para la entrada de cadenas.

Por cierto, no sabía sobre esa cosa de sincronización, agradable. Pero igual deberías intentarlo fgets.