Pull to refresh

Насколько медленны iostreams?

Sport programming *C++ *C *
Потоки ввода-вывода в стандартной библиотеке C++ просты в использовании, типобезопасны, устойчивы к утечке ресурсов, и позволяют простую обработку ошибок. Однако, за ними закрепилась репутация «медленных». Этому есть несколько причин, таких как широкое использование динамической аллокации и виртуальных функций. Вообще, потоки — одна из самых древних частей стандартной библиотеки (они начали использоваться примерно в 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 можно отнести простоту использования, типобезопасность и более легкую обработку ошибок.

Все последующие варианты с использованием 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. И это чемпион!
Tags:
Hubs:
Total votes 90: ↑88 and ↓2 +86
Views 74K
Comments Comments 80