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

1841

Я хотел сравнить строки чтения строкового ввода из 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, а второй - очень мощный сервер, не то чтобы это было слишком уместно.

$ 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

Крошечное приложение и резюме

Для полноты я подумал, что обновлю скорость чтения для того же файла в том же окне с помощью исходного (синхронизированного) кода 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
JJC
источник
14
Вы запускали свои тесты несколько раз? Возможно, есть проблема с дисковым кешем.
Вон Катон
9
@JJC: я вижу две возможности (при условии, что вы устранили проблему с кэшированием, предложенную Дэвидом): 1) <iostream>производительность - отстой. Не в первый раз это случается. 2) Python достаточно умен, чтобы не копировать данные в цикле for, потому что вы его не используете. Вы можете повторно протестировать, пытаясь использовать scanfи char[]. В качестве альтернативы вы можете попробовать переписать цикл так, чтобы что-то было сделано со строкой (например, сохранить 5-ю букву и объединить ее в результате).
JN
15
Проблема в синхронизации с stdio - см. Мой ответ.
Вон Катон
19
Так как никто, кажется, не упомянул, почему вы получаете дополнительную строку с C ++: не проверяйте cin.eof()!! Поместите getlineвызов в оператор «если».
Xeo
21
wc -lбыстрый, потому что читает поток более чем одной строкой одновременно (это может быть fread(stdin)/memchr('\n')комбинация). Результаты Python в том же порядке, например,wc-l.py
JFS

Ответы:

1645

По умолчанию 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метод.

Вон Катон
источник
142
Это должно быть наверху. Это почти наверняка правильно. Ответ не может состоять в том, чтобы заменить чтение fscanfвызовом, потому что это просто не делает так много работы, как Python. Python должен выделять память для строки, возможно, несколько раз, поскольку существующее распределение считается неадекватным - точно так же, как в подходе C ++ std::string. Эта задача почти наверняка связана с вводом / выводом, и слишком много FUD обходится вокруг стоимости создания std::stringобъектов в C ++ или использования <iostream>само по себе.
Карл Кнехтель
51
Да, добавление этой строки непосредственно над моим исходным циклом while ускорило код, чтобы превзойти даже Python. Я собираюсь опубликовать результаты в качестве окончательного редактирования. Еще раз спасибо!
JJC
6
Да, это на самом деле относится также к cout, cerr и clog.
Вон Катон
2
Чтобы сделать cout, cin, cerr и clog быстрее, сделайте это следующим образом std :: ios_base :: sync_with_stdio (false);
01100110
56
Обратите внимание, что sync_with_stdio()это статическая функция-член, и вызов этой функции для любого объекта потока (например cin) включает или выключает синхронизацию для всех стандартных объектов iostream.
Джон Цвинк
171

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

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
2mia
источник
159

Я здесь на несколько лет позади, но:

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

$ /usr/bin/time cat big_file | program_to_benchmark

Это неправильно по нескольким причинам:

  1. Вы на самом деле сроки выполнения cat, а не ваш эталон. Отображаемое использование ЦП 'user' и 'sys' timeотносится к catне вашей тестовой программе. Хуже того, «реальное» время также не обязательно точное. В зависимости от реализации catи конвейеров в вашей локальной ОС, возможно, что будет catзаписан окончательный гигантский буфер и он завершится задолго до того, как процесс чтения завершит свою работу.

  2. Использование catявляется ненужным и фактически контрпродуктивным; вы добавляете движущиеся части. Если вы работали в достаточно старой системе (т. Е. С одним ЦП и - в некоторых поколениях компьютеров - вводом-выводом быстрее, чем ЦП) - сам по себе тот факт, что catон работал, может существенно повлиять на результаты. Вы также подвержены любой буферизации ввода и вывода и другой обработке cat. (Это, вероятно, принесло бы вам награду «Бесполезное использование кошки», если бы я был Рэндал Шварц.

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

$ /usr/bin/time program_to_benchmark < big_file

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

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

О. Вы можете «исправить» это, синхронизируя только вашу программу:

$ cat big_file | /usr/bin/time program_to_benchmark

Б. или путем синхронизации всего трубопровода:

$ /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 --no-output)

  • на практике на современных машинах добавленное catв конвейер, вероятно, не имеет реального значения.

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

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

- это утверждает, что catво время теста потребляется 74% процессора; и действительно, 1,34 / 1,83 составляет примерно 74%. Возможно пробег:

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

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

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

На самом деле я провел несколько быстрых тестов с мусорным файлом объемом 1,5 гигабайта в системе Linux 3.13 (Ubuntu 14.04), получив эти результаты (на самом деле это результаты «best of 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)

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

Таким образом, на уровне эффективности 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результата каким-то небольшим фактором, чтобы «простить» стоимость работы catсамого себя.

Бела Любкин
источник
26
Вау, это было довольно проницательно! Хотя я знал, что cat не нужен для подачи ввода в стандартный поток программ и что перенаправление <shell является предпочтительным, я обычно придерживался cat из-за потока данных слева направо, который прежний метод сохраняет визуально когда я рассуждаю о трубопроводах. Различия в производительности в таких случаях я считаю незначительными. Но я очень ценю то, что ты обучил нас, Бела.
JJC
11
Перенаправление разбирается из командной строки оболочки на ранней стадии, что позволяет вам выполнить одно из следующих действий, если оно дает более приятный вид потока слева направо: $ < big_file time my_program $ time < big_file my_program это должно работать в любой оболочке POSIX (т.е. не `csh `а я не уверен насчет экзотики типа` rc`:)
Бела Лубкин
6
Опять же, помимо, возможно, неинтересной инкрементальной разницы в производительности из-за одновременного запуска двоичного файла `cat`, вы отказываетесь от возможности тестируемой программы иметь возможность mmap () входного файла. Это может иметь огромное значение в результатах. Это верно, даже если вы сами написали тесты на разных языках, используя только их идиому «строки ввода из файла». Это зависит от подробной работы их различных библиотек ввода / вывода.
Бела
2
Примечание: встроенная функция Bash timeизмеряет весь конвейер, а не первую программу. time seq 2 | while read; do sleep 1; doneотпечатки 2 сек, /usr/bin/time seq 2 | while read; do sleep 1; doneотпечатки 0 сек.
фольклор
1
@folkol - да, << Обратите внимание, что два конвейера показывают [показывают] больше ЦП [чем] в реальном времени [используя] (Bash) встроенную команду «время»; ... / usr / bin / time ... может рассчитывать только один элемент конвейера, переданный ему в его командной строке. >> '
Бела Лубкин
90

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

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

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

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

karunski
источник
5
Вы можете попробовать разные размеры буфера, чтобы получить больше полезной информации. Я подозреваю, что вы увидите быстро убывающую отдачу.
Карл Кнехтель
8
Я был слишком поспешен в своем ответе; установка размера буфера в значение, отличное от значения по умолчанию, не дает заметной разницы.
Карунски
109
Я бы также не стал устанавливать буфер 1 МБ в стеке. Это может привести к переполнению стека (хотя я думаю, что это хорошее место, чтобы обсудить это!)
Матье М.
11
Matthieu, Mac по умолчанию использует стек процессов 8 МБ. Linux использует 4 МБ на поток по умолчанию, IIRC. 1 МБ - не такая уж большая проблема для программы, которая преобразует ввод с относительно небольшой глубиной стека. Что еще более важно, std :: cin уничтожит стек, если буфер выйдет из области видимости.
SEK
22
@SEK Размер стека по умолчанию для Windows составляет 1 МБ.
Этьен
39

getlineОператоры потока scanfмогут быть удобны, если вам не важно время загрузки файла или если вы загружаете небольшие текстовые файлы. Но если вам важна производительность, вам нужно просто поместить в буфер весь файл (при условии, что он уместится).

Вот пример:

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

Если вы хотите, вы можете обернуть поток вокруг этого буфера для более удобного доступа, например так:

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

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

Stu
источник
20

Следующий код был для меня быстрее, чем другой код, опубликованный здесь: (Visual Studio 2013, 64-битный, 500 МБ файл с длиной строки равномерно в [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'; });
}

Он превосходит все мои попытки Python более чем в 2 раза.

Petter
источник
Вы можете получить даже быстрее, чем это с крошечной пользовательской, но совершенно простой C-программой, которая итеративно превращает небуферизованные readсистемные вызовы в статический буфер длины BUFSIZEили через эквивалентные соответствующие mmapсистемные вызовы, а затем перебирает этот буфер, считая символы новой строки for (char *cp = buf; *cp; cp++) count += *cp == "\n". Вы должны будете настроиться BUFSIZEна свою систему, однако, что STDIO уже сделал для вас. Но этот forцикл должен компилироваться в потрясающе быстрые инструкции на языке ассемблера для аппаратного обеспечения вашего устройства.
четверг,
3
count_if и лямбда также компилируются в «потрясающе быстро-быстрый ассемблер».
Петтер
17

Между прочим, причина, по которой количество строк для версии C ++ больше, чем количество для версии Python, заключается в том, что флаг eof устанавливается только при попытке чтения за пределами eof. Таким образом, правильный цикл будет:

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

    if (!cin.eof())
        line_count++;
};
Gregg
источник
70
Действительно правильная петля была бы: while (getline(cin, input_line)) line_count++;
Джонатан Уэйкли
2
@JonathanWakely я знаю, что я довольно поздно, но использовать ++line_count;и нет line_count++;.
Вэл говорит восстановить Монику
7
@val, если это что-то меняет, у вашего компилятора есть ошибка. Переменная a long, и компилятор вполне может сказать, что результат приращения не используется. Если он не генерирует идентичный код для постинкремента и преинкремента, он не работает.
Джонатан
2
Действительно, любой достойный компилятор сможет обнаружить неправильное использование после инкремента и заменить его преинкрементным, но компиляторы не обязаны это делать . Так что нет, он не сломан, даже если компилятор не выполняет подстановку. Более того, писать ++line_count;вместо этого line_count++;не мешало бы :)
Fareanor
1
@valsaysReinstateMonica В этом конкретном примере, почему один из них предпочтительнее? Результат здесь никоим образом не используется, поэтому он будет прочитан после while, верно? Будет ли иметь значение, если произошла какая-то ошибка, и вы хотели убедиться, что она line_countбыла правильной? Я просто догадываюсь, но я не понимаю, почему это важно.
TankorSmash
14

Во втором примере (с scanf ()) причина, по которой это все еще медленнее, может заключаться в том, что scanf ("% s") анализирует строку и ищет любой символ пробела (пробел, табуляция, символ новой строки).

Кроме того, да, CPython выполняет некоторое кэширование, чтобы избежать чтения с жесткого диска.

Davinchi
источник
12

Первый элемент ответа: <iostream>медленно. Чертовски медленно. Я получаю огромный прирост производительности, как показано scanfниже, но он все еще в два раза медленнее, чем 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;
}
JN
источник
Я не видел этот пост, пока я не сделал свое третье редактирование, но еще раз спасибо за ваше предложение. Странно, но теперь у меня нет двухкратного попадания против python со строкой scanf в edit3 выше. Я пользуюсь 2.7, кстати.
JJC
10
После исправления версии c ++ эта версия stdio значительно медленнее, чем версия c ++ iostreams на моем компьютере. (3 секунды против 1 секунды)
Карунски
10

Ну, я вижу , что в вашем втором растворе вы перешли от cinк scanf, который был первым предложение , которое я собирался сделать вас (КИН sloooooooooooow). Теперь, если вы переключитесь с scanfна fgets, вы увидите еще одно повышение производительности:fgets это самая быстрая функция C ++ для строкового ввода.

Кстати, не знал об этой вещи синхронизации, хорошо. Но вы все равно должны попробовать fgets.

Хосе Эрнесто Лара Родригес
источник
2
Исключение fgetsбудет неправильным (с точки зрения количества строк и с точки зрения разделения строк по циклам, если вам действительно нужно их использовать) для достаточно больших строк, без дополнительных проверок на неполные строки (и попытка компенсировать это включает выделение излишне больших буферов где std::getlineобрабатывает перераспределение, чтобы соответствовать фактическому вводу плавно). Быстро и неправильно легко, но почти всегда стоит использовать «немного медленнее, но правильно», что отключает sync_with_stdioвас.
ShadowRanger