¿Por qué la lectura de líneas desde la entrada estándar es mucho más lenta en C++ que en Python?

Resuelto JJC asked hace 12 años • 10 respuestas

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 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 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
JJC avatar Feb 21 '12 09:02 JJC
Aceptado

tl;dr: Debido a diferentes configuraciones predeterminadas en C++ que requieren más llamadas al sistema.

De forma predeterminada, cinestá 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 iostreamsa 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 cinla que realmente se necesita, entonces el segundo valor entero no estaría disponible para la scanffunció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 cincada carácter uno a la vez según sea necesario usando stdiofunciones. 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_stdiomé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 .

Vaughn Cato avatar Feb 21 '2012 03:02 Vaughn Cato

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
2mia avatar Mar 11 '2012 18:03 2mia

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:

  1. 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 muestra timeson los de cat, no los de su programa evaluado. Peor aún, la hora "real" tampoco es necesariamente exacta. Dependiendo de la implementación catde las canalizaciones en su sistema operativo local, es posible que catescriba un búfer gigante final y salga mucho antes de que el proceso de lectura termine su trabajo.

  2. El uso de cates 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 se catestuviera ejecutando podría influir sustancialmente en los resultados. También está sujeto a cualquier almacenamiento en búfer de entrada y salida y otros procesamientos catque 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 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á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 catinnecesariamente. 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 comparar sudo cat /dev/sda | /usr/bin/time my_compression_test --no-output:)

  • En la práctica , en las máquinas modernas, el añadido caten 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 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

¡Habría tomado sólo los 0,49 segundos restantes! Probablemente no: cataquí 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 -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; 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/timesolo da centésimas de segundo.

Entonces, en el nivel de eficiencia de wc -l, esto catmarca 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 catbinario.

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 catresultado por algún pequeño factor para "perdonar" el costo de funcionamiento cat.

Bela Lubkin avatar May 06 '2017 21:05 Bela Lubkin