- PVSM.RU - https://www.pvsm.ru -
Потоки ввода-вывода в стандартной библиотеке C++ просты в использовании, типобезопасны, устойчивы к утечке ресурсов, и позволяют простую обработку ошибок. Однако, за ними закрепилась репутация «медленных». Этому есть несколько причин, таких как широкое использование динамической аллокации и виртуальных функций. Вообще, потоки — одна из самых древних частей STL (они начали использоваться примерно в 1988 году), и многие решения в них сейчас воспринимаются как «спорные». Тем не менее, они широко используются, особенно когда надо написать какую-то простую программу, работающую с текстовыми данными.
Вопрос производительности iostreams не праздный. В частности, с проблемой производительности консольного ввода-вывода можно столкнуться в системах спортивного программирования, где даже применив хороший алгоритм, можно не пройти по времени только из-за ввода-вывода. Я также встречался с этой проблемой при обработке научных данных в тестовом формате.
Сегодня в комментариях у посту [1] возникло обсуждение о медленности iostreams. В частности, freopen [2] пишет
Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)
а aesamson [3] даёт такую рекомендацию
Можно заменить на 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
Итак, приступаем.
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.
int main()
{
std::cout << max_scanf() << std::endl;
return 0;
}
Время работы: 1.41 c
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 оказываются действительно никуда не годится по скорости?
std::cin
На самом деле, чтобы исправить ситуацию, достаточно добавить в программу одну единственную строчку. В самом начале функции main вставим:
std::ios::sync_with_stdio(false);
Что это значит?
Для того, чтобы в программе можно было смешивать iostreams и stdio, была введена эта синхронизация. По умолчанию, при работе со стандартными потоками (std::cin, std::cout, std::cerr
...) буфер сбрасывается после каждой операции ввода-вывода, чтобы данные не перемешивались. Если же мы предполагаем пользоваться только iostream, то мы можем отключить эту синхронизацию. Подробнее можно почитать на cppreference [4].
Время работы: 1.33 c
Совсем другое дело! Более того, это быстрее, чем scanf! То есть, не все так плохо. К плюсам же iostreams можно отнести простоту использования, типобезопасность и более легкую обработку ошибок.
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
Очень медленно!
std::istringstream
Оказывается, самое медленное в istringstream
— это его создание. А мы создаём для каждой входной строки заново. Попробуем переиспользовать один и тот же объект:
int max_iostream_iss_2(std::istream & f)
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 раза через классы потоков), но не катастрофично.
Что делать, если производительности все равно не хватает? Использовать более низкоуровневые средства ввода-вывода и кастомный парсер. В комментариях к упомянутому топику aesamson [3] привел пример кода, реализующего простейший парсер целых чисел (вероятно, взятый со 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
, и т.д. (много их).
Время работы:
No | Описание | Время работы |
---|---|---|
1 | scanf | 1.41 |
2 | std::cin | 4.41 |
3 | std::cin и std::ios::sync_with_stdio(false) | 1.33 |
4 | std::istringstream | 7.21 |
5 | std::istringstream с переиспользованием | 2.16 |
6a | getchar | 0.82 |
6b | getchar_unlocked | 0.28 |
Рекомендации:
std::cin/std::cout
, можно использовать std::ios::sync_with_stdio(false);
При этом скорость станет сравнимой или лучше чем scanf. (Только убедитесь, что вы не смешиваете потоковые и stdio операции на одном и том же потоке)getchar_unlocked
(или просто getchar
, если нужна потокобезопасность) и кастомный парсер.Внимание! Результаты справедливы только на конкретной системе и могут сильно отличаться на других системах! В частности, я быстренько попробовал clang + libc++ и получил гораздо худшую производительность потоков (тогда как при использовании libstdc++ и clang и gcc дали почти идентичные результаты). Обязательно тестируйте производительность при применении советов! (И, в идеале, сообщайте о результатах на вашей системе в комментариях, чтобы другие могли воспользвоваться). Полный код доступен здесь [5].
Автор: encyclopedist
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/proizvoditel-nost/77612
Ссылки в тексте:
[1] посту: http://habrahabr.ru/post/245801
[2] freopen: http://habrahabr.ru/users/freopen/
[3] aesamson: http://habrahabr.ru/users/aesamson/
[4] cppreference: http://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio
[5] здесь: https://gist.github.com/ilyapopov/1006a5a5ccdfdde85935
[6] Источник: http://habrahabr.ru/post/246257/
Нажмите здесь для печати.