proceso - ¿Por qué este código C es más rápido que este código C++? obtener la línea más grande en el archivo

proceso de compilacion en c

Question

Tengo dos versiones de un programa que hace básicamente lo mismo, obtener la mayor longitud de una línea en un archivo, tengo un archivo con aproximadamente 8 mil líneas, mi código en C es un poco más primitivo (¡por supuesto!) que el código que tengo en C ++. El programa C tarda aproximadamente 2 segundos en ejecutarse, mientras que el programa en C ++ tarda 10 segundos en ejecutarse (el mismo archivo que estoy probando para ambos casos). ¿Pero por qué? Esperaba que tomara la misma cantidad de tiempo o un poco más, ¡pero no 8 segundos más lento!

mi código en C:

#include <stdio.h>
#include <stdlib.h> 
#include <string.h>

#if _DEBUG
    #define DEBUG_PATH "../Debug/"
#else
    #define DEBUG_PATH ""
#endif

const char FILE_NAME[] = DEBUG_PATH "data.noun";

int main()
{   
    int sPos = 0;
    int maxCount = 0;
    int cPos = 0;
    int ch;
    FILE *in_file;              

    in_file = fopen(FILE_NAME, "r");
    if (in_file == NULL) 
    {
        printf("Cannot open %s/n", FILE_NAME);
        exit(8);
    }       

    while (1) 
    {
        ch = fgetc(in_file);
        if(ch == 0x0A || ch == EOF) // /n or /r or /r/n or end of file
        {           
            if ((cPos - sPos) > maxCount)
                maxCount = (cPos - sPos);

            if(ch == EOF)
                break;

            sPos = cPos;
        }
        else
            cPos++;
    }

    fclose(in_file);

    printf("Max line length: %i/n",  maxCount); 

    getch();
    return (0);
}

Mi código en C ++:

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string>

using namespace std;

#ifdef _DEBUG
    #define FILE_PATH "../Debug/data.noun"
#else
    #define FILE_PATH "data.noun"
#endif

int main()
{
    string fileName = FILE_PATH;
    string s = "";
    ifstream file;
    int size = 0;

    file.open(fileName.c_str());
    if(!file)
    {
        printf("could not open file!");
        return 0;
    }

    while(getline(file, s) )
            size = (s.length() > size) ? s.length() : size;
    file.close();

    printf("biggest line in file: %i", size);   

    getchar();
    return 0;
}

Answer 1

¿2 segundos por solo 8.000 líneas? No sé cuánto tiempo duran tus líneas, pero es probable que estés haciendo algo muy mal.

Este trivial programa Python se ejecuta casi instantáneamente con El Quijote descargado del Proyecto Gutenberg (40006 líneas, 2.2MB):

import sys
print max(len(s) for s in sys.stdin)

La temporización:

~/test$ time python maxlen.py < pg996.txt
76

real    0m0.034s
user    0m0.020s
sys     0m0.010s

Podría mejorar su código C almacenando en búfer la entrada en lugar de leer char por char.

Acerca de por qué el C ++ es más lento que C, debe estar relacionado con la construcción de los objetos de cadena y luego llamar al método de longitud. En C solo estás contando los caracteres a medida que avanzas.

Answer 2

Así que en algunos comentarios hice eco de las respuestas de la gente de que el problema probablemente fue la copia adicional realizada por su versión de C ++, donde copia las líneas en la memoria en una cadena. Pero quería probar eso.

Primero implementé las versiones fgetc y getline y las cronometré. Confirmé que en el modo de depuración la versión getline es más lenta, aproximadamente 130 µs frente a 60 µs para la versión fgetc. Esto no es sorprendente, dado el criterio convencional de que los iostreams son más lentos que el uso de stdio. Sin embargo, en el pasado, según mi experiencia, los flujos de iostreams se aceleran significativamente con la optimización. Esto se confirmó cuando comparé los tiempos del modo de lanzamiento: aproximadamente 20 µs usando getline y 48 µs con fgetc.

El hecho de que usar getline con iostreams sea más rápido que fgetc, al menos en el modo de lanzamiento, va en contra del razonamiento de que copiar todos los datos debe ser más lento que no copiarlos, por lo que no estoy seguro de lo que puede evitar toda optimización. y realmente no busqué ninguna explicación, pero sería interesante entender qué se está optimizando. Edición: cuando miré los programas con un generador de perfiles no era obvio cómo comparar el rendimiento, ya que los diferentes métodos se veían muy diferentes entre sí.

Anwyay quería ver si podía obtener una versión más rápida al evitar la copia utilizando el método get() en el objeto fstream y simplemente hacer exactamente lo que está haciendo la versión C. Cuando hice esto, me sorprendió bastante descubrir que el uso de fstream::get() era bastante más lento que los métodos fgetc y getline tanto en la depuración como en la versión; Aproximadamente 230 µs en depuración y 80 µs en Release.

Para reducir lo que sea la ralentización es que seguí adelante e hice otra versión, esta vez usando el stream_buf adjunto al objeto fstream, y el método snextc() en eso. Esta versión es, con mucho, la más rápida; 25 µs en depuración y 6 µs en versión.

Supongo que lo que hace que el fstream::get() sea ​​mucho más lento es que construye un objeto centinela para cada llamada. Aunque no he probado esto, no puedo ver que get() haga mucho más que solo obtener el siguiente carácter de stream_buf, excepto estos objetos de centinela.

De todos modos, la moraleja de la historia es que si quieres un io rápido, probablemente sea mejor que uses funciones de iostream de alto nivel en lugar de stdio, y para un acceso realmente rápido al stream_buf subyacente. edición: en realidad, esta moral solo puede aplicarse a MSVC, consulte la actualización en la parte inferior para obtener los resultados de una cadena de herramientas diferente.

Para referencia:

Usé VS2010 y chrono de boost 1.47 para el tiempo. Construí binarios de 32 bits (parece requerido por boost chrono porque parece que no puede encontrar una versión de 64 bits de esa biblioteca). No modifiqué las opciones de compilación, pero puede que no sean completamente estándar ya que hice esto en un proyecto de scratch contra cero.

El archivo con el que probé era la versión de texto simple de 1.1 MB 20.000 líneas de Oeuvres Complètes de Frédéric Bastiat, tomo 1 por Frédéric Bastiat de Project Gutenberg, http://www.gutenberg.org/ebooks/35390

Tiempos de modo de lanzamiento

fgetc time is: 48150 microseconds
snextc time is: 6019 microseconds
get time is: 79600 microseconds
getline time is: 19881 microseconds

Modo de depuración veces:

fgetc time is: 59593 microseconds
snextc time is: 24915 microseconds
get time is: 228643 microseconds
getline time is: 130807 microseconds

Aquí está mi versión fgetc() :

{
    auto begin = boost::chrono::high_resolution_clock::now();
    FILE *cin = fopen("D:/bames/automata/pg35390.txt","rb");
    assert(cin);
    unsigned maxLength = 0;
    unsigned i = 0;
    int ch;
    while(1) {
        ch = fgetc(cin);
        if(ch == 0x0A || ch == EOF) {
            maxLength = std::max(i,maxLength);
            i = 0;
            if(ch==EOF)
                break;
        } else {
            ++i;
        }
    }
    fclose(cin);
    auto end = boost::chrono::high_resolution_clock::now();
    std::cout << "max line is: " << maxLength << ''/n'';
    std::cout << "fgetc time is: " << boost::chrono::duration_cast<boost::chrono::microseconds>(end-begin) << ''/n'';
}

Aquí está mi versión getline() :

{
    auto begin = boost::chrono::high_resolution_clock::now();
    std::ifstream fin("D:/bames/automata/pg35390.txt",std::ios::binary);
    unsigned maxLength = 0;
    std::string line;
    while(std::getline(fin,line)) {
        maxLength = std::max(line.size(),maxLength);
    }
    auto end = boost::chrono::high_resolution_clock::now();
    std::cout << "max line is: " << maxLength << ''/n'';
    std::cout << "getline time is: " << boost::chrono::duration_cast<boost::chrono::microseconds>(end-begin) << ''/n'';
}

la fstream::get()

{
    auto begin = boost::chrono::high_resolution_clock::now();
    std::ifstream fin("D:/bames/automata/pg35390.txt",std::ios::binary);
    unsigned maxLength = 0;
    unsigned i = 0;
    while(1) {
        int ch = fin.get();
        if(fin.good() && ch == 0x0A || fin.eof()) {
            maxLength = std::max(i,maxLength);
            i = 0;
            if(fin.eof())
                break;
        } else {
            ++i;
        }
    }
    auto end = boost::chrono::high_resolution_clock::now();
    std::cout << "max line is: " << maxLength << ''/n'';
    std::cout << "get time is: " << boost::chrono::duration_cast<boost::chrono::microseconds>(end-begin) << ''/n'';
}

y la versión snextc()

{
    auto begin = boost::chrono::high_resolution_clock::now();
    std::ifstream fin("D:/bames/automata/pg35390.txt",std::ios::binary);
    std::filebuf &buf = *fin.rdbuf();
    unsigned maxLength = 0;
    unsigned i = 0;
    while(1) {
        int ch = buf.snextc();
        if(ch == 0x0A || ch == std::char_traits<char>::eof()) {
            maxLength = std::max(i,maxLength);
            i = 0;
            if(ch == std::char_traits<char>::eof())
                break;
        } else {
            ++i;
        }
    }
    auto end = boost::chrono::high_resolution_clock::now();
    std::cout << "max line is: " << maxLength << ''/n'';
    std::cout << "snextc time is: " << boost::chrono::duration_cast<boost::chrono::microseconds>(end-begin) << ''/n'';
}

actualizar:

Repito las pruebas usando clang (trunk) en OS X con libc ++. Los resultados para las implementaciones basadas en iostream se mantuvieron relativamente iguales (con la optimización activada); fstream::get() mucho más lento que std::getline() mucho más lento que filebuf::snextc() . Pero el rendimiento de fgetc() mejoró en relación con la implementación de getline() y se hizo más rápido. Quizás esto se deba a que la copia realizada por getline() convierte en un problema con esta cadena de herramientas, mientras que no fue con MSVC. ¿Tal vez la implementación CRT de Microsoft de fgetc () sea mala o algo así?

De todos modos, aquí están los tiempos (utilicé un archivo mucho más grande, 5.3 MB):

usando -Os

fgetc time is: 39004 microseconds
snextc time is: 19374 microseconds
get time is: 145233 microseconds
getline time is: 67316 microseconds

utilizando -O0

fgetc time is: 44061 microseconds
snextc time is: 92894 microseconds
get time is: 184967 microseconds
getline time is: 209529 microseconds

-O2

fgetc time is: 39356 microseconds
snextc time is: 21324 microseconds
get time is: 149048 microseconds
getline time is: 63983 microseconds

-O3

fgetc time is: 37527 microseconds
snextc time is: 22863 microseconds
get time is: 145176 microseconds
getline time is: 67899 microseconds

Answer 3

El programa C ++ construye objetos de cadena de las líneas, mientras que el programa C solo lee los caracteres y los mira.

EDITAR:

Gracias por los votos positivos, pero después de la discusión ahora creo que esta respuesta es incorrecta. Fue una primera suposición razonable, pero en este caso parece que los diferentes tiempos de ejecución (y muy lentos) son causados ​​por otras cosas.

Answer 4

Estoy bien con la gente de la teoría. Pero empecemos por ser empíricos.

Generé un archivo con 13 millones de líneas de archivo de texto para trabajar.

~$ for i in {0..1000}; do cat /etc/* | strings; done &> huge.txt

El código original editado para leer desde stdin (no debería afectar demasiado el rendimiento) lo hizo en casi 2 minutos.

Código C ++:

#include <iostream>
#include <stdio.h>

using namespace std;

int main(void)
{
    string s = "";
    int size = 0;

    while (cin) {
        getline(cin, s);
        size = (s.length() > size) ? s.length() : size;
    }
    printf("Biggest line in file: %i/n", size);

    return 0;
}

Tiempo de C ++:

~$ time ./cplusplus < huge.txt
real    1m53.122s
user    1m29.254s
sys     0m0.544s

Una versión ''C'':

#include <stdio.h>
int main(void)
{
    char *line = NULL;
    int read, max = 0, len = 0;

    while ((read = getline(&line, &len, stdin)) != -1)
        if (max < read)
            max = read -1;
    printf("Biggest line in file %d/n", max);

    return 0;
}

Rendimiento C:

~$ time ./ansic < huge.txt
real    0m4.015s
user    0m3.432s
sys     0m0.328s

Haz tus propios cálculos ...

Answer 5

Intenté compilar y ejecutar sus programas contra 40K líneas de código fuente C ++ y ambos se completaron en aproximadamente 25 ms. Solo puedo concluir que sus archivos de entrada tienen líneas extremadamente largas, posiblemente 10K-100K caracteres por línea. En ese caso, la versión C no tiene un rendimiento negativo de la longitud de línea larga, mientras que la versión C ++ tendría que seguir aumentando el tamaño de la cadena y copiando los datos antiguos en el nuevo búfer. Si tuviera que aumentar de tamaño una cantidad suficiente de veces que podría explicar la excesiva diferencia de rendimiento.

La clave aquí es que los dos programas no hacen lo mismo por lo que realmente no se pueden comparar sus resultados. Si pudo proporcionar el archivo de entrada, podríamos proporcionar detalles adicionales.

Probablemente podría usar tellg e ignore para hacer esto más rápido en C ++.

Answer 6

La versión de C ++ asigna y desasigna constantemente las instancias de std :: string. La asignación de memoria es una operación costosa. Además de eso se ejecutan los constructores / destructores.

Sin embargo, la versión C usa memoria constante, y solo es necesario: leer en caracteres individuales, configurar el contador de longitud de línea al nuevo valor si es más alto, para cada nueva línea y eso es todo.

Answer 7

No estás comparando manzanas con manzanas. Su programa C no copia los datos del búfer FILE* memoria de su programa. También funciona en archivos en bruto.

Su programa C ++ necesita recorrer la longitud de cada cadena varias veces: una vez en el código de flujo para saber cuándo terminar la cadena que le devuelve, una vez en el constructor de std::string y una vez en la llamada de su código a s.length() .

Es posible que pueda mejorar el rendimiento de su programa C, por ejemplo, utilizando getc_unlocked si está disponible para usted. Pero la mayor ganancia proviene de no tener que copiar sus datos.

EDIT: editado en respuesta a un comentario por bames53

Answer 8

Supongo que es un problema con las opciones del compilador que está utilizando, el compilador en sí mismo o el sistema de archivos. Acabo de compilar ambas versiones (con optimizaciones activadas) y las ejecuté en un archivo de texto de 92,000 líneas:

c++ version:  113 ms
c version:    179 ms

Y sospecho que la razón por la que la versión de C ++ es más rápida es porque fgetc es probablemente más lento. fgetc utiliza E / S en búfer, pero está realizando una llamada a la función para recuperar todos los caracteres. Lo he probado antes y fgetc no es tan rápido como hacer una llamada para leer toda la línea en una llamada (p. Ej., En comparación con fgets ).