Отзыв: The death of optimizing compilers
Оригинальная публикация D.J. Bernstein
Не могу сказать, что безусловно согласен с этим докладом, но он заставляет задуматься. Замечу, что форматирование оригинала очень своеобразно, и на мой взгляд, нечитаемо. Вероятно, изначально слайды были в текстовом формате. Но прочитать оригинал, безусловно, стоит.
Основные тезисы в моём пересказе.
Код программы можно разделить на 2 группы:
1. Небольшое количество «горячего» кода, многократное исполнение которого занимает почти всё время работы программы.
2. Большое количество «холодного» кода, который исполняется редко (в том числе, например, только при запуске) и не оказывает заметного влияния на производительность.
Производительность «холодного» кода никого не должна волновать. Достаточно много кода сейчас пишется на интерпретируемых языках программирования (Python) или исполняется в браузере с большими накладными расходами.
«Горячий» код, как правило, оптимизируется вручную разработчиками алгоритма, потому что его оптимизация требует глубокого знания алгоритма (грубо говоря, «чем можно пренебречь ради ускорения») и глубокого знания аппаратной платформы. Одно только руководство по системе команд процессоров Intel сейчас занимает 5 томов (2a-2d) и 2.2 тыс. страниц.
Оптимизирующие компиляторы — это очень сложные программы, которые сами могут вносить ошибки в оптимизируемый код. Состав стадий оптимизации влияет на время компиляции и, например, на удобство отладки. При этом для «холодного» кода оптимизации бесполезны. А для «горячего» кода компилятор не способен достичь уровня оптимизации, близкого к тому, который может получить специалист. Мы говорим об оптимизациях наподобие кэширования, изменения методов расчёта и формул. Компилятор, который может проводить только преобразования, сохраняющие семантику исходного кода, не имеет права так делать.
Вывод: дальнейшее усложнение оптимизирующих компиляторов не имеет особого смысла.
(В заключение автор цитирует Кнута о перспективах систем интерактивной трансформации программ, как одного из направлений развития. Но наиболее интересен, на мой взгляд, предыдущий тезис.)
Из своего опыта могу извлечь одно критическое замечание. Тезис про «горячие» участки справедлив скорее для отдельных программ или библиотек. Сам Bernstein известен в первую очередь как криптограф, а для криптографии это ещё более справедливо. Когда же речь заходит не об отдельно стоящей программе или библиотеке, а о системе, тем более распределённой, например, традиционной трёхзвенной архитектуры «клиент (в наше время обычно браузер) — сервер — база данных», не говоря уже о популярных в последнее время микросервисах, вопрос становится сложнее.
В зрелой системе, разработчики которой уделяют какое-то время профилированию и оптимизации «узких мест», профили каждого отдельного компонента, как правило, выравниваются. Чаще всего большая часть времени в таких системах тратится на взаимодействие компонентов, большой вклад в которое вносят разного рода задержки и накладные расходы на синхронизацию. С другой стороны, конечно, сложные оптимизирующие компиляторы таким системам тоже не сильно помогут. Их тоже оптимизируют вручную. Так что и это, можно сказать, подтверждает неочевидный тезис о превосходстве человека над компилятором в тех областях, где это имеет смысл.
Для углубления в тему я бы рекомендовал посмотреть на среду LuaJIT [1] и, посложнее, компилятор Терра [2] и на диссертацию Maximillian Bolingbroke по суперкомпиляции в GHC [5]. Среда LuaJIT [1] уже достаточно давно продемонстрировала подход, близкий к оптимальному для динамических языков. Программы на динамическом языке Lua в этой среде показывают производительность, близкую к языку C. Не могу привести ссылки на достоверные замеры производительности, но похоже, что JIT-компилятор V8, который используется в браузере Chromium и в платформе приложений NodeJS. Таким образом, реализацию LuaJIT, занимающую порядка 90 000 строк кода, можно считать иллюстрацией текущего состояния дел на стороне оптимизирующих компиляторов :)
Компилятор Terra [2] реализован на основе LuaJIT, но, с другой стороны, показывает пример той самой системы трансформации программ в представлении Кнута. В случае компилятора Terra некоторое типизированное подмножество языка Lua транслируется в биткод LLVM и оптимизируется примерно так же, как программы на языке C компилятором Clang. А оставшаяся часть программы пишется на языке Lua (и работает в LuaJIT), который выступает и в качестве умного гибрида препроцессора, компоновщика и связующего языка. В статье [3] авторы с помощью этого компилятора подготовили автоматически настраиваемые вычислительные ядра для обработки изображений, которые обгоняют по производительности аналогичные ядра на языке C, и которые при этом можно транслировать далее для FPGA-процессоров и ASIC-микросхем. Кстати говоря, что-то похожее Владимир Роганов делал для решения разреженной системы линейных уравнений в задаче моделирования атомной электростанции в нашей статье [4]. При запуске комплекс моделирования выполняет тесты нескольких библиотек, реализующих решение разреженной системы линейных уравнений. По результатам тестов автоматически (или автоматизированно — с возможным участием человека?) выбирается наилучший именно для той платформы, на которой запущен комплекс.
Наконец, в диссертации [5] Maximillian Bolingbroke показывает, что суперкомпиляция вполне может служить практически единственной оптимизацией в компиляторе. О чём-то подобном я ещё на младших курсах мехмата говорил с однокурсником Андреем Банниковым. Он как раз предполагал, что было бы здорово в компиляторе сделать оптимизатор с единственной универсальной оптимизацией — но тогда мы не были настолько погружены в тему, чтобы дойти до такого рода оптимизации. А сейчас возникает ощущение, что, действительно, в новых компиляторах стоит попробовать начать с суперкомпиляции и дополнить её, разве что, какими-то простыми оптимизациями по правилам на выходе и пессимизациями на входе.
В качестве заключительной мысли, выскажу в воздух: интересно, насколько сложно было бы реализовать язык Lua на основе примитивных языков типа Forth/machineForth/colorForth, и как бы в таком случае его производительность соотносилась с LuaJIT? Конечно, для долгоживущих программ трассирующий компилятор обгонит «простой» компилятор на Forth. Но мне кажется, кода в случае последнего будет значительно меньше, что значительно лучше для кэш-памяти.
Ссылки (все на HTTP-ресурсы):
Уже почти классические заметки о том, как устроен LuaJIT:
[1a] Mike Pall. LuaJIT's interpreter is fast, because:…
[1b] Mike Pall. LuaJIT 2.0 intellectual property disclosure and research opportunities
[3] Darkroom: Compiling High-Level Image Processing Code into Hardware Pipelines
Ссылка на страницу статьи, но где-то недалеко на сайте есть PDF номера с её полным текстом:
[5] Max Bolingbroke. Call-by-need supercompilation
-- CC-BY-SA: maxxk (Максим Кривчиков)
2020-12-23