Чтобы ускорить ввод-вывод в 5 раз, нужно всего лишь...

Revision ru3, by purplesyringa, 2024-02-26 08:22:18

...воспользоваться простой советской содой:

#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // Ваш код тут
    int n;
    std::cin >> n;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        sum += x;
    }
    std::cout << sum << std::endl;
}

Это ускорит код настолько, что вам в жизни больше не придется думать о скорости ввода-вывода. Ставьте классы и подписывайтесь на мой канал!


Ага, размечтались. Это не так работает. Мы строили культуру и... У нас все еще используется <iostream>, а значит, в коде появляется виртуальное наследование и все вытекающие из этого деоптимизации. Даже если вы нашли на задворках интернета сниппет "быстрый-ввод-вывод-от-васяна", вы все равно опираетесь на блочно буфферизованный вывод. (К тому же никакая из этих библиотек и знать не знает, что такое эти ваши флоаты.) В большинстве случаев большая часть процессорного времени растрачивается на кодирование и раскодирование чисел, а не взаимодействие с файловой системой.

Можно ли лучше? ...Тупой вопрос. Поста бы не было, будь это не так. Смотрите, к чему за полмесяца привело мое СДВГ:

Aggregated benchmark results

Результаты с Linux, поэтому они выглядят адекватно.

На Винде моя библиотека по крайней мере настолько же быстрая, как на этом графике, но при этом она умудряется значительно обходить <iostream> для целых чисел и <cstdio> для чисел с плавающей точкой. Это подтверждает байку "используйте cstdio пока вам не понадобятся флоаты", которая на моей машине не воспроизводилась, потому что, внезапно, относительная производительность cstdio и iostream под Линуксом ровно противоположная. Мда. (Тем, кто любит есть гнилые яблоки: ваш <iostream> отстой из-за использования libc++. Установите GCC вместе с Linux (brew тоже отстой), перейдите на cstdio или (что еще лучше (да, я завлекаю людей в свое болото, и что вы мне сделаете?)) мой I/O.)

Дальнейшие лучи любви будут направлены в сторону Windows Min-"как это вообще можно было зарелизить"-GW:

Integer input Integer output

Производительность сравнивается с <iostream> и <cstdio>, а также с вводом Копелиовича как самым частым примером быстрого ввода-вывода среди спортивных "я не буду идти километр до магазина" программистов.

"Random length" обозначает числа, длина которых распределена равномерно, а "random value" — числа, сами значения которых равномерно выбраны среди всех допустимых значений типа. В частности, в этом случае большинство чисел будет максимальной длины. Это предсказуемое поведение в некоторых случаях ускоряет обработку.

Floating-point input Floating-point output

rng распределено равномерно. Разница между rng и e^rng такая же, как между "random value" и "random length". Единицы измерения между разными тестами, кстати, несравнимы.

String data input String data output

Тут ничего интересного. Можно покекать с того, что if (flag) std::cout << "YES"; else std::cout << "NO"; быстрее, чем std::cout << (flag ? "YES" : "NO");.

Еще у меня быстрый std::bitset есть. Вот бы он еще был кому-то нужен...

Заметьте, что по некоторой причине вывод несколько медленнее ввода. Дело в том, что руки кривые тут не у меня, а у разработчиков операционных систем, у которых запись в RAM-диск медленнее записи в пайп. В общем и целом, на интерактивных задачах скорость ввода ухудшается — поскольку входной файл нельзя mmap'ать, — а вывода увеличивается — поскольку в выходной пайп можно писать в обход обработчиков vfs. К сожалению, вывод ускоряется только если flush вывода не происходит, что к интерактивным задачам применимо очень слабо. Наверное, это больше интересно разработчикам тестирующих систем.

Дай потыкать свою поделку

Держи:

#include <iostream>

/* Скопипастите сюда blazingio */

int main() {
    // Если вы привыкли писать эти две строчки, можете их оставить, они просто ничего не будут делать.
    // std::ios_base::sync_with_stdio(false);
    // std::cin.tie(nullptr);
    // Если вы используете std::cout.tie(nullptr);, вы неправы.
    // Поддержка этого не будет добавлена.
    // Оно вам не нужно. Удалите.
    // Вы наверняка добавили в каждое из своих решений лишние 12 байт. Они заняли место на диске.
    // Диски не резиновые, их производят маленькие дети на фабриках. Вы хотите, чтобы маленьким
    // детям из-за вас пришлось больше работать? Подумайте о детях.
    // Ну и о себе тоже. Одна из картинок загружается с моего домена. Я вас по IP вычислю.

    // Изливайте душу здесь
    int n;
    std::cin >> n;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        sum += x;
    }
    std::cout << sum << std::endl;
}

А вот большая синия ссылка на библиотеку, потому что иначе вы ее пропустите:

blazingio.min.hpp

Библиотека называется blazingio потому, что я профессиональная Rust-программистка и подписала соглашение, которое заставляет меня использовать слово "blazing" хотя бы по разу в каждом проекте, даже если он не написан на Rust. Она замещает std::cin и std::cout из <iostream>, поэтому их можно продолжать использовать как раньше.

Если вы привыкли к cin/cout, просто вставьте эту библиотеку в свой шаблон. Если она начинает творить какую-то дичь или вам просто захотелось ее отключить, просто удалите ее. Никаких изменений в других местах делать не нужно. Круто! Да это ж круто!

Минусы будут?

Купил батарейки

C-- на Codeforces нет, так что минусов нет, только плюсы.

А вообще, думать о минусах как-то пессимистично с вашей стороны. нет бы спросить "а еще будет?" или погладить по головке.

Главный минус в том, что код библиотеки большой. Размер около 9 KB, что примерно в 7 раз меньше ограничения размера посылки на Codeforces. В репозитории есть человекочитаемый код этого кода и инструкция о том, как собрать ужатую версию, если вы печетесь о размере сорсов. С другой стороны, если вы не используете большой шаблон помимо blazingio, это не должно быть проблемой.

Еще один минус в том, что blazingio держит огромные буфферы в памяти, то есть использование оперативки может быть увеличено на размер входных и выходных файлов. Обычно он не превышает 20 мебибайт. В большинстве случаев это не проблема, но это может быть полезно знать. Еще в скриптах ejudge есть легаси, из-за которого на многих инстансах ejudge приходится аллоцировать под буффер вывода ровно 24 МиБ: т.е. и место зря используется, и в редких случаях может оказаться недостаточно. Ждем фиксов.

Напоследок: эта библиотека может оказаться бесполезной. Когда-то существовали задачи, которые нельзя было решить без быстрого ввода-вывода, но теперь делать такие задачи — моветон. Однако даже если быстрый ввод-вывод не является необходимым, он может дать вам фору и позволить использовать менее эффективные алгоритмы в других местах.

Как это работает?

Я продала душу дьяволу. Вопросы?

Большинство спортпрогеров, к сожалению, не умеют применять трюки из бесполезных олимпиадных задач в вещах, которые кажущится низкоуровневыми. У олпрогеров есть и другие проблемы: грустная менталка, отрицательное число друзей в реальной жизни, а еще они считают нормальными симптомы выгорания и заметают под ковер мелтдауны. Еще они меньше знакомы с внутренностями ОС и железа. Может быть, это повод научиться чему-то новому.

К сожалению, у меня особо нет времени на полноценный разбор. Вот короткий список оптимизаций:

  • mmap на входном файле (аналогично на Windows)
  • Основанная на MAP_NORESERVE аллокация буффера вывода на Linux
  • Расширяемый без условных прыжков буффер на основе PAGE_GUARD на Windows
  • Оптимизироавнные fast paths для а) чтения из обычного файла, б) чтения из пайпа при непустом буффере
  • Костыли для плохого кодгена GCC при условном вызове сисколлов в hot loop с помощью инлайн-ассемблера (пришлось залезть в код XNU для поддержки таких методов и на M1, бррр)
  • Оптимизированное загрузкой цифр в u64 пока хватает точности чтение вещественных чисел
  • "Корневая декомпозиция" (ах если бы) для экспонент флоатов
  • Оптимизированные SIMD'ом ввод строк и ввод-вывод битсетов, включая SWAR на таргетах без SIMD
  • FILE_FLAG_NO_BUFFERING, FILE_FLAG_WRITE_THROUGH для вывода в файл на Windows
  • Вывод целых чисел без деления трюком Terje Mathisen, в том числе применительно к мантиссам

Если кому-то интересно почитать про такое поподробнее, скажите об этом, возможно, напишу пост про это.

Tags быстрый ввод, ввод-вывод

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English purplesyringa 2024-02-26 21:30:30 20
ru6 Russian purplesyringa 2024-02-26 21:30:18 20
ru5 Russian purplesyringa 2024-02-26 21:27:11 12 Мелкая правка: ' трюки из бесполезных олимпиадн' -> ' трюки из олимпиадн'
en5 English purplesyringa 2024-02-26 08:32:14 21 Tiny change: 'plz :3\n\n---\n\' -> 'plz :3\n\n[cut]\n\n<!-- -->\n\n---\n\'
ru4 Russian purplesyringa 2024-02-26 08:32:01 21 Мелкая правка: 'канал!\n\n---\n\' -> 'канал!\n\n[cut]\n\n---\n\'
ru3 Russian purplesyringa 2024-02-26 08:22:18 21 Мелкая правка: 'n\n // Your code here\n int ' -> 'n\n // Ваш код тут\n int '
en4 English purplesyringa 2024-02-26 08:21:26 0 (published)
en3 English purplesyringa 2024-02-26 08:21:16 980 (saved to drafts)
ru2 Russian purplesyringa 2024-02-26 08:19:25 0 (опубликовано)
en2 English purplesyringa 2024-02-26 08:18:51 0 (published)
ru1 Russian purplesyringa 2024-02-26 08:18:32 9847 Первая редакция перевода на Русский (сохранено в черновиках)
en1 English purplesyringa 2024-02-26 08:18:03 9539 Initial revision (saved to drafts)