Вопрос: Почему чтение строк из stdin происходит намного медленнее на C ++, чем Python?


Я хотел сравнить строки чтения ввода строки из stdin с помощью Python и C ++ и был шокирован, увидев, что мой код на C ++ работает на порядок медленнее, чем эквивалентный код Python. Поскольку мой C ++ ржавый, и я еще не эксперт Pythonista, скажите, пожалуйста, что я делаю что-то неправильно или я что-то не понимаю.


(Ответ TLDR: включить утверждение: cin.sync_with_stdio(false)или просто использовать fgetsвместо.

Результаты TLDR: прокрутите весь путь до нижней части моего вопроса и посмотрите на таблицу.)


Код 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

Эквивалент 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))

Вот мои результаты:

$ 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

Редактировать: Следует отметить, что я пробовал это как в Mac OS X v10.6.8 (Snow Leopard), так и в Linux 2.6.32 (Red Hat Linux 6.2). Первый - это MacBook Pro, а последний - очень мясистый сервер, а не то, что это слишком уместно.

Изменить 2: (Удалено это редактирование, как уже не применимо)

$ 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

Редактировать 3:

Хорошо, я попробовал предложить J.N. попытаться, чтобы Python сохранил строку, прочитанную: но это не имело никакого значения для скорости python.

Я также попробовал использовать J.N. scanfв charмассив вместо getlineв std::string, Бинго! Это привело к эквивалентной производительности как для Python, так и для C ++. (3,333,333 LPS с моими входными данными, которые, кстати, являются лишь короткими линиями из трех полей каждый, обычно шириной около 20 символов, хотя иногда и больше).

Код:

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

Скорость:

$ 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

(Да, я запускал его несколько раз.) Итак, я думаю, теперь я буду использовать scanfвместо getline, Но мне все же интересно, если люди считают, что это std::string/ getlineявляется типичным и разумным.

Редактировать 4 (было: Final Edit / Solution):

Добавление:

cin.sync_with_stdio(false);

Непосредственно выше моего первоначального цикла while получается код, который работает быстрее, чем Python.

Новое сравнение производительности (это на моем MacBook Pro 2011), используя исходный код, оригинал с отключенной синхронизацией и исходный код Python, соответственно, в файле с 20-миллиметровыми линиями текста. Да, я несколько раз запускал его, чтобы устранить дисковое кэширование.

$ /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

Спасибо @Vaughn Cato за его ответ! Любые специалисты по разработке, которые могут сделать или могут быть полезны, люди могут указать на то, почему происходит эта синхронизация, что это значит, когда это полезно, и когда это нормально отключать, было бы очень полезно потомству. :-)

Изменить 5 / Лучше Решение:

Как предложил Гэндальф Грей ниже, getsдаже быстрее, чем scanfили несинхронизированный cinподход. Я также узнал, что scanfа также getsявляются UNSAFE и НЕ ДОЛЖНЫ ИСПОЛЬЗОВАТЬСЯ из-за возможности переполнения буфера. Итак, я написал эту итерацию, используя fgets, более безопасная альтернатива получает. Вот подходящие строки для моих коллег-нобов:

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.");

Теперь вот результаты, используя еще более крупный файл (100 М строк, ~ 3,4 ГБ) на быстром сервере с очень быстрым диском, сравнивая код Python, несинхронизированный cin, и fgetsподходов, а также сравнения с утилитой wc. [ scanfошибка сегментации версии, и я не чувствую, как ее устраняют.]:

$ /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

Как вы видете, fgetsлучше, но все же довольно далеко от производительности wc; Я уверен, что это связано с тем, что wc проверяет каждый символ без копирования памяти. Я подозреваю, что в этот момент другие части кода станут узким местом, поэтому я не думаю, что оптимизация на этом уровне будет даже стоить даже, если это возможно (поскольку, в конце концов, мне действительно нужно хранить строки чтения в памяти).

Также обратите внимание, что небольшой компромисс с использованием char *буфер и fgetsпротив несинхронизированного cinчто строка может считывать строки любой длины, а первая требует ограничения ввода некоторого конечного числа. На практике это, вероятно, не проблема для чтения большинства входных файлов на основе строк, так как буфер может быть установлен на очень большое значение, которое не будет превышено действительным вводом.

Это было образовательным. Спасибо всем за ваши комментарии и предложения.

Редактировать 6:

Как было предложено J.F.Sebastian в комментариях ниже, утилита GNU wc использует обычный C read()(в оболочке safe-read.c) для чтения фрагментов (из 16k байт) за раз и подсчета новых строк. Вот эквивалент Python, основанный на коде J.F. (просто показывая соответствующий фрагмент, который заменяет Python forцикл:

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

Производительность этой версии довольно быстрая (хотя, конечно же, немного медленнее, чем исходная утилита C wc):

$ /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

Опять же, для меня немного глупо сравнивать C ++ fgets/ cinи первый код python, с одной стороны, wc -lи этот последний фрагмент Python с другой стороны, поскольку последние два фактически не сохраняют строки чтения, а просто подсчитывают символы новой строки. Тем не менее, интересно изучить все различные реализации и подумать о последствиях производительности. Еще раз спасибо!

Редактировать 7: Крошечное контрольное добавление и резюме

Для полноты я подумал, что обновляю скорость чтения для того же файла в том же поле с исходным (синхронизированным) кодом на C ++. Опять же, для файлового файла 100 М на быстром диске. Вот полная таблица:

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

1419


источник


Ответы:


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

std::ios_base::sync_with_stdio(false);

Обычно, когда входной поток буферизуется, вместо чтения одного символа за раз, поток будет считываться в больших кусках. Это уменьшает количество системных вызовов, которые обычно относительно дороги. Однако, поскольку FILE*исходя из stdioа также iostreamsчасто имеют отдельные реализации и, следовательно, отдельные буферы, это может привести к проблеме, если оба они используются вместе. Например:

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

Если больше ввода было прочитано cinчем это действительно необходимо, тогда второе целочисленное значение не будет доступно для scanfфункция, которая имеет свой собственный независимый буфер. Это приведет к неожиданным результатам.

Чтобы этого избежать, по умолчанию потоки синхронизируются с stdio, Один из общих способов достижения этого - cinчитайте каждый символ по одному при необходимости, используя stdioфункции. К сожалению, это приводит к большим накладным расходам. Для небольшого количества входных данных это не большая проблема, но когда вы читаете миллионы строк, оценка производительности значительна.

К счастью, разработчики библиотеки решили, что вы также сможете отключить эту функцию, чтобы повысить производительность, если вы знали, что делаете, поэтому они предоставили sync_with_stdioметод.


1239



Просто из любопытства я взглянул на то, что происходит под капотом, и я использовал dtruss / Трассирование на каждом тесте.

C ++

./a.out < in
Saw 6512403 lines in 8 seconds.  Crunch speed: 814050

Системные вызовы 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

питон

./a.py < in
Read 6512402 lines in 1 seconds. LPS: 6512402

Системные вызовы sudo dtruss -c ./a.py < in

CALL                                        COUNT
__mac_syscall                                   1
<snip>
open                                            5
pread                                           8
mprotect                                       17
mmap                                           21
stat64                                         29

109



Я воспроизвел оригинальный результат на моем компьютере, используя g ++ на Mac.

Добавление следующих операторов в версию C ++ перед whileцикл приводит к питон версия:

std::ios_base::sync_with_stdio(false);
char buffer[1048576];
std::cin.rdbuf()->pubsetbuf(buffer, sizeof(buffer));

sync_with_stdio улучшила скорость до 2 секунд, а установка большего буфера уменьшила ее до 1 секунды.


74



Я на несколько лет отстаю отсюда, но:

В «Редактировании 4/5/6» исходного сообщения вы используете конструкцию:

$ /usr/bin/time cat big_file | program_to_benchmark

Это неправильно по-разному:

  1. Вы на самом деле задумываете исполнение «кошки», а не своего теста. Использование «user» и «sys» CPU, отображаемое «временем», относится к «cat», а не к вашей тестовой программе. Хуже того, «реальное» время также не обязательно точно. В зависимости от реализации `cat` и конвейеров в вашей локальной операционной системе возможно, что` cat` пишет окончательный гигантский буфер и выходит задолго до того, как процесс чтения завершит свою работу.

  2. Использование «кошки» не является необходимым и на самом деле контрпродуктивным; вы добавляете движущиеся части. Если вы были на достаточно старой системе (то есть с одним процессором и - в некоторых поколениях компьютеров - в / в быстрее, чем у процессора), сам факт, что `cat` работал, может существенно покрасить результаты. Вы также можете использовать любую буферизацию ввода и вывода и другую обработку, которую может выполнять «кошка». (Это, скорее всего, принесет вам награду «Бесполезное использование кошки», если я буду Рэндалом Шварцем: https://en.wikipedia.org/wiki/Cat_(Unix)#UUOC_(Useless_Use_Of_Cat) )

Лучшей конструкцией было бы:

$ /usr/bin/time program_to_benchmark < big_file

В этом утверждении это оболочка который открывает файл big_file, передавая его в вашу программу (ну, собственно, «время», которое затем выполняет вашу программу как подпроцесс) в качестве уже открытого файлового дескриптора. 100% чтения файла строго зависит от программы, которую вы пытаетесь сравнить. Это дает вам реальное представление о его производительности без ложных осложнений.

Я упомянул два возможных, но на самом деле неправильных «исправления», которые также можно было бы рассмотреть (но я «их» по-разному, поскольку это не то, что было неправильно в исходном сообщении):

О. Вы можете «исправить» это по времени только своей программой:

$ cat big_file | /usr/bin/time program_to_benchmark

B. или по времени для всего трубопровода:

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

Они ошибочны по тем же причинам, что и # 2: они все еще используют `cat` без необходимости. Я упоминаю их по нескольким причинам:

  • они более «естественны» для людей, которые не совсем устраивают объекты перенаправления ввода-вывода оболочки POSIX

  • могут быть случаи, когда `cat` является (например: для чтения файла требуется какая-то привилегия для доступа, и вы не хотите предоставлять эту привилегию программе для сравнения: `sudo cat / dev / sda | / usr / bin / time my_compression_test - нет-output`)

  • на практике , на современных машинах добавленный «кот» в трубопроводе, вероятно, не имеет никаких реальных последствий

Но я говорю это последнее с некоторым колебанием. Если мы рассмотрим последний результат в «Редактировании 5» -

$ /usr/bin/time cat temp_big_file | wc -l
0.01user 1.34system 0:01.83elapsed 74%CPU ...

- это утверждает, что «кошка» потребляла 74% ЦП во время теста; и действительно 1,34 / 1,83 составляет около 74%. Возможно, запуск:

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

потребовалось бы всего лишь 0,49 секунды! Вероятно, нет: «cat» здесь должен был заплатить за системные вызовы read () (или эквивалентные), которые перенесли файл с «диска» (фактически буферный кеш), а также на запись в канале, чтобы доставить их на `wc`. Правильный тест все равно должен был бы выполнять эти вызовы read (); только вызовы write-to-pipe и read-from-pipe были бы сохранены, и они должны быть довольно дешевыми.

Тем не менее, я предсказываю, что вы сможете измерить разницу между `cat file | wc -l` и `wc -l <файл` и найдите заметную (2-значную процентную) разницу. Каждый из более медленных тестов будет платить аналогичное наказание в абсолютном времени; который, однако, будет составлять меньшую часть его большего общего времени.

На самом деле, я сделал несколько быстрых тестов с файлом мусора размером 1,5 гигабайта в системе Linux 3.13 (Ubuntu 14.04), получив эти результаты (это, на самом деле, «лучшие из 3» результатов, конечно, после правильного кэширования):

$ 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)

Обратите внимание, что результаты двух конвейеров утверждают, что они потребовали больше времени процессора (пользователь + sys), чем в реальном времени. Это связано с тем, что я использую встроенную команду «время» оболочки (Bash), которая понимает конвейер; и я на многоядерной машине, где отдельные процессы в конвейере могут использовать отдельные ядра, накапливая время процессора быстрее, чем в реальном времени. Используя / usr / bin / time, я вижу меньшее время процессора, чем в реальном времени, - показывая, что он может использовать только один элемент конвейера, переданный ему в командной строке. Кроме того, вывод оболочки дает миллисекунды, в то время как / usr / bin / time дает только hundreths секунды.

Таким образом, на уровне эффективности `wc -l`,` cat` имеет огромное значение: 409/283 = 1.453 или 45.3% больше в реальном времени, а 775/280 = 2,768 или колоссальный 177% больше используемого ЦП! На моем случайном ящике-есть-в-время-тест.

Я должен добавить, что существует по меньшей мере еще одно существенное различие между этими стилями тестирования, и я не могу сказать, является ли это выгодой или недостатком; вы должны сами решить это:

Когда вы запускаете `cat big_file | / usr / bin / time my_program`, ваша программа получает входные данные из канала, точно в темпе, отправленном `cat`, и в кусках, не больших, чем написано` cat`.

Когда вы запускаете `/ usr / bin / time my_program <big_file`, ваша программа получает открытый файловый дескриптор в фактический файл. Ваша программа - или во многих случаях библиотеки ввода-вывода языка, на котором он был написан, могут принимать различные действия, если они представлены файловым дескриптором, ссылающимся на обычный файл. Он может использовать mmap (2) для сопоставления входного файла в его адресное пространство, вместо использования явных системных вызовов read (2). Эти различия могут иметь гораздо больший эффект на результаты теста, чем небольшие затраты на запуск двоичного кода `cat`.

Конечно, это интересный результат теста, если одна и та же программа выполняет существенно разные отношения между этими двумя случаями. Это показывает, что, действительно, программа или библиотеки ее ввода-вывода находятся делая что-то интересное, например, используя mmap (). Поэтому на практике может быть полезно запустить тесты в обоих направлениях; возможно, дисконтируя результат `cat` каким-то небольшим фактором, чтобы« простить »стоимость запуска самой« кошки ».


68



getline, stream operators, scanf, can be convenient if you don't care about file loading time or if you are loading small text files. But, if the performance is something you care about, you should really just buffer the entire file into memory (assuming it will fit).

Here's an example:

//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();

If you want, you can wrap a stream around that buffer for more convenient access like this:

std::istrstream header(&filebuf[0], length);

Also, if you are in control of the file, consider using a flat binary data format instead of text. It's more reliable to read and write because you don't have to deal with all the ambiguities of whitespace. It's also smaller and much faster to parse.


22



By the way, the reason the line count for the C++ version is one greater than the count for the Python version is that the eof flag only gets set when an attempt is made to read beyond eof. So the correct loop would be:

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

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

10



The following code was faster for me than the other code posted here so far: (Visual Studio 2013, 64-bit, 500 MB file with line length uniformly in [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'; });
}

It beats all my Python attempts by more than a factor 2.


7



In your second example (with scanf()) reason why this is still slower might be because scanf("%s") parses string and looks for any space char (space, tab, newline).

Also, yes, CPython does some caching to avoid harddisk reads.


6



A first element of an answer: <iostream> is slow. Damn slow. I get a huge performance boost with scanf as in the below, but it is still two times slower than 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;
}

5