[C++] ¿Por qué las líneas de lectura de stdin son mucho más lentas en C ++ que en Python?


Answers

Solo por curiosidad he echado un vistazo a lo que ocurre 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
Question

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

(Respuesta de TLDR: incluya la instrucción: cin.sync_with_stdio(false) o simplemente use fgets lugar.

Resultados 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

Editar: Debo señalar que probé esto tanto con Mac OS X v10.6.8 (Snow Leopard) como con Linux 2.6.32 (Red Hat Linux 6.2). La primera es una MacBook Pro, y la última es un servidor muy robusto, no es que esto sea demasiado pertinente.

Editar 2: (Se eliminó esta edición, ya no se aplica)

$ 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

Editar 3:

De acuerdo, probé la sugerencia de JN de intentar que Python almacene la lectura de la línea: pero no importó la velocidad de Python.

También probé la sugerencia de JN de utilizar scanf en una matriz de caracteres en lugar de getline en una std::string . ¡Bingo! Esto dio como resultado un rendimiento equivalente para Python y C ++. (3,333,333 LPS con mis datos de entrada, que por cierto son solo líneas cortas de tres campos cada uno, generalmente de unos 20 caracteres de ancho, aunque a veces más).

Código:

char input_a[512];
char input_b[32];
char input_c[512];
while(scanf("%s %s %s\n", input_a, input_b, input_c) != EOF) {
    line_count++;
};

Velocidad:

$ cat test_lines | ./readline_test_cpp2
Read 10000000 lines in 3 seconds. LPS: 3333333
$ cat test_lines | ./readline_test2.py
Read 10000000 lines in 3 seconds. LPS: 3333333

(Sí, lo ejecuté varias veces.) Entonces, supongo que ahora scanf lugar de getline . Pero todavía tengo curiosidad si la gente piensa que este rendimiento alcanzado por std::string / getline es típico y razonable.

Editar 4 (fue: Final Edit / Solution):

Agregar:

cin.sync_with_stdio(false);

Inmediatamente por encima de mi ciclo while original, el resultado es un código que se ejecuta más rápido que Python.

Nueva comparación de rendimiento (esto está en mi MacBook Pro 2011), utilizando el código original, el original con la sincronización deshabilitada y el código de Python original, respectivamente, en un archivo con 20 millones de líneas de texto. Sí, lo ejecuté varias veces para eliminar la confusión del almacenamiento en caché de disco.

$ /usr/bin/time cat test_lines_double | ./readline_test_cpp
       33.30 real         0.04 user         0.74 sys
Read 20000001 lines in 33 seconds. LPS: 606060
$ /usr/bin/time cat test_lines_double | ./readline_test_cpp1b
        3.79 real         0.01 user         0.50 sys
Read 20000000 lines in 4 seconds. LPS: 5000000
$ /usr/bin/time cat test_lines_double | ./readline_test.py
        6.88 real         0.01 user         0.38 sys
Read 20000000 lines in 6 seconds. LPS: 3333333

¡Gracias a @Vaughn Cato por su respuesta! Cualquier elaboración que la gente pueda hacer o buenas referencias a las que la gente pueda hacer referencia en cuanto a por qué ocurre esta sincronización, qué significa, cuándo es útil y cuándo está bien desactivarla sería muy apreciada por la posteridad. :-)

Editar 5 / Mejor solución:

Como sugiere Gandalf The Gray a continuación, gets es incluso más rápido que scanf o el enfoque cin no sincronizado. También aprendí que scanf y scanf son SEGUROS y NO DEBEN UTILIZARSE debido al potencial de desbordamiento del buffer. Entonces, escribí esta iteración usando fgets , la alternativa más segura a get. Aquí están las líneas pertinentes para mis compañeros noobs:

char input_line[MAX_LINE];
char *result;

//<snip>

while((result = fgets(input_line, MAX_LINE, stdin )) != NULL)
    line_count++;
if (ferror(stdin))
    perror("Error reading stdin.");

Ahora, aquí están los resultados usando un archivo aún más grande (100M líneas; ~ 3.4 GB) en un servidor rápido con un disco muy rápido, comparando el código de Python, el cin no sincronizado y los enfoques de fgets , así como comparando con la utilidad wc . [La segmentación de la versión de scanf falló y no tengo ganas de solucionarlo.]:

$ /usr/bin/time cat temp_big_file | readline_test.py
0.03user 2.04system 0:28.06elapsed 7%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
Read 100000000 lines in 28 seconds. LPS: 3571428

$ /usr/bin/time cat temp_big_file | readline_test_unsync_cin
0.03user 1.64system 0:08.10elapsed 20%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
Read 100000000 lines in 8 seconds. LPS: 12500000

$ /usr/bin/time cat temp_big_file | readline_test_fgets
0.00user 0.93system 0:07.01elapsed 13%CPU (0avgtext+0avgdata 2448maxresident)k
0inputs+0outputs (0major+181minor)pagefaults 0swaps
Read 100000000 lines in 7 seconds. LPS: 14285714

$ /usr/bin/time cat temp_big_file | wc -l
0.01user 1.34system 0:01.83elapsed 74%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
100000000


Recap (lines per second):
python:         3,571,428
cin (no sync): 12,500,000
fgets:         14,285,714
wc:            54,644,808

Como puede ver, fgets es mejor, pero aún bastante lejos del rendimiento del Wc; Estoy bastante seguro de que esto se debe al hecho de que wc examina cada personaje sin ninguna copia de memoria. Sospecho que, en este punto, otras partes del código se convertirán en el cuello de botella, por lo que no creo que la optimización a ese nivel merezca la pena, incluso si es posible (ya que, después de todo, realmente necesito almacenar las líneas de lectura). en memoria).

También tenga en cuenta que una pequeña compensación con el uso de un búfer char * y fgets vs cin no sincronizado a cadena es que este último puede leer líneas de cualquier longitud, mientras que el primero requiere limitar la entrada a un número finito. En la práctica, esto probablemente no sea un problema para leer la mayoría de los archivos de entrada basados ​​en líneas, ya que el búfer se puede establecer en un valor muy grande que no se excedería con una entrada válida.

Esto ha sido educativo. Gracias a todos por sus comentarios y sugerencias.

Editar 6:

Según lo sugerido por JF Sebastian en los comentarios a continuación, la utilidad wc de GNU utiliza read() simple C read() (dentro del contenedor safe-read.c) para leer fragmentos (de 16k bytes) a la vez y contar nuevas líneas. Aquí hay un equivalente de Python basado en el código de JF (solo muestra el fragmento relevante que reemplaza el bucle de Python:

BUFFER_SIZE = 16384
count = sum(chunk.count('\n') for chunk in iter(partial(sys.stdin.read, BUFFER_SIZE), ''))

El rendimiento de esta versión es bastante rápido (aunque aún un poco más lento que la utilidad de C wc sin procesar, por supuesto):

$ /usr/bin/time cat temp_big_file | readline_test3.py
0.01user 1.16system 0:04.74elapsed 24%CPU (0avgtext+0avgdata 2448maxresident)k
0inputs+0outputs (0major+181minor)pagefaults 0swaps
Read 100000000 lines in 4.7275 seconds. LPS: 21152829

De nuevo, es un poco tonto para mí comparar C ++ fgets / cin y el primer código python por un lado para wc -l y este último fragmento de Python por el otro, ya que los dos últimos no almacenan las líneas de lectura, pero simplemente contar nuevas líneas. Aún así, es interesante explorar todas las diferentes implementaciones y pensar en las implicaciones de rendimiento. ¡Gracias de nuevo!

Edición 7: Adición y recapitulación del punto de referencia minúsculo

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). De nuevo, esto es para un archivo de línea de 100M en un disco rápido. Aquí está la tabla completa ahora:

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



Por cierto, la razón por la que el conteo de líneas para la versión de C ++ es uno mayor que el recuento para la versión de Python es que el indicador de eof solo se establece 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++;
};



Un primer elemento de una respuesta: <iostream> es lento. Maldición lenta. Obtuve un gran aumento de rendimiento con scanf como en el 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;
}



Estoy unos años atrás, 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 de dos maneras diferentes:

  1. En realidad estás sincronizando la ejecución de `cat`, no tu punto de referencia. El uso de CPU 'usuario' y 'sys' mostrado por `tiempo 'son los de' gato ', 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 buffer final gigante y salga mucho antes de que el proceso de lectura finalice su trabajo.

  2. El uso de `cat` es innecesario y de hecho contraproducente; estás agregando partes móviles. Si tuviera un sistema lo suficientemente antiguo (es decir, con una única CPU y, en ciertas generaciones de computadoras, E / S más rápido que la CPU), el simple hecho de que `cat` se ejecutara podría colorear sustancialmente los resultados. También está sujeto a lo que pueda hacer el almacenamiento en búfer de entrada y salida y otro procesamiento `cat`. (Esto probablemente le otorgue un premio de 'Uso inútil del gato' si fuera Randal Schwartz: https://en.wikipedia.org/wiki/Cat_(Unix)#UUOC_(Useless_Use_Of_Cat) )

Una mejor construcción sería:

$ /usr/bin/time program_to_benchmark < big_file

En esta declaración, es el intérprete de comandos el que abre big_file, pasándolo a su programa (bueno, en realidad al `tiempo` 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 comparar. Esto te hace una lectura real de su rendimiento sin complicaciones espurias.

Mencionaré dos "soluciones" posibles, pero realmente incorrectas, que también podrían considerarse (pero las "numere" de forma diferente ya que no son cosas que estaban mal en la publicación original):

R. Podrías 'arreglar' esto al sincronizar solo tu programa:

$ cat big_file | /usr/bin/time program_to_benchmark

B. o cronometrando la tubería completa:

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

Estos son incorrectos por las mismas razones que 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 necesita `cat` (p. ej .: el archivo que se va a leer requiere algún tipo de privilegio de acceso, y no se quiere otorgar ese privilegio al programa que se comparará:` ​​sudo cat / dev / sda | / usr / bin / time my_compression_test --no-output`)

  • en la práctica , en las máquinas modernas, el 'gato' añadido 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%. Tal vez una corrida de:

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

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

Aún así, predigo que sería capaz de medir la diferencia entre `archivo cat | wc -l` y `wc -l <file` y encuentra 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 más pequeña 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 los 'mejores de 3' resultados, 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 interconexión afirman haber tenido más tiempo de CPU (usuario + sys) que en tiempo real. Esto se debe a que estoy usando el comando integrado 'time' de shell (Bash), que es consciente de la interconexión; y estoy en una máquina multi-core 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. Usando / usr / bin / time veo un tiempo de CPU menor que en tiempo real, lo que muestra que solo puede medir el tiempo que el único elemento de interconexión pasó a él en su línea de comando. Además, la salida del shell da milisegundos mientras que / usr / bin / time solo da cientos de segundo.

Entonces, en el nivel de eficiencia de `wc -l`, el` gato` hace una gran diferencia: 409/283 = 1.453 o 45.3% más en tiempo real, y 775/280 = 2.768, ¡o un enorme 177% más de CPU utilizada! En mi caja de prueba aleatoria, "estaba ahí en el momento".

Debo añadir que existe 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 entrada de un conducto, exactamente 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 en el archivo real. Su programa, o en muchos casos las bibliotecas de E / S del idioma en el que fue escrito, puede tomar 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 explícitas de lectura (2). 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 punto 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 ambos sentidos; quizás descontando el resultado del 'gato' por algún pequeño factor para "perdonar" el costo de ejecutar `cat` en sí mismo.




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

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




Links