Блог пользователя purplesyringa

Автор purplesyringa, история, 3 месяца назад, перевод, По-русски

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

#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, в том числе применительно к мантиссам

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

  • Проголосовать: нравится
  • +288
  • Проголосовать: не нравится

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

One of the pictures on this page is loaded from my domain. I know your IP.

sir what the hell

besides some question probably relevant:
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    does this work for interactive tasks?

    Yeah! It automagically choses between algorithms for interactive and non-interactive tasks in runtime. You can use std::cout << std::flush or std::cout.flush() to flush stdout, or just use endl.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    IP tracking does not work for interactive tasks.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It does work, but if you don't need that support and want to disable it you can rebuild the library from source. This will give you a smaller minified code and will be potentially a bit faster.

»
3 месяца назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

The one problem with competitive programmers is they don't see how to apply the tricks they constantly use to seemingly low-level tasks. (Another problem is that most of them share the same mental conditions, and don't talk to anyone IRL, so they don't question their mental health and think their meltdowns are just a quirk.) They are also less aware of OS and hardware internals. So maybe this could be your chance to learn something new.

why are you exposing us :(

»
3 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Почему на картинке плюсы аккумуляторов 18650, а на подписи минусы батареек? Автор не шарит за матчасть?

»
3 месяца назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Getting Runtime error in 248325960 by adding it to 248326069.

Seems to be unstable with pragmas? Or in general?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Most likely, you just didn't copy the entire code. I tried to fix your code 248352372

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think Barys is right. I removed the line with sync_with_stdio and copied blazingio in and the tests passed: https://codeforces.com/contest/418/submission/248381558

    • »
      »
      »
      3 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

      Someone told me the problem was that you copied the older version of code, which for some reason stayed in GitHub caches. I updated the link.

      Additionally, I don't believe it can be unstable, because the library is covered with lots of tests and is additionally benchmarked on large data. It is tested on every target from the {x86_64, i386, aarch64} times {linux, macos, windows-mingw, windows-msvc} set, save for i386 Mac and aarch64 Windows, so every bug would be quickly noticed. See latest run.

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yep it works now. Thanks for the help, Amazing stuff!

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Ideally you should also add tests with sanitizers and other safety checks turned on — my fast IO was based on someone's fast IO and it had quite a bit of UB (memmove vs memcpy on overlapping ranges for example), and given how weird C++ object lifetimes (not the RAII thing but the lifetimes in the abstract machine model) are, and how much of SIMD is close to type punning, it is important to have such tests. In any case, formal proofs are more important than tests as primary checks for correctness, but tests are good for sanity checks and a library without tests is useless at best and dangerous in the worst case.

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Yeah, you're right. I'll add sanitizers/valgrind soon-ish. There are formal proofs for most of the non-obvious stuff in the comments, by the way.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Вывод целых чисел без деления трюком Terje Mathisen

Погуглил: всё сложно и непонятно.

Насколько вот такой колхоз на C (не C++) ущербнее по скорости?
Rev. 2
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    На моих тестах подобное всегда отрабатывало медленнее. Но, возможно, дело в разных тесткейсах было.

»
3 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

orz purplesyringa avx512 SSSE high performace optimization unroll-loops Ofast movsb intel manuals read online for free

»
3 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

А дайте какую-нибудь задачу, чтобы потестить. А то я попробовал на двух против шаблона который давно юзаю — в одной примерно одинаково отрабатывают, а в другой шаблон автора немного хуже.

»
3 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I tried comparing it with the fast IO that I use, and found that the fast IO in the blog is a bit slower. Note that a lot of the low-level code is taken from Nyaan's template, but I had to do some fixes for UB and did other optimizations and made it a drop-in replacement for std::cin, std::cout (but there might be some minor loose ends that I didn't bother fixing because I don't use them anyway — like reading into char* etc).

I wonder if it is possible to combine the ideas in both (for example, there is no manual SIMD in my fast IO, which can probably be done if the compiler's autovectorization is not optimal) to make an even faster template. On the other hand, great work around the QoL side of things — I really liked the std::bitset and std::cerr handling.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah, I know damn well what went wrong here. Fuck GCC and its stupid codegen. I'm working on a fix.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I think the main reason the fast IO you use is faster is because it uses a 40 KiB table to resolve a number up to 10000 to four decimal digits in $$$\mathcal{O}(1)$$$. This is a fine tradeoff for this particular task, but generally speaking, in realistic problems cache locality will be an important problem, so trashing 40 KiB of cache in a general-purpose I/O library is a bad idea. In contrast, blazingio uses a 200-byte table to resolve just two decimal digits. This decreases performance somewhat, but looks like a more reasonable choice to me, especially given that other optimizations somewhat offset the loss in efficiency.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Have you considered taking 3 digits at a time instead? It will make the cache locality hit negligible (and even 40KiB is usually fine considering most of the input is taken in the beginning of the program for most problems).

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The overhead is from writing the data. And I think

        // Read input
        for (int i = 0; i < q; i++) {
            // Handle query
            // Write output for query
        }
        

        is a rather common idiom. And you don't want to trash your L1 cache in such a loop.

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          I've never seen a slowdown due to cache misses in my IO template from my experience, though, even in problems with queries. Can you point out concrete problems where this is a real issue? And if it's a problem, reducing it to 3 digits at a time instead of 4 will keep it faster than just 2 digits at a time. Even if you're going to the L2 cache in the beginning of the loop due to IO at the end of the previous loop, unless a difference of 4 cycles matters (usually queries are at least 10s of cycles), practically the difference would be negligible. And the best way to fix that is to store your outputs in a buffer and do the conversion from ints to bytes in a vectorizable manner in the end.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    As for the third link, I'm somewhat afraid of using AVX512 as it is unavailable or even disabled on quite a few CPUs still in use, including (IIRC) Codeforces. I believe making do with AVX2 would be hard, efficiency-wise. So while the avenue is certainly worth pursuing, it's unfortunately out of scope for me.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

И без баттлов года)

»
3 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

ok but i perfer std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Polayadi Mwoneee

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice one. I will surely add this to my initial code.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как скачать ее можно чтобы импортнуть себе?