Насколько быстро парсится 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мс
15.5МБ
JavaCC
19мс
0,1мс
1.6МБ
Одним погожим солнечным деньком...
я решил собрать транслятор в 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
Такое время имеет следующие очевидные неудобства:
- потому что это плюс три секунды к запуску игры или приложения.
- во время разработки я использую горячую перегрузку шейдера и вижу результат сразу после изменения кода.
- я часто перезапускаю приложение и рад что оно стартует достаточно быстро (секунда-две).
Плюс три секунды на разогрев парсера — это неприемлемо. Конечно, сразу выяснилось что при последующих вызовах время парсинга падает до 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мс
15.5МБ
JavaCC
19мс
0,1мс
1.6МБ
В какой-то момент, я решил посмотреть на размер джара со всеми зависимостями. JetBrains велик вполне ожидаемо, а вот рантайм ANTLR удивляет своим размером.
Размер джара как таковой важен, конечно, для мобилок. Но и для десктопа имеет значение, т.к., фактически, означает количество дополнительного кода, в котором могут водиться баги, который должна индексировать IDE, который, как раз, и влияет на скорость первой загрузки и скорость разогрева. Кроме того, для сложного кода нет особой надежды транслировать на другой язык.
Я не призываю считать килобайты и ценю время программиста и удобство, но всё же об экономии стоит задумываться, потому что именно так проекты и становятся неповоротливыми и трудно поддерживаемыми.
Ещё пара слов об ANTLR и JavaCC
Серьёзной фичей ANTLR является разделение грамматики и кода. Это было бы хорошо, если бы за это не нужно было так дорого платить. Да и значение это имеет только для “серийных разработчиков грамматик”, а для конечных продуктов это не так важно, ведь даже существующую грамматику всё равно придётся прошерстить чтобы написать свой код. Плюс, если мы сэкономим и возьмём “стороннюю” грамматику — она может быть просто неудобна, в ней всё равно нужно будет досконально разбираться, преобразовывать дерево под себя. В общем, JavaCC, конечно, смешивает мух и котлеты, но такое ли большое это имеет значение и так ли это плохо?
Ещё одной фишкой ANTLR является множество target платформ. Но тут посмотреть можно с другой стороны — код из под JavaCC очень простой. И его очень просто… транслировать! Прямо с вашим кастомным кодом — хоть в C#, хоть в JS.
P.S.
Весь код находится тут github.com/kravchik/yast
Результатом парсинга у меня является дерево построенное на YastNode (это очень простой класс, фактически — мапа с удобными методами и айдишником). Но YastNode — это не совсем «сферическая нода в вакууме». Именно этим классом я активно пользуюсь, на его основе у меня собрано несколько инструментов — типизатор, несколько трансляторов и оптимизатор/инлайнер.
JavaCC парсер пока содержит не всю грамматику, осталось процентов 10. Но не похоже чтобы они могли повлиять на производительность — я проверял скорость по мере добавления правил, и она не менялась заметно. Кроме того, я уже сделал гораздо больше чем мне было нужно и просто пытаюсь поделиться неожиданным результатом найденным в процессе.
Комментарии (23)
vladimirsitnikov
15.12.2018 20:16+31) 21-ый век на дворе, а JMH почему-то не пахнет. Как так? Набросал замер на JMH — получается, что IntelliJ парсер в 4 раза быстрее чем JavaCC.
2) GaugeKotlinIntellijParser зачем-то пересоздаёт окружение при каждом парсинге. Зачем так? Его же переиспользовать можно и нужно.
3) yk.jcommon.utils.IO#readFile(java.lang.String) не закрывает файл
jRonn
16.12.2018 18:03Мне кажется так как претензия конкретно к холодному старту, JMH тут не имеет смысла использовать.
vladimirsitnikov
16.12.2018 20:54Если бы речь шла о скорости работы SQL запроса в enterprise приложении, то, да, её можно и без JMH измерить. А тут наоборот: JMH проще, быстрее и точнее.
1) Вообще говоря, «производительность» автор объявляет первым требованием
2) В JMH без проблем можно измерять «холодный старт». И измерять это можно более полно, т.к. в JMH есть встроенный механизм Forks — будут запускаться отдельные Java машины
3) Код на JMH гораздо компактнее, чем «рукописный». В итоге, человеку со стороны проверить гораздо проще
4) В JMH встроено много разнообразных профайлеров. Автор приводит цифры без какого-либо анализа того *почему* цифры именно такиеjorgen Автор
17.12.2018 10:44Про SQL — это несколько пренебрежительно, не находите?
1. Первое требование — удобство разработчика и пользователя.
2. Тут я меряю конкретно то что мне нужно.
3. Компактнее не выйдет. При сохранении функционала, конечно.
4. Вы невнимательно читали.
5. Мне не нужна цифра «время исполнения в Х итерациях после У разогревов». Мне нужно минимальное время к первому, десятому, сотому, тысячному вызову.
6. На 1000й вызов JetBrains моя цифра выходит чуть больше чем в JMH, на 50000й — меньше. Как я указывал, при таком агрессивном JIT, меня интересует именно динамика. А конкретное число — вообще имеет мало смысла. Я бы ещё понял претензию об однообразии данных!
Ну и мелочи. Мои тесты проходят за пару секунд, а не за минуту, ещё и форматируется это всё, чтобы в любой момент можно было повторить замеры и скопипастить в нужный отчёт.
Думаю, в 21м веке каждый волен использовать любой удобный инструмент, если понимает что он делает.
jorgen Автор
16.12.2018 19:311. 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
jorgen Автор
17.12.2018 10:16В №1 вы говорите об изменившихся цифрах. Но вы замеряете ДРУГУЮ имплементацию, а пишите что только заменили методику сбора.
Нужно быть внимательнее в построении предложений.
fogone
16.12.2018 01:10Я правильно понял, что посмотреть можно только на парсер, транслятор закрыт? Что же касается обсуждаемого вопроса: мне кажется, что тащить компилятор в продакшен рантайм занятие достаточно бессмысленное, ничто не мешает скомпилировать заранее, а для разработки можно и размер увеличить и подождать немного один раз.
Borz
16.12.2018 09:13а как же скрипты в runtime запускать?
Вот пример проекта: https://github.com/s1monw1/KtsRunner
jorgen Автор
16.12.2018 19:37Да, можно не тащить. Но и о разработчике я бы не стал забывать тоже, он ведь тот, кто чаще чем кто либо другой будет запускать проект. Ну и habr.com/post/433000/#comment_19503612
fogone
16.12.2018 21:37Я ведь и не предлагаю забывать. для разработки можно сделать режим разработчика, который используя тот же код может отслеживать и перекомпилировать на лету, для продакшена же это совершенно нужный инструмент, который добавляет сложности этой логике и вероятных ошибок
KvanTTT
16.12.2018 12:22Стоит попробовать преобразовать обычные правила в лево-рекурсивные в Kotlin грамматике. Скорее всего это ускорит парсер.
Endeavour
16.12.2018 13:20+ потестить профайлером на предмет неоднозначностей (ambiguity) в правилах. Грамматики из antlr репозитория часто ими грешат.
KvanTTT
16.12.2018 14:57Да уже: обобщенный алгоритм LL(*) (а точнее ALL) хоть и упрощает написание произвольных грамматик, однако усложняет сам код парсера, ресолвинг неоднозначностей. Поэтому нужно аккуратно их писать. К тому же он динамический.
KvanTTT
16.12.2018 15:04Также автору нужно попробовать использовать двухэтапную методику парсинга как это описано, например, в моей статье: Максимизация скорости парсинга в ANTLR.
jorgen Автор
16.12.2018 19:42Спасибо за ссылку, обязательно почитаю! Интересно будет узнать что в ANTLR можно сделать лучше. Однако, первой же в голову приходит мысль — а ведь в JavaCC я писал «в лоб», без каких либо ухищрений. И размер fat jar со временем первого старта — вряд ли изменятся.
(Кстати, грамматика на ANTLR — не моя)
KvanTTT
18.12.2018 12:10На JavaCC парсера не нашлось, а вот на хайповом ANTLR, ожидаемо, есть (раз,
два).Вообще говоря это одинаковые грамматики. Ну и ANTLR не такой уж и хайповый — там один мэинтейнер, который мержит пулл-риквесты раз в полгода. А версии выходят раз в год.
KumoKairo
А по какой причине шейдеры в GLSL кроспилируются каждый раз в рантайме заново, а не заранее на этапе сборки и не бандлятся в игру/приложение собственно в виде GLSL?
jorgen Автор
Конечно, в случае медленного/тяжёлого транслятора они транслируются заранее. Неудобства будут в основном у разработчиков и моддеров, но даже им можно помочь кешируя результат в файловой системе и транслируя только по необходимости. Правда дистрибуция стороннего парсера это ещё отдельный вопрос.
Т.е. всё решаемо, но мне было интересно откуда же берутся эти цифры, ведь тут 3 секунды старта, там 30 мегабайт исходников, так проекты и становятся неповоротливыми.
К тому же, я тут рассматриваю абстрактный парсер, у которого применением может быть не только трансляция шейдеров, но и, к примеру, скриптование.
KumoKairo
Тогда ещё вопрос — основной платформой и для текущего кроспилятора и для «к примеру, скриптования» является Android? Почему именно Java (как платформа в первую очередь, JVM)? Понятно, что кроспилированные шейдеры можно использовать в сыром виде, но что со скриптованием? Рассматривали ли вы какие-то альтернативные варианты типа скриптового рантайма на С например?
jorgen Автор
Конечно, выбор платформы это тема для совсем другой статьи, но лично моё мнение — Java, как и C#, позволяют разработчику быть гораздо эффективнее, чем… эм, многое другое.