Компилируем Kotlin: JetBrains VS ANTLR VS JavaCC


    Насколько быстро парсится Kotlin и какое это имеет значение? JavaCC или ANTLR? Годятся ли исходники от JetBrains?

    Сравниваем, фантазируем и удивляемся.

    tl;dr


    JetBrains слишком тяжело таскать за собой, ANTLR хайповый, но неожиданно медленный, а JavaCC ещё рано списывать.

    Парсинг простого Kotlin файла тремя разными реализациями:
    Имплементация Первый запуск 1000й запуск размер джара (парсера)
    JetBrains 3254мс 16,6мс 35.3МБ
    JetBrains (w/o analyzer) 1423мс 0,9мс 35.3МБ
    ANTLR 3705мс 137,2мс 1.4МБ
    JavaCC 19мс 0,1мс 0.8МБ

    Одним погожим солнечным деньком...


    я решил собрать транслятор в GLSL из какого-нибудь удобного языка. Идея была в том, чтобы программировать шейдеры прямо в идее и получить «бесплатно» поддержку IDE — синтаксис, дебаг и юнит-тесты. Получилось действительно очень удобно.

    С тех пор осталась идея использовать Kotlin — в нём можно использовать имя vec3, он более строг и в IDE с ним удобнее. Кроме того — он хайповый. Хотя с точки зрения моего внутреннего менеджера это всё недостаточные причины, но идея столько раз возвращалась, что я решил от неё избавиться просто реализовав.

    Почему не Java? Нет перегрузки операторов, поэтому синтаксис арифметики векторов будет уж слишком отличаться от того что вы привыкли видеть в геймдеве

    JetBrains


    Ребята из JetBrains выложили код своего компилятора на гитхаб. Как им пользоваться можно подсмотреть тут и тут.

    Сначала я использовал их парсер вместе с анализатором, потому что для трансляции в другой язык — необходимо знать какой тип у переменной без явного указания типа val x = vec3(). Тут тип для читателя очевиден, но в AST эту информацию не так просто получить, особенно когда справа другая переменная, или вызов функции.

    Здесь меня постигло разочарование. Первый запуск парсера на примитивном файле занимает 3с (ТРИ СЕКУНДЫ).

    Kotlin JetBrains parser
    first call elapsed : 3254.482ms
    min time in next 10 calls: 70.071ms
    min time in next 100 calls: 29.973ms
    min time in next 1000 calls: 16.655ms
    Whole time for 1111 calls: 40.888756 seconds

    Такое время имеет следующие очевидные неудобства:

    1. потому что это плюс три секунды к запуску игры или приложения.
    2. во время разработки я использую горячую перегрузку шейдера и вижу результат сразу после изменения кода.
    3. я часто перезапускаю приложение и рад что оно стартует достаточно быстро (секунда-две).

    Плюс три секунды на разогрев парсера — это неприемлемо. Конечно, сразу выяснилось что при последующих вызовах время парсинга падает до 50мс и даже до 20мс, что убирает (почти) из выражения неудобство №2. Но два остальных никуда не деваются. К тому же, 50мс на файл — это плюс 2500мс на 50 файлов (один шейдер — это 1-2 файла). А если это Android? (Тут мы пока говорим только про время.)

    Обращает на себя внимание сумасшедшая работа JIT. Время парсинга простого файла падает с 70мс до 16мс. Что означает, во первых — сам JIT потребляет ресурсы, а во вторых — на другой JVM результат может сильно отличаться.

    В попытке выяснить откуда такие цифры, нашёлся вариант — использовать их парсер без анализатора. Ведь мне нужно всего лишь расставить типы и сделать это можно относительно легко, в то время как JetBrains анализатор делает что-то гораздо более сложное и собирает гораздо больше информации. И тогда время запуска падает в два раза (но почти полторы секунды это всё равно прилично), а время последующих вызовов уже гораздо интереснее — с 8мс в первых десяти, до 0.9мс где-то к тысяче.

    Kotlin JetBrains parser (without analyzer) (исходник)
    first call elapsed : 1423.731ms
    min time in next 10 calls: 8.275ms
    min time in next 100 calls: 2.323ms
    min time in next 1000 calls: 0.974ms
    Whole time for 1111 calls: 3.6884801 seconds

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

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

    ANTLR


    На JavaCC парсера не нашлось, а вот на хайповом ANTLR, ожидаемо, есть (раз, два).

    Но вот что было неожиданно — так это скорость. Те же 3с на прогрузку (первый вызов) и фантастические 140мс на последующие вызовы. Тут уже не только первый запуск длится неприятно долго, но и потом ситуация не исправляется. Видимо, ребята из JetBrains, сделали какую-то магию, позволив JIT так оптимизировать их код. Потому что ANTLR совсем не оптимизируется со временем.

    Kotlin ANTLR parser (исходник)
    first call elapsed : 3705.101ms
    min time in next 10 calls: 139.596ms
    min time in next 100 calls: 138.279ms
    min time in next 1000 calls: 137.20099ms
    Whole time for 1111 calls: 161.90619 seconds

    JavaCC


    В общем, с удивлением отказываемся от услуг ANTLR. Парсинг не должен быть таким долгим! В грамматике Котлина нет каких-то космических неоднозначностей, да и проверял я его на практически пустых файлах. Значит, настало время расчехлить старичка JavaCC, закатать рукава, и всё таки «сделать самому и как надо».

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

    Kotlin JavaCC parser (исходник)
    first call elapsed : 19.024ms
    min time in next 10 calls: 1.952ms
    min time in next 100 calls: 0.379ms
    min time in next 1000 calls: 0.114ms
    Whole time for 1111 calls: 0.38707677 seconds

    Внезапные плюсы своего парсера на JavaCC
    Конечно, вместо написания своего парсера хотелось бы использовать готовое решение. Но существующие имеют огромные недостатки:

    — производительность (паузы при чтении нового шейдера недопустимы, как и три секунды разогрева на старте)
    — огромный рантайм котлина, я даже не уверен можно ли парсер с его использованием упаковать в финальный продукт
    — кстати, в текущем решении с Groovy та же беда — тянется рантайм

    В то время как получившийся парсер на JavaCC это

    + отличная скорость и на старте и в процессе
    + всего несколько классов самого парсера

    Выводы


    JetBrains слишком тяжело таскать за собой, ANTLR хайповый, но неожиданно медленный, а JavaCC ещё рано списывать.

    Парсинг простого Kotlin файла тремя разными реализациями:

    Имплементация Первый запуск 1000й запуск размер джара (парсера)
    JetBrains 3254мс 16,6мс 35.3МБ
    JetBrains (w/o analyzer) 1423мс 0,9мс 35.3МБ
    ANTLR 3705мс 137,2мс 1.4МБ
    JavaCC 19мс 0,1мс 0.8МБ

    В какой-то момент, я решил посмотреть на размер джара со всеми зависимостями. JetBrains велик вполне ожидаемо, а вот рантайм ANTLR удивляет своим размером.
    UPDATE: Изначально я написал 15МБ, но, как подсказали в комментариях, если подключить antlr4-runtime вместо antlr4, размер падает до ожидаемого. Хотя сам парсер JavaCC остаётся в 10 раз меньше ANTLR (если убрать вообще весь код, кроме самих парсеров).
    Размер джара как таковой важен, конечно, для мобилок. Но и для десктопа имеет значение, т.к., фактически, означает количество дополнительного кода, в котором могут водиться баги, который должна индексировать IDE, который, как раз, и влияет на скорость первой загрузки и скорость разогрева. Кроме того, для сложного кода нет особой надежды транслировать на другой язык.
    Я не призываю считать килобайты и ценю время программиста и удобство, но всё же об экономии стоит задумываться, потому что именно так проекты и становятся неповоротливыми и трудно поддерживаемыми.

    Ещё пара слов об ANTLR и JavaCC

    Серьёзной фичей ANTLR является разделение грамматики и кода. Это было бы хорошо, если бы за это не нужно было так дорого платить. Да и значение это имеет только для “серийных разработчиков грамматик”, а для конечных продуктов это не так важно, ведь даже существующую грамматику всё равно придётся прошерстить чтобы написать свой код. Плюс, если мы сэкономим и возьмём “стороннюю” грамматику — она может быть просто неудобна, в ней всё равно нужно будет досконально разбираться, преобразовывать дерево под себя. В общем, JavaCC, конечно, смешивает мух и котлеты, но такое ли большое это имеет значение и так ли это плохо?

    Ещё одной фишкой ANTLR является множество target платформ. Но тут посмотреть можно с другой стороны — код из под JavaCC очень простой. И его очень просто… транслировать! Прямо с вашим кастомным кодом — хоть в C#, хоть в JS.

    P.S.


    Весь код находится тут github.com/kravchik/yast

    Результатом парсинга у меня является дерево построенное на YastNode (это очень простой класс, фактически — мапа с удобными методами и айдишником). Но YastNode — это не совсем «сферическая нода в вакууме». Именно этим классом я активно пользуюсь, на его основе у меня собрано несколько инструментов — типизатор, несколько трансляторов и оптимизатор/инлайнер.

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

    Подробнее
    Реклама

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

      +1
      А по какой причине шейдеры в GLSL кроспилируются каждый раз в рантайме заново, а не заранее на этапе сборки и не бандлятся в игру/приложение собственно в виде GLSL?
        0
        Конечно, в случае медленного/тяжёлого транслятора они транслируются заранее. Неудобства будут в основном у разработчиков и моддеров, но даже им можно помочь кешируя результат в файловой системе и транслируя только по необходимости. Правда дистрибуция стороннего парсера это ещё отдельный вопрос.
        Т.е. всё решаемо, но мне было интересно откуда же берутся эти цифры, ведь тут 3 секунды старта, там 30 мегабайт исходников, так проекты и становятся неповоротливыми.
        К тому же, я тут рассматриваю абстрактный парсер, у которого применением может быть не только трансляция шейдеров, но и, к примеру, скриптование.
          0
          Тогда ещё вопрос — основной платформой и для текущего кроспилятора и для «к примеру, скриптования» является Android? Почему именно Java (как платформа в первую очередь, JVM)? Понятно, что кроспилированные шейдеры можно использовать в сыром виде, но что со скриптованием? Рассматривали ли вы какие-то альтернативные варианты типа скриптового рантайма на С например?
            0
            Конечно, выбор платформы это тема для совсем другой статьи, но лично моё мнение — Java, как и C#, позволяют разработчику быть гораздо эффективнее, чем… эм, многое другое.
        +3
        1) 21-ый век на дворе, а JMH почему-то не пахнет. Как так? Набросал замер на JMH — получается, что IntelliJ парсер в 4 раза быстрее чем JavaCC.
        2) GaugeKotlinIntellijParser зачем-то пересоздаёт окружение при каждом парсинге. Зачем так? Его же переиспользовать можно и нужно.
        3) yk.jcommon.utils.IO#readFile(java.lang.String) не закрывает файл
          +3
          Мне кажется так как претензия конкретно к холодному старту, JMH тут не имеет смысла использовать.
            0
            Если бы речь шла о скорости работы SQL запроса в enterprise приложении, то, да, её можно и без JMH измерить. А тут наоборот: JMH проще, быстрее и точнее.

            1) Вообще говоря, «производительность» автор объявляет первым требованием
            2) В JMH без проблем можно измерять «холодный старт». И измерять это можно более полно, т.к. в JMH есть встроенный механизм Forks — будут запускаться отдельные Java машины
            3) Код на JMH гораздо компактнее, чем «рукописный». В итоге, человеку со стороны проверить гораздо проще
            4) В JMH встроено много разнообразных профайлеров. Автор приводит цифры без какого-либо анализа того *почему* цифры именно такие
              +1
              Про SQL — это несколько пренебрежительно, не находите?

              1. Первое требование — удобство разработчика и пользователя.
              2. Тут я меряю конкретно то что мне нужно.
              3. Компактнее не выйдет. При сохранении функционала, конечно.
              4. Вы невнимательно читали.

              5. Мне не нужна цифра «время исполнения в Х итерациях после У разогревов». Мне нужно минимальное время к первому, десятому, сотому, тысячному вызову.
              6. На 1000й вызов JetBrains моя цифра выходит чуть больше чем в JMH, на 50000й — меньше. Как я указывал, при таком агрессивном JIT, меня интересует именно динамика. А конкретное число — вообще имеет мало смысла. Я бы ещё понял претензию об однообразии данных!

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

              Думаю, в 21м веке каждый волен использовать любой удобный инструмент, если понимает что он делает.
            0
            1. JMH интересен, конечно, и иногда цифры даже совпадают на стотысячный вызов. А иногда мой стотысячный выходит быстрее. В общем, это совсем другая тема, и для статьи, возможно, надёжнее было бы выложить именно его результаты. Но в любом случае, это всего лишь тысячный вызов, а, как я написал — меня интересовала именно динамика времени.
            2. Отличное замечание! Действительно, кешируя именно это значение можно ускорить JetBrains в два с половиной раза (в данных конкретных условиях).
            Kotlin IntelliJ parser (without analyzer, cached project)
            first call elapsed : 1272.145ms
            min time in next 10 calls: 5.031ms
            min time in next 100 calls: 1.486ms
            min time in next 1000 calls: 0.38ms
            Whole time for 1111 calls: 1.518542s

            3. Файл закроется в finalize, но вы правы, лучше делать это явно. Тем более раз он начал использоваться более чем для чтения пары файлов.
            4. А вот почему в вашем замере ускорение в четыре раза — это действительно интересно. У вас используется CoreLocalFileSystem и именно он даёт буст. С первых же вызовов 0.4мс вместо 5. Уж не кешируется ли там результат парсинга?

            Kotlin IntelliJ parser (without analyzer, CoreLocalFileSystem)
            first call elapsed : 1233.702ms
            min time in next 10 calls: 0.418ms
            min time in next 100 calls: 0.127ms
            min time in next 1000 calls: 0.041ms
            Whole time for 1111 calls: 0.11175224s
              0
              В №1 вы говорите об изменившихся цифрах. Но вы замеряете ДРУГУЮ имплементацию, а пишите что только заменили методику сбора.
              Нужно быть внимательнее в построении предложений.
              0
              Я правильно понял, что посмотреть можно только на парсер, транслятор закрыт? Что же касается обсуждаемого вопроса: мне кажется, что тащить компилятор в продакшен рантайм занятие достаточно бессмысленное, ничто не мешает скомпилировать заранее, а для разработки можно и размер увеличить и подождать немного один раз.
                0

                а как же скрипты в runtime запускать?
                Вот пример проекта: https://github.com/s1monw1/KtsRunner

                  0
                  мы ведь тут говорим и запуске шейдеров, а не о скриптовании
                  0
                  Да, можно не тащить. Но и о разработчике я бы не стал забывать тоже, он ведь тот, кто чаще чем кто либо другой будет запускать проект. Ну и habr.com/post/433000/#comment_19503612
                    0
                    Я ведь и не предлагаю забывать. для разработки можно сделать режим разработчика, который используя тот же код может отслеживать и перекомпилировать на лету, для продакшена же это совершенно нужный инструмент, который добавляет сложности этой логике и вероятных ошибок
                      0
                      я это все к тому, что намного интереснее было бы посмотреть на транслятор, чем на парсер
                        0
                        Транслятор пока не открывал
                  0

                  Стоит попробовать преобразовать обычные правила в лево-рекурсивные в Kotlin грамматике. Скорее всего это ускорит парсер.

                    0
                    + потестить профайлером на предмет неоднозначностей (ambiguity) в правилах. Грамматики из antlr репозитория часто ими грешат.
                      0
                      Да уже: обобщенный алгоритм LL(*) (а точнее ALL) хоть и упрощает написание произвольных грамматик, однако усложняет сам код парсера, ресолвинг неоднозначностей. Поэтому нужно аккуратно их писать. К тому же он динамический.
                        0

                        Также автору нужно попробовать использовать двухэтапную методику парсинга как это описано, например, в моей статье: Максимизация скорости парсинга в ANTLR.

                          0
                          Спасибо за ссылку, обязательно почитаю! Интересно будет узнать что в ANTLR можно сделать лучше. Однако, первой же в голову приходит мысль — а ведь в JavaCC я писал «в лоб», без каких либо ухищрений. И размер fat jar со временем первого старта — вряд ли изменятся.
                          (Кстати, грамматика на ANTLR — не моя)
                            0

                            А почему размер jar так важен? И у меня намного меньше:


                            • C# Optimized: 307 Кб (бинарь Kotlin.dll) + 1.48 Мб (размер рантайма).
                            • C# Standard: 305 Кб (бинарь Kotlin.dll) + 352 Кб (размер рантайма).
                            • Java: 671 Кб (скомпилированные файлы .class) + 330 Кб (размер рантайма).

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

                              +1
                              Я не говорю что прямо так важен, но обращать внимание на него стоит, ведь даже на десктопе — это не просто 30МБ на терабайтном винте, это 30МБ кода.
                              (Плюс абзац из публикации, не буду повторяться).

                              Размер я мерял со всеми зависимостями.
                              kotlinAntlr-0.1-SNAPSHOT-jar-with-dependencies — 15МБ, основной вес в зависимости com.ibm.icu
                                0
                                1) А зачем в зависимостях указывать <artifactId>antlr4</artifactId>, когда во время выполнения достаточно <artifactId>antlr4-runtime</artifactId>?
                                2) Зачем в jar-with-dependencies включать junit и hamcrest, ведь они только для тестов нужны? Зачем в измеряемый jar включать log4j и commons-lang3, которые вообще не используются в коде? Измерять нужно не jar-with-dependencies, а результат работы maven-shade-plugin'а. Либо оставляйте только реально нужные зависимости. Если всю эту ерунду удалить, то получается где-то 1 мегабайт.
                                3) Если удалить и yk/jcommon, то получается похоже на результат KvanTTT
                                  0
                                  Спасибо, поправил
                                    0
                                    Стоит упомянуть, что теперь большую часть занимает не ANTLR и не парсер, а yk.yast:common:jar и yk:jcommon:jar
                                      0
                                      Это же относительные результаты, понятно что во всех случаях что-то дополнительное есть. Но если таки заморочиться, то JavaCC выйдет ещё красивее — 66КБ против ANTLR 680КБ. О чём я, кстати, упомянул.
                                        0
                                        Ещё раз: проблема не в конкретных цифрах, а в том, что они означают совсем не то, что читатель предполагает. Вы пишете, что «парсер на ANTLR занимает столько-то», и логично предполагать, что там «парсер+необходимая ANTLR обвязка».
                                        А по факту же, вы туда вкладываете свои commons (которые занимают половину результитрующего jar), log4j, commons-lang и далее по списку.
                                          0
                                          Я нигде не говорил что это размер чистого парсера. Написано: "… посмотреть на размер джара со всеми зависимостями".
                                          Кроме того, я везде привожу ссылки на код, который тестируется. Как тут можно что-то не так понять?
                                          И ещё раз. Тем не менее. Я упомянул. Про чистый размер парсеров.
                                            0
                                            Как тут можно что-то не так понять?

                                            Ясно как: никому и в голову не придёт, что вы, помимо необходимого, в jar включаете десяток-другой абсолютно лишних зависимостей.
                                              0
                                              И ещё раз. Тем не менее. Я упомянул. Про чистый размер парсеров.
                                                0
                                                В начале статьи лишь слова «размер джара (парсера) = 1.4МБ».
                                                Слово jcommon в статье вообще не встречается.
                                                log4j тоже не встречается.
                                                То, что в JetBrains парсер входит Kotlin runtime тоже нигде не говорится.
                                                  0
                                                  Это название колонки в таблице :) В секции tl;dr :)
                      0
                      На JavaCC парсера не нашлось, а вот на хайповом ANTLR, ожидаемо, есть (раз,
                      два).

                      Вообще говоря это одинаковые грамматики. Ну и ANTLR не такой уж и хайповый — там один мэинтейнер, который мержит пулл-риквесты раз в полгода. А версии выходят раз в год.

                        0
                        Да, там мёрж грамматики одного автора в общий репо. Подробности поленился расписывать.
                        +1
                        JavaCC парсер пока содержит не всю грамматику

                        А какой процент unit-test'ов (я про официальные Kotlin тесты) проходит этот парсер?

                        Например, JavaCC парсер считает, что -789 относится к определению переменной x, хотя это, очевидно, не так:

                        fun getResult() {
                        val x = 123 + 456
                        - 789
                        }
                          0
                          Не запускал, конечно. Грамматика не покрыта же ещё.
                          Кстати, интересно было бы по ANTLR посмотреть. Там наткнулся что вот такой код SimpleClass().foo<String>("") не парсится.
                            0
                            К слову, в ANTLR грамматике какая-то самодеятельность: callExpression в официальной Kotlin грамматике отсутствует. Из-за подобного растёт неоднозначность, время парсинга и наверняка будут ошибки
                              0

                              Можно завести issue в трекере :) А еще добавить код, который не парсится, в файл Test.kt.

                          +2
                          осталось процентов 10. Но не похоже чтобы они могли повлиять на производительность


                          1) У вас не реализован парсинг functionType, а это довольно мутная часть языка (леворекурсивная и всё такое)

                          2) У вас не реализован парсинг functionLiteral, а это тоже непростой синтаксис. Например, в конструкции class Child: Parent by delegateMethod { ... } фигурные скобки могут быть как телом класса Child, так и лямбдой-параметром к методу delegateMethod

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

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

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