Привет. Меня зовут Виктор Петухов. Я учусь на втором курсе аспирантуры Университета ИТМО и уже более двух лет работаю в JetBrains в команде Kotlin Compiler. Перед тем, как поступить в аспирантуру, я думал о том, как наука может помочь в моих рабочих задачах, таких как тестирование компилятора. К тому времени JetBrains Research уже вела научную работу в области тестирования компиляторов, я решил посмотреть ее и посмотреть, есть ли еще открытые актуальные проблемы. Работая в то время инженером по обеспечению качества в команде компиляторов Kotlin, я столкнулся с некоторыми проблемами, автоматическое обнаружение которых еще не исследовалось. Одной из таких проблем, которые меня интересовали, были проблемы с производительностью компилятора. Я подумал, что было бы здорово создавать программы, в которых компилятор будет работать медленнее или потреблять больше памяти. Это будет большим подспорьем для команды компиляторов в раннем обнаружении таких проблем. Итак, с этого момента я начал изучать тему автоматического обнаружения проблем с производительностью компилятора. Потом с этой темой я поступил в аспирантуру ИТМО. Позже к проекту присоединился Владислав Сайфулин, который в итоге лег в основу его бакалаврской диссертации. А теперь я рассказываю вам о начале этого исследования :)

Почему компиляторы?

Как известно, языки программирования и их компиляторы действительно важны в индустрии программирования. Один из интересных аспектов - влияние на каждый программный продукт в мире, даже на самого себя. Воздействие означает, насколько быстро программа работает и насколько правильно зависит, среди прочего, от компилятора, с которым она была скомпилирована. Например, некоторые логические ошибки в исходном коде clang (clang - компилятор для C и C ++ в байт-код LLVM) гипотетически могут привести к различным сбоям огромного количества программ мира, в том числе компиляторов других языков программирования. Это указывает на высокую актуальность исследований в области тестирования компиляторов. Так что этот факт нам показался вдохновляющим!

Почему тестирование производительности?

С тех пор мы погрузились в исследование того, что мир придумал для тестирования компиляторов. Оказалось, что было много попыток разработать инструменты, позволяющие автоматически находить ошибки в компиляторах. Некоторые исследователи пытались найти уязвимости безопасности в интерпретаторах, таких как V8 (движок для обработки исходного кода JavaScript). Другие исследователи создали исходный код, для которого компилятор генерирует исключение. Наконец, были попытки сравнить поведение компилятора на сгенерированном коде с некоторым эталонным компилятором. Но лишь несколько исследователей пытались найти проблемы с производительностью компилятора, поскольку задача обнаружения проблем с производительностью в компиляторах действительно сложна. Он состоит из двух частей: во-первых, вам нужно сгенерировать программный код (что уже является нетривиальной задачей), а во-вторых, вам нужно сделать это таким образом, чтобы характеристики производительности сгенерированной программы были как «плохие». по возможности; а для остальных перечисленных задач достаточно просто сгенерировать код. Поэтому мы хотели заполнить пробелы в этой области и помочь команде компиляторов провести тестирование с помощью нашего исследования.

Почему генетическое программирование?

Основная задача при тестировании компиляторов - это создание программного кода, на котором будет тестироваться соответствующий компилятор. Существующие работы в области тестирования компилятора решают эту проблему четырьмя различными способами:

  • По формальной грамматике языка: просто сгенерируйте код, следуя случайным доступным правилам грамматики;
  • С помощью написанного вручную генератора исходного кода языкового подмножества: приложить достаточно большие инженерные усилия даже для поддержки небольшого подмножества языка программирования высокого уровня;
  • Использование мутаций: скрещивание нескольких фрагментов кода для получения новых;
  • Использование машинного обучения: примените машинное обучение любым из вышеперечисленных способов и сделайте это умнее! Мы можем обучить нейронную сеть семантике языка и, например, грамотно выбирать пути правил грамматики.

С одной стороны, мы хотим, чтобы пространство сгенерированных программ не было очень ограниченным, как это, скорее всего, было бы с вручную написанным генератором исходного кода (обратите внимание, что инженерные усилия по написанию генератора абсолютно любого кода могут быть сопоставимы с написанием соответствующий компилятор).

С другой стороны, мы хотим иметь дело с семантически правильными фрагментами кода. Генератор кода с помощью языковой грамматики может создавать только синтаксически правильные фрагменты кода. Имея это в виду, мы решили мутировать фрагменты кода, и, если все пойдет хорошо, начать делать это умнее, обучая нейронную сеть семантике языка. Не забывайте, что нам нужно не только сгенерировать код, но и сделать это так, чтобы сгенерированные программы были как можно более «плохими» с точки зрения производительности. Говоря математическими словами, нам нужно одновременно оптимизировать какое-то значение производительности, например, время анализа сгенерированной программы или память, потребляемую во время ее компиляции. Мы использовали генетическое программирование, которое представляет собой эволюционный подход, позволяющий осуществлять поиск в пространстве компьютерных программ. При использовании генетического программирования подразумевается реализация операторов кроссовера и мутации, а также определение фитнес-функции, благодаря которой будут выбраны лучшие программы. Фитнес-функция - это именно то, что нужно для решения проблемы оптимизации значений производительности. В свою очередь, оператор кроссовера предполагает комбинацию существующих правильных программ, а оператор мутации устраняет предвзятость в отношении набора данных, добавляя принципиально новый код (например, полученный из грамматики). Так что давай попробуем!

Что из этого вышло?

Выбор языка

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

Набор данных

Во-первых, мы подумали, на каком наборе данных было бы удобнее проводить эксперименты. Главный критерий выбора - изолированность всех фрагментов кода, то есть полные семантически правильные программы, не зависящие от других источников или библиотек. Выбор оказался довольно простым и очевидным. Существующие тесты компилятора очень хорошо подходят! Они самодостаточны, их довольно много (хотя и не так, как хотелось бы), их легко собрать (все они есть в репозитории Kotlin).

Структура данных

Начнем с представления программы, с которой будет работать генетический алгоритм. В Kotlin есть удобное представление программы, которое называется PSI (интерфейс структуры программы). Это просто конкретное синтаксическое дерево, и его узлы могут быть однозначно сопоставлены с исходным кодом. Так что будем работать с этим.

Какой показатель эффективности мы измеряем?

Очевидно, что лучше начать с самого простого, например, с момента анализа программы. На данный момент мы получим время анализа от компилятора Kotlin (он может вывести его, если вы передадите специальный флаг), но в будущем мы добавим альтернативное независимое измерение, косвенно связанное со временем выполнения, а именно число выполненных инструкций в байт-коде (и показать взаимосвязь между ними). В будущем мы также собираемся измерять другие характеристики, такие как время генерации кода, размер кучи JVM и так далее.

Определение операторов

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

Где P₁ - исходная программа, P₂ - измененная программа, X₁ - исходное дерево синтаксического анализа, X₂ - дерево синтаксического анализа измененной программы.

Мы включили в функцию пригодности произведение времени анализа и увеличенного времени анализа, потому что мы хотим, прежде всего, выбрать программы, время анализа которых довольно велико, и в то же время увеличено по сравнению с предыдущим. образец. Нормализация по IncreasedParseTreeSize позволяет нам исключить естественное увеличение времени анализа из-за увеличения исходного кода. Коэффициент k предлагается подбирать опытным путем.

Соответственно, функцию выбора можно определить следующим образом:

Мы добавляем второй фактор K как среднее расстояние между деревьями согласно некоторой метрике сравнения деревьев, чтобы сохранить представителей разных поколений (то есть, чтобы не сосредотачиваться на программах того же типа). Fⁱ - функция пригодности для процедуры i-й мутации.

Следующим шагом является введение операторов кроссовера и мутации. Оператор кроссовера можно записать в следующем виде:

где Xⁱ - это набор всех поддеревьев i-го дерева синтаксического анализа программы; i, j - случайные индексы.

Чтобы увеличить долю семантически правильного кода, мы решили не просто объединить фрагменты кода из нашего набора данных, а сделать это с некоторыми ограничениями. На первой итерации мы пытаемся ввести ограничения на типы переменных, а именно, что один фрагмент кода заменяется другим только в том случае, если в месте подстановки есть переменные соответствующих типов. Поэтому мы налагаем следующие ограничения на индексы i и j:

OutputTypes (X) для программы n и поддерева j должны возвращать только те типы, которые присутствуют в InputTypes (X) для программы m и поддерева i или их подтипов в терминах языка программирования Kotlin. InputTypes (X) возвращает все типы, доступные во фрагменте кода X. OutputTypes (X) возвращает все типы required для фрагмента кода (required необходимо для сохранения семантической правильности именования переменных фрагмента кода по модулю).

Пример комбинации фрагментов кода приведен на рисунке 1.

Следующий оператор - оператор мутации. Его определение довольно простое:

generateNode () и changeNodeValueToGenerated () могут быть реализованы с использованием грамматики Котлина. Выбор конкретной функции может осуществляться с помощью специальной эвристики или случайным образом.

Предварительные результаты

Мы реализовали некий прототип, основанный на описанной выше теории. На данный момент мы не реализовали все описанное, но уже получили интересные результаты. Например, мы обнаружили следующую проблему производительности в компиляторе Kotlin: лямбда-выражения, расположенные справа от оператора + =, анализируются экспоненциально с увеличением глубины вложения лямбда-выражений (см. рисунок 2). В данном примере самая глубокая лямбда анализируется 8 раз.

Эта проблема уже была известна команде компиляторов Kotlin, но факт ее обнаружения говорит о востребованности такого инструмента. Также были обнаружены некоторые другие известные проблемы, такие как связывание использования переменных в коллекциях или глубокий вызов конструктора класса данных.

Вывод

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

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