Потоки ввода-вывода в стандартной библиотеке C++ просты в использовании, типобезопасны, устойчивы к утечке ресурсов, и позволяют простую обработку ошибок. Однако, за ними закрепилась репутация «медленных». Этому есть несколько причин, таких как широкое использование динамической аллокации и виртуальных функций. Вообще, потоки — одна из самых древних частей стандартной библиотеки (они начали использоваться примерно в 1988 году), и многие решения в них сейчас воспринимаются как «спорные». Тем не менее, они широко используются, особенно когда надо написать какую-то простую программу, работающую с текстовыми данными.
Вопрос производительности iostreams не праздный. В частности, с проблемой производительности консольного ввода-вывода можно столкнуться в системах спортивного программирования, где даже применив хороший алгоритм, можно не пройти по времени только из-за ввода-вывода. Я также встречался с этой проблемой при обработке научных данных в текстовом формате.
Сегодня в комментариях у посту возникло обсуждение о медленности iostreams. В частности, freopen пишет
а aesamson даёт такую рекомендацию
В этом посте я развею и подтвержу некоторые мифы и дам пару рекомендаций.
Все измерения в этом посте приведены для системы Ubuntu 14.10 с компилятором GCC 4.9.1, компилировалось с ключами
Запуск проводился на ноутбуке с процессором Intel Core2 Duo P8600 (2.4 ГГц).
В спортивном программировании, как и в UNIX-way, обычно входные данные подаются на входной поток. Итак, задача:
На входной поток (stdin) поступает много неотрицательных целых чисел по одному на строке. Программа должна вывести максимальное из входных чисел.
Сформируем входные данные
В файл data мы записали 10 миллионов последовательных целых чисел, общим объёмом 76 мегабайт.
Запускать программу мы будем так
Итак, приступаем.
1.
Решим задачу с использованием старого доброго scanf.
При использовании scanf важно не забыть всегда проверять возвращаемое значение — это количество реально прочитанных и заполненных аргументов (GCC с -Wall напомнит об этом). В нашем случае при успешном чтении возвращаемое значение должно равняться 1.
Время работы: 1.41 c
2. Наивный
Теперь решим задачу самым простым способом при помощи iostreams:
Время работы: 4.41 c
Ого! Потоки оказались медленнее чем scanf в 3 раза! То есть выходит, что iostream оказываются действительно никуда не годится по скорости?
3. Быстрый
На самом деле, чтобы исправить ситуацию, достаточно добавить в программу одну единственную строчку. В самом начале функции main вставим:
Что это значит?
Для того, чтобы в программе можно было смешивать iostreams и stdio, была введена эта синхронизация. По умолчанию, при работе со стандартными потоками (
Время работы: 1.33 c
Совсем другое дело! Более того, это быстрее, чем scanf! То есть, не все так плохо. К плюсам же iostreams можно отнести простоту использования, типобезопасность и более легкую обработку ошибок.
Все последующие варианты с использованием std::cin будут использовать эту оптимизацию.
4. Наивный
Помимо ввода из файла, стандартная библиотека предоставляет также классы для ввода из строки с таким же интерфейсом. Посмотрим, насколько это медленно. Будем читать из входного потока по одной строке, а затем парсить её с помощью
Время работы: 7.21 c
Очень медленно!
5. Переиспользование
Может показаться удивительным, но самое медленное в
Обратите внимание, что нужны 2 вызова — clear, чтобы сбросить флаги состояния, и str, чтобы задать новый буфер, из которого будет происходить чтение.
Время работы: 2.16 c
Это другое дело. Это ожидаемо медленнее, чем чтение напрямую из
Что делать, если производительности все равно не хватает? Использовать более низкоуровневые средства ввода-вывода и кастомный парсер. В комментариях к упомянутому топику aesamson привел пример кода, реализующего простейший парсер целых чисел (вероятно, взятый со StackOverflow). Для чтения из входного потока используется
Время работы:
Очень хороший результат! И видно, насколько велико замедление из-за блокировок ради потокобезопасности.
Но у такого подхода есть минусы — необходимо писать парсеры для всех используемых типов данных (а это уже не так просто даже для чисел с плавающей запятой), сложность обработки ошибок, потоконебезопасность в случае
7. C++11:
Спасибо Lol4t0 что напомнил в комментариях про появившиеся в C++11 функции
Время работы: 1.04 c
Это самый быстрый стандартный способ чтения целых чисел. (А для чисел с плавающей точкой есть аналогичные функции stof/stod).
Попробуем написать Самый Быстрый вариант. Будем читать входные данные большими блоками и затем парсить с помошью Boost::Spirit::Qi, который заявляется как генератор очень быстрых парсеров. Это compile-time генератор: мы описываем грамматику на С++ в нотации, приближенной к BNF, и во время компиляции с помощью магии метапрограммирования генерируется парсер.
Время работы: 0.18 c
Это рекорд!
* — Измерения на файле со 100 миллионами чисел (размер файла 848 мегабайт).
Внимание! Результаты справедливы только на конкретной системе и могут сильно отличаться на других системах! В частности, я быстренько попробовал clang + libc++ и получил гораздо худшую производительность потоков (тогда как при использовании libstdc++ и clang и gcc дали почти идентичные результаты). Обязательно тестируйте производительность при применении советов! (И, в идеале, сообщайте о результатах на вашей системе в комментариях, чтобы другие могли воспользвоваться). Полный код доступен здесь.
Update 1. По совету Lol4t0 добавлен метод номер 7.
Update 2. В таблицу добавлены времена выполнения на clang+libc++ (версия 3.5.0, выполнялось на той же системе). Видно, что производительность потоков очень плохая, да к тому же трюк с выключением синхронизации не работает. В результате stoi оказывается в 2 раза медленнее чем scanf.
Update 3. Добавлен вариант номер 8: чтение большими блоками и разбор с помощью Boost::Spirit. И это чемпион!
Вопрос производительности iostreams не праздный. В частности, с проблемой производительности консольного ввода-вывода можно столкнуться в системах спортивного программирования, где даже применив хороший алгоритм, можно не пройти по времени только из-за ввода-вывода. Я также встречался с этой проблемой при обработке научных данных в текстовом формате.
Сегодня в комментариях у посту возникло обсуждение о медленности iostreams. В частности, freopen пишет
Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)
а aesamson даёт такую рекомендацию
Можно заменить на getchar_unlocked() для *nix или getchar() для всех остальных.
getchar_unlocked > getchar > scanf > cin, где ">" означает быстрее.
В этом посте я развею и подтвержу некоторые мифы и дам пару рекомендаций.
Все измерения в этом посте приведены для системы Ubuntu 14.10 с компилятором GCC 4.9.1, компилировалось с ключами
g++ -Wall -Wextra -std=c++11 -O3
Запуск проводился на ноутбуке с процессором Intel Core2 Duo P8600 (2.4 ГГц).
Постановка задачи
В спортивном программировании, как и в UNIX-way, обычно входные данные подаются на входной поток. Итак, задача:
На входной поток (stdin) поступает много неотрицательных целых чисел по одному на строке. Программа должна вывести максимальное из входных чисел.
Сформируем входные данные
seq 10000000 > data
В файл data мы записали 10 миллионов последовательных целых чисел, общим объёмом 76 мегабайт.
Запускать программу мы будем так
time ./a.out < data
Итак, приступаем.
1. scanf
Решим задачу с использованием старого доброго scanf.
int max_scanf()
{
int x;
int max = -1;
while (scanf("%d", &x) == 1)
{
max = std::max(x, max);
}
return max;
}
При использовании scanf важно не забыть всегда проверять возвращаемое значение — это количество реально прочитанных и заполненных аргументов (GCC с -Wall напомнит об этом). В нашем случае при успешном чтении возвращаемое значение должно равняться 1.
Функция main
int main()
{
std::cout << max_scanf() << std::endl;
return 0;
}
Время работы: 1.41 c
2. Наивный std::cin
Теперь решим задачу самым простым способом при помощи iostreams:
int max_iostream(std::istream & f)
{
int x;
int max = -1;
while(f >> x)
max = std::max(x, max);
return max;
}
Время работы: 4.41 c
Ого! Потоки оказались медленнее чем scanf в 3 раза! То есть выходит, что iostream оказываются действительно никуда не годится по скорости?
3. Быстрый std::cin
На самом деле, чтобы исправить ситуацию, достаточно добавить в программу одну единственную строчку. В самом начале функции main вставим:
std::ios::sync_with_stdio(false);
Что это значит?
Для того, чтобы в программе можно было смешивать iostreams и stdio, была введена эта синхронизация. По умолчанию, при работе со стандартными потоками (
std::cin, std::cout, std::cerr
...) буфер сбрасывается после каждой операции ввода-вывода, чтобы данные не перемешивались. Если же мы предполагаем пользоваться только iostream, то мы можем отключить эту синхронизацию. Подробнее можно почитать на cppreference.Время работы: 1.33 c
Совсем другое дело! Более того, это быстрее, чем scanf! То есть, не все так плохо. К плюсам же iostreams можно отнести простоту использования, типобезопасность и более легкую обработку ошибок.
Все последующие варианты с использованием std::cin будут использовать эту оптимизацию.
4. Наивный std::istringstream
Помимо ввода из файла, стандартная библиотека предоставляет также классы для ввода из строки с таким же интерфейсом. Посмотрим, насколько это медленно. Будем читать из входного потока по одной строке, а затем парсить её с помощью
std::istringstream
:int max_iostream_iss(std::istream & f)
{
int x;
int max = -1;
std::string line;
while (std::getline(f, line))
{
std::istringstream iss(line);
if(! (iss >> x))
break;
max = std::max(x, max);
}
return max;
}
Время работы: 7.21 c
Очень медленно!
5. Переиспользование std::istringstream
Может показаться удивительным, но самое медленное в
istringstream
— это его создание. А мы создаём для каждой входной строки заново. Попробуем переиспользовать один и тот же объект:int max_iostream_iss_2(std::istream & f)
{
int x;
int max = -1;
std::string line;
std::istringstream iss(line);
while (std::getline(f, line))
{
iss.clear(); // Сбрасываем флаги ошибок
iss.str(line); // Задаём новый буфер
if(! (iss >> x))
break;
max = std::max(x, max);
}
return max;
}
Обратите внимание, что нужны 2 вызова — clear, чтобы сбросить флаги состояния, и str, чтобы задать новый буфер, из которого будет происходить чтение.
Время работы: 2.16 c
Это другое дело. Это ожидаемо медленнее, чем чтение напрямую из
std::cin
(данные проходят 2 раза через классы потоков), но не катастрофично. 6. Хотим ещё быстрее! (getchar/getchar_unlocked)
Что делать, если производительности все равно не хватает? Использовать более низкоуровневые средства ввода-вывода и кастомный парсер. В комментариях к упомянутому топику aesamson привел пример кода, реализующего простейший парсер целых чисел (вероятно, взятый со StackOverflow). Для чтения из входного потока используется
getchar_unlocked
— потоконебезопасная версия getchar
. Я добавил пропуск лишних символов и простейшую обработку конца файла:bool read_int_unlocked(int & out)
{
int c = getchar_unlocked();
int x = 0;
int neg = 0;
for (; !('0'<=c && c<='9') && c != '-'; c = getchar_unlocked())
{
if (c == EOF)
return false;
}
if (c == '-')
{
neg = 1;
c = getchar_unlocked();
}
if (c == EOF)
return false;
for (; '0' <= c && c <= '9' ; c = getchar_unlocked())
{
x = x*10 + c - '0';
}
out = neg ? -x : x;
return true;
}
int max_getchar_unlocked()
{
int x;
int max = -1;
while(read_int_unlocked(x))
max = std::max(x, max);
return max;
}
Время работы:
getchar
0.82 с, getchar_unlocked
0.28 с!Очень хороший результат! И видно, насколько велико замедление из-за блокировок ради потокобезопасности.
Но у такого подхода есть минусы — необходимо писать парсеры для всех используемых типов данных (а это уже не так просто даже для чисел с плавающей запятой), сложность обработки ошибок, потоконебезопасность в случае
getchar_unlocked
. Альтернативно — можно попробовать воспользоваться генератором парсеров, например re2c
, boost::Spirit::Qi
, и т.д. (много их).7. C++11: std::stoi
Спасибо Lol4t0 что напомнил в комментариях про появившиеся в C++11 функции
std::stoi/std::stol/std::stoll
. Будем читать по одной строке с помощью getline, а затем парсить её с помощью stol. Код будет выглядеть так:int max_stoi(std::istream & f)
{
int max = -1;
std::string line;
while (std::getline(f, line))
{
int x = std::stoi(line);
max = std::max(x, max);
}
return max;
}
Время работы: 1.04 c
Это самый быстрый стандартный способ чтения целых чисел. (А для чисел с плавающей точкой есть аналогичные функции stof/stod).
8. Бонус: Чтение большими блоками + Boost::Spirit
Попробуем написать Самый Быстрый вариант. Будем читать входные данные большими блоками и затем парсить с помошью Boost::Spirit::Qi, который заявляется как генератор очень быстрых парсеров. Это compile-time генератор: мы описываем грамматику на С++ в нотации, приближенной к BNF, и во время компиляции с помощью магии метапрограммирования генерируется парсер.
Код (внимание, boost и метапрограммирование detected!)
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/spirit/include/phoenix_statement.hpp>
template <typename Iterator>
Iterator max_parser(Iterator first, Iterator last, int& max)
{
namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phoenix = boost::phoenix;
using qi::int_;
using qi::_1;
using ascii::space;
using phoenix::ref;
using phoenix::if_;
using qi::eoi;
using qi::lexeme;
bool r = qi::phrase_parse(first, last,
// Begin grammar
(
*lexeme[int_ >> (!eoi)][if_(_1 > ref(max))[ref(max) = _1]]
)
,
// End grammar
space);
return first;
}
int max_spirit(std::istream & f)
{
size_t chunk_size = 1 << 20;
std::unique_ptr<char[]> buffer(new char[2*chunk_size]);
char * middle = buffer.get() + chunk_size;
char * begin = middle;
int max = -1;
while(true)
{
f.read(middle, chunk_size);
if (f.gcount() == 0)
break;
char * end = middle + f.gcount();
char * last = max_parser(begin, end, max);
if (last < middle)
break;
// copy the remaining data just before the middle:
begin = middle - (end - last);
std::copy(last, end, begin);
}
return max;
}
Время работы: 0.18 c
Это рекорд!
Результаты и советы
Время работы:
No | Метод | GCC 4.9.1 | clang 3.5.0 + libc++ | GCC 100M* |
---|---|---|---|---|
1 | scanf | 1.41 | 1.48 | |
2 | std::cin | 4.41 | 13.30 | |
3 | std::cin и std::ios::sync_with_stdio(false) | 1.33 | 13.24 | |
4 | std::istringstream | 7.21 | 9.16 | |
5 | std::istringstream с переиспользованием | 2.16 | 7.92 | |
6a | getchar | 0.82 | 0.84 | 9.14 |
6b | getchar_unlocked | 0.28 | 0.26 | 2.94 |
7 | std::getline + std::stoi | 1.04 | 3.53 | 10.8 |
8 | Большой блок + Boost::Spirit | 0.18 | 1.67 | 1.90 |
* — Измерения на файле со 100 миллионами чисел (размер файла 848 мегабайт).
Рекомендации:
- В C++11 самый быстрый стандартный способ чтения чисел из потока —
std::getline
+std::stol
(в сочетании сsync_with_stdio(false)
, если используются стандартный потокstd::cin
). Этот способ заметно быстрее чем scanf и уступает только способам с getchar. - Для того, чтобы ускорить
std::cin/std::cout
, можно использоватьstd::ios::sync_with_stdio(false);
При этом скорость станет сравнимой или лучше чем scanf. (Только убедитесь, что вы не смешиваете потоковые и stdio операции на одном и том же потоке) - У istringstream очень медленный конструктор. Поэтому производительность можно серьёзно поднять если переиспользовать объект потока.
- Большей производительности можно добиться, используя
getchar_unlocked
(или простоgetchar
, если нужна потокобезопасность) и кастомный парсер. - Ещё большей производительности можно достигнуть, если читать данные большими кусками и работать затем исключительно в памяти.
Внимание! Результаты справедливы только на конкретной системе и могут сильно отличаться на других системах! В частности, я быстренько попробовал clang + libc++ и получил гораздо худшую производительность потоков (тогда как при использовании libstdc++ и clang и gcc дали почти идентичные результаты). Обязательно тестируйте производительность при применении советов! (И, в идеале, сообщайте о результатах на вашей системе в комментариях, чтобы другие могли воспользвоваться). Полный код доступен здесь.
Update 1. По совету Lol4t0 добавлен метод номер 7.
Update 2. В таблицу добавлены времена выполнения на clang+libc++ (версия 3.5.0, выполнялось на той же системе). Видно, что производительность потоков очень плохая, да к тому же трюк с выключением синхронизации не работает. В результате stoi оказывается в 2 раза медленнее чем scanf.
Update 3. Добавлен вариант номер 8: чтение большими блоками и разбор с помощью Boost::Spirit. И это чемпион!