Подтвердить что ты не робот

Почему этот код C быстрее, чем этот код на С++? получение самой большой строки в файле

У меня есть две версии программы, которые делают в основном одно и то же, получая самую большую длину строки в файле, у меня есть файл с примерно 8 тысячами строк, мой код на C немного более примитивен (из конечно!), чем код, который у меня есть на С++. Программа C занимает около 2 секунд для запуска, а программа на С++ занимает 10 секунд для запуска (тот же файл, который я тестирую для обоих случаев). Но почему? Я ожидал, что это займет столько же времени или немного больше, но не на 8 секунд медленнее!

мой код в 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);
}

мой код в С++:

#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;
}
4b9b3361

ОТВЕТЫ

Ответ 1

Версия С++ постоянно выделяет и освобождает экземпляры std::string. Распределение памяти - дорогостоящая операция. В дополнение к этому выполняются конструкторы/деструкторы.

Однако в версии C используется постоянная память, и просто необходимо: чтение в одиночных символах, установка счетчика длины строки к новому значению, если оно выше, для каждой новой строки и для нее.

Ответ 2

Я предполагаю, что это проблема с параметрами компилятора, которые вы используете, самим компилятором или файловой системой. Я только что скомпилировал обе версии (с оптимизацией) и провел их с текстовым файлом в 92 000 строк:

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

И я подозреваю, что причина, по которой версия С++ быстрее, потому что fgetc, скорее всего, медленнее. fgetc использует буферизованный ввод-вывод, но вызывает вызов функции для каждого символа. Я тестировал его раньше, а fgetc - не так быстро, как сделать вызов для чтения всей строки в одном вызове (например, по сравнению с fgets).

Ответ 3

Итак, в нескольких комментариях я повторил ответы людей, что проблема, скорее всего, является дополнительным копированием, сделанным вашей версией на С++, где он копирует строки в память в строке. Но я хотел проверить это.

Сначала я реализовал версии fgetc и getline и приурочил их. Я подтвердил, что в режиме отладки версия getline медленнее, около 130 мкс против 60 мкс для версии fgetc. Это неудивительно, учитывая традиционную мудрость, что iostreams медленнее, чем использование stdio. Однако в прошлом мне показалось, что iostreams значительно ускоряются от оптимизации. Это было подтверждено, когда я сравнивал время выпуска: около 20 мкс с использованием getline и 48 мкс с fgetc.

Тот факт, что использование getline с iostreams быстрее, чем fgetc, по крайней мере в режиме выпуска, противоречит рассуждениям о том, что копирование всех этих данных должно быть медленнее, чем не копирование, поэтому я не уверен, что вся оптимизация чтобы избежать, и я действительно не искал никаких объяснений, но было бы интересно понять, что нужно оптимизировать. edit: когда я смотрел на программы с профилировщиком, было неясно, как сравнивать производительность, поскольку разные методы выглядели настолько отличными друг от друга

Anwyay Я хотел посмотреть, могу ли я получить более быструю версию, избегая копирования с использованием метода get() в объекте fstream и просто делайте именно то, что делает версия C. Когда я это сделал, я был очень удивлен, обнаружив, что использование fstream::get() было довольно медленным, чем методы fgetc и getline как в отладке, так и в выпуске; Около 230 мкс при отладке и 80 мкс в Release.

Чтобы сузить все замедления, я пошел вперед и сделал другую версию, на этот раз используя stream_buf, прикрепленный к объекту fstream, и метод snextc(). Эта версия, безусловно, самая быстрая; 25 мкс в отладке и 6 мкс в выпуске.

Я предполагаю, что то, что делает метод fstream::get() настолько медленнее, что он создает сторожевые объекты для каждого вызова. Хотя я не тестировал это, я не вижу, что get() делает намного больше, чем просто получение следующего символа из stream_buf, за исключением этих сторожевых объектов.

Во всяком случае, мораль этой истории заключается в том, что если вы хотите быстро io, вам, вероятно, лучше всего использовать функции iostream на высоком уровне, а не stdio, а для действительно быстрого доступа к базовому stream_buf. edit: на самом деле эта мораль может применяться только к MSVC, см. обновление внизу для получения результатов из другой инструментальной цепочки.

Для справки:

Я использовал VS2010 и chrono от boost 1.47 для синхронизации. Я построил 32-битные двоичные файлы (кажется, требуется ускорение chrono, потому что он не может найти 64-битную версию этой библиотеки). Я не настраивал параметры компиляции, но они, возможно, не были полностью стандартными, так как я делал это в проекте "Скриншот против меня".

Файл, с которым я тестировался, был версией текстовой версии Oeuvres Complétes de Frédéric Bastiat в версии 1.1 MB объемом 20 000 строк, тома 1 от Frédéric Bastiat от Project Gutenberg, http://www.gutenberg.org/ebooks/35390

Время в режиме разблокировки

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

Время отладки:

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

Здесь моя версия 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';
}

Здесь моя версия 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';
}

версия 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';
}

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

обновление:

Я повторил тесты, используя clang (trunk) в OS X с libС++. Результаты для реализаций на основе iostream оставались относительно одинаковыми (при включенной оптимизации); fstream::get() намного медленнее, чем std::getline() намного медленнее, чем filebuf::snextc(). Но производительность fgetc() улучшилась относительно реализации getline() и стала быстрее. Возможно, это связано с тем, что копирование, выполняемое getline(), становится проблемой этой инструментальной цепочки, в то время как это не с MSVC? Возможно, реализация fgetc() в Microsoft CRT плоха или что-то в этом роде?

В любом случае, вот времена (я использовал гораздо больший файл, 5.3 МБ):

с использованием -Os

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

с использованием -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

Ответ 4

Вы не сравниваете яблоки с яблоками. Ваша программа C не копирует данные из буфера FILE* в вашу программную память. Он также работает с необработанными файлами.

Ваша программа на С++ должна проходить по длине каждой строки несколько раз - один раз в коде потока, чтобы узнать, когда прекратить строку, которую он возвращает вам, один раз в конструкторе std::string, и один раз в ваш кодовый вызов s.length().

Возможно, вы могли бы повысить производительность своей C-программы, например, используя getc_unlocked, если она вам доступна. Но самая большая победа связана с необходимостью не копировать ваши данные.

EDIT: отредактирован в ответ на комментарий от bames53

Ответ 5

2 секунды всего 8000 строк? Я не знаю, как долго ваши линии, но есть вероятность, что вы делаете что-то очень не так.

Эта тривиальная программа Python выполняется почти мгновенно с El Quijote, загруженной из Project Gutenberg (40006 строк, 2,2 МБ):

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

Время:

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

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

Вы можете улучшить свой C-код, буферизируя ввод, а не читать char на char.

О том, почему С++ медленнее C, он должен быть связан с построением строковых объектов и вызовом метода length. В C вы просто считаете символы, когда идете.

Ответ 6

Я попытался скомпилировать и запустить ваши программы с 40K строк источника С++, и они оба завершили примерно за 25 мс. Я могу только заключить, что ваши входные файлы имеют чрезвычайно длинные строки, возможно, 10K-100K символов в строке. В этом случае версия C не имеет отрицательной производительности от длинной длины строки, в то время как версия С++ должна будет продолжать увеличивать размер строки и копировать старые данные в новый буфер. Если он должен был увеличить размер достаточное количество раз, что могло бы объяснить чрезмерную разницу в производительности.

Ключевым моментом здесь является то, что две программы не делают то же самое, поэтому вы не можете сравнить их результаты. Если бы вы могли предоставить входной файл, мы могли бы предоставить дополнительные сведения.

Вы могли бы использовать tellg и ignore, чтобы сделать это быстрее на С++.

Ответ 7

Программа С++ строит строковые объекты строк, а программа C просто читает символы и смотрит на символы.

EDIT:

Спасибо за upvotes, но после обсуждения я теперь думаю, что этот ответ неверен. Это было разумное первое предположение, но в этом случае кажется, что разные (и очень медленные) времена выполнения вызваны другими вещами.

Ответ 8

Я в порядке с теоретическими людьми. Но позвольте получить эмпирическое.

Я создал файл с 13 миллионами строк текстового файла для работы.

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

Исходный код, отредактированный для чтения из stdin (не должен влиять слишком сильно на производительность) сделал это почти через 2 минуты.

Код С++:

#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;
}

Время С++:

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

Версия A '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;
}

C:

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

Сделайте свою собственную математику...