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

2014

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


(Respuesta de 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 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 robusto, 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 índice 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ínea de 100M en un disco rápido. Aquí está la comparación, con varias soluciones / enfoques:

Implementación Líneas por segundo
python (predeterminado) 3,571,428
cin (predeterminado / ingenuo) 819,672
cin (sin sincronización) 12,500,000
fgets 14,285,714
wc (no es una comparación justa) 54.644.808
5
  • 18
    ¿Ejecutó sus pruebas varias veces? Quizás haya un problema de caché de disco. 21/02/12 a las 2:20
  • @VaughnCato Sí, y también en dos máquinas diferentes.
    JJC
    21/02/12 a las 2:22
  • 18
    El problema es la sincronización con stdio; vea mi respuesta. 21 feb 2012 a las 3:30
  • 23
    Dado que nadie parece haber mencionado por qué obtienes una línea adicional con C ++: ¡¡No pruebes cin.eof()!! Ponga la getlinellamada en la declaración 'if'.
    Xeo
    21/02/12 a las 18:29
  • 23
    wc -les rápido porque lee la transmisión más de una línea a la vez (puede ser una fread(stdin)/memchr('\n')combinación). Los resultados de Python están en el mismo orden de magnitud, por ejemplo,wc-l.py
    jfs
    27/02/12 a las 0:21
1799

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

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

std::ios_base::sync_with_stdio(false);

Normalmente, cuando un flujo de entrada se almacena en búfer, en lugar de leer un carácter a la vez, el flujo se leerá en porciones más grandes. Esto reduce el número de llamadas al sistema, que suelen ser relativamente caras. Sin embargo, dado que los FILE*basados stdioy a iostreamsmenudo tienen implementaciones separadas y, por lo tanto, búferes separados, esto podría generar un problema si ambos se usan juntos. Por ejemplo:

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

Si se leyera más entrada cinde la que realmente se necesitaba, 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 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, esto no es un gran problema, pero cuando lee millones de líneas, la penalización del rendimiento es significativa.

Afortunadamente, los diseñadores de la biblioteca decidieron que también debería poder deshabilitar esta función para obtener un rendimiento mejorado si sabía lo que estaba haciendo, por lo que proporcionaron el sync_with_stdiométodo.

3
  • 164
    Esto debería estar en la parte superior. Es casi seguro que sea correcto. La respuesta no puede estar en reemplazar la lectura con una fscanfllamada, porque eso simplemente no funciona tanto como Python. Python debe asignar memoria para la cadena, posiblemente varias veces, ya que la asignación existente se considera inadecuada, exactamente como el enfoque de C ++ con std::string. Es casi seguro que esta tarea está ligada a E / S y hay demasiado FUD circulando sobre el costo de crear std::stringobjetos en C ++ o usarlos <iostream>en sí mismos. 21/02/12 a las 3:34
  • 60
    Sí, agregar esta línea inmediatamente arriba de mi bucle while original aceleró el código para superar incluso a Python. Estoy a punto de publicar los resultados como edición final. ¡Gracias de nuevo!
    JJC
    21/02/12 a las 3:45
  • 63
    Tenga en cuenta que sync_with_stdio()es una función miembro estática, y una llamada a esta función en cualquier objeto de flujo (por ejemplo cin) activa o desactiva la sincronización para todos los objetos estándar de iostream. 21 de enero de 2015 a las 1:16
196

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 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
0
181

Estoy algunos años atrasado 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á cronometrando la ejecución cat, no su punto de referencia. El uso de CPU de 'usuario' y 'sys' mostrado por timees el de catsu programa comparado, no el de usted. Peor aún, el tiempo "real" tampoco es necesariamente exacto. Dependiendo de la implementación de caty de 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 finalice su trabajo.

  2. El uso de cates innecesario y de hecho contraproducente; está agregando partes móviles. Si estuviera en 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 se catestuviera ejecutando podría alterar sustancialmente los resultados. También está sujeto a cualquier almacenamiento en búfer de entrada y salida y a otros procesos cat. (Esto probablemente te haría ganar un premio por 'Uso inútil de 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, 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 da una lectura real de su desempeño sin complicaciones falsas.

Mencionaré dos posibles 'arreglos', pero en realidad 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 todo el oleoducto:

$ /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 del todo 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 las máquinas modernas, lo que se agrega caten 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 catconsumió el 74% de la CPU durante la prueba; y de hecho 1,34 / 1,83 es ​​aproximadamente 74%. Quizás una serie de:

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

hubiera tomado solo los 0.49 segundos restantes! Probablemente no: cataquí tuvo que pagar por las read()llamadas al sistema (o equivalente) que transfirieron el archivo desde 'disco' (en realidad, caché de búfer), así como las escrituras de canalización para entregarlas wc. La prueba correcta todavía habría tenido que hacer esas read()llamadas; sólo se habrían guardado las llamadas write-to-pipe y read-from-pipe, y deberían ser bastante económicas.

Aún así, predigo que podrá 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 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), obteniendo estos resultados (estos son en realidad los mejores resultados de 3; después de preparar la 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 + sistema) que el tiempo real del reloj de pared. Esto se debe a que estoy usando el comando 'time' incorporado del shell (bash), que es consciente de 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 más pequeño que el tiempo real, lo que muestra que solo puede cronometrar el elemento de canalización único 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, cathace una gran diferencia: 409/283 = 1.453 o 45.3% más en tiempo real, y 775/280 = 2.768, ¡o un 177% más de CPU usada! En mi caja de prueba aleatoria de que estaba allí en ese 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 se ejecuta cat big_file | /usr/bin/time my_program, su programa recibe información de una tubería, precisamente al ritmo enviado por cat, y en trozos no mayores que los escritos por cat.

Cuando lo ejecuta /usr/bin/time my_program < big_file, su programa recibe un descriptor de archivo abierto al archivo real. Su programa, o en muchos casos las bibliotecas de E / S del idioma en el que se escribió, puede realizar diferentes acciones cuando se le presenta un descriptor de archivo que hace referencia a un archivo normal. Puede usar mmap(2)para mapear el archivo de entrada en 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 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 funciona 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(). Por tanto, en la práctica, sería 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 funcionamiento cat.

2
  • 31
    ¡Vaya, eso fue bastante revelador! Si bien he sido consciente de que cat no es necesario para alimentar la entrada a stdin de programas y que se prefiere la redirección <shell, generalmente me quedé con cat debido al flujo de datos de izquierda a derecha que el método anterior conserva visualmente cuando razono sobre oleoductos. Las diferencias de rendimiento en tales casos me parecen insignificantes. Pero aprecio que nos hayas educado, Bela.
    JJC
    9 de mayo de 2017 a las 1:16
  • 13
    La redirección se analiza desde la línea de comandos del shell en una etapa temprana, lo que le permite hacer uno de estos, si le da una apariencia más agradable de flujo de izquierda a derecha: $ < big_file time my_program $ time < big_file my_program esto debería funcionar en cualquier shell POSIX (es decir, no `csh `y no estoy seguro de exotica como` rc` :) 10 de mayo de 2017 a las 21:55
105

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

Agregar las siguientes declaraciones a la versión de C ++ justo antes del whilebucle lo pone en línea 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 la configuración de un búfer más grande la redujo a 1 segundo.

3
  • 118
    También evitaría configurar un búfer de 1 MB en la pila. Puede provocar un desbordamiento de la pila (¡aunque supongo que es un buen lugar para debatir al respecto!) 21 feb 2012 a las 7:30
  • 13
    Matthieu, Mac utiliza una pila de procesos de 8 MB de forma predeterminada. Linux usa 4 MB por subproceso predeterminado, IIRC. 1 MB no es un gran problema para un programa que transforma la entrada con una profundidad de pila relativamente baja. Sin embargo, lo que es más importante, std :: cin destruirá la pila si el búfer se sale de su alcance.
    SEK
    14 de enero de 2014 a las 9:28
  • 22
    @SEK El tamaño de pila predeterminado de Windows es 1 MB. 15 de marzo de 2014 a las 2:11
45

getline, operadores de flujo,, scanfpueden ser convenientes si no le importa el tiempo de carga del archivo o si está cargando archivos de texto pequeños. Pero, si el rendimiento es algo que le importa, realmente debería almacenar todo el archivo en la memoria (suponiendo que se ajuste).

He aquí 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 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 de los espacios en blanco. También es más pequeño y mucho más rápido de analizar.

24

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 una 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 por más de un factor 2.

0
20

Por cierto, la razón por la que 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 activa 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++;
};
1
  • 74
    El bucle realmente correcto sería: while (getline(cin, input_line)) line_count++; 5 de mayo de 12 a las 14:42
dieciséis

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 las lecturas del disco duro.

12

Bueno, veo que en tu segunda solución cambiaste de cina scanf, que fue la primera sugerencia que te iba a hacer ( cines lentoooooooooooow). Ahora, si cambia de scanfa fgets, verá 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, bueno. Pero aún deberías intentarlo fgets.

0
10

Un primer elemento de una respuesta: <iostream>es lento. Maldita sea lento. Obtengo un gran aumento de rendimiento con scanfel siguiente, pero sigue siendo 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;
}
0