Насколько медленны 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 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 дали почти идентичные результаты). Обязательно тестируйте производительность при применении советов! (И, в идеале, сообщайте о результатах на вашей системе в комментариях, чтобы другие могли воспользвоваться). Полный код доступен здесь.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Want something else to read? How about 'Grievous Censorship' By The Guardian: Israel, Gaza And The Termination Of Nafeez Ahmed's Blog