Насколько медленны iostreams?
Потоки ввода-вывода в стандартной библиотеке 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.Функция main int main() { std::cout << max_scanf() << std::endl; return 0; } Время работы: 1.41 c2. Наивный 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 дали почти идентичные результаты). Обязательно тестируйте производительность при применении советов! (И, в идеале, сообщайте о результатах на вашей системе в комментариях, чтобы другие могли воспользвоваться). Полный код доступен здесь.
