Насколько медленны 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. И это чемпион!
    Метки:
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 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

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