Оптимизация компилятора: где и как я могу получить представление о том, какова отдача от различных оптимизаций?

Question

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

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

Answer 1

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

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

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

Answer 2

Язык в щеке:

1. Hubris
2. Тесты
3. Замешательство

Более серьезно, это зависит от архитектуры и целей вашего компилятора. Вот опыт одного человека ...

Перейти на "большие выплаты":

• генерация собственного кода
• регистр распределения
• планирование команд

Перейти к оставшимся "низко висящим фруктам":

• снижение прочности
• постоянное распространение
• копирование распространения

Продолжайте бенчмаркинг.

посмотрите на вывод; исправить все, что выглядит глупо.

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

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

Answer 3

Исторически сложилось, что существуют «алгоритмические» оптимизации, из которых код должен выиграть в большинстве случаев, например развертывание цикла (и разработчики компилятора должны сначала реализовать эти «документированные» и «проверенные» оптимизации).

Кроме того, существуют типы оптимизации, которые могут выиграть от типа используемого процессора (например, использование инструкций SIMD на современных процессорах).

См. Оптимизация компилятора в Википедии для справки.

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

Answer 4

Это действительно зависит от того, что вы компилируете. В последнее время в списках рассылки LLVM было довольно хорошее обсуждение , что, конечно, в определенной степени относится к имеющимся у них оптимизаторам. Они используют сокращения для большинства своих проходов оптимизации, если вы не знакомы ни с одним из сокращений, которые они подбрасывают, вы можете посмотреть их проходы page для документации. В конечном итоге вы можете потратить годы на чтение научных работ по этому предмету.

Answer 5

Я не пишу компилятор, но почему бы не просто постепенно оптимизировать части вашего кода, постоянно профилируя?

Моя схема оптимизации обычно идет:

1) убедитесь, что программа работает

2) найти что-то для оптимизации

3) оптимизировать

4) сравнить результаты теста с полученными из 1; если они разные, то оптимизация - это действительно серьезное изменение.

5) сравнить разницу во времени

Постепенно я получу это быстрее.

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

Answer 6

Стоит отметить, что во многих случаях разработчики компиляторов НЕ будут тратить много времени, если таковые вообще имеются, на обеспечение оптимизации своих библиотек. Тесты имеют тенденцию уменьшать или даже игнорировать различия в библиотеках, возможно потому, что вы можете просто использовать разные библиотеки. Например, алгоритмы перестановки в GCC асимптотически * менее эффективны, чем они могли бы быть при попытке перестановки сложных данных. Это связано с неправильным созданием глубоких копий во время вызовов функций подкачки. Это, вероятно, будет исправлено в большинстве компиляторов с введением ссылок на rvalue (часть стандарта C ++ 0x). Переписать STL намного быстрее, на удивление легко.

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

Answer 7

Это одна из тех тем, где научные статьи (возможно, ACM) могут быть одним из лучших источников актуальной информации. Лучшее, что можно сделать, если вы действительно хотите это знать, - это создать некоторый код в неоптимизированной форме, а другой - в форме, которую могла бы принять оптимизация (развернутые циклы и т. Д.), И выяснить, где выгоды, вероятно, будут использовать компилятор с отключенной оптимизацией.

Answer 8

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