¿Por qué la lectura de líneas desde la entrada estándar es mucho más lenta en C++ que en Python?
Quería comparar la lectura de líneas de entrada de cadena desde la entrada estándar 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. Dado que mi C++ está oxidado y todavía no soy un Pythonista experto, dígame si estoy haciendo algo mal o si no entiendo algo.
( Respuesta TLDR: incluya la declaración: cin.sync_with_stdio(false)
o simplemente úsela fgets
en 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 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
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 potente, aunque esto no es 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 apéndice y resumen del punto de referencia
Para completar, pensé en actualizar 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íneas de 100 M en un disco rápido. Aquí está la comparación, con varias soluciones/enfoques:
Implementación | Líneas por segundo |
---|---|
pitón (predeterminado) | 3.571.428 |
cin (predeterminado/ingenuo) | 819.672 |
cin (sin sincronización) | 12.500.000 |
fgets | 14.285.714 |
wc (comparación no justa) | 54.644.808 |
tl;dr: Debido a diferentes configuraciones predeterminadas en C++ que requieren más llamadas al sistema.
De forma predeterminada, cin
está sincronizado con stdio, lo que hace que evite cualquier almacenamiento en búfer de entrada. Si agrega esto en la parte superior de su archivo principal, debería ver un rendimiento mucho mejor:
std::ios_base::sync_with_stdio(false);
Normalmente, cuando un flujo de entrada se almacena en el búfer, en lugar de leer un carácter a la vez, el flujo se leerá en fragmentos más grandes. Esto reduce el número de llamadas al sistema, que suelen ser relativamente caras. Sin embargo, dado que los FILE*
basados stdio
y iostreams
a menudo tienen implementaciones separadas y, por lo tanto, buffers separados, esto podría generar un problema si ambos se usaran juntos. Por ejemplo:
int myvalue1;
cin >> myvalue1;
int myvalue2;
scanf("%d",&myvalue2);
Si se leyera más entrada de cin
la que realmente se necesita, entonces el segundo valor entero no estaría disponible para la scanf
función, que tiene su propio búfer independiente. Esto conduciría a resultados inesperados.
Para evitar esto, de forma predeterminada, las transmisiones se sincronizan con stdio
. Una forma común de lograr esto es leer cin
cada carácter uno a la vez según sea necesario usando stdio
funciones. Desafortunadamente, esto genera muchos gastos generales. Para pequeñas cantidades de entrada, esto no es un gran problema, pero cuando lees millones de líneas, la penalización en el 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 sabía lo que estaba haciendo, por lo que proporcionaron el sync_with_stdio
método. Desde este enlace (énfasis añadido):
Si la sincronización está desactivada, los flujos estándar de C++ pueden almacenar en búfer sus E/S de forma independiente, lo que puede ser considerablemente más rápido en algunos casos .
Solo por curiosidad, eché un vistazo a lo que sucede debajo del capó y usé dtruss/strace en cada prueba.
C++
./a.out < in
Saw 6512403 lines in 8 seconds. Crunch speed: 814050
llamadas al sistemasudo 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 sistemasudo dtruss -c ./a.py < in
CALL COUNT
__mac_syscall 1
<snip>
open 5
pread 8
mprotect 17
mmap 21
stat64 29
Llevo unos años de retraso aquí, pero:
En 'Editar 4/5/6' de la publicación original, estás usando la construcción:
$ /usr/bin/time cat big_file | program_to_benchmark
Esto está mal de dos maneras diferentes:
En realidad, estás cronometrando la ejecución de
cat
, no tu punto de referencia. El uso de CPU de 'usuario' y 'sys' que se muestratime
son los decat
, no los de su programa evaluado. Peor aún, la hora "real" tampoco es necesariamente exacta. Dependiendo de la implementacióncat
de las canalizaciones en su sistema operativo local, es posible quecat
escriba un búfer gigante final y salga mucho antes de que el proceso de lectura termine su trabajo.El uso de
cat
es innecesario y de hecho contraproducente; estás agregando partes móviles. Si estuviera en un sistema suficientemente antiguo (es decir, con una sola CPU y, en ciertas generaciones de computadoras, E/S más rápidas que la CPU), el mero hecho de que secat
estuviera ejecutando podría influir sustancialmente en los resultados. También está sujeto a cualquier almacenamiento en búfer de entrada y salida y otros procesamientoscat
que puedan realizarse. (Esto probablemente te haría ganar un premio por "Uso inútil de un gato" si yo 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 y lo pasa a su programa (bueno, en realidad al 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ás intentando comparar. Esto le brinda una lectura real de su desempeño sin complicaciones espurias.
Mencionaré dos 'soluciones' posibles, pero en realidad incorrectas, que también podrían considerarse (pero las 'numero' de manera diferente ya que no son cosas que estuvieran mal en la publicación original):
R. Podrías "solucionar" este problema cronometrando sólo tu programa:
$ cat big_file | /usr/bin/time program_to_benchmark
B. o cronometrando todo el proceso:
$ /usr/bin/time sh -c 'cat big_file | program_to_benchmark'
Estos son incorrectos por las mismas razones que el punto 2: todavía se usan cat
innecesariamente. Los menciono por varias razones:
son más "naturales" para las personas que no se sienten del todo cómodas con las funciones de redirección de E/S del shell POSIX.
Puede haber casos en los que
cat
sea 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 va a compararsudo cat /dev/sda | /usr/bin/time my_compression_test --no-output
:)En la práctica , en las máquinas modernas, el añadido
cat
en la tubería probablemente no tenga consecuencias reales.
Pero digo esto último con cierta vacilación. Si examinamos el último resultado en 'Edición 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 el 74%. Quizás una serie de:
$ /usr/bin/time wc -l < temp_big_file
¡Habría tomado sólo los 0,49 segundos restantes! Probablemente no: cat
aquí tuve que pagar por las read()
llamadas al sistema (o equivalentes) que transfirieron el archivo desde el 'disco' (en realidad, caché del búfer), así como por las escrituras de canalización para entregarlos a wc
. La prueba correcta aún habría tenido que hacer esas read()
llamadas; sólo se habrían guardado las llamadas de escritura a canalización y lectura desde canalización, y deberían ser bastante económicas.
Aun así, predigo que podrás medir la diferencia entre cat file | wc -l
y wc -l < file
y 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; lo que, sin embargo, equivaldría a una fracción menor de su tiempo total mayor.
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), y obtuve estos resultados (estos son en realidad resultados del "mejor de 3"; 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 consumido más tiempo de CPU (usuario+sistema) que el tiempo real del reloj de pared. Esto se debe a que estoy usando el comando 'time' incorporado del shell (bash), que reconoce la canalización; y estoy en una máquina de múltiples núcleos donde procesos separados en una canalización 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 más pequeño que el tiempo real, lo que muestra que solo puede cronometrar el único elemento de canalización que se le pasa en su línea de comando. Además, la salida del shell da milisegundos, mientras que /usr/bin/time
solo da centésimas de segundo.
Entonces, en el nivel de eficiencia de wc -l
, esto cat
marca una gran diferencia: 409/283 = 1,453 o 45,3% más de tiempo real, y 775/280 = 2,768, ¡o un enorme 177% más de CPU utilizada! En mi cuadro de prueba aleatorio de "estaba allí en ese momento".
Debo agregar que existe al menos otra diferencia significativa entre estos estilos de prueba, y no puedo decir si es un beneficio o un defecto; Tienes que decidir esto tú mismo:
Cuando ejecuta cat big_file | /usr/bin/time my_program
, su programa recibe información de una canalización, precisamente 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 para el archivo real. Su programa, o en muchos casos las bibliotecas de E/S del lenguaje en el que fue escrito, pueden realizar diferentes acciones cuando se les 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 al sistema. Estas diferencias podrían tener un efecto mucho mayor en los resultados de su punto de referencia que el pequeño costo de ejecutar el cat
binario.
Por supuesto, es un resultado de referencia interesante si el mismo programa funciona de manera significativamente diferente en los dos casos. Muestra que, efectivamente, el programa o sus bibliotecas de E/S están haciendo algo interesante, como usar mmap()
. Por lo tanto, en la práctica podría ser bueno ejecutar los puntos de referencia en ambos sentidos; tal vez descontando el cat
resultado por algún pequeño factor para "perdonar" el costo de funcionamiento cat
.