04 СериЯ. ФормальныЕ ПреобразованиЯ и ОптимизациЯ
В. Ф. Турчин отмечает[62], что достоинства всякого формализованного языка определяются не только тем, сколь он удобен для непосредственного использования человеком, но и тем, в какой степени тексты на этом языке поддаются формальным преобразованиям.
Например, ссылочная прозрачность означает, что параметры функций не обязаны вычисляться перед вызовом — вместо этого фактически переданное выражение может быть целиком подставлено на место переменной в функции, и поведение функции от этого не изменится. Это открывает возможности почти произвольных автоматических преобразований программ[en]: могут устраняться ненужные промежуточные представления данных, редуцироваться сложные цепочки вычислений, подбираться оптимальное количество параллельных процессов, вводиться мемоизация, и пр. С другой стороны, это означает полное отсутствие побочных эффектов, а это делает реализацию некоторых алгоритмов заведомо менее эффективной, чем при использовании изменяемого состояния.
Для небольших и простых программ языки высокого уровня порождают машинный код большего размера и исполняются медленнее. Однако для алгоритмически и структурно сложных программ преимущество может быть на стороне некоторых языков высокого уровня, так как человек физически не способен выражать сложные концепции с учётом их эффективного исполнения на языке машины. К примеру, существует бенчмарк, на котором MLton и Stalin Scheme[en] уверенно опережают GCC. Есть масса частных причин, по которым автоматическая оптимизация в ходе трансляции языков высокого уровня даёт в принципе более высокую скорость исполнения, чем сознательный контроль способа реализации на языках низкого уровня. Например, имеются достоверные данные о том, что автоматическое управление памятью более эффективно, чем ручное, уже только при использовании динамического метода (см. сборка мусора)[63], а существует и потенциально более эффективный статический метод (см. управление памятью на основе регионов). Далее, для каждого микроконтекста необходимо распределить регистры с учётом минимизации обращения к памяти, а это требует решения задачи раскраски графа. Такого рода особенностей машинной логики очень много, так что общая информационная сложность возрастает экспоненциально при каждом «шаге на уровень вниз», а компиляция языка высокого уровня может включать десятки таких шагов.
Существует множество стратегий автоматической оптимизации. Некоторые универсальны, другие могут быть применимы лишь к языкам определённой природы, а некоторые зависят от способа использования языка. Примером может служить оптимизация хвостовых вызовов и её частный случай — оптимизация хвостовой рекурсии. Хотя компиляторы многих языков осуществляют оптимизацию хвостовой рекурсии при определённых условиях, лишь некоторые языки способны семантически гарантировать оптимизацию хвостовых вызовов в общем случае. Стандарт языка Scheme требует, чтобы всякая реализация гарантировала её. Для многих функциональных языков она в принципе применима, но лишь оптимизирующие компиляторы её выполняют. В языках вроде Си или С++ она может производиться лишь в определённых случаях и лишь при использовании глобального анализа потока управления[64].
Языки высшего порядка в большинстве случаев вынуждены исполняться медленнее, чем языки первого порядка. Причины лежат как в самой декомпозиции линейного кода на цепочку вложенных вызовов, так и в вытекающих особенностях низкоуровневого представления функций (см. замыкание) и данных (обёрнутое (англ. boxed), теговое). Однако существуют техники агрессивной оптимизации программ, позволяющие редуцировать языки высшего порядка до языков первого порядка (см. дефункциализация[en], MLton, Stalin Scheme[en]).
[rating]
