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

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

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

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

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

EDIT:

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

Я изменил одну из функций с необработанными указателями (int и boolean) на std::vector и std::vector... С -O0 -NDEBUG показатели - 5.46s (необработанный указатель) и 11.1s (std::vector). И с -O2 -NDEBUG, показатели 2.02s (необработанный указатель) и 2.21s (std::vector). Один и тот же алгоритм, одна реализация использует 4/5 динамических массивов int и boolean. А другой использует вместо этого std::vector и std::vector. Они одинаковы в каждом другом случае

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

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

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

Ответ 1

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

Speed

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

Размер

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

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

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(), и как оптимизировать когда размер копии известен.

Ответ 2

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

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

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

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