Генетическое программирование для тестирования компилятора: опыт аспиранта ML-лаборатории ИТМО

    Виктор Петухов, студент второго курса аспирантуры Университета ИТМО и техлид в одной из команд проекта Kotlin в JetBrains (занимается компилятором Kotlin), решил совместить работу с детальным изучением профессиональной проблематики в научном формате и присоединился к лаборатории машинного обучения ИТМО. Рассказываем, что из этого получилось.

    Фотография Marc Reichelt / Unsplash.com
    Фотография Marc Reichelt / Unsplash.com

    История вопроса

    Языки программирования — фундамент огромного спектра продуктов, сервисов и критически значимой инфраструктуры. В своей научной статье по этой теме Виктор подчеркивает, что ошибки в коде компиляторов действительно могут привести к существенным последствиям. Однако количество всевозможных тестовых сценариев для них обычно крайне велико, поэтому составлять их приходится с привлечением интеллекта — человеческого или «искусственного», чтобы должным образом исследовать наиболее подверженные ошибкам части компилятора.

    Но автоматическое составление таких тестов обладает ограничениями. Как правило, мы тяготеем к генерированию семантически корректных фрагментов кода, минуя парсер (самую простую часть компилятора) и пробираясь к самым сложными частям: подсистеме вывода типов, механизму разрешения вызовов и прочим. Если использовать для этого формальную модель, такую как грамматику, доля получаемых семантически корректных фрагментов кода будет слишком мала.

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

    Задача попутной оптимизации характеристики производительности при генерации кода является не простым дополнением к произвольной генерации. На данный момент над этой проблемой работает не так много специалистов, поэтому Виктор увидел здесь возможность для развития профессиональных и научных компетенций — решил предложить такой способ генерации исходного кода на Kotlin, чтобы «либо время компиляции, либо потребляемая память были максимальными».

    Как это работает

    Использование генетического программирования для тестирования производительности компилятора подразумевает, что с каждой новой генерацией кода осуществляется оптимизация некоторого целевого параметра — например, использованной памяти.

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

    Пример скрещивания фрагментов исходного кода с учетом типов
    Пример скрещивания фрагментов исходного кода с учетом типов

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

    В ходе эксперимента были обнаружены некоторые проблемы в производительности компилятора Kotlin — например, экспоненциальный рост времени анализа лямбд в правой части оператора «+=» по мере увеличения глубины вложенности этих лямбд. Команда компилятора уже занимается этой проблемой. На скриншоте далее — показываем, как изменяется время компиляции приведенного фрагмента кода, если добавлять вложенные лямбды.

    Пример точечной проблемы, которую удалось обнаружить
    Пример точечной проблемы, которую удалось обнаружить

    Что дальше

    Сейчас проектом занимаются пять человек. Это — коллективный труд исследователей Университета ИТМО и представителей JetBrains. Коллеги убеждены в целесообразности продолжения исследования и совершенствования предложенного Виктором подхода.

    «Мы хотели бы реализовать и оператор мутации, чтобы избавиться от предвзятости относительно начального набора данных и генерировать принципиально новые конструкции языка. Помимо генетического программирования мы планируем применить здесь и генеративные модели, а затем провести сравнение результатов и подумать о разработке методологии тестирования производительности компиляторов»

    — Виктор Петухов, аспирант второго года обучения, программист — на факультете ИТ и программирования, программист в JetBrains, в команде компилятора Kotlin.


    Дополнительное чтение в нашем блоге на Хабре:


    Университет ИТМО
    IT's MOre than a University

    Комментарии 3

      +1
      Есть ли планы на open source генератора?
        +1
        На данный момент реализация находится внутри репозитория компилятора (https://github.com/Recognized/kotlin), но позже мы планируем вынести её в отдельную тулу.
        0

        Когда-то делал что-то похожее — генетический оптимизатор байткода JVM. Но тогда так и не нашел к чему бы его применить — такие небольшие оптимизации давали совсем мизерный выигрыш по времени.


        https://habr.com/ru/post/265195/

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое