Это перевод статьи за авторством nor, на авторские права не претендую.

Введение

Какое то время назад автор статьи и ToxicPie9 сделали и запостили мем:

На удивление, достаточно много людей не до конца поняли его: в сообществе до сих пор много заблуждений насчет прагм. Большинство пользователей C++ на Codeforces пишут в начале каждой посылки прагмы, но, как мне кажется, мало кто полностью понимают, как именно работают прагмы; люди просто верят, что после добавления прагм код будет работать не хуже и успокаиваются на этом. На самом деле, прагмы — что-то из разряда черной магии и их используют как правильно, так и неправильно в соревновательном сообществе. Большинство спортивных программистов примерно понимают, что прагмы могут серьезно ускорить код, но иногда наоборот замедляют его или даже приводят к UB на определенных платформах. Дальше в статье будет рассказано, что именно происходит после того, как в коде обнаруживаются строки #pragma GCC optimize и #pragma GCC target, и как их стоит и не стоит использовать.

В дальнейшем будут обсуждаться только оптимизации на GCC компиляторах; на остальных платформах и компиляторах эти же оптимизации могут не работать. Можно считать, что большинство из таких оптимизаций работают на Codeforces и других не слишком старых x86 платформах.

Примеры неправильного использования

Следующие строки ничего не меняют в исполнении программы.

#pragma GCC optimize(" unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)

Это реальные ошибки, которые можно заметить даже у некоторых красно-черных пользователей Codeforces; возможно, этот блог породил сколько-то ошибок, потому что именно он, по видимости, популяризовал идею использования прагм, но в тексте блога были небольшие неточности. Многие люди ошибочно думают, что какие-то из вышеперечисленных примеров работают, но это неправда...)

Важно заметить, что нет смысла писать прагмы в середине кода, потому что тогда часть кода не будет ускорена — лучше всего писать прагмы в самом начале файла (прим: в новых версиях g++ pragma target не работает, если ее написать перед подключением некоторых заголовков из STL, об этом можно почитать здесь)

Чтобы проверить, что прагмы праивльно обработаны компилятором, можно компилировать код с флагом -Wall (более конкретно, достаточно флага -Wunknown-pragmas). Например, если скомпилировать код сверху с -Wall, получим следующее сообщение об ошибке:

foo.cpp:2: warning: ignoring ‘#pragma gcc optimize’ [-Wunknown-pragmas]
    2 | #pragma gcc optimize("Ofast")
      | 
foo.cpp:3: warning: ignoring ‘#pragma GCC optimization’ [-Wunknown-pragmas]
    3 | #pragma GCC optimization("Ofast")
      | 
foo.cpp:4: warning: ignoring ‘#pragma optimize ’ [-Wunknown-pragmas]
    4 | #pragma optimize(Ofast)
      | 
foo.cpp:1:37: warning: bad option ‘-f unroll-loops’ to pragma ‘optimize’ [-Wpragmas]
    1 | #pragma GCC optimize(" unroll-loops")
      |                                     ^

Проверьте, если в вашем шаблоне есть похожие проблемы, если да — пора менять шаблон)

В чем смысл "#pragma GCC optimize"?

По сути, это флаг, показывающий компилятору, что можно использовать определенные низкоуровневые оптимизации. Синтаксис такой: #pragma GCC optimize (option, option2, ...)

Судя по официальной документации по GCC прагмам, такие прагмы позволяют задать глобальные флаги для оптимизации. Вот что меняют некоторые из них:

• O0, O1 : довольно безполезные уровни оптимизации для спортивного программирования, так что обсуждать их не будем
• O2: на Codeforces эта опция включена по умолчанию, так что, вероятно, эффекта от включения этой оптимизации вы не увидите
• O3: эта оптимизация иногда модет замедлить ваш код из-за раздувания его размера, но в спортивном программировании такое случается редко. Например, этот уровень оптимизации применяет такие ускорения:
• Автоматическая векторизация кода там, где архитектура компилятора это позволяет. Эта оптимизация способна сильно ускорить код с использованием SIMD (single instruction, multiple data) — более подрообное описание ниже
• Function inlining — процесс записи какой-то функции текстом в то место, где ее вызвали, вместо, грубо говоря, вызова себя по указателю (подробнее про inlining можно почитать в документации)
• Loop unrolling — примерно то же, что и function inlining, но применительно к циклам: тело цикла записывается много раз с хитрыми проверками, которые работают так же, как и обычные циклы, но используют меньше проверок (например, меньше проверок на выход за пределы цикла). O3 делает это чуть аггрессивнее, чем О2, что может привести к cache misses (непопаданию в кэш, что приводит к необходимости обращаться в более долгую память)

• Ofast: самый рискованный уровень оптимизации. Он включает в себя все оптимизации из О3 с некоторыми другими, спорными оптимизациями, которые не входят в стандарт. Например, он вводит оптимизацию fast-math, которая предполагает, что операции с числами с плавающей точкой ассоциативны, что может привести к ошибкам при работе с нецелыми числами. В общем и целом, Ofast имеет вероятность ускорить ваш код, но лучше использовать его только при полной уверенности, что вы знаете, что делает та или иная оптимизация.

Также можно использовать некоторые отдельные оптимизации, например:

• unroll-loops — применяет "развертывание циклов", как описано выше. Иногда приводит к увеличению размера кода и cache misses.
• unroll-all-loops — название говорит само за себя, применяет loop unrolling практически везде. Обычно замедляет выполнение программы.
• strict-overflow — помогает компилятору пользоваться тем фактом, что переполнение целочисленных знаковых типов — это UB. Видел когда-то забавный пример, где такая оптимизация заставляла цикл никогда не останавливаться, потому что в какой-то момент счетчик цикла обязательно должен был переполниться.
• trapv — в целом, это не оптимизация, эта прагма сильно замедляет код, но заставляет компилятор генерировать RE каждый раз, когда целочисленные знаковые типы переполняются, что делает ее полезной для отладки кода (Прим.авт.ред: лучше использовать санитайзеры вместо этого, если архитектура системы позволяет)

Полный список поддерживаемых флагов можно найти здесь.

Например, правильно будет ипсользовать прагмы так

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

или так

#pragma GCC optimize("O3,unroll-loops")

или так

#pragma GCC optimize("O3","unroll-loops")

Заметим, что параметры внутри кавычек — строки, и во втором варианте не нужно ставить пробелы до или после запятых. В последнем случае, конечно, можно ставить как угодно: на парсинг кода это не повлияет.

Что такое "#pragma GCC target"?

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

Компиляторы позволяют использовать эти инструкции для ускорения. Например, процессоры, которые поддерживают инструкцию popcnt могут выполнить функцию __builtin_popcount за всего одну процессорную инструкцию вместо log(log(C)) для простой реализации. Для векторизации кода тоже нужны инструкции, поддерживающие векторизацию. Такими, например, являются наборы инструкций sse4.2, avx, avx2. Вот список списков инструкций, которые обычно поддерживаются на Codeforces:

• avx и avx2: это списки инструкций, позволяющие использовать векторизацию по 8,16 и 32 бита (т.е. появляется возможность выполнять определенныю инструкцию сразу на битность процессора/размерность чисел числах одновременно). Лучше использовать avx2, т.к. он новее.
• sse, sse2, sse3, sse4, sse4.1, sse4.2: списки инструкций, тоже подходящие для векторизации, но новее и хуже, чем avx и avx2. Они могут быть полезны на проверяющих платформах типа Яндекс.контест, потому что там avx2 не поддерживается.

• popcnt, lzcnt — инструкции, оптимизирующие операции popcount и count leading zeros из серии __builtin_popcount и __builtin_clz.

• abm, bmi,bmi2: списки инструкций для манипуляций с битами (см. документацию по процессорным инструкциям). Поддерживают такие битовые операции, как ctz, blsi и pdep
• fma: не так часто используемый список инструкций, т.к. avx и sse уже поддерживают большинство его операций
• mmx: еще более старый, чем sse* список инструкций, потому, по большому счету, бесполезный

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

Синтаксис у pragma target такой же, как у optimize; пример:

#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

В общем и целом, есть две главных причины, по которым можно использовать #pragma GCC target:

• Удобно использовать его с #pragma optimize. Таким образом мы позволяем компилятору эффективно генерировать SIMD инструкции, которые ускоряют код в 2-8 раз..

• Использование #pragma target иногда позволяет использовать встроенные функции с++.

Например,

#include <immintrin.h> // returns the odd bits of x: 0b01010101 -> 0b1111 uint32_t odd_bits(uint32_t x) { return _pext_u32(x, 0x55555555u); }

не скомпилируется, если мы не укажем, из какого таргета брать функцию. Обычно такое можно сделать, указав при компиляции флаг -mbmi2, но на Codeforces это невозможно, поэтому можно написать #pragma GCC target("bmi2").

Например, этот код сильно полагается на SIMD инструкции, ужимая код с асимптотикой $$$n log n$$$ с большой константой при $$$n \approx 5 * 10^5$$$ в 49 мс.

Стоит понимать, что векторизация не будет работать вез включенных O3 или Ofast оптимизаций, или, более конкретно, O2 оптимизаций с включенным tree-vectorize таргетом.

Атрибуты функций

Если вам захочется включить эти оптимизации локально, можно сделать это с помощью атрибутов функций. Например, используя

__attribute__((target("avx2"), optimize("O3", "unroll-loops"))) void work() {
    // do something
}

компилятор включит эти атрибуты только для этой функции, а остальной код будет скомпилирован с голбальными параметрами оптимизации.

Бонус

#pragma GCC ivdep: эта прагма заставляет компилятор векторизовать цикл даже если он не был векторизован из-за того, что компилятор не смог доказать, что векторизация безопасна из-за зависимостей от памяти внутри цикла. Если мы можем, исходя из какой-то внешней информации, доказать что векторизация безопасна, можно смело писать эту прагму, в ином случае стоит ожидать UB при выполнении такого векторизованного цикла.

#pragma GCC push_options, #pragma GCC pop_options: эти прагмы позволяют добавлять-удалять параметры оптимизации из используемого множества оптимизаций, позволяющие временно переключится на другой набор оптимизаций. #pragma GCC reset_options сбрасывает все параметры оптимизации.

#pragma GCC optimize "Ofast" и \#pragma GCC optimize "-Ofast" тоже работают. Также работают прагмы типа \#pragma GCC optimize "-funroll-loops" и \#pragma GCC optimize "unroll-loops". С другой стороны, \#pragma GCC target "avx2" работает, а \#pragma GCC target "-mavx2" — нет.

Предостережения

Как мы уже выяснили, могут возникать некоторые подводные камни, связанные с использованием прагм, например:

• Некоторые прагмы могут замедлять выполнение кода из-за раздувания рамера кода и всего с этим связанного.
• Прагмы могут вызывать UB, если неаккуратно выбрать списки инструкций для #pragma target. Так, лучше всего на каждой платформе проверять, правильно ли работает тот или иной набор инструкций. Есть способы проверить, что платформа, на которой запускается код, поддерживает определенный набор инструкций, но на каждой отдельной платформе наборы инструкций, строго говоря, implementation-defined, потому нельзя полагаться только на то, поддерживаются инструкции или нет: они могут работать по-разному. С другой стороны, удобно запускать свой код с чем-то наподобие assert(__builtin_cpu_supports("avx2")).
• В общем случае, точную константу на низком уровне угадать невозможно, и полагаться стоит на производительность, а не на подсчет количества используемых инструкций. Это также значит, что не стоит полностью полагаться на содержимое блога и надеяться, что прагмы помогут упихать любое решение за $$$O(n^2)$$$ при $$$n \approx 10^5$$$. Неплохой способ проверить себя — посмотреть на сгенерированный ассемблерный код вашей программы на godbolt.org

Примеры

Было несколько интересных инцидентов за историю Codeforces, которые указывают, как сильно прагмы могут ускорить код, Например:

• https://mirror.codeforces.com/blog/entry/89640
• https://mirror.codeforces.com/blog/entry/66279
• https://mirror.codeforces.com/blog/entry/81467 (здесь unroll-loops на самом деле не используется)

Еще полезную информацию по этой теме можно найти в обсуждении этого комментария: https://mirror.codeforces.com/blog/entry/94609?#comment-836718

Заключение

Если вы пролистали весь блог и начали читать только с этого момента, рекомендую почитать примеры неправильного использования прагм и проверить, правильно ли вы их используете.

Нет прагм, которые было бы на 100% безопасно использовать. Не верьте, что прагмы просто магическим образом ускорят все ваши посылки. Скорее всего, понадобится провести немного тестов, чтобы понять, какие прагмы могут ускорить ваш код.

Помните, что прагмы стоит писать в самом начале кода до include-ов, чтобы все части кода были ускорены.

Когда запуск программы локализуется только на одной платформе, результаты работы прагм чуть боле предсказуемы. Точнее,

• O2, включенная на Codeforces по умолчанию, имеет огромное количество оптимизаций по сравнению с O0. Если поднять уровень оптимизации до O3 или даже Ofast, производительность кода может как вырасти, так и упасть в зависимости от вашего кода и ввода программы. Большинство тестирующих систем поддерживают функцию запуска на своих тестах, что, в целом, может помочь определить, какие прагмы использовать. Имеет смысл протестировать и другие флаги, если знаете, что они делают.
• Обычно таргеты avx и avx2 поддерживаются новыми тестирующими системами. Когда это правда, эти таргеты обычно могут помочь ускорить ваш код. Часто они работают, если ваш код легко векторизуем — написание такого кода требует определенного опыта. В любом случае, свои тесты всегда полезны (стоит проверить, что они не вызывают ошибок из-за архитектурных различий). Если avx и avx2 не поддерживаются, можно попробовать пакеты типа sse* .
• Остальные таргеты, например, popcnt и bmt обычно не сильно меняют производительность кода, с другой стороны, операции наподобие __lg, popcount и т.д. требуют эти флаги для ускорения. Это бывает важно при использовании bitset-ов или при большом количестве битовых манипуляций.

На Codeforces лично автор использует такие прагмы:

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

Если на платформе не поддерживается avx2, можно переключиться на avx или sse*.

Благодарности

Спасибо nor за написание статьи и ToxicPie9 за помощь в ее подготовке.