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




que devuelve getline (7)

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

Por cierto, no sabía acerca de esa cosa de sincronización, bonito. Pero aún deberías probar fgets .

https://code.i-harness.com

Quería comparar líneas de lectura de entrada de cadena desde stdin usando Python y C ++ y me sorprendió ver que mi código de C ++ ejecutaba un orden de magnitud más lento que el código de Python equivalente. Dado que mi C ++ está oxidado y aún no soy un experto pitonista, 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 fgets 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 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 tener en cuenta 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 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

Adenda de referencia minúscula 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

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'; });
}

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


Estoy unos años atrasados ​​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 en un par de 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" mostrado por "tiempo" son los de "cat", 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 búfer gigante final y salga mucho antes de que el proceso del lector finalice su trabajo.

  2. El uso de `cat` es innecesario y, de hecho, contraproducente; Estás agregando partes móviles. Si estaba en un sistema suficientemente antiguo (es decir, con una sola CPU y, en ciertas generaciones de computadoras, I / O más rápido que la CPU), el simple hecho de que "cat" se estuviera ejecutando podría influir sustancialmente en los resultados. También está sujeto a lo que pueda hacer el búfer de entrada y salida y otro procesamiento que pueda hacer `cat`. (Es probable que esto te gane un premio de "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 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 evaluar. Esto le da una lectura real de su rendimiento sin complicaciones espurias.

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

A. Puedes 'arreglar' esto programando solo tu 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 en 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 en los que se necesite `cat` (por ejemplo: el archivo que se va a leer requiere algún tipo de privilegio para acceder, y usted no quiere otorgar ese privilegio al programa para ser evaluado:` sudo cat / dev / sda | / usr / bin / time my_compression_test --no-output`)

  • en la práctica , en las máquinas modernas, el agregado 'cat' 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%. Quizás una racha de:

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

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

Sin embargo, predigo que sería capaz de medir la diferencia entre `cat cat | wc -l` y `wc -l <file` y encuentre una diferencia notable (porcentaje de 2 dígitos). Cada una de las pruebas más lentas habrá pagado una multa 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 1.5 gigabytes de basura, en un sistema Linux 3.13 (Ubuntu 14.04), obteniendo estos resultados (estos son en realidad los mejores resultados de 3; 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 canalización afirman haber consumido más tiempo de CPU (usuario + sistemas) que en tiempo real. Esto se debe a que estoy usando el comando 'time' incorporado en el shell (Bash), que es consciente de la tubería; y estoy en una máquina multi-core donde 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 en tiempo real, lo que demuestra que solo puede medir el tiempo que el elemento de canalización pasado pasa a su línea de comando. Además, la salida del shell da milisegundos, mientras que / usr / bin / time solo da cientos de segundos.

Entonces, en el nivel de eficiencia de `wc -l`, el` cat` hace 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 utilizada! En mi caja de prueba al azar estaba allí en el tiempo.

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; Usted tiene que decidir esto usted mismo:

Cuando ejecutas `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 partes no mayores que las escritas por` cat`.

Cuando 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 lenguaje 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 asignar el archivo de entrada a su espacio de direcciones, en lugar de usar llamadas de sistema de lectura (2) explícitas. 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 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 están haciendo algo interesante, como usar mmap (). Entonces, en la práctica, podría ser bueno ejecutar los puntos de referencia en ambas direcciones; tal vez descontando el resultado del 'gato' por un pequeño factor para "perdonar" el costo de ejecutar el "gato" en sí.


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

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

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

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 bucle while 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 lo redujo a 1 segundo.


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

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

getline , stream operadores, scanf , pueden ser convenientes 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 importa, realmente debería almacenar el archivo entero en la memoria (asumiendo 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 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 del espacio en blanco. También es más pequeño y mucho más rápido de analizar.







getline