Численное моделирование
0,3
рейтинг
18 декабря 2014 в 22:10

Разработка → Насколько медленны iostreams?

Потоки ввода-вывода в стандартной библиотеке 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. И это чемпион!
Илья Попов @encyclopedist
карма
40,0
рейтинг 0,3
Численное моделирование
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (77)

  • +5
    Вы забыли самый быстрый стандартный способ:

    while (std::getline(f, line))
    {
        int x = std::stoi(line);
        max = std::max(x, max);
    }
    
    • +1
      Спасибо за напоминание! Я в своё время рассматривал этот вариант, но не применил, потому что версия компилятора в университете была слишком старой. Сейчас обновлю пост.
  • +1
    Я бы с удовольствием посмотрел сравнение std::ostringstream с snprintf для форматирования строк.
    • +1
      А не отпугивает от потоков, кхм, некоторая многословность?
      printf("%.2f\n", count * 100.0 / total);
      vs
      std::cout << std::setprecision(2) << std::fixed << count * 100.0 / total << std::endl
      + во времена g++ 3.3-4.0 в ostringstream была утечка памяти — с тех пор отношусь к ним с большой подозрительностью
      • +2
        В общем-то можно убрать std:: повсюду (добавив директиву ранее). Станет чуть короче.
        Но вот со скоростью… мда…

        Мы тут как-то свой printf делали (чтоб кидать дампы в обработчиках сигнала — где нежелательно, чтобы вдруг где-то malloc() в недрах вдруг вызвался, потому что будет «ой, всё!»). Структура то элементарна — очень простой ДКА — и уже можно по крайней мере целые числа и строки выводить.
        Но вот добрались до флотов — и чтоб не городить огород попробовали самый простой метод, что на поверхности: вместо флота 1.99 — выводить целое 199, нарисовав точку после единицы (ну т.е. умножаем флот на precision, и выводим уже int, только в вывод впихиваем точку). Вот его как раз из любопытства забенчили по сравнению со стандартным printf.

        Так вот такой бенч:
        #ifdef USE_SPRINTF
        void outf ( char* out, float arg )
        {
        	sprintf ( out, "%f", arg );
        }
        const char * sName = "Using sprintf res=%s\n";
        #else
        void outf ( char* out, float arg )
        {
        	unsigned int x = arg;
        	arg -=x;
        	UItoA ( &out, x);
        	*out++='.';
        	x=arg*1000000;
        	UItoA ( &out, x);
        	*out++='\0';
        }
        const char * sName = "Using own UItoA res=%s\n";
        #endif
        
        int main(int argc, char *argv[])
        {
        	float b;
        	b=3556.2323;
        	char cout[100];
        	int i;
        	for (i=0; i<100000000; ++i)
        		outf(cout,b);
        	printf (sName,cout);
        	return 0;
        }
        

        (UItoA — это наша собственная очень простая реализация; не стал приводить. Но там в самом деле всё просто :) ).

        А результат любопытный:
        printf — 54.69c (при этом вывелось 3556.232422)
        «целое с точкой» — 1.376с (при этом вывелось 3556.232421)

        Разница — в 40 раз!
        Т.е. если вдруг нужно выводить не хитрые флоты с огромными экспонентами, а вот такие, обычные, и причём нужно выводить много и быстро — свой «велосипед» рулит!
  • +1
    крутяк, а я то думаю, почему практически во всем коде по обработке данных в нашей лабе, юзают scanf для чтения, когда есть cin!

    надо будет посмотреть как на кластере уменьшится время обработки данных (36гб .txt) если поменять всё на std::stoi
    • +1
      Не забудьте только выключить синхронизацию, если читаете из cin, иначе будет медленно. (Если читаете из файла, то отключать не нужно).
      • 0
        То есть при считывании из файла данная директива отключения синхронизации бесполезна и не даёт прироста скорости? Или же вообще вредна становится? Что произойдёт, если я всё же включу её перед считыванием данных из файла?
        • 0
          Синхронизация включена по умолчанию только на стандартных потоках: cin, cerr, cout, clog. На обычных файлах синхронизация и так должна быть выключена.
        • +3
          Что произойдёт, если я всё же включу её перед считыванием данных из файла?
          Простите — но с чем именно вы собрались синхронизировать файловый поток? Для синхронизации требуется два объекта. cin синхронизирован с stdin, cout — с stdout, а с чем будет синхронизирован созданный вами объект?
          • 0
            Не знаю :)
            Я только начинаю изучать плюсы и то, пока в рамках учебного курса в ВУЗе, поэтому многого ещё не понимаю. Но, будучи по натуре адовым перфекционистом, стараюсь искать все способы максимальной оптимизации.
  • +3
    Так а где же бенчмарк способа «читать данные большими кусками и дальше работать в памяти»?
    • –1
      походу, это std::istringstream + время на считывание
    • +3
      Готово! Номер 8, новый чемпион.
      • 0
        А как насчёт аналогичной замены getchar_unlocked() в Си на свою реализацию :)?
        • 0
          Что-нибудь вроде такого (я особо не оптимизировал, сорри):

          #include <stdio.h>
          
          long read_batched(long *out)
          {
              char buf[20];
              long c, x = 0, neg = 0;
              char *res = fgets(buf, sizeof(buf), stdin);
              if (res == NULL) return 0;
          
              while ((c = *(res++)) != 0) {
                  if ('0' <= c && c <= '9') {
                      x = x*10 + c - '0';
                  } else if (c == '-') {
                      neg = 1;
                  } else {
                      break;
                  }
              }
          
              *out = neg ? -x : x;
              return 1;
          }
          
          int main()
          {
              long x;
              long max = -1;
          
              while (read_batched(&x)) {
          	    if (x > max) max = x;
              }
              printf("%ld\n", max);
              return 0;
          }
          
          • 0
            Или, лучше, вот такого:

            #include <stdio.h>
            #include <unistd.h>
            
            int main()
            {
                long max = -1;
                char buf[655360];
                long c, x = 0, neg = 0, n, i;
            
                while ((n = read(0, buf, sizeof(buf))) > 0) {
                    for (i = 0; i < n; i++) {
                        c = buf[i];
                        if ('0' <= c && c <= '9') {
                            x = (x<<1) + (x<<3) + c - '0';
                        } else if (c == '-') {
                            neg = 1;
                        } else { // newline
                            if (x > max) max = x;
                            x = 0;
                            neg = 0;
                        }
                    }
                }
            
                printf("%ld\n", max);
                return 0;
            }
            
            • +4
              Ваш код — хороший пример того, что некоторые «классические» ручные оптимизации устарели, и только мешают компиляторам.

              В вашем коде строка
              x = (x<<1) + (x<<3) + c - '0';
              

              компилируется в 3 инструкции lea:
              	leaq	0(,%rbx,8), %rcx
              	leaq	(%rcx,%rbx,2), %rcx
              	leaq	-48(%rax,%rcx), %rbx
              

              тогда как более наивное
              x = x*10 + c - '0';
              

              всего в 2 таких же инструкции
              	leaq	(%rbx,%rbx,4), %rcx
              	leaq	-48(%rax,%rcx,2), %rbx
              

              Поиграться можно тут: gcc.godbolt.org
              (Кстати, clang выдаёт второй вариант кода в обоих случаях)
              • 0
                Оптимизацию со сдвигом я просто взял из оригинальной функции freopen, которую вы «переписали» :)
            • +2
              Производительность, как и ожидалось, самая лучшая:
              10M -> 0.16 с
              100M -> 1.80 с
              Только писать парсер чего-то более сложного — замучаться.
  • –5
    По-моему главная проблема iostreams не в скорости, а в очень спорном синтаксесе, который можно спутать с битовым сдвигом.
    • +7
      Спутать это может только тот, кто ни разу не работал с потоками. Все же обычно ввод-вывод используется как оператор (то есть результат операции никуда не сохраняется) — а битовый сдвиг используется внутри выражения.
      • –3
        Ну да, спутать конечно, врядли, я скорее про то, что это выглядит странно. Выводить и вводить данные уже определенным в языке оператором побитового сдвига. Притомерно так же, еслиб, например, у строк был переопределен оператор деления, для чего-нибудь.
        • +10
          А вас не смущает, что для строк переопределен оператор "+" — то есть математического суммирования? Думаю, что вы просто привыкли к этому и не задумываетесь. А вот в PHP, например (не к ночи будет помянут), насколько я помню, строки конкатенируются оператором "."…

          Почему выбрали '<<' и '>>'? Я в головы авторам STL не заглядывал, но думаю, идеи такие:
          Парсер C++ (в отличие от Perl, например), не дает возможности придумать какой-то свой, новый оператор. Применяется то, что есть.
          Это с одной стороны. А с другой, сами операторы побитового сдвига применяются довольно редко, в основном только в контексте суровой целочисленной арифметики, которая очень редко соседствует в коде с работой ввода-вывода. Разумеется, я тут говорю о программах серьезных, а не о студенческих лабах. Кроме того, знак '<<' прямо просится, чтобы его прочесть как «пропихнуть влево» и даже человеку, незнакомому с возможностью переопределять операторы в C++, очень легко понять, что означает cout << "Hello!".

          Что касается оператора деления для строк — а что, я бы, например, не прочь был посмотреть на split, который выглядит как stringList = "a,b,cc,ddd" / ','. Почему нет? Мы же делим строку на части, так? Отличная метафора…
          • 0
            Так дело решается наследованием и реализацией своего оператора. Если сами не хотите, могу сочинить пример)
          • +1
            Так Unix shell же, в нём запись в файл (поток) именно так и выглядит $ cmd >> file. Или это вам тоже кажется неудачным решением? Да и интуитивно это вполне понятно. Ведь оператор сдвига не просто так именно такой "<<" или ">>" воспринимается как перемещение чего-либо влево или вправо соответственно. Как уже говорилось выше, никто не считает, что "+" — неудачный оператор для конкетации строк, потому что он интуитивно понятен. Оператор >> в качестве оператора вывода тоже вполне понятен интуитивно и поэтому, как мне кажется, вполне удачен.
        • 0
          boost::filesystem весьма активно использует оператор деления для объединения путей, например.
          • +2
            << отлично подходят по приоритету (по сравнению с другими операциями которыйе могут быть в строчке) и по порядку вызова слева на право.
  • +1
    Можно было ещё читать с помощью getchar_unlocked в буфер типа char[12] (если в строке больше символов, это в int32 всё равно не влезет — игнорировать или сообщать об ошибке), а потом atoi сделать. Тогда можно не парсить цифры вручную, а скорость должна быть сравнимая с самым быстрым способом.
  • +2
    Если хотите совсем-совсем быстро, то когда-то давно уже проводили и обсуждали большие сравнения: (раз, два) как для ввода, так и для вывода, рекомендую!
    • 0
      Спасибо за ссылки! А набор способов у меня почти тот же самый.
  • +8
    Ещё нужно помнить про локали. У сишной и плюсовой частей они рулятся независимо, но об этом часто забывают.
    Например, выводим через cout. А читаем через sscanf.
    В рантайме плюсовая библиотека при запуске выставит локаль в системную. А сишная часть останется в C.
    И банальный код, который запишет в файл float-значение через cout, а потом попытается прочитать его через sscanf окажется зависимым от системной локали! (например, запишется число с разделителем-запятой. А при чтении будет ожидаться точка -> ошибка!)
    • 0
      Действительно интересно — а влияет ли выбранная локаль?
      std::locale loc(std::locale("C"));
      std::cin.imbue(loc);
      

      Правда следует иметь ввиду, что копирование локали почему-то довольно медленная операция.
  • –6
    Интересно было бы с node.js сравнить, например.
    • 0
      Сравните! Я вот, например, взял и померил для Java (ради интереса). Использовал самый тупой способ — класс Scanner, который является некоторым аналогом потока ввода из iostream. Получилась вот такая прога:
      package readnum;
      
      import java.util.Scanner;
      
      public class ReadNum {
      	public static void main(String[] args) {
      		
      		Scanner sc = new Scanner(System.in);
      		int max = 0;
      		while (sc.hasNextInt()) {
      			int next = sc.nextInt();
      			if (next > max) {
      				max = next;
      			}
      		}
      		System.out.println("Max: " + max);
      	}
      }
      


      И вот вывод ее:
      $ time java -cp bin readnum.ReadNum < data
      Max: 999999
      
      real    0m2.173s
      user    0m0.031s
      sys     0m0.015s
      


      Две с хвостиком секунды. Вполне достойно, как мне кажется. То есть с getchar не сравнить, но с iostream вполне конкурирует…
      • +1
        Сколько у вас было значений на входе? (в посте — 10 миллионов)
        • 0
          Это потому, что я — дурень и читал целые числа. А они закончились на 1 миллионе (который в файле отображен как 1e+6)

          Так что беру свои слова назад. У меня — кошмар по производительности:

          package readnum;
          
          import java.util.Scanner;
          
          public class ReadNum {
          	public static void main(String[] args) {
          		
          		Scanner sc = new Scanner(System.in);
          		double max = 0;
          		while (sc.hasNextDouble()) {
          			double next = sc.nextDouble();
          			if (next > max) {
          				max = next;
          			}
          		}
          		sc.close();
          		System.out.println("Max: " + max);
          	}
          }
          


          $ time java -cp bin readnum.ReadNum < data
          Max: 1.0E7
          
          real    1m2.414s
          user    0m0.015s
          sys     0m0.031s
          


          Чтобы спасти положение, добавляем буфферизацию:

          package readnum;
          
          import java.io.BufferedReader;
          import java.io.InputStreamReader;
          import java.util.Scanner;
          
          public class ReadNum {
          	public static void main(String[] args) {
          		
          		Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
          		double max = 0;
          		while (sc.hasNextDouble()) {
          			double next = sc.nextDouble();
          			if (next > max) {
          				max = next;
          			}
          		}
          		sc.close();
          		System.out.println("Max: " + max);
          	}
          }
          


          получаем копеечный прирост:
          $ time java -cp bin readnum.ReadNum < data
          Max: 1.0E7
          
          real    1m1.802s
          user    0m0.015s
          sys     0m0.015s
          


          из чего делаем вывод — тормозит Scanner. Избавляемся от него:

          package readnum;
          
          import java.io.BufferedReader;
          import java.io.IOException;
          import java.io.InputStreamReader;
          
          public class ReadNum {
          	public static void main(String[] args) throws IOException {
          		
          		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          		double max = 0;
          		String line;
          		while ((line = br.readLine()) != null) {
          			double next = Double.parseDouble(line);
          			if (next > max) {
          				max = next;
          			}
          		}
          		br.close();
          		System.out.println("Max: " + max);
          	}
          }
          


          И получаем отличный результат:
          $ time java -cp bin readnum.ReadNum < data
          Max: 1.0E7
          
          real    0m2.222s
          user    0m0.000s
          sys     0m0.047s
          


          То есть те же 2 секунды, что и для iostream. Из чего делаем простой вывод: Java быстро читает и достойно парсит double. Но Scanner никуда не годится. Тормозит жутко. Если мне надо будет прочитать гигабайт чисел из потока ввода, воспользуюст вашим кодом с getchar и JNI. Слава богу, в реальности таких задач немного :)
      • 0
        Раз пошла такая пьянка, на моей машине быстрый cin из третьего варианта с 10 миллионами отрабатывает за 1.2 секунды, следующая строчка на Haskell — за 4.8:
        import qualified Data.Text as T
        import qualified Data.Text.IO as TI
        import qualified Data.Text.Read as TR
        
        main = TI.interact (T.pack . show . maximum . map (fst . either error id . TR.decimal) . T.lines)
        
        • +1
          cin из третьего варианта с 100 миллионами справился за 11.97 секунды, а следующая строчка на Haskell — за 6.87. Вот так вот.

          import qualified Data.ByteString.Lazy.Char8 as B
          import Data.Maybe
          import Data.List
          
          main = B.interact $ B.pack . show . foldl' max 0 . map (fst . fromJust . B.readInt) . B.lines
          
          • +1
            Спасибо. Не попробовал с ByteString, а зря, тут он куда более к месту, как вы и показали.
            • +1
              Data.Text работает с Unicode, что является непозволительной роскошью в данном случае. И вообще я удивлен, как оно вложилось в такое приличное время и не выжрало половину памяти с ленивым maximum.

              Кстати, вариант с ByteString также обогнал 7 (getline + stoi) и 6a (getchar).
  • +1
    А мне кажется, что не совсем корректно приводить сравнение на максимальной оптимизации компилятора -O3. Всё же по умолчанию у gcc используется оптимизация -O2 — как более безопасная.
    • 0
      У GCC в -O3 нет ничего «небезопасного». Это какой-то старый миф (возможно, в каких-то старых версиях было по-другому).
      -O3
      Optimize yet more. -O3 turns on all optimizations specified by -O2 and also turns on the -finline-functions, -funswitch-loops, -fpredictive-commoning, -fgcse-after-reload, -ftree-loop-vectorize, -ftree-loop-distribute-patterns, -ftree-slp-vectorize, -fvect-cost-model, -ftree-partial-pre and -fipa-cp-clone options.

      Другое дело, что, теоретически, оптимизации из O3 могут приводить в раздуванию кода или падению производительности, хотя я на практике такого не наблюдал.
      Я сам всегда использую -O3.
      • 0
        К сожалению это не миф, так как ошибок неправильной работы программы на -O3 было значительное количество по сравнению с -O2…
        Я лишь хотел сказать, что немного не верно сравнивать время и возможности работы ввода и вывода, когда компилятор ради увеличения времени компиляции сокращает и упрощает код, тем самым меняя изначальный контекст самого сравнения.
        • +6
          Скорее всего, ошибки таки в самой программе, а не в оптимизациях компилятора.
          • +1
            Компилятор — такая же программа, написанная программистами, допускающими ошибки.
            Поверьте, не всегда правильно работают даже компиляторы.
            как пример
            • +6
              Никто не отрицает. Но случаев когда в неправильной работе программы после оптимизации действительно виноват компилятор — единицы, против целого моря кривого кода кишащего UB.
          • 0
            Скорее всего, там ошибки в оптимизациях программы, а не в оптимизациях компилятора.
  • 0
    Очень занимательная статья, спасибо.

    Вопрос к измерениям: времена получены на единичном запуске или это среднее по какому-то значению?
    • 0
      * по количеству запусков, конечно.
    • 0
      Я усреднял по 3-5 запускам. Но поскольку не ставилось задачи измерить точно, а только качественно сравнить, я не заморачивался с процедурой измерения.
      • 0
        Не подскажете, какой разброс был для коротких времен?
        • +1
          Для getchar_unlocked (первое измерение опущено):
          0.271
          0.276
          0.278
          0.272
          0.282
          То есть разброс около 0.01 с (поэтому времена приведены с 2 знаками).
  • +1
    iostreams — это не часть STL, это часть стандартной библиотеки.
    • +1
      Согласен, спасибо. Сейчас исправлю.
  • 0
    А с чем связана такая низкая производительность с clang?
    • 0
      В основном виновата libc++. С чем это связано, не знаю, возможно libc++ оптимизирован в основном для MacOS, а оптимизации на Linux + GNU внимание не уделялось. При использовании libstdc++ производительность получается почти как у GCC (но все равно ниже).
  • 0
    А если попробовать mmap? Мне кажется это должно быть быстрее всего.
    • 0
      Только если у вас не btrfs.
  • 0
    Одна фишка из построчного чтения (если нужна скорость, нет boost'a), и олимпиадная задача (по большому счёту, забить на безопасность):
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(void) {
        int x;
        int max = -1;
        char my_string[256];
        
        while (gets(my_string)) {
            x = atoi(my_string);
        	max = (max < x) ? x : max;
        }
        printf("%d\n", max);
        return 0;
    }
    

    #include <iostream>
    
    int main(void)
    {
    	std::ios::sync_with_stdio(false);
        int max = -1;
        std::string line;
        while (std::getline(std::cin, line))
        {
            int x = std::stoi(line);
            max = std::max(x, max);
        }
    	std::cout << max << '\n';
        return 0;
    }
    

    g++ -O3 -Wall -Wextra -std=c++11 main.cpp -o maincpp
    gcc -O3 -Wall -Wextra main.c -o mainc
    time ./maincpp < data
    10000000
    
    real	0m0.987s
    user	0m0.960s
    sys	0m0.028s
    
    time ./mainc < data 
    10000000
    
    real	0m0.716s
    user	0m0.701s
    sys	0m0.016s
    

    Печально то, что GCC в Ubuntu 14.04 ругается на gets_s(), даже с включённым флагом -std=c11
    Кроме того, GCC таки выдаёт ошибку:
    main.c: In function ‘main’:
    main.c:9:5: warning: ‘gets’ is deprecated (declared at /usr/include/x86_64-linux-gnu/bits/stdio2.h:233) [-Wdeprecated-declarations]
         while (gets(my_string)) {
         ^
    /tmp/ccPqtomN.o: In function `main':
    main.c:(.text.startup+0x45): warning: the `gets' function is dangerous and should not be used.
    
    • 0
      gcc -std=c11 -O3 main.c
      main.c: In function ‘main’:
      main.c:9:5: warning: implicit declaration of function ‘gets_s’ [-Wimplicit-function-declaration]
           while (gets_s(my_string, 256)) {
           ^
      /tmp/ccfjPrOZ.o: In function `main':
      main.c:(.text.startup+0x47): undefined reference to `gets_s'
      collect2: error: ld returned 1 exit status
      

      И, ох, как некрасиво я отформатировал файл C++, прошу прощения.
      • 0
        Забавно, что лично у меня на моем процессоре быстрее всего работает такая программа (файл test.c):

        #include <stdio.h>
        #include <unistd.h>
        
        int main()
        {
            long max = -1;
            char buf[655361], *bufp;
            long c, x = 0, n;
        
            while ((n = read(0, buf, sizeof(buf) - 1)) > 0) {
                buf[n] = 0;
                bufp = buf;
                while ((c = *(bufp++)) != 0) {
                    c -= '0';
                    if (c >= 0 && c <= 9) {
                        x = x*10 + c;
                    } else if (c == '\n' - '0') {
                        if (x > max) max = x;
                        x = 0;
                    }
                }
            }
        
            printf("%ld\n", max);
            return 0;
        }
        


        Если посмотреть на времена, то получается вот что:

        $ clang -o merhalak -O3 merhalak.c
        $ time ./merhalak <ololo.txt
        warning: this program uses gets(), which is unsafe.
        683641836811
        
        real	0m1.166s
        user	0m1.123s
        sys	0m0.037s
        $ clang -o test -O3 test.c
        $ time ./test <ololo.txt
        683641836811
        
        real	0m0.145s
        user	0m0.118s
        sys	0m0.025s
        


        Если компилировать с помощью gcc 4.9, то ваша программа становится чуточку быстрее, а моя — чуточку медленее:

        $ gcc-4.9 -o merhalak -O3 merhalak.c && time ./merhalak <ololo.txt 
        warning: this program uses gets(), which is unsafe.
        683641836811
        
        real	0m1.140s
        user	0m1.104s
        sys	0m0.033s
        
        $ gcc-4.9 -o test -O3 test.c && time ./test <ololo.txt 
        683641836811
        
        real	0m0.166s
        user	0m0.140s
        sys	0m0.024s
        
        • 0
          Да, использовать read я не догадался.
          Не подскажете, как поправить проблему с gets_s()? У меня система ругается на не найденное определение функции. Кроме того, если запускаю, например файл, в котором есть <threads.h> и компилирую с -std=c11, он ругается на не найденный заголовок. Есть ли вообще поддержка c11 в gcc/clang?
          • 0
            Используйте fgets вместо get_s ;).
            Про c++ и про c++11 в частности я ничего не знаю :). В любом случае, в clang поддержка C++ не очень хорошая
            • 0
              Я говорю про 11-ый стандарт Си, не плюсов. В частности, в википедии сказано, что
              Функция gets, признанная устаревшей в текущей ревизии стандарта языка Си (ISO/IEC 9899:1999/Cor.3:2007(E)), была заменена новой безопасной альтернативой gets_s
              Но ничего из этого я не нашёл.
              • 0
                В стандарте безопасные функции (с окончанием _s ) описаны в приложении K как optional.
                Так что википедия в данном случае неточна.
            • –3
              В clang поддержка C++ как раз считается одной из самых лучших. А с неподдержкой чего столкнулись вы столкнулись?
              • 0
                Я, к счастью, не пишу на C++, поэтому не сталкивался с тем, что в clang что-то не поддерживается. Но мое утверждение было основано на том, что поскольку clang спонсировался долгое время компанией Apple, то в первую очередь в clang развивалась поддержка C и Objective C, и во вторую очередь C++. Сейчас, возможно, ситуация меняется, но очень долгое время поддержка C++ в clang была не в приоритете.
          • 0
            threads.h в стандарте объявлен необязательным.

            The headers <complex.h>, <stdatomic.h>, and <threads.h> are conditional features that implementations need not support; see 6.10.8.3.

          • 0
            Новые версии gcc и clang на Linux x86 поддерживают <threads.h> (ох уж этот хабрапарсер), хотя, вообще говоря, не обязательны для поддержки согласно стандарту. По очевидным причинам — в некоторых ОС потоков просто нет ) Так что уточните, пожалуйста платформу и ось
            • 0
              Ubuntu 14.04 x86_64, gcc 4.8.2
              • 0
                О, извините за невольное введение в заблуждение. Был невнимательным и подумал что речь идёт о C++. GCC до сих пор не поддерживает threading из c11, да и вообще много чего оттуда не поддерживает. Судя по всему, проблема не с компилятором а с библиотекой.
                • 0
                  Кажется, что из одного заблуждения вывели, а в другое ввели. «много чего» это threading, analyzability и bounds-checking? В шапке ведь написано, что поддержка C11 практически полностью обеспечена с парой примечаний. А библиотека, то библиотека, со стороны компилятора всё необходимое реализовано.
  • 0
    результаты на linux mint 17.2,
    clang 3.5.0-4, x84_64. $ seq 1000000 | time testN
    Скрытый текст
    scanf
    10000000
    1.35user 0.06system 0:01.52elapsed 92%CPU (0avgtext+0avgdata 2724maxresident)k
    0inputs+0outputs (0major+116minor)pagefaults 0swaps
    iostream + nosync
    10000000
    1.47user 0.04system 0:01.59elapsed 95%CPU (0avgtext+0avgdata 2620maxresident)k
    0inputs+0outputs (0major+119minor)pagefaults 0swaps
    iostream
    10000000
    4.27user 0.07system 0:04.40elapsed 98%CPU (0avgtext+0avgdata 2600maxresident)k
    0inputs+0outputs (0major+112minor)pagefaults 0swaps
    iostream + ss + nosync
    10000000
    6.73user 0.06system 0:06.86elapsed 99%CPU (0avgtext+0avgdata 2624maxresident)k
    0inputs+0outputs (0major+119minor)pagefaults 0swaps
    iostream + ss
    10000000
    11.05user 0.13system 0:11.33elapsed 98%CPU (0avgtext+0avgdata 2572maxresident)k
    0inputs+0outputs (0major+112minor)pagefaults 0swaps
    iostream + ss2 + nosync
    10000000
    2.42user 0.03system 0:02.49elapsed 98%CPU (0avgtext+0avgdata 2620maxresident)k
    0inputs+0outputs (0major+117minor)pagefaults 0swaps
    iostream + ss2
    10000000
    5.51user 0.08system 0:05.62elapsed 99%CPU (0avgtext+0avgdata 2572maxresident)k
    0inputs+0outputs (0major+110minor)pagefaults 0swaps
    getchar + nosync
    10000000
    1.05user 0.09system 0:01.18elapsed 96%CPU (0avgtext+0avgdata 2592maxresident)k
    0inputs+0outputs (0major+117minor)pagefaults 0swaps
    getchar
    10000000
    1.09user 0.06system 0:01.23elapsed 93%CPU (0avgtext+0avgdata 2536maxresident)k
    0inputs+0outputs (0major+111minor)pagefaults 0swaps
    getchar unl + nosync
    10000000
    0.64user 0.08system 0:00.74elapsed 98%CPU (0avgtext+0avgdata 2588maxresident)k
    0inputs+0outputs (0major+114minor)pagefaults 0swaps
    getchar unl
    10000000
    0.70user 0.06system 0:00.87elapsed 87%CPU (0avgtext+0avgdata 2536maxresident)k
    0inputs+0outputs (0major+111minor)pagefaults 0swaps


    вариант stoi не скомпилился
    iostreams_performance.cpp:146:22: error: no member named 'stoi' in namespace 'std'
            int x = std::stoi(line);
    

    а мне было лень исправлять

    g++ 4.8.2
    Скрытый текст
    scanf
    10000000
    1.35user 0.06system 0:01.48elapsed 95%CPU (0avgtext+0avgdata 2664maxresident)k
    168inputs+0outputs (1major+112minor)pagefaults 0swaps
    iostream + nosync
    10000000
    1.47user 0.05system 0:01.58elapsed 96%CPU (0avgtext+0avgdata 2636maxresident)k
    0inputs+0outputs (0major+122minor)pagefaults 0swaps
    iostream
    10000000
    4.30user 0.07system 0:04.41elapsed 99%CPU (0avgtext+0avgdata 2540maxresident)k
    0inputs+0outputs (0major+113minor)pagefaults 0swaps
    iostream + ss + nosync
    10000000
    6.89user 0.07system 0:07.03elapsed 98%CPU (0avgtext+0avgdata 2564maxresident)k
    0inputs+0outputs (0major+119minor)pagefaults 0swaps
    iostream + ss
    10000000
    10.72user 0.09system 0:10.89elapsed 99%CPU (0avgtext+0avgdata 2544maxresident)k
    0inputs+0outputs (0major+113minor)pagefaults 0swaps
    iostream + ss2 + nosync
    10000000
    2.21user 0.04system 0:02.30elapsed 97%CPU (0avgtext+0avgdata 2636maxresident)k
    0inputs+0outputs (0major+120minor)pagefaults 0swaps
    iostream + ss2
    10000000
    5.37user 0.08system 0:05.50elapsed 99%CPU (0avgtext+0avgdata 2616maxresident)k
    0inputs+0outputs (0major+115minor)pagefaults 0swaps
    getchar + nosync
    10000000
    1.00user 0.06system 0:01.18elapsed 90%CPU (0avgtext+0avgdata 2640maxresident)k
    0inputs+0outputs (0major+122minor)pagefaults 0swaps
    getchar
    10000000
    0.94user 0.10system 0:01.15elapsed 90%CPU (0avgtext+0avgdata 2608maxresident)k
    0inputs+0outputs (0major+113minor)pagefaults 0swaps
    getchar unl + nosync
    10000000
    0.58user 0.08system 0:00.78elapsed 85%CPU (0avgtext+0avgdata 2636maxresident)k
    0inputs+0outputs (0major+120minor)pagefaults 0swaps
    getchar unl
    10000000
    0.58user 0.03system 0:00.64elapsed 97%CPU (0avgtext+0avgdata 2472maxresident)k
    0inputs+0outputs (0major+109minor)pagefaults 0swaps
    stoi + nosync
    10000000
    1.14user 0.02system 0:01.25elapsed 93%CPU (0avgtext+0avgdata 2636maxresident)k
    0inputs+0outputs (0major+122minor)pagefaults 0swaps
    stoi
    10000000
    4.09user 0.05system 0:04.25elapsed 97%CPU (0avgtext+0avgdata 2544maxresident)k
    0inputs+0outputs (0major+113minor)pagefaults 0swaps

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.