Какой уровень оптимизации (g ++) вы используете при сравнении двух разных алгоритмов, написанных на C ++?

Question

У меня есть два алгоритма, написанные на C ++. Насколько я знаю, это нормально для компиляции с
-O0 -NDEBUG (g ++) при сравнении производительности двух алгоритмов (бессимптомно они одинаковы). Но я думаю, что уровень оптимизации несправедлив по отношению к одному из них, потому что он использует STL в каждом случае. Программа, использующая обычный массив, превосходит алгоритм STL-Heavy в 5 раз быстрее, в то время как она компилируется с опциями -O0. Но разница в производительности не сильно отличается, когда я компилирую их с -O2 -NDEBUG.

Есть ли какой-нибудь способ получить лучшее от STL (я получаю сильный удар по производительности в операторе vector []) на уровне оптимизации -O0?

Какой уровень оптимизации (и, возможно, такие переменные, как -NDEBUG) вы используете при сравнении двух алгоритмов?

Также будет очень полезно, если кто-то может дать некоторое представление о тенденции в академических исследованиях по сравнению производительности алгоритмов, написанных на C ++?

EDIT:

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

Я изменил одну из функций с необработанными указателями (int и boolean) на std :: vector и std :: vector ... С -O0 -NDEBUG производительность составляет 5,46 с (необработанный указатель) и 11,1 с (стандартное указание) ::вектор). А с -O2 -NDEBUG производительность составляет 2,02 с (необработанный указатель) и 2,21 с (std :: vector). Тот же алгоритм, одна реализация использует 4/5 динамических массивов int и boolean. А другой использует вместо этого std :: vector и std :: vector. Они одинаковы в любом другом случае

Вы можете видеть, что в -O0 std :: vector превосходит в два раза быстрее указатели. Хотя в -O2 они практически одинаковы.

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

Есть ли какие-то опции компилятора, которые мне не хватает?

Answer 1

Это зависит от того, что вы хотите оптимизировать.

Скорость

Я предлагаю использовать -O2 -NDEBUG -ftree-vectorize, и если ваш код специально предназначен для работы на x86 или x86_64, добавьте -msse2. Это даст вам общее представление о том, как он будет работать с GIMPLE.

размер

Я считаю, что вы должны использовать -Os -fno-rtti -fno-exceptions -fomit-frame-pointer. Это сведет к минимуму размер исполняемого файла до некоторой степени (при условии C ++).

---

В обоих случаях скорость алгоритма не зависит от компилятора, но компилятор может радикально изменить поведение кода, если он может «доказать», что он может.

GCC обнаруживает «общий» код, такой как кодированные вручную min() и max(), и превращает их в одну инструкцию SSE (для x86 / x86_64 и при установленном -msse) или использует cmov, когда доступен i686 (SSE имеет более высокий приоритет). GCC также получит свободу в переупорядочении циклов, развертывании и вставке функций, если он этого захочет, и даже в удалении ненужного кода.

Что касается вашего последнего редактирования:

Вы можете видеть, что в -O0 std :: vector опережает в два раза быстрее указатели. Хотя в -O2 они почти то же самое.

Это потому, что std::vector все еще имеет код, который генерирует исключения и может использовать rtti. Попробуйте сравнить с -O2 -NDEBUG -ftree-vectorize -fno-rtti -fno-exceptions -fomit-frame-pointer, и вы увидите, что std :: vector будет немного лучше, чем ваш код. GCC знает, что такое «встроенные» типы и как их использовать в реальном мире, использует и с радостью сделает это - точно так же, как он знает, что делают memset() и memcpy(), и как соответственно оптимизировать, когда Размер копии известен.

Answer 2

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

Собираетесь ли вы компилировать свой код для выпуска только с -O0? Возможно нет. Вы также можете сравнить производительность алгоритмов при компиляции с любыми флагами компиляции, которые вы на самом деле намереваетесь использовать.

Answer 3

У вас есть два алгоритма , реализованных в C ++. Если вы хотите сравнить относительную производительность двух реализаций, вам следует использовать уровень оптимизации, который вы собираетесь использовать в своем конечном продукте. Для меня это -O3.

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

Как разработчик, пишущий код, где производительность является проблемой, хорошей идеей является знание диапазона оптимизаций, которые компилятор может и может применить к вашему коду. Не оптимизация несправедливо наказывает код, который написан четко, но предназначен для легкой оптимизации против кода, который уже «микрооптимизирован».

Answer 4

Не вижу смысла не компилировать и запускать их оба в O2. Если вы не делаете это как чисто академическое упражнение (и даже если бы вы это делали, очень маловероятно, что оптимизация произвела бы фундаментальные изменения в свойствах алгоритма - хотя, я думаю, я был бы счастлив, если бы GCC начал использовать O (N) источник в сборку O (lgN)), вам понадобится информация, которая будет согласована с тем, что вы получите при запуске финальной программы. Скорее всего, вы не будете выпускать программу с O0-оптимизациями, поэтому вы не хотите сравнивать алгоритмы под O0-оптимизациями.

Answer 5

Такое сравнение менее справедливо, чем получение полезной информации. Вам следует использовать уровень оптимизации, который вы планируете использовать, когда / если код введен в промышленное использование. Если вы в основном проводите исследования, поэтому вы лично не планируете использовать его в производственной среде, вы застряли на чуть более сложной задаче - угадать, что кто-то, кто запустит в производство, вероятно делать.

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

Лично я обычно использую -O2 с gcc. Мое общее правило - использовать самый низкий уровень оптимизации, который включает автоматическое встраивание. Я пишу большую часть своего кода, ожидая, что компилятором будут встроены небольшие функции, и специально пишу код, чтобы помочь в этом (например, часто используя функторы вместо функций). Если компилятор не настроен на создание кода для этих встроенных компонентов, вы не получите то, что я действительно хотел. Производительность кода, когда он скомпилирован таким образом, на самом деле ничего не значит - я бы, конечно, не планировал бы когда-либо действительно использовать его таким образом.