Потоки ввода-вывода в стандартной библиотеке C++ просты в использовании, типобезопасны, устойчивы к утечке ресурсов, и позволяют простую обработку ошибок. Однако, за ними закрепилась репутация «медленных». Этому есть несколько причин, таких как широкое использование динамической аллокации и виртуальных функций. Вообще, потоки — одна из самых древних частей STL (они начали использоваться примерно в 1988 году), и многие решения в них сейчас воспринимаются как «спорные». Тем не менее, они широко используются, особенно когда надо написать какую-то простую программу, работающую с текстовыми данными.
Вопрос производительности 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.
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 можно отнести простоту использования, типобезопасность и более легкую обработку ошибок.
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 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, и т.д. (много их).
Результаты и советы
Время работы:
| 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 операции на одном и том же потоке) - У istringstream очень медленный конструктор. Поэтому производительность можно серьёзно поднять если переиспользовать объект потока.
- Большей производительности можно добиться, используя
getchar_unlocked(или простоgetchar, если нужна потокобезопасность) и кастомный парсер. - Ещё большей производительности вероятно можно достигнуть, если читать данные большими кусками и работать затем исключительно в памяти.
Внимание! Результаты справедливы только на конкретной системе и могут сильно отличаться на других системах! В частности, я быстренько попробовал clang + libc++ и получил гораздо худшую производительность потоков (тогда как при использовании libstdc++ и clang и gcc дали почти идентичные результаты). Обязательно тестируйте производительность при применении советов! (И, в идеале, сообщайте о результатах на вашей системе в комментариях, чтобы другие могли воспользвоваться). Полный код доступен здесь.
Автор: encyclopedist
