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

avatar
JJC
21 февраля 2012 в 02:17
282414
10
2028

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


(Ответ TL; DR: включите выражение: cin.sync_with_stdio(false) или просто используйте вместо него fgets.

Результаты TL; DR: прокрутите до конца моего вопроса и посмотрите на таблицу.)


Код 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-мегабайтный строковый файл на быстром диске. Вот сравнение с несколькими решениями / подходами:

Реализация строк в секунду
python (по умолчанию) 3,571,428
cin (по умолчанию / наивный) 819 672
cin (без синхронизации) 12 500 000
fgets 14 285 714
туалет (нечестное сравнение) 54 644 808
Источник
Vaughn Cato
21 февраля 2012 в 02:20
18

Вы запускали тесты несколько раз? Возможно, проблема с кешем диска.

JJC
21 февраля 2012 в 02:22
0

@VaughnCato Да, и на двух разных машинах тоже.

Vaughn Cato
21 февраля 2012 в 03:30
18

Проблема в синхронизации со stdio - см. Мой ответ.

Xeo
21 февраля 2012 в 18:29
23

Поскольку никто, кажется, не упомянул, почему вы получаете дополнительную строку с C ++: Не тестируйте против cin.eof() !! Поместите вызов getline в оператор if.

jfs
27 февраля 2012 в 00:21
23

wc -l работает быстро, потому что он читает поток более одной строки за раз (это может быть комбинация fread(stdin)/memchr('\n')). Результаты Python имеют тот же порядок величины, например wc-l.py

Ответы (10)

avatar
Vaughn Cato
21 февраля 2012 в 03:24
1818

tl; dr: из-за различных настроек по умолчанию в C ++, требующих большего количества системных вызовов.

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

Karl Knechtel
21 февраля 2012 в 03:34
166

Это должно быть наверху. Это почти наверняка верно. Ответ не может заключаться в замене чтения вызовом fscanf, потому что это попросту не так много работает, как Python. Python должен выделить память для строки, возможно, несколько раз, поскольку существующее выделение считается недостаточным - точно так же, как подход C ++ с std::string. Эта задача почти наверняка связана с вводом-выводом, и слишком много FUD обходится вокруг стоимости создания std::string объектов в C ++ или использования <iostream> самого по себе.

JJC
21 февраля 2012 в 03:45
60

Да, добавление этой строки непосредственно над моим исходным циклом while ускорило код, превзойдя даже python. Я собираюсь опубликовать результаты как окончательную редакцию. Спасибо еще раз!

John Zwinck
21 января 2015 в 01:16
64

Обратите внимание, что sync_with_stdio() является статической функцией-членом, и вызов этой функции для любого объекта потока (например, cin) включает или выключает синхронизацию для всех стандартных объектов iostream.

avatar
Bela Lubkin
2 июня 2020 в 18:52
190

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

В 'Edit 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, который затем выполняет вашу программу как подпроцесс) в качестве уже открытого файлового дескриптора. За 100% чтения файла полностью отвечает программа, которую вы пытаетесь протестировать. Это дает вам реальное представление о его характеристиках без ложных осложнений.

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

А. Вы можете "исправить" это, выбрав время только для вашей программы:

$ 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

занял бы только оставшиеся 0,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), получив эти результаты (на самом деле это «лучший из трех» результатов; после заполнения кеша, конечно) :

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

Обратите внимание, что результаты двух конвейеров утверждают, что они заняли больше процессорного времени (пользователь + системный), чем реальное время настенных часов. Это потому, что я использую встроенную команду 'time' оболочки (bash), которая учитывает конвейер; и я нахожусь на многоядерной машине, где отдельные процессы в конвейере могут использовать отдельные ядра, накапливая процессорное время быстрее, чем в реальном времени. Используя /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.

JJC
9 мая 2017 в 01:16
32

Вау, это было довольно проницательно! Хотя я знал, что cat не нужен для ввода в стандартный ввод программ и что предпочтительнее перенаправление <shell, я обычно придерживался cat из-за потока данных слева направо, который первый метод сохраняет визуально. когда я рассуждаю о трубопроводах. Я обнаружил, что разница в производительности в таких случаях незначительна. Но я очень ценю то, что ты обучил нас, Бела.

Bela Lubkin
10 мая 2017 в 21:55
13

Перенаправление извлекается из командной строки оболочки на ранней стадии, что позволяет вам выполнить одно из следующих действий, если это дает более приятный вид потока слева направо: $ < big_file time my_program $ time < big_file my_program Это должно работать в любом POSIX shell (т.е. не `csh`, и я не уверен в экзотике вроде` rc` :)

avatar
23 апреля 2014 в 14:56
25

Следующий код был для меня быстрее, чем другой код, опубликованный здесь: (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 более чем в два раза.

avatar
Stu
13 марта 2012 в 23:04
46

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

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

avatar
2mia
11 марта 2012 в 18:10
198

Просто из любопытства я посмотрел, что происходит под капотом, и использовал 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

Python

./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
avatar
Gregg
11 марта 2012 в 16:37
20

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

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

    if (!cin.eof())
        line_count++;
};
Jonathan Wakely
5 мая 2012 в 14:42
75

Действительно правильный цикл будет: while (getline(cin, input_line)) line_count++;

avatar
José Ernesto Lara Rodríguez
22 февраля 2012 в 02:33
12

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

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

avatar
karunski
21 февраля 2012 в 03:33
106

Я воспроизвел исходный результат на своем компьютере с помощью 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 секунды.

Matthieu M.
21 февраля 2012 в 07:30
121

Я бы также не стал устанавливать в стеке буфер размером 1 МБ. Это может привести к coderhelper (хотя я думаю, это хорошее место для обсуждения этого!)

SEK
14 января 2014 в 09:28
13

Матье, Mac по умолчанию использует стек процессов размером 8 МБ. Linux по умолчанию использует 4 МБ на поток, IIRC. 1 МБ - не такая уж большая проблема для программы, которая преобразует ввод с относительно небольшой глубиной стека. Что еще более важно, std :: cin уничтожит стек, если буфер выйдет за пределы области видимости.

Étienne
15 марта 2014 в 02:11
24

@SEK Размер стека Windows по умолчанию составляет 1 МБ.

avatar
davinchi
21 февраля 2012 в 03:32
16

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

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

avatar
J.N.
21 февраля 2012 в 03:17
10

Первый элемент ответа: <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;
}